离散证明题集锦

《离散证明题集锦》由会员分享，可在线阅读，更多相关《离散证明题集锦（30页珍藏版）》请在装配图网上搜索。

1、离散证明题集锦一命题逻辑例：给出(PQ)(PQ)的真值表PQ(PQ) (PQ)00 1 0 1 1 1 101 1 0 1 1 1 010 1 0 1 0 1 111 0 1 1 0 0 0步骤 解：一般说来，n个命题变元组成的命题公式共有2n种真值指派。l 定理1：任何两个重言式的合取或析取，仍然是重言式。 证明：设A、B为两个重言式，则AB和AB的真值分别等于TT和TT。l 定理2：对一个重言式的同一分量都用任何一个命题公式置换，所得命题公式仍为一个重言式。（即代入规则） 证明：由于重言式的真值与分量的真值指派无关，故对同一分量以任何一个命题公式置换后，重言式的真值不变。l 定理3：设A、

2、B是两个命题公式，AB当且仅当AB是一个重言式。（前面已证） 证明：若AB，则对于A、B所包含的分量的任意指派，A、B均取相同的真值，即AB是一个重言式；若AB是一个重言式，即对于分量的任意指派，A、B均取相同的真值，即ABl 定理1：设A1是命题公式A的子公式，若A1B1，则若将A中的A1用B1来替换，得到公式B ，则B与A等价，即AB.(替换规则)。 证明： 因为对变元的任一组指派， A1与B1真值相同，故以B1取代A1后，公式B与公式A相对于变元的任一指派的真值也必相同，所以AB。l 证明下列命题公式(可以利用基本等价式) Q(P(PQ)QP (PQ)(PQ)P (PQ)(QR)PQR

3、PQQPQ 解：1.原式Q(PP) (PQ) QP(PQ) QP2.原式 (（PQ）P) (PQ) Q) (PP) (PQ) (PQ) (QQ) P(PQ) (PQ) PPP3.原式（PQ）(QR) (PQ) (QR) (PQR) (QQR) PQR（零率）4.原式（ PQ）Q（PQ）(QQ) PQ（运算次序优先级：，）例: 求证: (P Q) (P Q) 为永真式。解：原式（PQ）（PQ）(PQP) （PQQ）T例： 求证Q(PQ)P证法1：前件真推导后件真证法2：后件假推导前件假 证法3：定义定理：设P、Q为任意两个命题公式，PQ的充分必要条件是PQ且QP。证明：若PQ，则PQ为重言式，即

4、PQ和QP是重言式；若有PQ且QP，则PQ和QP是重言式，即PQ为重言式例 已知A是B的充分条件, B是C的必要条件，C是D的必要条件, D是B的必要条件, 问：(1) A是D的什么条件?(2) B是D的什么条件?解 已知AB, CB, DC, BD, 故有(1) AB, BD, 所以 AD, 即 A是D的充分条件(2) DC, CB, 所以 DB, 又因为BD, 所以 BD, 即 B是D的充要条件。定理：如果AB，则A* B*。 证明：设P1,P2,Pn是出现在命题公式A、B中的原子变元，因为AB，即：A(P1,P2,Pn)B(P1,P2,Pn)是一个重言式。故有： A(P1,P2,Pn)B

5、(P1,P2,Pn)是一个重言式。即A(P1,P2,Pn)B(P1,P2,Pn) A* B* ，即A* B*例 判断下面各推理是否正确. (1)如果天气凉快,小王就不去游泳.天气凉快,所以小王没去游泳. (2)如果我上街,我一定去新华书店.我没上街.所以我没去新华书店.解: 解上述类型的推理问题,应先将命题符号化,然后写出前提、结论和推理的形式结构,最后进行判断. (1)P：天气凉快; Q：小王去游泳. 前提：PQ, P. 结论： Q. 推理的形式结构为 (PQ)P) Q. (*)判断(*)是否为重言式.真值表法 真值表的最后一列全为1,因而(*)是重言式.所以推理正确.等价演算法 (P Q)

