1、离散数学习题答案 习题一 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） 两个三角形相似，当且仅当他们的对应角
2、相等或者对应边成比例 - 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 语言是最完美的程序设计语言 - Y， T/F （ 2）这件事大概是小王干的 - N （ 3） x2 = 64 - N （ 4）可导的实函数都是连续函数 - Y， T/
3、F （ 5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利 - N （ 6）客观规律是不以人们意志为转移的 - Y， T （ 7）到 2020 年，中国的国民生产总值将赶上和超过美国 - Y， N/A （ 8）凡事都有例外 - Y， F 3、构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式 （ 1） （ P （ P Q） Q 解： P Q P Q P （ P Q） （ P （ P Q） Q 可满足式 0 0 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 0 1 1 （ 2） （ 4） 表 略 ：（ 2）可满足式、（ 3）永真式 、（ 4）可满足式 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？ 解
5、： （ 1） 如果 P Q Q R，不能判断 P R，因为如果 Q = P R, 那么 P Q P P R Q R，但 P 可以不等价于 R. （ 2） 如果 P Q Q R，不能判断 P R，因为如果 Q = P R, 那么 P Q P P R Q R，但 P 可以不等价于 R. （ 3）如果 P R，那么有 P R，因为 P R，则 P R 为永真式，及有 P R 为永真式，所以 P R. 8、把下列各式用等价表示出来 （ 1） (P Q) P 解：原式 (P Q) (P Q) (P P) (P Q) (P Q) (P Q) (P Q) (P P) (P P) 9、证明： 是最小功能完备集
6、合 证明 : 因为 , 是最小功能完备集合 ,所以 ,如果 能表示出 ,则其是功能完备集合。由于 P Q ( P) 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 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0
7、0 1 1 1 1 1 1 所以： 主合取范式为 = ( P Q R) ( P Q R) = M4 M6 主析取范式为 = ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) = m0 m1 m2 m3 m5 m7 等价变换法（略） (4) (P (Q R) ( P ( Q R) 解：真值表法 所以： 主合取范式为 = (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R) = M1 M2 M3 M4 M5 M6 主析取范式为 = ( P Q R) (P Q R) = m0 m7 等价变换法（
8、略） 14、 从 A,B,C,D 4 个 人中派 2 人出差，要求满足下列条件：如果 A 去，则必须在 C 或 D 中选一人同去； B 和 C不能同时去； C 和 D不能同时去。用构造范式的方法决定选派方案。 解： 由题设 A： A 去， B： B 去， C： C 去， D： D 去则满足条件的选派应满足如下范式： （ A（ CD）（ B C）（ C D） 构造和以上范式等价的主析取范式 （ A（ CD）（ B C）（ C D） （ A B C D ）（ A B C D）（ A B C D）（ A B C D）（ A B C D）（ A B C D）（ A B C D）（ A B C D） P
9、 Q R Q R Q R P (Q R) P ( Q R) (P (Q R) ( P ( Q R) 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求： （ A B C D），（ A B C D），（ A B C D） 即有三种方案： A 和 C 去或者 A 和 D 去或者 B 和 D 去。 15、证明下列蕴含试： （ 1）
10、 P Q=P (P Q) 证明： P Q P Q T ( P Q) ( P P) ( P Q) P (P Q) P (P Q) 所以，这是个等价式，因此也是个蕴含式 （ 2） (P Q) Q= (P Q) 证明： (P Q) Q ( P Q) Q (P Q) Q (P Q) (Q Q) (P Q) T (P Q) 所以，这是个等价式，因此也是个蕴含式 （ 3） P P R=S 证明： P P R F = S (F 可蕴含任何命题公式 ) （ 4） P=Q R R 证明： P=T Q R R （任何公式可蕴含永真式） 18、 一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找
11、珍宝的线索如下： （ 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
12、（ R P）（ R S）（ T M） R（ R S）（ T M） S（ T M） S 即珍宝藏在花园正中地下 20、演绎证明下面各蕴含式： （ 4） (R Q) (R S),(Q E) (S B), (E B),(P R) P 证明：运用反证方法，将结论的非纳入前提，证明步骤如下 1 P p(附加前提 ) 2 P R p 3 R T 1,2 I 4 (R Q) (R S) p 5 Q S T 3,4 I 6 (Q E) (S B) p 7 E B T 5,6 I 8 (E B) p 9 F(矛盾式 ) T 7,8 E （ 5） P (Q R),Q (R S) P (Q S) 证明：运用 cp
13、法，将结论条件式的前件作为前提，证明步骤如下 1 P p(附加前提 ) 2 P (Q R) p 3 Q R T 1,2 I 4 Q (R S) p 5 R (Q S) T 4 E 6 Q S T 3,5 I 7 P (Q S) CP 1,6 21、把下列句子演绎成逻辑形式，并给出证明 （ 2）某公司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实： 被盗现场没有留下任何痕迹 失盗时，小花或则小英正在卡拉 ok 厅 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去 如果失盗时小花正在卡拉 ok 厅唱歌，那么金刚是最大的嫌疑者 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出
14、旅游 如果失盗时小英正在卡拉 ok 厅唱歌，那么瘦子是最大的嫌疑者 根据以上事实，请通过演绎推理找出偷窃者 解： 根据给定的条件有下述命题： P： 现场无任何痕迹 Q：失窃时，小花在 OK 厅 R：失窃时，小英在 OK 厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者 则根据案情有如下命题公式： P， Q R， S P， Q T， S R， R M P P S P P S T I S R P R T I Q R P Q T I Q T P T T I 即 金刚是偷窃者 23、利用消解法证明下列各蕴含式： （ 3） P (Q R),Q (R S) P (Q S) 证明： P (Q
15、R) P Q R Q (R S) Q R S （ P (Q S)） P Q S 因此子句集合 = P Q R， Q R S， P， Q， S 消解过程如下： 1 P Q R p 2 P p 3 Q R 由 1， 2归结 4 Q p 5 R 由 3， 4归结 6 Q R S p 7 S p 8 Q R 由 6， 7归结 9 R 由 4， 8归结 10 FLASE 由 5， 9归结 导出空子句 习题 二 1、 把下列谓词翻译成谓词公式 （ 1）每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数 解： R(x) - x 是实数 Ra(x) - x 是有利数 翻译如下： (x)( Ra(
16、x) R(x) (x)( 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）任何正整数不是合数就是质
17、数 解： A(x) - 是正整数 (x) - 是合数 (x) - 是质数 翻译如下： (x)（ A(x) (x) (x)） （ 6） 凡是存钱的人都想有利息，如 果没有利息，人们就不会存钱 解： A(x) - 是存钱的人 F(x， y) - 想有 P - 存钱没有利息 Q: - 人们不存钱 a: - 利息 翻译如下： (x)（ A(x) F(x， a)）（ P Q） 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、指出下列公式中的约束变元和自由变元
18、，并确定公式 的辖域 解：略 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
19、诚实 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 x2 0 答：为假命题 （ 2） (x)2x8 x2-6x+5 0 答：为真命题，当 4， 5 使满足谓词公式 （ 3） (x) (y)x+y=1024 答：为真命题，对任意整数 x
20、， y 取值为 1024-x 及可 （ 4） (y) (x)xy10 x+y 2 答：为真命题， y=0 及成立 9、 证明下列各式成立： （ 1） (x) (y)P(x) Q(y) (x)P(x) (y)Q(y) 证明：右式 (x) (y) P(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) 显然和
21、(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、 把下列公式化为等价的前束范式，再求出对应的 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,
22、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) (x)P(x) Q(a) 15、下面给出了对 (x) P(x) Q(x) (x) P(x) (x)Q(x)的证明： （ 原 证明过程略） 试判断这个证明是否正确。你能给出一个证明吗？ 答：这个证明不正确，因为： 如果 P Q 则 Q P 而 P Q 不一定成立，因此在这个证明过程中，第二步到第三步的蕴含不
23、成立 17、 判别下面各个推理是否正确，如果不正确，指出错在什么地方（题目不再重复） （ 1）答：不正确，全称指定应该变为其他非 x 的变元，可修改为： P(y) Q(x) （ 2）答：正确 （ 3）答：不正确，全称指定应该使用相同的个体常量，可修改为： P(a) Q(a) （ 4）答：题目不正确，存在量词的指导变元应该是另外的变元符号 （ 5）答：不正确，存在量词的辖域应该包含全部的谓词，可修改为： (x)P(x) Q(x) （ 6）答：不正确，对不同的个体常元应该用不同的变元进行存在指定，可修改为： (x)P(x) Q(b) （ 7）答：不正确，推理过程中，应该先使用存在指定，然后使用全称
24、指定 习题 三 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）假，例如： 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、 证明下列各式
25、 （ 1） A (B-C) = (A B)-(A C) 证明：左式 = A (B C) = (A B C) (A B A) = (A B) (C A) = (A B) (A C) = (A B)-(A C) = 右式 （ 2） A - (B C) = (A-B) (A-C) 证明：右式 = (A B) (A C) = A B C = A (B C) = A - (B C) = 左式 （ 3） (A-B)-C = A-(B C)=(A-C)-B 证明： (A-B)-C = A B C = A (B C) = A-(B C) = A C B = (A-C)-B （ 4） A (B C)=(A B)
26、 C CA 证明：充分性 A (B C)=(A B) C (A B) (A C) = (A B) C 假设 C 不是 A 的子集，则 C 中 必存在元素 c 在 C 中而不在 A 中，那么 c 一定不在等式的左端集合中，而一定在右端集合中，矛盾 CA 必要性 CA ， A C = C ，等式两端同时并上另一个集合，等式成立 (A B) (A C) = (A B) C A (B C)=(A B) C （ 5） A (B C) = (A B) (A C) 证明：左式 = A（ B C-B C） = A（ (B C) (B C)） = A (B C) (BC)=ABC + ACB 右式 = （ (A B) (A C)） - （ (A B) (A C)） = （ A (B C)） （ A B C） = A (B C) (A B C) = ABC + ACB 所以，左式 = 右式 10、 下面三式中，哪个可得出 B=C 的结论 （ 1） A B=A C 答：不能得出此结论，因为如果 B C,但 B,C 都是 A 的子集， A B=A C 成立 （ 2） A B=A C 答：不能得出此结论，因为 B C，但 A 是 C B 子集， A B=A C 成立
