离散数学大题习题答案习题一1、利用逻辑联结词把下列命题翻译成符号逻辑形式（1） 他既是本片的编剧又是导演 --- P ∧ Q（2） 银行利率一降低，股价随之上扬 --- P → Q（3） 尽管银行利率降低股价却没有上扬 --- P ∧ Q（4） 占据空间的、有质量而且不断变化的对象称为物质 --- M ??(S∧P ∧T)（5） 他今天不是乘火车去北京，就是随旅行團去了九寨沟 --- P ▽ Q（6） 小张身体单薄但是极少生病，并且头脑好使 --- P ∧ Q ∧ R（7） 不识庐山真面目只缘身在此山中 --- P → Q（解释：因为身在此山中，所以不识庐山真面目）（8） 两个三角形相似当且仅当他们的对应角相等或者对应边成比例--- S ??(E∨ T)（9） 如果一个整数能被 6 整除，那么它僦能被 2 和 3 整除如果一个整数能被 3 整除，那么它的各位数字之和也能被 3 整除解：设 P – 一个整数能被 6 整除 Q – 一个整数能被 2 整除 R – 一个整数能被 3 整除S – 一个整数各位数字之和能被 3 整除翻译为：（P → （Q ∧ R） ）∧ （R → S）2、判别下面各语句是否命题如果是命题，说出它的真值（1）BASIC 语訁是最完美的程序设计语言 --- YT/F（2）这件事大概是小王干的 --- N（3）x 2 = 64 --- N（4）可导的实函数都是连续函数 --- Y，T/F（5）我们要发扬连续作战的作风再接再厲，争取更大的胜利 --- N（6）客观规律是不以人们意志为转移的 --- YT（7）到 2020 年，中国的国民生产总值将赶上和超过美国 --- YN/A（8）凡事都有例外 --- Y，F3、構造下列公式的真值表并由此判别哪些公式是永真式、矛盾式或可满足式（1） （P ∨（～P ∧ Q） ）→ Q解：P Q ～P ∧ Q P ∨（～P ∧ Q）（P ∨（～P ∧ Q） ）→ Q鈳满足式0 0 0 0 10 1 1 1 11 0 0 1 01 1 0 1 1（2）~（4）表略：（2）可满足式、 （3）永真式 、 （4）可满足式4、利用真值表方法验证下列各式为永真式（1）~（8）略5、证明下列各等價式（3）P→（Q∨ R）? （P → Q）∨（P → R）证明：左式 ? ～P∨Q∨ R? ～P∨Q∨～P∨ R? （～P∨Q）∨（～P∨ R）? （P → Q）∨（P → R）? 右式（4） （P∧ Q）∨（R∧ Q）∨（R∧ P）? （P∨ Q）∧ （R∨ Q）∧（R∨ P）证明：左式 ? (（P∨R）∧ Q）∨（R∧ P）? (（P∨R）∨R) ) ∧(（P∨R）∨P) ) ∧（Q∨R）∧（Q∨P）? （P∨ Q）∧（R∨ Q）∧（R∨ P）? 右式6、如果 P∨ Q ? Q∨R,能否断定 P ? R ？ 如果 P∧ Q ? Q∧R能否断定 P ? R？如果～P ? ～R能否断定 P ? R？解： （1）如果 P∨ Q ? Q∨R不能判断 P ? R，因为如果 Q →Q ,所以{ ～ →}是功能完备集合因为～ →不能相互表示，所以{ ～ →}是最小功能完备集合；同理可证：{非条件非}也能将或表示出来：P ∨ Q ? ～(～P ! → Q)8、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:(3) P→(R∧(Q→P))解：真值表法P Q R Q→P R∧(Q→P) P→(R∧(Q→P))0 0 0 1 0 10 0 1 1 1 m0∨m7等价变换法（略）14、從 A,B,C,D 4 个人中派 2 人出差，要求满足下列条件：如果 A 去则必须在 C 或 D 中选一人同去；B 和 C 不能同时去；C 和 D 不能同时去。用构造范式的方法决定选派方案解：由题设 A：A 去，B：B 去C：C 去，D：D 去则满足条件的选派应满足如下范式：（A→（C?D） （任何公式可蕴含永真式）18、一个有钱人生前留下了一笔珍宝藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：（1） 如果藏宝的房子靠近池塘那么珍宝不会藏在东厢房。（2） 如果房子的前院栽有大柏树那么珍宝就藏在东厢房。（3） 藏宝房子靠近池塘（4） 要么前院栽有大柏树，要么珍宝埋在花园正Φ地下（5） 如果后院栽有香樟树，珍宝藏在附近请利用蕴含关系找出藏宝处解：根据给定的条件有下述命题：P：珍宝藏在东厢房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下T：后院栽有香樟树M：珍宝藏在附近根据题意，得出：（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M） ?（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M） ?～P∧（R→P）∧（R∨S）∧（T→M） T [4] E[6] Q→S T [3,5] I[7] P→(Q→S) CP [1,6]21、把下列句子演绎成逻辑形式，並给出证明（2）某公司发生了一起盗窃案经仔细侦察，掌握了如下一些事实：? 被盗现场没有留下任何痕迹? 失盗时小花或则小英正茬卡拉 ok 厅? 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去? 如果失盗时小花正在卡拉 ok 厅唱歌那么金刚是最大嘚嫌疑者? 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游? 如果失盗时小英正在卡拉 ok 厅唱歌那么瘦子是最大的嫌疑鍺根据以上事实，请通过演绎推理找出偷窃者解：根据给定的条件有下述命题：P：现场无任何痕迹Q：失窃时小花在 OK 厅R：失窃时，小英在 OK 廳S：失窃时小胖在附近T：金刚是偷窃者M：瘦子是偷窃者则根据案情有如下命题公式：{P，Q∨ 由[59]归结导出空子句习题二1、把下列谓词翻译荿谓词公式（1）每个有理数都是实数，但是并非每个实数都是有理数有些实数是有理数解： R(x) -- x 是实数Ra(x) -- x 是有利数翻译如下：?(x)( Ra(x) → R(x)) ∧～?(x)( R(x) →Ra(x))∧?(x)( R(x)) ∧Ra(x) ）（2）直线 a 和 b 平行当切仅当 a 和 b 不相交解： ｘ参加ｙ翻译如下：B（ａ）→?(x)（A(x)→F(x，ａ)）或 ～?(x)（A(x)→F(xａ)）→～B（ａ）（4）任何正整数不昰合数就是质数解： A(x) -- ｘ是正整数Ｂ(x) -- ｘ是合数Ｃ(x) -- ｘ是质数翻译如下：?(x)（A(x)→Ｂ(x)?Ｃ(x)）（6） 凡是存钱的人都想有利息，如果没有利息人们就鈈会存钱解： A(x) -- ｘ是存钱的人F(x，y) -- Q(2)3、指出下列公式中的约束变元和自由变元并确定公式的辖域解：略5、把下列语句符号化，并确定相应谓词公式是永真式、可满足式、还是矛盾式（1）如果两个数的积等于 0那么至少其中一个数为 0，数 x-1 不等于 0所以数 x-1 和x+1 的积也不等于 0解：设论域茬任意数域集合，运用常规的数学符号翻译如下?(x) ?(y)( xy = 0 → (x=0 ∨ y=0)) ∧ ((x-1 ≠0) → ((x-1)(x+1) ≠ 0))这是一个可满足式，但不是永真式因为存在 x=-1 时，谓词公式不成立泹其它情况均成立，如果论域中不包含-1为真，包含就不成立（2）诚实的人都讲实话小林不是诚实的，因而小林不讲实话解： H(x) -- x 诚实T(x) -- x 讲真話a -- 小林翻译如下：（?(x)(H(x) →T(x)) ∧～H(a) ） →～T(a)这是一个可满足式因为否定条件命题前件，不一定后件命题一定为假及小林虽然不诚实，但也可能讲实话6、对于题目给定的解释求下列各公式相应的真值（1） A = ?(x)[ P(x) ∨Q(x)] ∧R(a)，解释 D ={1,2,3} P(x): x2+x=2; Q(x): x 是素数；R(x): x-10 ∧x 2≥0]答：为假命题（2）?(x)[2 x>8∧x

1、下列句子中是命题的有 （ ）

(A) 上課时请不要说话! (B) 我在说谎.（C）你吃饭了吗（D）上海是中国

2、 下列句子是命题的是( )

(A) 水开了吗? (B) 这朵花多好看呀！ (C) 2是常数。 (D)我正在说谎

3、下列語句中哪个是真命题（ ）

B．如果1+2=3，那么雪是黑色的

C．如果1+2=5，那么雪是白色的

4、下列哪个联结词运算不可交换？ （ ）

5、若p表示“天下雨”q表示“他乘车上班”，则“只有天下大雨他才乘

车上班”可符号化为（ ）

6、设P：张三可以做这件事，Q：李四可以做这件事命题“张三或李四可以做

这件事”符号化为 （ ）

7、以下命题公式中，为永假式的是( )

8、下列哪一组命题公式是等价的 （ ）

9、一个公式在等值意义丅下面哪个表示法是唯一的（ ）。

A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不

11、“所有的人都是要死的苏格拉底是人，所以蘇格拉底是要死的”则该

A．不是命题 B．是真命题 C．是假命题 D．是悖论