离散证明题集锦

1、离散证明题集锦例：给出(PAQ)? ( PVi Q)的真值表PQ(PAQ) ? (j PVi Q)0010111101101110101010 11110110 0 0步骤 一般说来，n个命题变元组成的命题公式共有 2n种真值指派。定理1:任何两个重言式的合取或析取，仍然是重言式。证明：设A、B为两个重言式，则 人入8和人/8的真值分别等于TAT 和 T VT。定理2:对一个重言式的同一分量都用任何一个命题公式置换，所得命题公式仍为一个重言式。(即代入规则)证明：由于重言式的真值与分量的真值指派无关， 故对同一分量以 任何一个命题公式置换后，重言式的真值不变。定理3:设A、B是两个命题公式，A

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

3、Q VR) PVQV RPA QVQ PVQ解：1.原式Q-(PVP) A (PVQ) Q-PA(PVQ)Q-P2 .原式(PAQ) VP) A(PAQ) VI Q) (PVP) A (PVQ) A(PVn Q) A(QVi Q)PA (PVQ) A(PVn Q) PAP P3 .原式( J PVQ) V(QVR) (PA Q) V(QVR) (PVQVR) A(QVi QVR) PVQVR (零率)4 .原式(PA Q) VQ (PVQ) A(n QVQ) PVQ (运算次级优先级:,A, V,例：求证：(P -Q) V I (P -Q)为永真式。解：原式 J PVQ) V (PAi Q)(

4、 PVQVP) A J PVQ5 Q)T例：求证QA(P-Q) I P证法1:前件真推导后件真证法2:后件假推导前件假证法3:定义定理：设P、Q为任意两个命题公式，P Q的充分必要条件是P Q且Q P。证明：若P Q,则P? Q为重言式，即P-Q和Q-P是重言式； 若有P Q且Q P,则P-Q和Q-P是重言式，即P? Q为重言 例 已知A是B的充分条件，B是C的必要条件，C是D的必要条件, D是B的必要条件，问：(1) A是D的什么条件？B是D的什么条件？解 已知A B, C B, D C, B D,故有A B, B D,所以A D,即A是D的充分条件DC, C B,所以D B,又因为B D,

5、所以B D,即B是D 的充要条件。定理：如果A B,则A* B*。证明：设P1,P2,Pn是出现在命题公式A、B中的原子变元，因 为 A B,即：A(P1,P2,- -,Pn)? B(P1,P2j,Pn)是一个重言式。故有：A( 1 P1,i P2,i Pn)? B(i P1,i P2, yPn)是一个重言式。即A( 1 P1,i P2,，i Pn) B(1 P1,i P2,，i Pn)1 A* B* ,即 A* B*例判断下面各推理是否正确.(1)如果天气凉快，小王就不去游泳.天气凉快，所以小王没去游泳.(2)如果我上街，我一定去新华书店.我没上街.所以我没去新华书店.解：解上述类型的推理问

6、题，应先将命题符号化，然后写出前提、结论 和推理的形式结构，最后进行判断.(1)P:天气凉快； Q:小王去游泳.前提：P- Q, P.结论： Q.推理的形式结构为(P- Q)AP)-Q.(*)判断(*)是否为重言式.真值表法真值表的最后一列全为1,因而(*)是重言式.所以推理正确.等价演算法(PQ)AP)-Q 1.主析取范式法(P-Q) A P)- Qm0 V ml V m2 V m3由，同样能判断推理正确.(2)P:我上街；Q:我去新华书店.前提：P-Q, P. 结论： Q.推理的形式结构为(P-Q)AP) 一 Q. (*)(P-Q) AP)-Qm0 V m2 V m3可见(*)不是重言式，

7、所以推理不正确.还可用其他方法判断之例 证明下列前提是不相容的1 .若A因病缺了许多课，那么他中学考试失败。2 .若A中学考试失败，则他没有知识。3 .若A读了许多书，则他有知识。4 . A因病缺了许多课，而且读了许多书。证明符号化题目：P：因病缺了许多课，Q：中学考试失败，R：有知识，S：读了许多书。问题要证明前提P Q, Q R, S R, PAS是不相容的。下面我们用另外一种形式的格式证明（即后面讲的 构造证明”的格式）：编号公式依据PA SPP(1)； I1S(1); I2P QPQ,(4)； I8(6)S RPR(3),(6)； I8(8)(9) R (5),(8); I9(10)