6、P) Q 1.主析取范式法 (P Q)P) Q m0m1m2m3 由,同样能判断推理正确.(2)P：我上街; Q：我去新华书店. 前提：PQ, P. 结论： Q. 推理的形式结构为 (PQ) P) Q. (*) (PQ) P) Q m0m2m3可见(*)不是重言式,所以推理不正确.还可用其他方法判断之.例 证明下列前提是不相容的。1. 若A因病缺了许多课, 那么他中学考试失败。2. 若A中学考试失败, 则他没有知识。3. 若A读了许多书, 则他有知识。4. A因病缺了许多课, 而且读了许多书。证明 符号化题目: P: 因病缺了许多课, Q: 中学考试失败, R: 有知识, S: 读了许多书。问

7、题要证明前提PQ, QR, SR, PS是不相容的。下面我们用另外一种形式的格式证明（即后面讲的“构造证明”的格式）： 编号公式依据 (1)PSP(2)P(1); I1(3)S (1); I2(4)PQP(5)Q(2),(4); I8(6)SRP(7)R(3),(6); I8(8)QRP (9)R(5),(8); I9(10)RR(7),(9)例 张三说李四在说谎, 李四说王五在说谎, 王五说张三、李四都在说谎。问谁说真话, 谁说假话？解 设A:张三说真话; B:李四说真话; C:王五说真话依题意有 AB, BC, CAB。(A B)(B C)(C AB) (AB)(BA)(BC)(C B)

8、(C(AB)(AB)C) (ABC)(AB)C) (ABC)(AC)(BC) ABC即: 李四说真话, 张三和王五说假话。l 例1.9.3：求证： S是前提W，WQ,QR和RS的有效结论。 l 证明：1(1)WQP2(2)QRP 1,2(3)WRT,(1)(2)I11 3(4)WP1,2,3(5)RT,(3)(4)I84(6)RSP1,2,3,4(7)ST,(5)(6)I8（这部分的T，I8等是另外一本书的内容，所以不用管，只要会推就行）例 前提: 如果马会飞或羊吃草, 则母鸡就会是飞鸟; 如果母鸡是飞鸟, 那么烤熟的鸭子还会跑; 烤熟的鸭子不会跑。结论: 羊不吃草。解 符号化上述语句, P:

9、 马会飞, Q: 羊吃草, R: 母鸡是飞鸟, S: 烤熟的鸭子还会跑, S: 烤熟的鸭子不会跑, Q: 羊不吃草。前提集合PQR, RS, S, 结论C : Q。(1)SP(2)RSP (3)R(1), (2), I9(4)PQRP(5)(PQ)(3), (4), I9(6)PQ(5), E5 (7)Q(6), I 2例 如果我的考试通过, 那么我很快乐。如果我快乐, 那么阳光很好。现在是凌晨一点, 天很暖和。试给出结论。解 设P: 我的考试通过, Q: 我很快乐, R: 阳光很好, S: 天很暖和。把“凌晨一点”理解为阳光不好。前提为:PQ, QR, RS。编号公式依据(1) PQP(2)

10、 QRP(3) PR(1), (2)；I11(4) RSP(5) R(4)；I1(6) P(3), (5)；I9结论: P, 我的考试没通过。例 前提: PQ, PR, RS;结论: SQ。证明 (1)SCP (2)RSP (3)SR(2), E (4) R(1), (3), I (5)PRP (6) RP(5), E (7)P(4), (6), I (8)PQP (9)PQ(8), E (10)Q(7), (9), I (11)SQ(1), (10), CP（CP规则这部分因为好像多了一个条件，所以用起来可能会比较简单）例1.9.5：证明RS可从前提P(QS)，RP和Q推出。证明：(CP规则

11、，因为结论RS为条件式)1(1)RP P2(2)RP(附加前提) 1,2(3)PT,(1)(2)I10 3(4)P(QS) P1,2,3(5)QS T, (3,4)I84(6)Q P1,2,3,4(7)ST,(5)(6)I81,3,4 (8)RSCP,(2)(7)例1.9.4：证明从前提PQ，(QR)可演绎出P.证明：(反证法)1(1)PP（附加前提）2(2)PQP 1,2(3)QT,(1)(2)I8 3(4)(QR)P3(5)QRT, (4)E53(6)Q T，(5)I11,2,3(7)QQT,(3)(6)例 “如果春暖花开, 燕子就会飞回北方。如果燕子飞回北方, 则冰雪融化。所以, 如果冰

