第编数理逻辑课件.ppt

1、1第 3 编 数 理 逻 辑第 6 章 命 题 逻 辑26.1 6.1 命题的概念与表示命题的概念与表示命题命题 日常语言不确切，具有二义性需引入目标语言、公式符号。目标语言：表达判断的一些语言的汇集。判断：肯定、否定的思维形式。命题：能表达判断，具有确定真值的陈述句。3 真值：命题的判断结果称为真值。只有“真”和“假”两种，记为“T”和“F”，或“1”和“0”。没有判断无所谓是非的句子感叹句、疑问句、祈使句不是命题。原子命题：不能分为更简单的陈述句。复合命题：由联结词、标点符号和原子命题复合构成的命题。用大写字母A,B,.,P,Q,.或Ai,12等表示命题。例 P:今天下雨。12:今天刮风。

2、命题标识符：表示命题的符号。4例：语句是否命题真值中国人民是伟大的。中国人民是伟大的。雪是黑的。雪是黑的。1+1=10别的星球上有生物。别的星球上有生物。全体立正！全体立正！明天是否开会？明天是否开会？天气多好啊！天气多好啊！我正在说谎。我正在说谎。我学英语，或者我学日语。我学英语，或者我学日语。如果天气好，那么我去散步。如果天气好，那么我去散步。10?(悖论)?5 命题常量：一个命题标识符表示确定的命题。命题变量：一个命题标识符仅表示任意命题的位置标志(无真值)。原子变元：命题变元表示原子命题。66.2 命题联结词命题联结词 复合命题原子命题+联结词1)否定否定定义定义 设P为命题，P的否定

3、是一个新的命题，记为P。若P为T，则P为F；若P为F，则P为T。PP1001例：P：上海是大城市。P：上海不是大城市。或上海是不大的城市。一元联结词。72)合取合取(并且并且)定义定义 两个命题P、Q的合取是一个复合命题，记作PQ。当且仅当P、Q同为T时，PQ为T；在其它情况下，PQ的真值为F。PQPQ000010100111例:P:今天下雨.Q:明天下雨.PQ:今天下雨且明天下雨。今天明天都下雨。这两天都下雨。二元联结词。8 与自然语言不同。P：我们去看电影。Q：房间里有十张桌子。PQ：我们去看电影且房间里有十张桌子。仍是新命题。可将若干个命题联结一起。P：高中毕业。Q：上分数线。R：被某大

4、学录取。PQR：大学生。93)析取析取(或者或者)定义定义 两个命题P、Q的析取是一个复合命题，记作PQ。当且仅当P、Q同为F时，PQ为F；在其它情况下，PQ的真值为T。PQPQ000011101111例:P:今天下雨.Q:今天刮风.PQ:今天下雨或者刮风。二元联结词。10 日常语言中的“或者”可分“可兼或”与“不可兼或”两种：例例1：今天晚上我在家看电视或去剧院看戏。(不可兼或)例例2：他可能是100米或400米赛跑的冠军。(可兼或)析取是可兼或。例例3：P:他中了大奖。Q:他中了小奖。PQ:他中了大奖或者中了小奖。(也可能两奖都中)114)不可兼析取不可兼析取 (排斥析取排斥析取)定义定义

5、 设设P、Q是两个命题，复合命题P Q称为P、Q的不可兼析取。P Q的真值为T当且仅当P与Q的真值不相同；否则，P Q的真值为F。PQP Q000011101110例:P:他坐船去大连。Q:他乘车去大连。P Q:他坐船或乘车去大连。二元联结词。P Q (PQ)(PQ)125)蕴含蕴含(条件条件)定义定义 两个命题P、Q的蕴含是一个复合命题，记作PQ。当且仅当P的真值为T，Q的真值为F时，PQ的真值为F；在其它情况下，PQ的真值为T。PQPQ001011100111例1:“如果某动物为哺乳动物，则它必胎生”。将命题符号化。设P:某动物为哺乳动物。Q:某动物胎生。命题符号化：PQ。且命题为真：PQ

6、 1。二元联结词。13例例2:“如果我得到这本小说，那么我今天就读完它”。将命题符号化，并求命题的真值。解解 设P:我得到这本小说.Q:我今天就读完它.命题符号化：PQ。且命题的真值有以下四种实际情况：(1)我得到这本小说，我今天读完它。(T)(2)我得到这本小说，我今天没有读完。(F)(3)我没有得到这本小说，我今天读完它。(T)(4)我没有得到这本小说，我今天没有读完。(T)14例例3:“如果雪是黑的，那么太阳从西方出”。将命题符号化，并求命题的真值。解解 设P:雪是黑的。Q:太阳从西方出。命题符号化：PQ。且命题的真值：PQ 1.例例4:“如果雪是黑的，那么太阳从东方出”。将命题符号化，