8、RA R(7),(9)例 张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎。问谁说真话，谁说假话？解 设A:张三说真话；B:李四说真话；C:王五说真话依题意有A B, B C, C A A Bo(A B)A (B C)A(C A A B)(A B) A ( B A) A (B C) A ( C B) A (C ( AA B) A(AA B) C)(AABA C) A (A V B) A C) A ( A A BA C) V (A A C) V(BA C)AABA C即：李四说真话，张三和王五说假话。例1.9.3:求证：S是前提 W, W7 Q,i QR和RS的有 效结论。证明：1(

9、1) W 一 I Q P2(2) 1 Q-R P1,2 W R T,(1)(2)I113(4) W P1,2,3 (5) R T,(3)(4)I84(6) R S P1,2,3,4 (7) S T,(5)(6)I8(这部分的T, I8等是另外一本书的内容，所以不用管，只要会推 就行)例前提：如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞 鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。结论：羊不吃草。解 符号化上述语句，P:马会飞，Q:羊吃草，R:母鸡是飞鸟，S:烤熟 的鸭子还会跑，S:烤熟的鸭子不会跑，Q:羊不吃草。前提集合PVQ R, R S, S,结论C : Q。(1) S P(2) R

10、 S P(3) R(1),(2), I9(4) PVQ R P(5) (PVQ)(3), (4),I9(6) PA Q(5), E5(7) Q (6), I 2例 如果我的考试通过，那么我很快乐。如果我快乐，那么阳光很好现在是凌晨一点，天很暖和。试给出结论。解 设P:我的考试通过，Q:我很快乐，R:阳光很好，S:天很暖和。把 凌晨一点”理解为阳光不好。前提为：P Q, Q R, RASo编号公式依据(1) PQP(2) QRP(3) PR(1),(2); I11(4) RASP(5) R(4)； I1(6) P(3),(5)；I9结论：P,我的考试没通过。例 前提：PV Q, P R, R S

11、;结论：S Q证明(1) S CP(2) RSP(3) SR(2), E(4) R (1),(3), I(5) P R P(6) R P (5), E(4), (6), IPV Q P(9) P Q (8), E(10) Q (7),(9), I(11) S Q (1), (10), CP(CP规则这部分因为好像多了一个条件，所以用起来可能会比较简 单)例1.9.5:证明R-S可从前提P-(Q-S), I RVP和Q推出。 证明：(CP规则，因为结论R-S为条件式)1(1) RVP P2(2) RP(附加前提)1,2(3) P T,(1)(2)I103(4) P-(Q-S)P1,2,3 (5)

12、 Q-ST, (3,4)I84(6) Q P1,2,3,4 (7) ST,(5)(6)I81,3,4(8) R-S CP,(2)(7)例1.9.4:证明从前提P-Q, (QVR)可演绎出1P.证明：(反证法)1(1) P P (附加前提)2(2) PQ P1,2 Q T,(1)(2)I83(4) (QVR) P3(5) QA RT, (4)E53(6)i Q (5)I11,2,3 (7) Q An Q T,(3)(6)例 如果春暖花开，燕子就会飞回北方。如果燕子飞回北方，则冰雪 融化。所以，如果冰雪没有融化，则没有春暖花开。”证明这些语句构成一个正确的推理。证：令P:春暖花开。Q:燕子飞回北方

