12024/9/23离散数学Discrete Mathematics 第一章第一章逻辑与与证明明& 学学习内容内容1.1 1.1 逻辑逻辑逻辑逻辑1.2 1.2 命命命命题题题题等价等价等价等价1.3 1.3 谓词谓词谓词谓词和量和量和量和量词词词词 1.4 1.4 对对对对偶与范式偶与范式偶与范式偶与范式1.5 1.5 推理推理推理推理规规规规那么那么那么那么1.6 1.6 证证证证明明明明导论导论导论导论1.7 1.7 证证证证明的方法和明的方法和明的方法和明的方法和战战战战略略略略1.8 1.8 数理数理数理数理逻辑逻辑逻辑逻辑的运用的运用的运用的运用&命命题等价等价命题公式命题公式真值表真值表等价公式等价公式重言式和蕴含式重言式和蕴含式&命命题变元元&复合命复合命题&命命题公式公式&命命题公式公式&命命题公式公式&命命题公式公式&命命题公式公式商定：商定：为方便，最外方便，最外层括号可以不写，括号可以不写，合式公式可以写成：合式公式可以写成：PQ， PR，(PQ)R假假设规定定逻辑联接接词的的优先先级：、那么：那么：PQR也是合式公式也是合式公式&命命题等价等价命题公式命题公式真值表真值表等价公式等价公式重言式和蕴含式重言式和蕴含式&命命题公式的公式的赋值 设pl，p2，pn是出如今公式A中的全部命题变元，给pl，p2，pn各指定一个真值，称为对公式A的一个赋值或解释。 假设指定的赋值使A的真值为T，那么称这个赋值为A的成真赋值，假设使A的真值为F，那么称这个赋值为A的成假赋值。 例如，给公式(pqr)赋值011是指p=0，q=1，r=1，它是该公式的成真赋值；赋值110是指p=1，q=1，r=0，它是该公式的成假赋值。 &真真值表的概念表的概念&真真值表的概念表的概念 P Q PPQ(PQ)Q T T F T T T F F T T F T T T T F F T F F&真真值表的概念表的概念阐明明: :设P1P1，P2,PnP2,Pn为命命题公式公式P P中的中的命命题变量，量，对于命于命题变元每一种真元每一种真值指派的能指派的能够组合，都能独一确定合，都能独一确定P P的真的真值即有即有2 2的的n n次次幂种分布。种分布。为了有序地列出公式的真了有序地列出公式的真值表，在表，在对命命题变元做指派元做指派时，可以按照二，可以按照二进制数的次序列表。制数的次序列表。 【例】构造命题公式pq的真值表，并求成真赋值和成假赋值。 解：命题公式pq的真值表如表1.6所示。00，01，11是成真赋值，10是成假赋值。 ppqpq0011011110001101pqpqpqpq(pq)(pq)0001111010100010001001110001 【例】构造命题公式(pq)(pq)的真值表，并求成真赋值和成假赋值。 解：命题公式(pq)(pq)的真值表如下表所示。00， 11是成真赋值，01，10是成假赋值。 为了有序地列出了有序地列出A(P1,P2,Pn)A(P1,P2,Pn)的真的真值表，可以将表，可以将F F看成看成0 0，将，将T T看成看成1 1，按照二，按照二进制数制数000, 0001, 00010, 000, 0001, 00010, , 1110, 111(, 1110, 111(即十即十进制的制的0,1,2,. ,2n -1)0,1,2,. ,2n -1)的次的次序序进展指派列真展指派列真值表。表。如如A(P,Q)A(P,Q)的真的真值表可按照如下次序指派：表可按照如下次序指派： 00(F,F) 00(F,F)，01(F,T)01(F,T)，10(T,F)10(T,F)，11(T,T)11(T,T)如如A(P,Q,R)A(P,Q,R)的真的真值表可按照如下次序指派：表可按照如下次序指派： 000(F,F,F), 001(F,F,T), 010(F,T,F), 000(F,F,F), 001(F,F,T), 010(F,T,F), 011(F,T,T) 011(F,T,T) 100(T,F,F), 101(T,F,T), 110(T,T,F), 100(T,F,F), 101(T,F,T), 110(T,T,F), 111(T,T,T)111(T,T,T)&真真值表构造表构造总结例如列出例如列出P P(Q(QR)R)的真值表的真值表 P Q R Q RP(QR)000 F F F T T001 F F T T T010 F T F F T 011 F T T T T100 T F F T T101 T F T T T110 T T F F F111 T T T T T察看下面的真值表PQP QPQ（P Q）（P Q）PQFFTTTTFTTTFFTFFFFFTTTTTT在上面的真实表中他能否发现什么问题？P Q P Q？P Q P Q P Q ？&命命题等价等价命题公式命题公式真值表真值表等价公式等价公式重言式和蕴含式重言式和蕴含式&命命题公式的等价公式的等价AB的定的定义义：A、B是含有命是含有命题变题变元元P1,P2,Pn的命的命题题公式，如不公式，如不论对论对P1,P2,Pn作任何指派，都使得作任何指派，都使得A和和B的真的真值值一一样样，那么称之，那么称之为为A与与B等价，等价，记记作作AB。显显然然P QPQ P Q P Q PQ提示：判提示：判别别两个公式能否等价，更好的方法是当两个公式能否等价，更好的方法是当变变元数元数不多不多时时，直接构造两个公式的真，直接构造两个公式的真值值表，看两个真表，看两个真值值表能表能否相等即可。否相等即可。&命命题公式的等价公式的等价&命命题公式的等价公式的等价pqppqqqpp(qp)pqp(pq)p(pq)00111111011001111001111111001101&命命题公式的等价公式的等价&命命题公式的等价公式的等价 4.分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 5.德摩根律 (AB)AB (AB)AB 6.幂等律 AAA，AAA 7.吸收律 A(AB)A， A(AB)A 8.零律 A11，A00 &命命题公式的等价公式的等价 9.同一概 A0A， A1A 10.排中律 AA1 11.矛盾律 AA0 12.条件等价式 ABAB 13.双条件等价式 AB(AB)(BA) 14.假言易位式 ABBA 15.双条件否认等价式 ABAB &命命题公式的等价公式的等价ABABAABBABAB (AB)(AB)0011101011001010010101100010&命命题公式的等价公式的等价ABABAABBABAB (AB)(AB)0011101011001010010101100010312024/9/23 (p q) (q p) (q p) (p q ) p q Examples:p pp pp q (p q) (q p)- Contradiction- Tautology - Contingency- ?&命命题公式的等价公式的等价证明等价公式成立的常用方法：证明等价公式成立的常用方法： 方法方法1： 真值表。真值表。 方法方法2：等价公式推导。：等价公式推导。(用置换定律用置换定律)置换定律置换定律:A是一个命题公式，是一个命题公式，X是是A中的一部分中的一部分且也是合式公式，假设且也是合式公式，假设XY，用，用Y替代替代A中的中的X得到公式得到公式B，那么，那么AB。满足置换定律满足置换定律的变换称为等价变换。的变换称为等价变换。&命命题公式的等价公式的等价例例题1. 1. 求求证吸收律吸收律 P(PQ) P(PQ)P P证明明 P(PQ) P(PQ) (PF)(PQ) ( (PF)(PQ) (同一概同一概) ) P(FQ) ( P(FQ) (分配分配律律) ) PF PF ( (零律零律) ) P P ( (同一概同一概) )&命命题公式的等价公式的等价例例题2. 2. 求求证 ( ( PQ)(PQ) PQ)(PQ) P P证明明 ( ( PQ)(PQ)PQ)(PQ) ( ( PQ)(PQ) (PQ)(PQ) (公式公式E11)E11) ( (PP Q)(PQ) (Q)(PQ) (摩根定摩根定律律) ) (P (P Q)(PQ) (Q)(PQ) (对合律合律) ) P(P( QQ) (QQ) (分配律分配律) ) PT (PT (互互补律律) ) P (P (同一概同一概) )公式公式E11 E11 ： P PQ QPQ PQ 例题例题例题例题3. 3. 3. 3. 化简化简化简化简 (PQ)(PQ)(PQ)(PQ)( P(P(P(P( PQ)PQ)PQ)PQ) 解解解解 原公式原公式原公式原公式 (PQ)(PQ)(PQ)(PQ)( PPPP P)Q) (E11,P)Q) (E11,P)Q) (E11,P)Q) (E11,结合结合结合结合) ) ) ) (PQ)(PQ)(PQ)(PQ)( PQ) (PQ) (PQ) (PQ) (对合律，幂等律对合律，幂等律对合律，幂等律对合律，幂等律) ) ) ) (PQ)(Q(PQ)(Q(PQ)(Q(PQ)(Q P) (P) (P) (P) (交换律交换律交换律交换律) ) ) ) (PQ)Q)(PQ)Q)(PQ)Q)(PQ)Q) P (P (P (P (结合律结合律结合律结合律) ) ) ) QQQQ P (P (P (P (吸收律吸收律吸收律吸收律) ) ) )公式公式公式公式E11 E11 E11 E11 ： P P P PQ Q Q QPQ PQ PQ PQ &命命题公式的等价公式的等价36Example1证证明明p(qr)(pq)r证证p(qr)p( qr) 蕴蕴涵等涵等值值式，置式，置换规换规那么那么 ( pq)r 结结合律，置合律，置换规换规那么那么 (pq)r 德摩根律，置德摩根律，置换规换规那么那么 (pq)r 蕴蕴涵等涵等值值式，置式，置换规换规那么那么 阐明阐明: :也可以从右边开场演算也可以从右边开场演算( (操作一遍操作一遍) )因每一步都用置换规那么，故可不写因每一步都用置换规那么，故可不写熟练后，根本等值式也可以不写出熟练后，根本等值式也可以不写出 &证明两公式等明两公式等值37 Example2 Showthat(p (p q)andp qarelogicallyequivalent.Solution:De Morgan law德摩根律德摩根律De Morgan law德摩根律德摩根律The double negation law双非律双非律The distributive law分配分配律律The contradiction law矛盾矛盾律律The identity law恒等律恒等律38Example3Showthatisatautology.Solution:&命命题等价等价命题公式命题公式真值表真值表等价公式等价公式重言式和蕴含式重言式和蕴含式&重言式重言式命题公式命题公式真值表真值表等价公式等价公式重言式和蕴含式重言式和蕴含式Formula察看下面真值表：PQ (P Q) (P Q) P PFFFTFTFTTFFTTTFTv可可见不不论P P、Q Q取取值如何，如何， PP PP 的真的真值总为真，真， ( P Q) ( P Q) ( P Q) ( P Q)的真的真值总为假。故称假。故称 PPPP为重言式重言式( (永真式永真式) )；v 称称 ( P Q) ( P Q) ( P Q) ( P Q)为矛盾式矛盾式( (永永假式假式) )。&重言式重言式永真永真( (重言重言) )式式TautologyTautology公式中的命题变量元论怎公式中的命题变量元论怎样指派，公式对应的真值恒为样指派，公式对应的真值恒为T T。 永假矛盾式永假矛盾式Contradiction)Contradiction)公式中的命题变量公式中的命题变量无论怎样代入，公式对应的真值恒为无论怎样代入，公式对应的真值恒为F F。 可满足公式可满足公式SatisfactionSatisfaction公式中的命题变量无论公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为怎样代入，公式对应的真值总有一种情况为T T。普通命题公式普通命题公式ContingencyContingency既不是永真公式也不是既不是永真公式也不是永假公式。永假公式。&假假设干定干定义假假设A是永真式，那么是永真式，那么 A是永假式。是永假式。假假设A，B是永真式，那么是永真式，那么(AB)、(AB)、(AB)和和(AB)也都是永真式。也都是永真式。假假设A是永真式，那么是永真式，那么A的置的置换例式也是永真式。例式也是永真式。&重言式的根本性重言式的根本性质假设用公式X交换命题公式A中的某个变元, 交换后得到的新公式B称为A的置换例式。v公式公式A A：P(P( P(PP(PQ)Q)R) R) 用用(D(DE)E)交交换A A中中P P得到得到A A的置的置换例式例式 B B： (D(DE)(E)( (D(DE)(DE)(DE)E)Q)Q)R)R)v假假设A A是永真式，例如是永真式，例如A A为 PPPP，用，用 (D (DE)E)交交换A A中中P P，得到，得到A A的置的置换例式例式B B：v (D (DE)(DE)(DE) E) ，显然然B B也是永真式。也是永真式。v结论：假：假设可以断定可以断定给定公式是某个永真式的置定公式是某个永真式的置换例例式的式的话，那么，那么这个公式也是永真式。个公式也是永真式。&重言式的根本性重言式的根本性质定理：定理：设A、B为两个命题公式，AB当且仅当AB为重言式证明明假设假设A AB B，那么无论进展怎样的指派，那么无论进展怎样的指派，A A、B B的真值都一样，即的真值都一样，即A AB B为重言式。为重言式。假设假设A AB B为重言式，那么无论进展怎为重言式，那么无论进展怎样的指派，样的指派， A AB B的真值都为的真值都为T T，也就，也就是说是说A A和和B B的真值一样，即的真值一样，即A AB B。&A AB B与与A AB B的关系的关系 定定义：假：假设公式公式AB是重言式，那么称是重言式，那么称A重言重言(永真永真)蕴涵涵 B，记作作AB。例如：例如： (P(PQ)Q 可可记作作P(PQ)Q留意：留意：A AB B可以了解成由可以了解成由A A可推出可推出B B，即由，即由A A为真，为真，可以推出可以推出B B也为真。也为真。&重言永真重言永真蕴含式含式方法列真值表。略方法列真值表。略方法假设前件为真，推出后件也为真。方法假设前件为真，推出后件也为真。方法假设后件为假，推出前件也为假。方法假设后件为假，推出前件也为假。&蕴含式的含式的证明方法明方法例：求例：求证(AB)C) D( CD) A B证明明:设前件前件(AB)C) D( CD)为真。那么真。那么(AB)C)、 D、( CD)均真，均真，由此由此 可得可得 (AB) (AB) 为T T，即，即 AA B B为T T。 (AB)(AB)C)C) D(D( CD) CD) AA B B D D为为T T，那么，那么D D为为F F CDCD为T TC C为为F F (AB)C为TABAB为为F F&蕴含式的含式的证明方法明方法例：求例：求证(AB)C) D( CD) A B证明明:假假设后件后件 A B为F,那么那么A与与B均均为T。1.如如C为F，那么，那么(AB)C为F，所以前件，所以前件(AB)C) D( CD)为F2.如如C为T，那么，那么假假设D为T，那么，那么 D为F，所以，所以前件前件(AB)C) D( CD)为假假假假设D为F，那么，那么 CD为F，所以，所以前件前件(AB)C) D( CD)为假。假。(AB)C) D( CD) A B&蕴含式的含式的证明方法明方法I1.PQP,I2.PQQI3.PPQI4.QPQI5. PPQI6.QPQI7. (PQ)PI8. (PQ)QI9.P,QPQI10. P(PQ)QI11.P(PQ)QI12. Q(PQ)PI13.(PQ)(QR)PRI14.(PQ)(PR)(QR)RI15.AB(AC)(BC)I16.AB(AC)(BC)&重要的重要的蕴含式含式定理：定理：设P、Q为两个命题公式，PQ当且仅当PQ且QP证明明必要性：假设必要性：假设P PQ Q，那么对于任何指，那么对于任何指派，派，P P、Q Q都同真值，故都同真值，故P PQ Q为为T T， Q QP P为为T T，即，即P PQ Q，Q QP P充分性：假设充分性：假设P PQ Q，Q QP P，那么，那么P PQ Q为为T T ，Q QP P为为T T，所以，所以，P P Q Q为为T T，P P Q Q为重言式，即为重言式，即P PQ Q&等价式与等价式与蕴含式的关系含式的关系AB且且A为重言式，那么重言式，那么B必必为重言式重言式假假设AB且且BC，那么，那么AC(传送性送性)假假设AB且且AC，那么，那么A(BC)假假设AB且且CB，那么，那么(AC)B&蕴含式的性含式的性质