7、并求命题的真值。解解 设P:雪是黑的。Q:太阳从东方出。命题符号化：PQ。且命题的真值：PQ 1.15 PQ中P称为前件，Q称为后件。自然语言中，若前提为假，无论结论为真或假，往往无法判断。PQPQ001011100111 在条件命题中，当前提为假时，结论都为真 称“善意的推定”。PQ“如果P那么Q”“只要P则Q”“从P推出Q”“P仅当Q”“只有Q才P”“P蕴含Q”166)等价等价(双条件双条件)定义定义 给定两个命题P和Q，复合命题PQ称为双条件命题。当P、Q的真值相同时，PQ的真值为T；在其它情况下，PQ的真值为F。PQPQ001010100111例1:“两个三角形全等当且仅当对应边相等”

8、。设P:两个三角形全等。Q:三角形对应边相等。命题符号化：PQ。且命题为真：PQ 1。二元联结词。17例例2:“燕子飞回南方，春天来了”。将命题符号化，并求命题的真值。解解:设P:燕子飞回南方。Q:春天来了。命题符号化：PQ。且命题的真值：PQ 1.例例3:“2+2=4 当且仅当雪是白的”。将命题符号化，并求命题的真值。解解 设P:2+2=4。Q:雪是白的。命题符号化：PQ。且命题的真值：PQ 1.18 复合命题：设 A1,A2,An是命题,用五种逻辑联结词将这n个命题联结起来，得到一个新命题，称为复合命题。19练习练习1.设命题P，Q的真值为1，命题R，S的真值为0，试确定下面命题的真值：(

9、PQR)(PQ)(RS);解：(PQR)(PQ)(RS)(110)(11)(00)(10)(10)00 01 1 206.3 命题公式的翻译与解释命题公式的翻译与解释 用大写英文字母代表一个抽象命题,而不代表一个具体命题,这个抽象命题称为命题符号.原子：命题符号称为原子.定义 合式公式是如下定义的一个符号串(1)原子是合式公式；(2)若G,H是合式公式，则如下符号串(G),(GH),(GH),(GH),(GH),(G H)是合式公式；(3)所有公式都是有限次使用(1)(2)得到的符号串。21 命题公式：由命题变项、联结词、括号按一定规则组成的合式公式为命题公式。例：如下符号串 (P (Q R)

10、(Q (S)R)就是公式。五种逻辑联结词的优先级按如下次序递减 ,故上例可写成:P(QR)Q(SR)对公式中的每个原子赋值后，公式就有一个真值。对原子一组赋值称公式的一个解释。22定义定义 设G是公式，A1,A2,An 是出现在G中的所有原子,指定 A1,A2,.An 一组真值,则这组真值称为G的一组赋值(解释、指派）,记作I。例：G PQR.G的真值记为 TI(G)1.010:RQPI 一般地G是具有n个不同原子的公式,则G有2n 个不同的赋值。对一个公式G,将它在所有赋值下所取的真值列成一个表,称为G的真值表。6.4 真值表与等价公式真值表与等价公式23PQR000001010011100

11、101110111例例:求G P (Q R)的真值表。PQRRQ RP(Q R)000110001000010110011010100111101000110111111011成真赋值成假赋值PQRRQ R0001100100010110110110011101001101111101PQRR0001001001010110100110101101111024 有时赋值 0,0,0 写成 P,Q,R,0,0,1 写成 P,Q,R,0,1,0 写成 P,Q,R,1,1,1 写成 P,Q,R,25定义定义：如果公式G,H在任一组赋值 I 下真值相同，则称公式G,H等值，记作 G H。“”不是联结词

12、，它表示两个公式的关系。逻辑等价26P Q1101可见在所有赋值 I 下真值相同，PQ PQ.例例：用真值表证明公式 PQ 和 PQ等值.证：由真值表：PQ00011011P1100PQ110127例例：证明 P Q (PQ)(PQ)。P Q P Q P Q PQ PQ(PQ)(PQ)0 01100000 11010111 00111011 1000000证证：由真值表可见在所有赋值 I 下真值相同，P Q (PQ)(PQ)。28 共学了六个联结词：,全功能联结词组：任一命题公式都可用组中的联结词表示，这样的联结词组称全功能联结词组。如,.由于PQ (PQ)(QP),也是全功能联结词组。由于P

13、 Q (PQ)(PQ),也是全功能联结词组。由于PQ PQ,也是全功能联结词组。29 并非所有联结词都是必要的，公式中有些联结词可由其它联结词代替。最小联结词组：任一命题公式可由这些联结词表示，但不能再少一个。如 ,。因为 PQ (PQ)如 ,。因为 PQ (PQ)30常用的逻辑等价式 A B (A B)(B A)(等价式)A B A B (蕴含式)A A A，A A A (幂等律)A B B A，A B B A (交换律)A (B C)(A B)C A (B C)(A B)C (结合律)A (A B)A，A (A B)A (吸收律)A (B C)(A B)(A C)A (B C)(A B)(

14、A C)(分配律)A 0 A，A 1 A (同一律)A 0 0，A 1 1 (零律)A A 1，A A 0 (否定律)(A B)A B,(A B)A B(德摩根律)31 A A (双重否定律)A B B A (假言易位)A B A B (等价否定式)(A B)(A B)A (归谬律)A B (A B)(A B)(异或等值式)32 以上公式的证明有两种方法：(1)真值表；(2)利用公式。例例：证明吸收律A (A B)A。证证一：ABA BA (A B)0000010010011111A (A B)A。33证证二：A (A B)(A 1)(A B)A (1 B)A 1 A A (A B)A。34代

15、换规则 在等值式中某命题变项用新的命题公式取代，得到新的等值式。如由 A A A 可产生 (P Q)(P Q)(P Q)等等。等值演算：从某公式A推导出新公式B，且使 A B。由基本等值式可以产生无数个不同等值式。35 重言式、永真式：G在所有的赋值下都是真的。矛盾式、永假式：G在所有的赋值下都是假的。可满足式：除矛盾式以外的公式。仅可满足式：除重言式和矛盾式以外的公式。6.5 重言式与蕴含式重言式与蕴含式36例：G P PQ 1PQ P G0011011110011101 G 是重言式。PQ P PQK00110011101000011011 K P(PQ)K是可满足式。(仅可满足式)H P

16、 PQ 0 H 是矛盾式。PQ P H001001101000110037重言蕴含式的三种等价定义重言蕴含式的三种等价定义定义定义1：设G,H是两个公式，如果对任意赋值I，都有TI(G)TI(H)，则称G重言蕴含H，记作G H.定义定义2：设G,H是两个公式，对任意赋值I，如果G为真，必有H为真，则称G重言蕴含H，记作G H.定义定义3：设G,H是两个公式，如果(GH)是恒真公式，则称G重言蕴含H，记作G H.例例1:证P PG.证1:PGPG000011101111由定义1得证.证2:若P 1,则PG 1G 1由定义2得证.证3:P(PG)P(PG)PPG 1G 1由定义3得证.38(1)证

17、明两个公式等值，化简公式；(2)判别公式的类型；(3)解决实际问题。等值式的推演能够解三类问题：39例例1 证明(1)(PQ)(PQ)P (2)P(QR)(PQ)R 证证:(1)(PQ)(PQ)P(QQ)P1 P(PQ)(PQ)P(2)P(QR)P(QR)PQR (PQ)R (PQ)R P(QR)(PQ)R 40例例2 化简(AB)(BA)C.解解：BA BA AB AB。(AB)(BA)C(AB)(AB)C 1C(由等价的定义：当P、Q的真值相同时，PQ的真值为 1)C.41例例3 判别下列公式的类型:(1)Q(PQ)P).解解：Q(PQ)P)Q(PQ)P)PQ(PQ)1.公式Q(PQ)P)