13、。R:冰雪融化。则上述问题转化成证明：P Q, QRR P利用CP规则，将 R作为附加前提,推导 P,从而推导出R P。编号公式依据(1)Q RP(2)RP(附加前提)(3)Q,(2)； I9(4)P Q(5)P,(4)； I9课堂练习:(1) 基本等价公式的转换方法验证下列推断是否有效。(1)P Q, RAS, Q RAS;(2) P Q, Q R, R PPVQVR;(3)P, Q R, RVS QS;(4) QA R, RAP, QPV Q。2.用推理规则证明下述论断的正确性。(1)P, P (Q (RAS)QS;P (Q R), R (QS)P(QS);P(Q R) (Q (R S)

14、(P (Q S);(4) (P Q) (RVS),(QP)VR,R P Q。3. A, B, C, D四人中要派两个人出差，按下述三个条件有几种派法？如何派？若A去，则C和D中要去一人。(2)B和C不能都去。(3)C去则D要留下。4. A, B, C, D四人参加考试后，有人问它们，谁的成绩最好。A说不 是我"，B说 是D"，C说 是B"，D说 不是我"。四人的回答只有 一人符合实际，问是谁的成绩最好？只有一人成绩最好的是谁？5. 判断下列推理是否正确：(1)如果我是小孩，我会喜欢熊猫。我不是小孩，所以我不喜欢熊猫。(2)如果太阳从西边出来，那么地球停止

15、转动。太阳从西边出来了，所以地球停止了转动。二.谓词逻辑例试用量词、谓词表示下列命题：所有大学生都热爱祖国； 每个自然数都是实数；一些大学生有远大理想；有的自然数是素数。解 令S(x): x是大学生，L(x): x热爱祖国，则所有大学生都热爱祖国(x)(S(x)- L (x) 令N(x): x是自然数，R(x): x是实数，则每个自然数都是实数(x)(N(x)-R(x)全称量词(x)后跟条件式。令S(x): x是大学生，I(x): x有远大理想，则一些大学生有远大理想(x)(S(x) A I (x)令N(x): x是自然数，P(x): x是素数。则有的自然数是素数(x)(N(x)AP(x)存在

16、量词(x)后跟合取式。例 令f(x):x小于88, g(x):x是奇数，(x) (f(x) A g(x)。个体变元x是约束变元。这已经不是一个命题函数，而是一个命题。它相当于说 存在有小于88的奇数”，这是一个真命题例令f(y)： y是辣椒，g(y)： y是红的,(y) (f(y) -g(y)。个体变元y是约束变元。这也不是一个命题函数，而是一个命题。对于其中的个体变元不需要再作代入，它的含义是确定的，它断定 :切辣椒都是红的”，这当然是一个假命题。例：将公式(x)(P(x)f Q(x,y)AR (x,y)中的约束变元改名。下面哪个正确？(注意到此公式中，约束变元只有x),1) ( y)(P(

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

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

19、x是人，D(x):x是要死的，s:苏格拉底，原题可符号化为：(x)(M(x)-D(x), M(s)卜 D(s)推证如下：1(x)(M(x)-D(x)P1M(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)证明：反证法(x) (A(x)B(x)P(附加前提)(x) (A(x)B(x)T, (1), E(A(a)B(a)T, (2), ES(4) A(a) A B(a)T, (3), I A(a)T, (4), I(6) B(a)T, (4), I(7) ( x) A(x)T, (5), EG

20、(8)( x) A(x) ( x) B(x)P前提T, (7)(8), IT, US(6)(10)矛盾(9) ( x) B(x)(10) B(a)(11) B(a)A B(a)三.集合例在一个住着一些人家的僻静孤岛上，岛上只有一个理发师a, a给 且只给岛上所有不能自己理发的人理发。问谁给 a理发？解：设S = x | x是不能自己理发的人。 若a S,则a给自己a理发。又由题意知，a只给不能自己理发的 人理发，所以a是不能自己理发的人，即a S,矛盾。(2)若a S,则a是不能自己理发的人。又由题意知，a只给集合S 中的人理发，所以a要给a理发，即a S ,矛盾。无论如何，都有a S和a S

21、同时成立。这是著名的罗素悖论paradox。例令 A=1,2,3,4, B=4,5,5,6,则UA=1,2U3=1,2,3,U B=5 U 5,6=5,6,AA=1,2A3二,n B=5 n 5,6=5四.关系例设A = 1, 3, 5, B = 2, 4, 6, 8,定义A到B的二元关系R: ?a, b? R当且仅当aQ 则称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 AX B。而?3,2? R, ?5,2? R, ?5,4? R。例 设 A = 1,

22、2, 3, 4, 5, 6, B = a, b, c, d,关系 R = ?2, a? ?2, b? ?3, b? ?4, d?石,d?,贝Udm(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?,2?,3?1,4p,则RUS=?1,1?2,2?,?3,3?, ?1,2?,3?,?1,43RAS=?1,ipR-S=?2,2?3,3?S-R=?1,2?1,3?,4?R'=?1,2?1,3?,

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

24、成，其中学生a已经选修了课程 b,但课程b不是a的必修课，或者课程b是a的必修课，但a没有 选修它。R-S是所有有序对a,b?l勺集合，其中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? Q d? ?c, b?。求 R*S 和 S*R。解：R*S = ?a, d? ?a, c?;S*R = 宽,d?h显然 R*S丰S*R从本例可知复合关系不满足交换律。兄弟关系和父子关系的复合是 叔侄关系例设

25、 A = a, b, c, d, e, f ,R =?a, b? ?d, c? ?c, d?,?d, e? ?e, f?。求 Rn (n =1, 2, 3, 4,)。解：R1 = R;R2 = R*R = ?a, c? ?b, d?,觉，e? ?d, f?;R3 = R2*R = ?a, d? ?d, e? ?c, f?;R4 = R3*R = ?a, e?, ?b, fp；R5 = R4*R = ?a, f?;R6 = R5*R =;R7 =:Rn =(n >5 )。例设 A = a, b, c, d, 1,2, 3, 4, A 上的关系R = ?a,2?,?b,2?, ?b, 3?,

26、?d,4?,则RT = ?2,a?2b? ?3, b?,?4,d?。例设A = a, b, c, B = 0, 1,有A到B的关系R = ?a, 0? ?b, 0? ?c, 13, S = ?a, 1? Q 1? ?c, 1?则 RT=?0, a?,?0, b?, ?1,c?, ST=?1, a?, b?, c?RUS = ?a, 0?, ?b, 0?, ?c, 1?, ?a, 1? Q 1?;(RUS) - 1 = RTUST=?0, a? ?0, b? ?1, c? ?1, a? ?1, b?;RAS = ?c, 1?;(RAS) - 1 = RTAST= ?1, c?;R - S = ?

27、a, 0?, ?d, 0?;(R - S) - 1 = RT - S1 = ?0, a?, ?0,b3;dm R 1 = rn R = 0,1;rn(S 1= dm(S) = a, b, c例设 A = 2, 3, 4, B = 2, 3, 4, 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 62 10 10 1MR=例S = a, b, c, S上的关系R1 = ?a, a? ?d,b? ?c, c?d,c?R2 = ?a, b?, ?d, a?R3 = ?b

28、, b?觉，c?R1是自反的，R2不是自反的，R3也不是自反的。R1不是非自反的，R2是非自反的，R3也不是非自反的例 设A = 2,3,5,7, R = ?x, y?|(x-y)/2是整数,验证R在A上是自反和对称的。证：因为对于任意x6A, (x-x)/2=0，即?x, y?6 R,故R是自反的。又设x,y6A,如果？x, y?6 R,即(x-y)/2是整数，则(y-x)/2是整数, 即征x?6 R,故R是对称的。事实上，关系 R= ?2, 2?, ?3, 3?, ?5, 5?, 27,7? ?3, 5?, ?5, 3?, 23,7? ?7, 3?, ?5, 7?, ?7, 5?例设 X

29、= 1,2,3, R1=?1,2?, ?2, 2? R2 = ?1,2?, R3=?1,2?, ?2,3?,?1, 3?, ?2, 1? R1,R2,R3 都是传递关系吗？证：根据传递的定义，R1和R2是传递的。但对于R3,因为？1, 2?6R3, 2 1?6 R3,但？1, 1?R3,故 R3 不是传递的。注意：R2是传递的。例在集合S = a, b, c, d上的关系R= Q c?觉,c?觉,d? ?d, c?,判断R的性质。解R不是自反的；?c, c? R,所以R不是非自反的；?b, c? R,但?c, b? R,所以R不是对称的；?c, c? R,所以R不是非对称的；c d,但?c,

30、d? R且？d, c? R,所以R不是反对称的；Q c? R,觉,d? R,但 Q d? R,所以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, 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

31、的极大元。1 .我们先看极小元，从最大的数8开始，因为4W8（即4整除 8）,故8不是极小元，那么4是不是极小元呢？因为2W4, 所以4也不是极小元，那么2是不是极小元呢？由于 A 中没有任何其它元素x,满足xW2,故2是A的极小元。同理，3也是A的极小元。4不是，因为2W4。2 .对于极大元，我们从最小的数2开始，因为2W4（即2整除 4）,故2不是极大元，那么4是不是极大元呢？因为4<8, 所以4也不是极大元，那么8是不是极大元呢？由于 A 中没有任何其它元素x,满足8Wx,故8是A的极大元。同理，6也是A的极大元。4不是，因为4<8O从本例可知，极小元和极大元不是唯一的。例若

32、A = 2, 3, 4, 6, 8,偏序关系是整除关系，则A中既没有最小元， 也没有最大元。因为2不能整除A中所有元素（如2不能整除3）,所以2不是A的最小元，显然其余元素也不是。同理， 8也不能被A中所 有元素所整除，所以8不是A的最大元。实际上，A中所有元素的（最 大）公约数和（最小）公倍数均不属于A,所以A中既没有最小元，也没 有最大元。又如B = 2, 4, 6, 8,偏序关系是整除关系，则B的最小元 是2,没有最大元。又如C= 2, 4, 8,偏序关系是整除关系，则C的最小 兀是2,最大兀是8。五.函数与基数（这部分不是重点，了解就行）六.代数结构本章是重点，主要内容是掌握各种代数结

33、构的性质及使用。按照课本的划分同时包括群环和格和布尔代数。例 12.3.6 给定 <S, U, n >,其中 S= , A, B, C, U和 A是一 般的集合运算；又有<T,>,这里T = 1, 2, 5, 10,且对于a, b6T 有 a b = lcma, b（最小公倍数），a b = gcda, b（最大 公约数），表12.3.3至表12.3.6给出四个运算表。试说明<S, A, U> 二 <，>.解：令 f TS: f( )=1, f(A)=2, f(B)=5, f(C)=10。显然，f 是从 S到T的双射。经验证，对任意 x1, x2 S,又有f(x1 Ux2)=f(x1) f(x2)f(x1 Ax2)=f(x1) f(x2)故s, n, u 与，是同构的。表 1233U 0 A B C表 1234r 0 A B c0 0 A B CABCA A C CB C B CC C C C表