1、离散数学习题答案习题一1、利用逻辑联结词把下列命题翻译成符号逻辑形式（1） 他既是本片的编剧，又是导演 - P Q（2） 银行利率一降低，股价随之上扬 - P Q（3） 尽管银行利率降低，股价却没有上扬 - P Q（4） 占据空间的、有质量而且不断变化的对象称为物质 - M (SP T)（5） 他今天不是乘火车去北京，就是随旅行团去了九寨沟 - P Q（6） 小张身体单薄，但是极少生病，并且头脑好使 - P Q R（7） 不识庐山真面目，只缘身在此山中 - P Q（解释：因为身在此山中，所以不识庐山真面目）（8） 两个三角形相似，当且仅当他们的对应角相等或者对应边成比例- S (E T)（9）
2、 如果一个整数能被 6 整除，那么它就能被 2 和 3 整除。如果一个整数能被 3 整除，那么它的各位数字之和也能被 3 整除解：设 P 一个整数能被 6 整除 Q 一个整数能被 2 整除 R 一个整数能被 3 整除S 一个整数各位数字之和能被 3 整除翻译为：（P （Q R） ） （R S）2、判别下面各语句是否命题，如果是命题，说出它的真值（1）BASIC 语言是最完美的程序设计语言 - Y，T/F（2）这件事大概是小王干的 - N（3）x 2 = 64 - N（4）可导的实函数都是连续函数 - Y，T/F（5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利 - N（6）客观规律是不以
3、人们意志为转移的 - Y，T（7）到 2020 年，中国的国民生产总值将赶上和超过美国 - Y，N/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）证明：左式 PQ R PQP R （PQ）（P
4、R） （P Q）（P R） 右式（4） （P Q）（R Q）（R P） （P Q） （R Q）（R P）证明：左式 (（PR） Q）（R P） (（PR）R) ) (（PR）P) ) （QR）（QP） （P Q）（R Q）（R P） 右式6、如果 P Q QR,能否断定 P R ？ 如果 P Q QR，能否断定 P R？如果P R，能否断定 P R？解： （1）如果 P Q QR，不能判断 P R，因为如果 Q = P R, 那么 P Q PP R QR，但 P 可以不等价于 R.（2）如果 P Q QR，不能判断 P R，因为如果 Q = P R, 那么 P Q PP R QR，但 P 可以
5、不等价于 R.（3）如果P R，那么有 P R，因为P R，则P R 为永真式，及有 P R 为永真式，所以 P R.8、把下列各式用等价表示出来（1）(PQ) P解：原式 (PQ) (PQ) (PP) (PQ) (PQ) (PQ) (PQ) (PP) (PP)9、证明： 是最小功能完备集合证明: 因为, 是最小功能完备集合,所以,如果 能表示出,则其是功能完备集合。由于 P Q (P) Q ,所以 是功能完备集合。因为 不能相互表示，所以 是最小功能完备集合；同理可证：非，条件非也能将或表示出来：P Q (P ! Q)8、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:(3)
6、 P(R(QP)解：真值表法P Q R QP R(QP) P(R(QP)0 0 0 1 0 10 0 1 1 1 10 1 0 0 0 10 1 1 0 0 11 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以：主合取范式为 = (PQR) (PQR) = M4M6主析取范式为 = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7等价变换法（略）(4) (P(QR) (P(QR)解：真值表法所以：主合取范式为 = (PQR) ( PQR) ( PQR) (PQR) ( PQR) ( PQR) = M1M2M3M
7、4M5M6主析取范式为 = (PQR)(PQR) = m0m7等价变换法（略）14、从 A,B,C,D 4 个人中派 2 人出差，要求满足下列条件：如果 A 去，则必须在 C 或 D 中选一人同去；B 和 C 不能同时去；C 和 D 不能同时去。用构造范式的方法决定选派方案。解：由题设 A：A 去，B：B 去，C：C 去，D：D 去则满足条件的选派应满足如下范式：（A（CD） ）（BC）（CD）构造和以上范式等价的主析取范式（A（CD） ）（BC）（CD）（AB C D ）（ABCD）（ABCD）P Q R QR QR P(QR) P(QR)(P(QR) (P(QR)0 0 0 0 1 1 1
8、 10 0 1 0 0 1 0 00 1 0 0 0 1 0 00 1 1 1 0 1 0 01 0 0 0 1 0 1 01 0 1 0 0 0 1 01 1 0 0 0 0 1 01 1 1 1 0 1 1 1（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：（ABCD） ， （AB CD） ， （ABC D ）即有三种方案：A 和 C 去或者 A 和 D 去或者 B 和 D 去。15、证明下列蕴含试：（1）PQ=P (PQ)证明：PQ P Q T( P Q) (PP) (P Q) P (PQ) P (PQ)所
9、以，这是个等价式，因此也是个蕴含式（2）(PQ) Q= (PQ)证明：(PQ) Q (PQ) Q (PQ) Q (PQ) (QQ) (PQ) T (PQ)所以，这是个等价式，因此也是个蕴含式（3）PPR=S证明：PPR F = S (F 可蕴含任何命题公式)（4）P=QRR证明：P=T QRR （任何公式可蕴含永真式）18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：（1） 如果藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。（2） 如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。（3） 藏宝房子靠近池塘。（4） 要么前院栽有大柏树，要么珍宝埋在花园正中地
10、下。（5） 如果后院栽有香樟树，珍宝藏在附近。请利用蕴含关系找出藏宝处解：根据给定的条件有下述命题：P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下T：后院栽有香樟树M：珍宝藏在附近根据题意，得出：（QP）（RP）Q（RS）（TM） ？（QP）（RP）Q（RS）（TM） P（RP）（RS）（TM） R（RS）（TM） S（TM）S 即珍宝藏在花园正中地下20、演绎证明下面各蕴含式：（4）(RQ) (RS),(QE) (SB), (EB),(PR) P证明：运用反证方法，将结论的非纳入前提，证明步骤如下1 P p(附加前提)2 PR p3 R T 1,2
11、I4 (RQ) (RS) p5 QS T 3,4 I6 (QE) (SB) p7 EB T 5,6 I8 (EB) p9 F(矛盾式) T 7,8 E（5）P(QR),Q(RS) P(QS)证明：运用 cp 法，将结论条件式的前件作为前提，证明步骤如下1 P p(附加前提)2 P(QR) p3 QR T 1,2 I4 Q(RS) p5 R(QS) T 4 E6 QS T 3,5 I7 P(QS) CP 1,621、把下列句子演绎成逻辑形式，并给出证明（2）某公司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实： 被盗现场没有留下任何痕迹 失盗时，小花或则小英正在卡拉 ok 厅 如果失窃时小胖正
12、在附近，他就会习惯性地破门而入偷走东西后扬长而去 如果失盗时小花正在卡拉 ok 厅唱歌，那么金刚是最大的嫌疑者 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游 如果失盗时小英正在卡拉 ok 厅唱歌，那么瘦子是最大的嫌疑者根据以上事实，请通过演绎推理找出偷窃者解：根据给定的条件有下述命题：P：现场无任何痕迹Q：失窃时，小花在 OK 厅R：失窃时，小英在 OK 厅S：失窃时，小胖在附近T：金刚是偷窃者M：瘦子是偷窃者则根据案情有如下命题公式：P，Q R，S P，Q T， S R，R M P P SP P S TI SR P R TI QR P Q TI QT P T TI即 金刚是偷窃
13、者23、利用消解法证明下列各蕴含式：（3）P(QR),Q(RS) P(QS)证明： P(QR) P QRQ(RS) Q RS（P(QS)） PQS因此子句集合 = PQR，QRS，P，Q，S 消解过程如下：1 PQR p2 P p3 QR 由1，2归结4 Q p5 R 由3，4归结6 QRS p7 S p8 QR 由6，7归结9 R 由4，8归结10 FLASE 由5，9归结导出空子句习题二1、把下列谓词翻译成谓词公式（1）每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数解： R(x) - x 是实数Ra(x) - x 是有利数翻译如下：(x)( Ra(x) R(x) (x)(
14、 R(x) Ra(x)(x)( R(x) Ra(x) ）（2）直线 a 和 b 平行当切仅当 a 和 b 不相交解： A(x) - x 是直线F(x，y) - x 与 y 平行G（x,y) - 与相交 翻译如下：( )()（A()A( ) (F(，) G（,)）)（3）除非所有的会员都参加，这个活动才有意义解： A(x) - 是会员B(x) - x 有意义 - 这个活动F(x，y) - 参加翻译如下：B（）(x)（A(x)F(x，)）或 (x)（A(x)F(x，)）B（）（4）任何正整数不是合数就是质数解： A(x) - 是正整数(x) - 是合数(x) - 是质数翻译如下：(x)（A(x)(
15、x)(x)）（6） 凡是存钱的人都想有利息，如果没有利息，人们就不会存钱解： A(x) - 是存钱的人F(x，y) - 想有P - 存钱没有利息Q: - 人们不存钱a: - 利息翻译如下：(x)（A(x)F(x，a)）（PQ）2、设论域 D = 0, 1, 2，把下列公式用不含量词的公式表示出来（3）(x) P(x) (x)Q(x)解：上式 （P(0) P(1) P(2)） Q(0) Q(1) Q(2)3、指出下列公式中的约束变元和自由变元，并确定公式的辖域解：略5、把下列语句符号化，并确定相应谓词公式是永真式、可满足式、还是矛盾式（1）如果两个数的积等于 0，那么至少其中一个数为 0，数 x
16、-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)这是一个可满足式，因为否定条件命题前件，不一定后件命题一定为假。及小林虽然不诚实
17、，但也可能讲实话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 20答：为假命题（2）(x)2 x8x 2-6x+50答：为真命题，当 4，5 使满足谓词公式（3）(x) (y)x+y=1024答：为真命题，对任意整数 x，y 取值为 1024-x 及可（4）(y) (x)xy10x+y 2答：为真命题，y=0 及成立9、证明下列各式成立：（1）(x) (y)P(x) Q(y) (x)P(x) (y)Q(y)证明：右式 (x) (y) P(
18、x) Q(y) (x) P(x) (y)Q(y) (x)P(x) (y)Q(y)10、判别(x)P(x) Q(x) (x)P(x) (x)Q(x)是否成立，如果成立，请给出证明；如果不成立，找一个解释予以说明解：(x)P(x) Q(x) (x) P(x) Q(x) (x) P(x) (x)Q(x) (x) P(x) (x)Q(x) 显然和(x)P(x) (x)Q(x) 不等价，现构造如下解释设论域为 D=a,b，P(a) = 0, P(b) = 1, Q(a) = 0, Q(b) = 0, 则(x)P(x) Q(x)解释为真，而(x)P(x) (x)Q(x) 解释为假，所以不等价11、把下列公
19、式化为等价的前束范式，再求出对应的 SKolem 范式（4）(x) P(x,0) (y)P(y,f(x) (z)Q(x,z)解：原式 (x) P(x,0) (y)P(y,f(x) (z)Q(x,z) (x) (y) (z) P(x,0) (P(y,f(x) Q(x,z)其 SKolem 范式为：(x) (z) P(x,0) (P(g(x),f(x) Q(x,z)13、证明下列各式成立（1）(x) (y)P(x) Q(y) (x)P(x)证明：左式 (x) P(x) (y)Q(y) (x)P(x)（2）( (x)P(x) Q(a) (x)P(x) Q(a)证明：左式 (x)P(x) Q(a) (
20、x)P(x) Q(a)15、下面给出了对(x) P(x) Q(x) (x) P(x) (x)Q(x)的证明：（原证明过程略）试判断这个证明是否正确。你能给出一个证明吗？答：这个证明不正确，因为：如果 P Q 则Q P 而 P Q 不一定成立，因此在这个证明过程中，第二步到第三步的蕴含不成立17、判别下面各个推理是否正确，如果不正确，指出错在什么地方（题目不再重复）（1）答：不正确，全称指定应该变为其他非 x 的变元，可修改为：P(y) Q(x)（2）答：正确（3）答：不正确，全称指定应该使用相同的个体常量，可修改为：P(a) Q(a)（4）答：题目不正确，存在量词的指导变元应该是另外的变元符号
21、（5）答：不正确，存在量词的辖域应该包含全部的谓词，可修改为：(x)P(x) Q(x) （6）答：不正确，对不同的个体常元应该用不同的变元进行存在指定，可修改为：(x)P(x) Q(b) （7）答：不正确，推理过程中，应该先使用存在指定，然后使用全称指定习题三4、仔细区分集合中的关系符号 和 ，并判断下列各蕴含关系的真假（题目内容，见课本）（1）真，根据子集的定义，任何属于 B 集合的元素也属于 C 集合（2）假，例如：A = 1,2 B = 1,2, 2, 3 C=B，1 属于 A，但并不是 C 集的元素（3）假，例如：A=1,2 B=1,2,3 C=1,2,3，A 不是 C 的元素（4）假
22、，例如：A=1,2 B=1,2,3 C=1,2,3，A 不是 C 的子集（5）假，例如：A=1 B=1,2,3 C=1,2,3，A 不是 C 的元素（6）真，子集关系具有传递性9、证明下列各式（1）A(B-C) = (AB)-(AC) 证明：左式 = A(BC) = (AB C) (ABA) = (AB) (CA) = (AB) (A C) = (AB)-(A C) = 右式（2）A - (BC) = (A-B) (A-C)证明：右式 = (AB)(A C) = ABC = A (B C) = A - (BC) = 左式（3）(A-B)-C = A-(BC)=(A-C)-B证明：(A-B)-C
23、 = ABC = A (BC) = A-(BC) = A C B = (A-C)-B（4）A(BC)=(AB) C C A证明：充分性 A(BC)=(AB) C (AB) (A C) = (AB) C假设 C 不是 A 的子集，则 C 中必存在元素 c 在 C 中而不在 A 中，那么 c 一定不在等式的左端集合中，而一定在右端集合中，矛盾 CA必要性 CA ， AC = C ，等式两端同时并上另一个集合，等式成立 (AB) (AC) = (AB) C A(BC)=(A B) C（5）A(BC) = (AB) (AC)证明：左式 = A（B C-BC）= A（(B C) (BC)）= A(B C) (BC)=ABC + ACB右式 = （(A B) (AC)）- （(A B) (AC)）= （A(BC)）（ABC ）= A(BC) (ABC) = ABC + ACB 所以，左式 = 右式10、下面三式中，哪个可得出 B=C 的结论（1）AB=AC答：不能得出此结论，因为如果 B C,但 B,C 都是 A 的子集，AB=AC 成立（2）AB=AC答：不能得出此结论，因为 B C，但 A 是 CB 子集，AB=AC 成立