18、为重言式。42(2)(PP)(QQ)R).解解：(PP)(QQ)R)1(0R)10 0.公式(PP)(QQ)R)为矛盾式。(3)(PQ)P.解解：(PQ)P (PQ)P P当P1,公式 0；当P0,公式 1。公式(PQ)P是可满足式。43对偶式 对偶式:在一个不含联结词和的公式里,将换成,换成,1 换成0,0换成1,得一新公式,称为原公式的对偶式.将一个等值式的等号两端换成其对偶式,得到一新等值式,称为原等值式的对偶式.对偶性质:如果一个等值式是成立的,其对偶等值式也成立.6.6 范式范式44 公式的形式千变万化：G G (G H)G G G 1等等，是否有标准形式？定义定义：有限个命题变项或

19、其否定构成的析取式称为简单析取式。有限个命题变项或其否定构成的合取式称为简单合取式。如：PQ；ABC.定义定义：有限个简单合取式构成的析取式称为析取范式。有限个简单析取式构成的合取式称为合取范式。如：P(PQ)(PQR)；Q(PQ)(PQR).45 析取范式的对偶式称为合取范式；合取范式的对偶式称为析取范式。如：(PQ)(PQR)；对偶式为(PQ)(PQR).PQR 既是析取范式，又是合取范式。PQR 既是析取范式，又是合取范式。P 既是析取范式，又是合取范式。46定理定理(范式存在定理)：对于任意公式，都存在等值于它的析取范式和合取范式。证证：对任意公式G，通过如下算法可得出等值于G的范式：

