离散数学PPT课件19命题逻辑推理.ppt

1-7.命题逻辑推理推理就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为前提。得到的新的判断为前提的有效结论。实际上，推理的过程就是证明永真蕴含式的过程，即令H1，H2，Hn是已知的命题公式(前提)，若有 H1H2.Hn C 则称C是H1，H2，Hn的有效结论，简称结论。如何根据前提得到结论，需要有推理的如何根据前提得到结论，需要有推理的规则。下面先介绍两个规则。下面先介绍两个推理规则推理规则。规则规则P P(引入前提规则引入前提规则)：在推理过程中，：在推理过程中，可以随时引入前提。可以随时引入前提。规则规则T T(引入结论规则引入结论规则)：在推理过程中，：在推理过程中，如果前边有一个或几个公式永真蕴涵公如果前边有一个或几个公式永真蕴涵公式式S S，则可将，则可将S S纳入推理过程中。纳入推理过程中。在推理过程中，还要应用教材在推理过程中，还要应用教材2323永真蕴永真蕴涵式和涵式和9 9页中等价公式页中等价公式 (常用的公式要熟常用的公式要熟记记)下面主要介绍三种推理方法：下面主要介绍三种推理方法：直接推理、条件论证及反证法直接推理、条件论证及反证法重要的重言蕴涵式(如教材第43页所示)I1.PQP I2.PQQ I3.PPQ I4.QPQ I5.PPQ I6.QPQ I7.(PQ)P I8.(PQ)Q I9.P,Q PQ I10.P(PQ)Q I11.P(PQ)Q I12.Q(PQ)P I13.(PQ)(QR)PR I14.(PQ)(PR)(QR)R I15.AB(AC)(BC)I16.AB(AC)(BC)重要的等价公式重要的等价公式:对合律对合律 E1 PP交换律交换律 E2 PQQP E3 PQQP 结合律结合律 E4 P(QR)(PQ)R E5 P(QR)(PQ)R 分配律分配律 E6 P(QR)(PQ)(PR)E7 P(QR)(PQ)(PR)底底-摩根定律摩根定律 E8 (PQ)P Q E9 (PQ)P Q 幂等律幂等律 E10 PPP E11 PPP同一律同一律 E12 PFP E13 PTP 零律零律 E14 PTT E15 PFF E16 PQPQ E17 (PQ)P Q E18 PQQP E19 P(QR)(PQ)R E20 PQ(PQ)(QP)E21 PQ(PQ)(P Q)E22 (PQ)PQ吸收律吸收律 P(PQ)P P(PQ)P互补律互补律 P PT P PF PQ(PQ)(P Q)一一.直接推理直接推理直接推理直接推理，就是从前提直接推出结论。，就是从前提直接推出结论。上面讲到推理的过程实际上是证明永真上面讲到推理的过程实际上是证明永真蕴含式的过程。只不过证明的过程采用蕴含式的过程。只不过证明的过程采用另外一种书写格式另外一种书写格式。格式中包含格式中包含：步骤号，给定前提或得出：步骤号，给定前提或得出的结论，推理时所用规则，此结论是从的结论，推理时所用规则，此结论是从哪几步得到的以及所用公式。下面请看哪几步得到的以及所用公式。下面请看一些例子。一些例子。例题求证例题求证 PQPQ，QRQR，P P R R证明证明 序号序号 前提或结论前提或结论 所用规则所用规则 从哪几步得到从哪几步得到 所用公式所用公式 (1)P P(1)P P (2)P (2)PQ P Q P (3)Q T (1)(2)I (3)Q T (1)(2)I1111 (4)QR P (4)QR P (5)R T (3)(4)I (5)R T (3)(4)I1111（注公式注公式I I1111为：为：P,PQ P,PQ Q）例题求证例题求证(PQ)(QR)(PQ)(QR)R R P P(1)QR P(1)QR P(2)(2)R PR P(3)Q T (1)(2)I(3)Q T (1)(2)I1010(4)(4)(PQ)P(PQ)P(5)(5)PP Q T (4)EQ T (4)E8 8(6)(6)P T (3)(5)IP T (3)(5)I1010注公式注公式I I1010为：为：P,PQ P,PQ Q 公式公式E E8 8为：为：(PQ)(PQ)PP Q Q 例题用命题逻辑推理方法证明下面推例题用命题逻辑推理方法证明下面推理的有效性：理的有效性：如果我学习，那么我数学不会不及格。如果我学习，那么我数学不会不及格如果我不热衷于玩扑克，那么我将学习。如果我不热衷于玩扑克，那么我将学习。但是我数学不及格。因此，我热衷于玩但是我数学不及格。因此，我热衷于玩扑克。扑克。解设解设 P P：我学习。：我学习。Q Q：我数学及格。：我数学及格。R R：我热衷于玩扑克。：我热衷于玩扑克。于是符号化为：于是符号化为：PQPQ，RPRP，Q Q R RPQPQ，RPRP，Q Q R R(1)PQ P(1)PQ P(2)(2)Q P Q P(3)(3)P T(1)(2)IP T(1)(2)I1212 (4)(4)RP PRP P(5)(5)R T(3)(4)IR T(3)(4)I1212 (6)R T(5)E(6)R T5)E1 1 注：公式注：公式I I1212为：为：Q Q，PQ PQ P P 公式公式E E1 1 为：为：R RR 例题求证例题求证P(QS),P(QS),RP,Q RP,Q RS RS 证明证明(1)P(QS)P(1)P(QS)P (2)(2)P(P(QS)T(1)EQS)T(1)E1616 (3)(3)P(SP(S Q)T(2)EQ)T(2)E3 3 (4)(4)(PS)PS)Q T(3)EQ T(3)E5 5 (5)Q P (5)Q P (6)(6)PS T(4)(5)IPS T(4)(5)I1010 (7)PS T(6)E (7)PS T(6)E1616 (8)(8)RP PRP P (9)RP T(8)E (9)RP T(8)E1616 (10)RS T(7)(9)I (10)RS T(7)(9)I1313二二.条件论证条件论证定理定理1-7.11-7.1 如果如果H H1 1HH2 2.H.Hn nRR，则则 H H1 1HH2 2.H.Hn n RSRS证明证明 因为因为H H1 1HH2 2.H.Hn n 则则 (H(H1 1HH2 2.H.Hn nR)R)S S 是永真式是永真式根据结合律得根据结合律得 (H(H1 1HH2 2.H.Hn n)R)S)R)S 是永真式。是永真式。根据公式根据公式E E1919得得 (H(H1 1HH2 2.H.Hn n)(RS)(RS)是永真式。是永真式。即即 H H1 1HH2 2.H.Hn n RS RS 定理得证。定理得证。E E1919:P:P(QR)(QR)(PQ)R(PQ)R 此定理告诉我们，如果要证明的结论是此定理告诉我们，如果要证明的结论是蕴涵式蕴涵式(RS)(RS)形式，则可以把结论中蕴形式，则可以把结论中蕴涵式的前件涵式的前件R R作为附加前提，与给定的前作为附加前提，与给定的前提一起推出后件提一起推出后件S S即可。即可。我们把上述定理写成如下规则：我们把上述定理写成如下规则：规则规则CPCP(Conditional(Conditional roof)roof)：如果如果H H1 1HH2 2.H.Hn nR R S S，则，则 H H1 1HH2 2.H.Hn n RS RS 下面我们用条件论证方法求证例题下面我们用条件论证方法求证例题 P(QS),P(QS),RP,Q RP,Q RS RS例题例题 用条件论证，证明例题用条件论证，证明例题 P(QS),P(QS),RP,Q RP,Q RS RS证明证明 (1)R P(1)R P(附加前提附加前提)(2)(2)RP PRP P (3)P T (1)(2)I (3)P T (1)(2)I1010 (4)P(QS)P (4)P(QS)P (5)QS T (3)(4)I (5)QS T (3)(4)I1111 (6)Q P (6)Q P (7)S T (5)(6)I (7)S T (5)(6)I1111 (8)RS CP (8)RS CP与例题相比，因为它增加了一个附加前提，与例题相比，因为它增加了一个附加前提，所以推理就容易些。所以推理就容易些。例题例题 用命题逻辑推理方法证明下面推用命题逻辑推理方法证明下面推理的有效性：理的有效性：如果体育馆有球赛，青年大街交通就拥如果体育馆有球赛，青年大街交通就拥挤。在这种情况下，如果小王不提前出挤。在这种情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。发也未迟到，则体育馆没有球赛。证明证明 先将命题符号化。先将命题符号化。设设 P P：体育馆有球赛。：体育馆有球赛。Q Q：青年大街交通拥挤。：青年大街交通拥挤。R R：小王提前出发。：小王提前出发。S S：小王迟到。：小王迟到。PQPQ，(Q(Q R)S R)S(RR S)S)P P PQPQ，(Q(Q R)S R)S(RR S)S)P P证明证明(1)(1)RR S P(S P(附加前提附加前提)(2)(2)R T(1)IR T(1)I1 1(3)(3)S T(1)IS T(1)I2 2(4)(Q(4)(Q R)S PR)S P(5)(5)(Q(Q)T(3)(4)I)T(3)(4)I1212(6)(6)QR T(5)EQR T(5)E8 8(7)7)Q T(2)(6)IQ T(2)(6)I1010(8)PQ P(8)PQ P(9)(9)P T(7)(8)IP T(7)(8)I1212(10)(10)(RR S)S)P CPP CP三三.反证法反证法反证法的主要思想是：假设结论不成立，反证法的主要思想是：假设结论不成立，可以推出矛盾的结论可以推出矛盾的结论(矛盾式矛盾式)。下面先。下面先介绍有关概念和定理。介绍有关概念和定理。定义定义：设：设H H1 1，H H2 2，.，H Hn n是命题公式，是命题公式，P P1 1，P P2 2，.，P Pm m是公式中的命题变元，如是公式中的命题变元，如果对所有命题变元至少有一种指派，使果对所有命题变元至少有一种指派，使得得H H1 1HH2 2.H.Hn n 的真值为的真值为T T，则称公，则称公式集合式集合HH1 1,H,H2 2,H Hn n 是是相容的相容的(也称是也称是一一致的致的)；如果对所有命题变元每一种指派，；如果对所有命题变元每一种指派，都使得都使得H H1 1HH2 2.H.Hn n的真值为的真值为F F，则称，则称公式集合公式集合HH1 1,H,H2 2,H Hn n 是是不相容的不相容的(也称也称是是不一致的不一致的)。定理定理1-7.21-7.2 若要证明相容的公式集合若要证明相容的公式集合HH1 1,H,H2 2,.H,.Hn n 可以推出公式可以推出公式C C，只要证明，只要证明H H1 1HH2 2.H.Hn n C C是个矛盾式即可。是个矛盾式即可。证明证明 设设H H1 1HH2 2.H.Hn n C C 是矛盾式，则是矛盾式，则(H(H1 1HH2 2.H.Hn n C)C)是个永真式。是个永真式。上式上式 (H(H1 1HH2 2.H.Hn n)C)C (H(H1 1HH2 2.H.Hn n)C)C 所以所以 H H1 1HH2 2.H.Hn n C C实际上，要证明实际上，要证明H H1 1HH2 2.H.Hn n C C，只要，只要证明证明 H H1 1HH2 2.H.Hn n C C可推出矛盾式可推出矛盾式即可，即即可，即 H H1 1HH2 2.H.Hn n C C R R R R例例 PQ,(PQ,(QR)QR)R,R,(PS)PS)S S(1)(1)S P(S P(假设前提假设前提)(2)S T(1)E(2)S T(1)E1 1(3)(3)(PS)PPS)P(4)P(4)PS T(3)ES T(3)E8 8(5)P T(2)(4)I(5)P T(2)(4)I1010(6)PQ P(6)PQ P(7)Q T(5)(6)I(7)Q T(5)(6)I1111(8)(8)(QR)QR)R PR P(9)(9)QR T(8)IQR T(8)I1 1 (10)(10)R T(8)IR T(8)I2 2(11)R T(7)(9)I(11)R T(7)(9)I1010(12)R(12)RR T(10)(11)IR T(10)(11)I9 9本节要本节要掌握三种推理方法掌握三种推理方法，按照所要求，按照所要求格式正确地书写推理过程。格式正确地书写推理过程。作业作业第第35页：页：1.16 ,1.17