12、雪没有融化, 则没有春暖花开。 ”证明这些语句构成一个正确的推理。证: 令 P: 春暖花开。Q: 燕子飞回北方。R:冰雪融化。则上述问题转化成证明: PQ, QR RP 利用CP规则, 将R作为附加前提, 推导P, 从而推导出RP。 编号 公式 依据 (1) QR P (2) R P(附加前提) (3) Q (1),(2); I9 (4) PQ 前提 (5) P (3),(4); I9课堂练习：1. 用基本等价公式的转换方法验证下列推断是否有效。(1)P Q，RS，Q RS；(2)P Q，Q R，R P PQR；(3)P，Q R，RS Q S；(4)QR，RP，Q PQ。2. 用推理规则证明下

13、述论断的正确性。(1)P，P (Q (RS) Q S；(2)P (Q R)，R (Q S) P (Q S)；(3)P (Q R) (Q (R S) (P (Q S)；(4)(P Q) (RS)，(Q P)R，R P Q。3. A, B, C, D四人中要派两个人出差，按下述三个条件有几种派法？如何派？(1)若A去，则C 和D中要去一人。(2)B和C不能都去。(3)C去则D要留下。4. A, B, C, D四人参加考试后，有人问它们，谁的成绩最好。A说“不是我”，B说“是D”， C说“是B”，D说“不是我”。四人的回答只有一人符合实际，问是谁的成绩最好？只有一人成绩最好的是谁？5. 判断下列推理

14、是否正确：(1)如果我是小孩，我会喜欢熊猫。我不是小孩，所以我不喜欢熊猫。(2)如果太阳从西边出来，那么地球停止转动。太阳从西边出来了，所以地球停止了转动。二谓词逻辑例 试用量词、谓词表示下列命题： 所有大学生都热爱祖国； 每个自然数都是实数； 一些大学生有远大理想； 有的自然数是素数。解 令S(x)：x是大学生，L(x)：x热爱祖国，则所有大学生都热爱祖国 (x)(S(x)L(x) 令N(x)：x是自然数，R(x)：x是实数，则每个自然数都是实数 (x)(N(x)R(x) l 全称量词(x)后跟条件式。令S(x)：x是大学生， I(x)：x有远大理想，则一些大学生有远大理想 ($x)(S(x

15、)I(x)令N(x)：x是自然数， P(x)：x是素数。则有的自然数是素数 ($x)(N(x)P(x)l 存在量词($x)后跟合取式。例 令f(x):x小于88，g(x):x是奇数，($x) (f(x)g(x) 。 个体变元x是约束变元。这已经不是一个命题函数, 而是一个命题。它相当于说“存在有小于88的奇数”, 这是一个真命题例 令f(y): y是辣椒，g(y): y是红的，(y) (f(y) g(y)。个体变元y是约束变元。这也不是一个命题函数,而是一个命题。 对于其中的个体变元不需要再作代入, 它的含义是确定的, 它断定“一切辣椒都是红的”, 这当然是一个假命题。例：将公式(x)(P(x

16、)Q(x,y)R (x,y)中的约束变元改名。下面哪个正确？（注意到此公式中，约束变元只有x）,1）(y)(P(y) Q (y,y)R (x,y)2）(z)(P(z) Q (x,y)R (x,y)3）(z)(P(z) Q (z,y)R (x,y)例：将公式(x)(P(y)Q(x,y)R (x,y)中的自由变元代入。（注意到此公式中y为自由变元，x既是约束出现，也是自由出现。）我们以y为例，试判断下面哪个正确？1）(x)(P(z) Q (x,z)R (x,y)2）(x)(P(x) Q (x,z)R (x,x)3）(x)(P(z) Q (x,z)R (x,z)例 在公式(x) (Q(x) R(x,

17、 y)($z) P(x, z)中，x既为约束出现，又为自由出现，下面用两种方法，使变元x在公式中只呈一种形式出现解 用约束变元的改名规则得:(u) (Q(u) R(u, y)($z) P(x, z); 或用自由变元得代入规则得:(x )(Q(x) R(x, y)($z) P(u, z)。（重做前一例题，将自由出现的x进行代入）重做例：将公式(x)(P(y)Q(x,y)R (x,y)中的自由变元代入。注意到此公式中y为自由变元，x既是约束出现，也是自由出现。这次，我们将自由出现的x代入，得：(x)(P(y) Q (x,y)R (z,y)例 试证明下面苏格拉底论证：所有人都是要死的，苏格拉底是人，

18、因此，苏格拉底是要死的。证明： 令M(x):x是人，D(x):x是要死的，s:苏格拉底，原题可符号化为：(x)(M(x)D(x)，M(s) D(s)推证如下：1 (1) (x)(M(x)D(x) P1 (2) M(s)D(s) UI,(1)3 (3) M(s) P1,3 (4) D(s) T,(2),(3),I例 证明 ($x)A(x)(x)B(x) (x)(A(x)B(x) 证明：反证法(1) (x) (A(x) B(x)P(附加前提)(2) ($x) (A(x) B(x)T, (1), E(3) (A(a) B(a)T, (2), ES(4) A(a)B(a)T, (3), I(5) A(

19、a)T, (4), I(6) B(a)T, (4), I(7) ($x) A(x)T, (5), EG(8) ($x) A(x) (x) B(x)P前提(9) (x) B(x)T, (7)(8), I(10) B(a)T, US(11)B(a)B(a)(6)(10)矛盾三集合例 在一个住着一些人家的僻静孤岛上, 岛上只有一个理发师a, a给且只给岛上所有不能自己理发的人理发。问谁给a理发？解: 设 S = x | x 是不能自己理发的人。(1) 若aS, 则a给自己a理发。又由题意知, a只给不能自己理发的人理发, 所以a是不能自己理发的人, 即aS, 矛盾。(2) 若aS, 则a是不能自己理

20、发的人。又由题意知, a只给集合S中的人理发, 所以a要给a理发, 即aS , 矛盾。无论如何, 都有aS和aS同时成立。这是著名的罗素悖论paradox。例 令A=1,2,3,4, B=4,5,5,6,则A=1,23=1,2,3, B=55,6=5,6, A=1,23=, B=55,6=5四关系例 设 A = 1, 3, 5, B = 2, 4, 6, 8, 定义A到B的二元关系R: a, bR当且仅当ab, 则称R为A到B的“小于”关系。R = 1,2, 1,4, 1,6, 1,8, 3,4, 3,6, 3,8, 5,6, 5,8是A到B的一个关系, 显然R AB。而 3,2R, 5,2R

21、, 5,4R。例 设A = 1, 2, 3, 4, 5, 6, B = a, b, c, d, 关系R = 2, a, 2, b, 3, b, 4, d, 6, d, 则dm(R) = 2, 3, 4, 6, rn(R) = a, b, d,fl(R)=2,3,4,6,a,b,d。例 设A = 1, 2, 3, B=1, 2, 3, 4,从A到B上的关系R=1,1,2,2,3,3,S=1,1,1,2,1,3,1,4，则RS=1,1,2,2,3,3, 1,2,1,3,1,4RS=1,1R-S=2,2,3,3S-R=1,2,1,3,1,4R=1,2,1,3,1,4, 2,1,2,3,2,4, 3,

22、1,3,2,3,4要注意的是, 作为关系, 补运算是对全域关系而言的, 并不是对全集U而言的。例 设A和B分别是学校的所有学生和所有课程的集合。假设R由所有有序对a,b组成，其中a是选修课程b的学生。S由所有有序对a,b构成，其中课程b是a的必修课。什么是关系RS，RS，RS，R-S和S-R？解：关系RS由所有的有序对a,b组成，其中a是一个学生，他或者选修了课程b，或者课程b是他的必修课。RS是所有有序对a,b的集合，其中a是一个学生，他选修了课程b并且课程b也是a的必修课。 RS由所有有序对a,b组成，其中学生a已经选修了课程b，但课程b不是a的必修课，或者课程b是a的必修课，但a没有选修

23、它。 R-S是所有有序对a,b的集合，其中a已经选修了课程b但课程b不是a的必修课。S-R是所有有序对a,b的集合，其中课程b是a的必修课，但a没有选它。例 设A = a, b, c, d, A上的关系R = a, a, a, b, b, d, S = a, d, b, c, b, d, c, b。求 R*S 和 S*R。解: R*S = a, d, a, c； S*R = c, d。显然 R*S S*R 从本例可知复合关系不满足交换律。兄弟关系和父子关系的复合是叔侄关系例 设A = a, b, c, d, e, f , R =a, b, b, c, c, d, d, e, e, f。求Rn

24、(n =1, 2, 3, 4, )。解：R1 = R； R2 = R*R =a, c, b, d, c, e, d, f； R3 = R2*R =a, d, b, e, c, f； R4 = R3*R =a, e, b, f； R5 = R4*R = a, f； R6 = R5*R = ； R7 = ； Rn = ( n5 )。例 设A = a, b, c, d, 1, 2, 3, 4, A上的关系R = a, 2, b, 2, b, 3, d, 4, 则 R1 = 2, a, 2, b, 3, b, 4, d。例 设A = a, b, c, B = 0, 1, 有A到B的关系 R = a,

25、0, b, 0, c, 1, S = a, 1, b, 1, c, 1则 R1=0, a,0, b, 1,c, S1=1, a,1, b,1, cRS = a, 0, b, 0, c, 1, a, 1, b, 1；(RS) 1 = R1S1 = 0, a, 0, b, 1, c, 1, a, 1, b；RS = c, 1; (RS) 1 = R1S1= 1, c;R S = a, 0, b, 0；(R S) 1 = R1 S1 = 0, a, 0, b；dm R1 = rn R = 0, 1；rn(S1)= dm(S) = a, b, c例 设A = 2, 3, 4, B = 2, 3, 4,

26、 5, 6, 定义A到B的二元关系R:aRb当且仅当a整除b。R=2, 2, 2, 4, 2, 6, 3, 3, 3, 6, 4, 4 2 3 4 5 6 2 1 0 1 0 1MR= 3 0 1 0 0 1 4 0 0 1 0 0 例 S = a, b, c, S上的关系R1 = a, a, b, b, c, c, b, cR2 = a, b, b, aR3 = b, b, c, cR1是自反的, R2不是自反的, R3也不是自反的。R1不是非自反的, R2是非自反的, R3也不是非自反的。例 设A2,3,5,7，Rx, y|(x-y)/2是整数，验证R在A上是自反和对称的。证：因为对于任意

27、xA，(x-x)/20,即x, yR，故R是自反的。又设x,yA，如果x, yR，即(x-y)/2是整数，则(y-x)/2是整数，即y, xR，故R是对称的。事实上，关系R 2, 2, 3, 3, 5, 5, 7, 7, 3, 5, 5, 3, 3, 7, 7, 3, 5, 7, 7, 5例 设X1,2,3，R11, 2, 2, 2， R21, 2， R31, 2, 2, 3,1, 3, 2, 1，R1,R2,R3都是传递关系吗？证：根据传递的定义，R1和R2是传递的。但对于R3,因为1, 2R3，2, 1R3，但1, 1R3,，故R3不是传递的。注意：R2是传递的。例 在集合S = a, b

28、, c, d上的关系R b, c, c, c, c, d, d, c, 判断R的性质。解 R不是自反的； c, cR，所以R不是非自反的； b, cR, 但 c, bR, 所以R不是对称的； c, cR，所以R不是非对称的；c d, 但 c, dR且d, cR, 所以R不是反对称的；b, cR, c, dR, 但 b, dR, 所以R不是可传递的。例 A = 1, 2, 3, 4, 5, 6, 7, R是A上的模3同余关系。显然R是A上的等价关系, A中各元素关于R的等价类分别是:1R = 1, 4, 7,4 R= 1, 4, 7, 7 R= 1, 4, 72 R = 2, 5,5 R = 2

29、, 5,3 R = 3, 6,6 R = 3, 6, 可以看出, 彼此等价的元素其等价类是相同的, 所以不同的等价类仅有3个, 它们是1 R, 2 R和3 R。例 若A = 2, 3, 4, 6, 8, 偏序关系是整除关系, 则2和3是A的极小元, 6和8是A的极大元。1. 我们先看极小元,从最大的数8开始,因为48(即4整除8),故8不是极小元，那么4是不是极小元呢？因为24,所以4也不是极小元，那么2是不是极小元呢？由于A中没有任何其它元素x, 满足x2,故2是A的极小元。同理，3也是A的极小元。4不是，因为24。2. 对于极大元，我们从最小的数2开始,因为24(即2整除4),故2不是极大

30、元，那么4是不是极大元呢？因为48,所以4也不是极大元，那么8是不是极大元呢？由于A中没有任何其它元素x, 满足8x,故8是A的极大元。同理，6也是A的极大元。4不是，因为48。l 从本例可知, 极小元和极大元不是唯一的。例 若A = 2, 3, 4, 6, 8, 偏序关系是整除关系，则A中既没有最小元, 也没有最大元。 因为 2不能整除A中所有元素(如2不能整除3),所以2不是A的最小元，显然其余元素也不是。同理，8也不能被A中所有元素所整除，所以8不是A的最大元。实际上，A中所有元素的(最大)公约数和(最小)公倍数均不属于A, 所以A中既没有最小元, 也没有最大元。 又如B = 2, 4,

31、 6, 8, 偏序关系是整除关系,则B的最小元是2,没有最大元。又如C= 2, 4, 8,偏序关系是整除关系,则C的最小元是2,最大元是8。 五函数与基数（这部分不是重点，了解就行）六代数结构本章是重点，主要内容是掌握各种代数结构的性质及使用。按照课本的划分同时包括群环和格和布尔代数。例12.3.6 给定，其中S=，A，B，C，和是一般的集合运算；又有，这里T = 1，2，5，10，且对于a，bT有a b = lcma，b(最小公倍数)，a b = gcda，b(最大公约数) ，表12.3.3至表12.3.6给出四个运算表。试说明.解：令fTS：f()=1，f(A)=2，f(B)=5，f(C)

32、=10。显然，f是从S到T的双射。经验证，对任意x1, x2S，又有f(x1x2)=f(x1) f(x2)f(x1x2)=f(x1) f(x2)故与是同构的。例13.1.1 给定和，其中N为自然数集合，+和为普通加法和乘法。由普通加法和乘法满足封闭性和结合律易知，和都是半群，而且还是独异点。因为0是+的幺元，1是的幺元。 关于独异点，有下面二个性质：定理13.1.5 设为独异点，则关于的运算表中任两列或任两行均不相同。证明：对任意a,bM，且ab，有eaabeb和aeabbe即在的运算表中任两列或任两行均不相同。注意：这个定理对半群不一定成立，这个定理的成立完全是由于幺元的存在。定理13.1.

33、6 给定独异点，对任意a，bM且a，b均有逆元，则(1) (a-1)-1=a。(2) ab有逆元，且(ab)-1=b-1a-1。证明：(1)因为a-1是a的逆元，即aa-1=a-1a=e，故(a-1)-1=a。(2)因为(ab)(b-1a-1)=a(bb-1)a-1= aea-1= aa-1=e，同理(b-1a-1)(ab) =e，故(ab)-1=b-1a-1。例13.4.1 给定和，其中Z和Q分别是整数集合和有理数集合，+和是一般加法和乘法。可知是群，0是幺元，每个元素iZ的逆元是-i；不是群，1是幺元，0无逆元。但便成为群。例 是环，其中Mn(R)是n阶实矩阵的集合，+、 分别是矩阵加法和乘法。例14.4.1 和皆为域，而不为域，其中R、Q和Z分别为实数集合、有理数和整数集合，+和是普通加法和乘法。例如：设是一个格，其中Sa,b,c,d,e,f,g,h，如图所示，取hfcbedgaS1=a,b,d,fS2=c,e,g,hS3=a,b,c,d,e,g,h问，其中哪些构成格？哪些是的子格？,是的子格，而虽然是格，但不是的子格，因为bd=fS3。七图论根据图的同构定义，可以给出图同构的必要条件如下：(1) 结点数目相等；(2) 边数相等；(3) 度数相同的结点数目相等。 （注：可编辑下载，若有不当之处，请指正，谢谢!）