20、(1)将,化为,；(2)将 移到原子前；(3)反复使用分配律,即可得到等值于G的范式。例例1:将G(P(QR)S 化为析取范式和合取范式.解：G (P(QR)S (P(QR)S (P(Q R)S P(QR)S (PS)(QR)(PSQ)(PSR)析取范式合取范式47例例2：将P(QR)化为析取范式和合取范式。解解：P(QR)(合取范式)(PQ)(PR)(析取范式)析取范式和合取范式不唯一。如：P P 1 P(QQ)(PQ)(PQ).P P 0 P(QQ)(PQ)(PQ).(第二式由对偶关系得到)主析取范式和主合取范式唯一。48定义定义：n个命题变项P1,P2,Pn,每个变项与它的否定不同时出现

21、，但是两者必须出现一个,且排列顺序与 P1,P2,Pn的顺序一致,这样的简单合取式称为关于P1,P2,Pn 的一个极小项或布尔合取。含n个命题变项的公式G共有2n个极小项，且与公式G的2n个赋值对应。49例例：公式G中包含P,Q,R三个命题变项：极小项成真赋值记法PQR0 0 0m0PQ R0 0 1m1P QR0 1 0m2P Q R0 1 1m3 PQR1 0 0m4 PQ R1 0 1m5 P QR1 1 0m6 P Q R1 1 1m750定义定义：对于含有n个命题变项的命题公式，如果有一个仅由极小项的析取构成的等值式,则该等值式称为原命题公式的主析取范式。定理定理：任何命题公式都存在

22、与之等值的主析取范式，并且是唯一的。求主析取范式的方法求主析取范式的方法:1.真值表法 在一个命题公式的真值表中，真值为1的赋值所对应的极小项的析取，即为此命题公式的主析取范式。51例3 用真值表法求 PQ,PQ,(PQ)的主析取范式。解：PQPQP Q(P Q)00101011011000111110PQ (PQ)(PQ)(PQ)m0m1m3(0,1,3)P Q (PQ)m3 (3)(P Q)(PQ)(PQ)(PQ)m0m1m2 (0,1,2)522.等值演算法：(1)求命题公式的析取范式；(2)“消去”命题公式中所有矛盾式的析取项(如 P P)，合并相同项；(3)若析取范式的某个合取项缺少

23、命题变项Pj或Pj，则添加(Pj Pj)，再用分配律展开；(4)将极小项按由小到大的次序排列，用表示之。53例例：求公式G (RP)(Q (P R)的主析取范式。解解：G (RP)(Q (P R)(RP)(Q (P R)(R P)(Q P)(Q R)(R P)(Q Q)(QP)(R R)(Q R)(P P)(RPQ)(RPQ)(QPR)(QPR)(QRP)(QRP)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)54(PQR)(PQR)(PQR)(PQR)m3 m1 m7 m6 m1 m3 m6 m7 (1,3,6,7).对任意公式G,存在唯一一个与G等值的主析取范式。恒假公式的主

24、析取范式用 0 表示。55 主合取范式定义定义：n个命题变项P1,P2,Pn,每个变项与它的否定不同时出现，但是两者必须出现一个,且排列顺序与 P1,P2,Pn的顺序一致,这样的简单析取式称为关于P1,P2,Pn 的一个极大项或布尔析取。极小项的对偶称为极大项。含n个原子的公式G共有2n个极大项，且与公式G的2n个赋值对应。56例例：公式G中包含P,Q,R三个命题变项：极大项成假赋值记法 P Q R0 0 0M0 P QR0 0 1M1 PQ R0 1 0M2 PQR0 1 1M3P Q R1 0 0M4P QR1 0 1M5PQ R1 1 0M6PQR1 1 1M757定义定义：对于含有n个

25、命题变项的命题公式，如果有一个仅由极大项的合取构成的等值式,则该等值式称为原命题公式的主合取范式。定理定理：任何命题公式都存在与之等值的主合取范式，并且是唯一的。58例5 用真值表法求(R(PQ)(P(Q R)的主合取范式。解：P Q RR(PQ)P(Q R)(R(PQ)(P(Q R)0 0 01110 0 10100 1 01110 1 11111 0 01001 0 11111 1 01001 1 110059 M1M4M6M7 (1,4,6,7)(R(PQ)(P(Q R)(PQR)(PQR)(PQR)(PQR)60等值演算法：(1)求命题公式的合取范式；(2)“消去”命题公式中所有永真的

26、合取项(如 P P)，合并相同项；(3)若合取范式的某个析取项缺少命题变项Pj或Pj，则添加(Pj Pj)，再用分配律展开；(4)将极大项按由小到大的次序排列，用表示之。61主合取范式的求法与主析取范式的求法类似。例例：求公式G (PQ)P 的主合取范式。解：G (PQ)P(PQ)P(PQ)P(P P)(Q P)P (Q P)P(Q Q)(Q P)(PQ)(P Q)(P Q)(PQ)(P Q)M0 M1 (0,1).62主析取范式、主合取范式和真值表之间的关系：主析取范式主合取范式真值表 知道三者之一能直接求出另外两个。63例例:G (RP)(Q (P R),求G的主析取范式，主合取范式和真值

27、表。P Q RG0 0 000 0 110 1 000 1 111 0 001 0 101 1 011 1 11解解：前已求出G的主析取范式G (PQR)(PQR)(PQR)(PQR)m1 m3 m6 m7 (1,3,6,7)(0,2,4,5)M0M2M4M5 (PQR)(PQR)(PQR)(PQR)(主合取范式)(真值表).64 同一赋值对应的极小项和极大项不相同。如公式G中包含P,Q二个原子。P Q极小项极大项0 0PQ P Q0 1P Q PQ1 0 PQP Q1 1 P QPQ 主析取范式 极小项 成真赋值 主合取范式 极大项 成假赋值65 主范式的用途：(1)判断(证明)两个公式等值

28、；(2)判断公式的类型：解题可考虑三种方法：等值公式；主范式；真值表。(3)解决实际问题；(4)求公式的成真赋值和成假赋值。含2n个极小项(1)永真式含0个极小项(0)永假式至少含1个极小项 可满足666.7 命题逻辑的推理理论命题逻辑的推理理论推理推理：从给定的前提推出一个结论。也称为演绎、形式证明、蕴含。定义定义：设A1,A2,.,Am,C为命题公式，如果(A1,A2,.,Am)C 为重言式，则称C为前提A1,A2,.,Am的有效结论，或称由A1,A2,.,Am逻辑地推出C.记作A1A2.Am C 上式为重言蕴含式。67 判断推理的五种方法：真值表法等值演算法主析取范式法直接证法间接证法1

29、.真值表法如果A1A2.Am=1,C也为1，则有A1A2.Am C68例例1：C是否是前提A1和A2的有效结论。(1)A1:PQA2:PC:Q (2)A1:PQA2:PC:Q (3)A1:PQA2:QC:P PQPPQ0011011110001101解：构造真值表(1)当A1和A2都为1时，C为1，PQ,P Q.(2)当A1和A2都为1时，C有值为0，Q不是PQ和P 的有效结论.(2)当A1和A2都为1时，C有值为0，P不是PQ和Q 的有效结论.692 等值演算法例2:证例1中各题(1)A1:PQ A2:P C:Q 解：(1)(PQ)P)Q(PQ)P)Q(PQ)P)Q(PQ)PQ(PPQ)(Q

30、PQ)11 1所以 PQ,P Q.70(2)(PQ)P)Q(2)A1:PQ A2:P C:Q (PQ)P)Q(PQ)P)Q PQ不是重言式，所以Q 不是 PQ 和 P 的有效结论。713 主析取范式法例3:证例1中各题(1)A1:PQ A2:P C:Q 解：(1)(PQ)P)Q(PQ)P)Q (PQ)P)Q(PQ)PQ(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)m0m1m2m3 (0,1,2,3)所以 PQ,P Q.72(2)(PQ)P)Q(2)A1:PQ A2:P C:Q (PQ)P)Q(PQ)P)Q PQ M0 (0)(1,2,3)不是重言式，所以Q 不是 PQ

31、 和 P 的有效结论。734 直接证法直接证法(形式演绎形式演绎)A1，A2，.，An B (从前提推演出结论)形式演绎规则:规则P:在推导的过程中引入已知前提公式;规则T:在演绎过程中可以利用前面演绎出来的中间结果推出新的命题公式。演绎过程中需要用到等值式和重言蕴含式。74重言蕴含式(14个)I1 A B A I2 A B B (化简)I3 A A B I4 B A B (附加)I5 A (A B)I6 B (A B)I7 (A B)A I8 (A B)BI9 A,B A B (合取引入)I10 A,A B B (析取三段论)I11 A,A B B (假言推论)I12 B,A B A (拒取

32、式)I13 A B,B C A C (假言三段论)I14 A B,A C,B C C (构造性二难)I5和I7、I6和I8互为逆否命题。I1 A B A I2 A B B (化简)I3 A A B I4 B A B (附加)I5 A (A B)I6 B (A B)I7 (A B)A I8 (A B)BI9 A,B A B (合取引入)I10 A,A B B (析取三段论)I11 A,A B B (假言推论)I12 B,A B A (拒取式)I13 A B,B C A C (假言三段论)I14 A B,A C,B C C (构造性二难)I5和I7、I6和I8互为逆否命题。75例例4:证明CD,(

33、CD)H,H(AB),(AB)(RS)RS.证证:(1)CD P (2)(CD)H P (3)H T(1)(2)(4)H(AB)P (5)AB T(3)(4)(6)(AB)(RS)P (7)RS T(5)(6)CD,(CD)H,H(AB),(AB)(RS)RS.76例例5:证明AB,AC,DE,DC,E B 证证:(1)E P (2)DE P (3)D T(1)(2)(4)DC P (5)C T(3)(4)(6)ACP (7)A T(5)(6)(8)ABP (9)B T(7)(8)AB,AC,DE,DC,E B 77例例6:证明 P Q,PR,QS SR.证证:(1)P Q P (2)PQ T

34、(1)(3)QS P (4)PS T(2)(3)(5)SP T(4)(6)PR P (7)SR T(5)(6)(8)SR T(7)P Q,PR,QS SR 78例例6:证明 P Q,PR,QS SR.证二证二:(1)Q S P (2)S Q T(1)(3)P Q P (4)Q P T(3)(5)S P T(2)(4)(6)P R P (7)S R T(5)(6)(8)SR T(7)P Q,PR,QS SR 795 间接证法 有时要证明的结论以蕴含式的形式出现：A1，A2，.，An B C由于 A1A2.An(B C)(A1A2.An B)C 这说明可把B作为附加前提加入到前提中，这种方法称为附

35、加前提证法，简称CP规则。规则CP:如果需要演绎出的公式具有B C 的形式,则可以将B 做为附加前提使用,而力图演绎出C即可。80例例7:证明 P (Q S),R P,Q R S.证证:(1)R P(附加)(2)R P P (3)P T(1)(2)(4)P(QS)P (5)QS T(3)(4)(6)Q P (7)S T(5)(6)(8)RS CP(1)(7)P (Q S),R P,Q R S.81例例7:证明 P (Q S),R P,Q R S.证二证二:(1)Q P (2)P(QS)P (3)P Q S T(2)(4)P S T(1)(3)(5)P S T(4)(6)R P P (7)R P

36、 T(6)(8)R S T(5)(7)P (Q S),R P,Q R S.82例例6:证明 P Q,PR,QS SR.证三证三:等价于证 P Q,PR,QS SR.(1)S P(附加)(2)Q S P (3)S Q T(2)(4)Q T(1)(3)(5)P Q P (6)P T(4)(5)(7)P R P (8)R T(6)(7)(9)SR CP(1)(8)P Q,PR,QS SR 83 反证法反证法(归谬法归谬法)例例8:证明 RQ,RS,SQ,PQ P.证证:反证法(1)P P(附加)(2)PQ P (3)QT(1)(2)(4)RQ P (5)R T(3)(4)(6)RS P (7)S T(5)(6)(8)SQ P (9)Q T(7)(8)(3)(9)矛盾(P Q),Q R,R P.84例例9:证明(P Q),Q R,R P.证证:反证法。(1)P P(附加)(2)(P Q)P (3)P Q T(2)(4)Q T(1)(3)(5)Q R P (6)R T(4)(5)(7)R P (6)与(7)矛盾，(P Q),Q R,R P.