数理逻辑与集合论：2-3 命题逻辑的等值和推理演算

1、第2章 命题逻辑的等值和推理演算 2.1 等值定理2.2 等值公式2.3 命题公式与真值表的关系2.4 联结词的完备集2.5 对偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 归结推理法讨论讨论等值演算等值演算讨论讨论推理演算推理演算主析取范式的用途如如 PQ = P Q = m0 x mx1 = m00 m01 m01 m11 = m0 m1 m3 = (0,1,3) P (P Q) = m0 x m11 = m00 m01 m11 = m0 m1 m3 = (0,1,3)所以所以 PQ = P (P Q)定理定理 任何命题公式都存任何命题公式都存在与之等值的

2、主析取范在与之等值的主析取范式式, , 并且是惟一的并且是惟一的. .(1)(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值(2)(2)判断公式的类型判断公式的类型(3)(3)判断判断两个公式是否等值两个公式是否等值主析取范式的应用(4)举例例：甲、乙、丙、丁四人参例：甲、乙、丙、丁四人参加考试，有人问他们，谁加考试，有人问他们，谁的成绩最好，的成绩最好， 甲说：甲说：“不是我不是我” 乙说：乙说：“是丁是丁” 丙说：丙说：“是乙是乙” 丁说：丁说：“不是我不是我” 四人的回答只有一人符合四人的回答只有一人符合实际，实际，问是谁的成绩最好，问是谁的成绩最好，若只有一人成绩最好，他若只

3、有一人成绩最好，他是谁？是谁？解此类问题的步骤为：解此类问题的步骤为： 将简单命题符号化将简单命题符号化 写出各复合命题写出各复合命题 写出由中复合命题组写出由中复合命题组成的合取式成的合取式 求中所得公式的主析求中所得公式的主析取范式取范式主析取范式的应用举例解解 设设A：甲的成绩最好：甲的成绩最好 B：乙的成绩最好，：乙的成绩最好， C：丙的成绩最好：丙的成绩最好 D：丁的成绩最好，：丁的成绩最好， (1) ( A D B D) (2) ( A D B D) (3) ( A D B D) (4) ( A D B D)例：甲、乙、丙、丁四人参例：甲、乙、丙、丁四人参加考试，有人问他们，谁加考

4、试，有人问他们，谁的成绩最好，的成绩最好， 甲说：甲说：“不是我不是我” 乙说：乙说：“是丁是丁” 丙说：丙说：“是乙是乙” 丁说：丁说：“不是我不是我” 四人的回答只有一人符合四人的回答只有一人符合实际实际，问是谁的成绩最好，问是谁的成绩最好，若只有一人成绩最好，他若只有一人成绩最好，他是谁？是谁？主析取范式的应用举例 (1) ( A D B D) (2) ( A D B D) (3) ( A D B D) (4) ( A D B D) (1) (4)构成的析取式为构成的析取式为 ( A D B D) (A D B D) ( A D B D) (A D B D)主析取范式的应用举例 求求中所

5、得公式的主析取范式中所得公式的主析取范式 ( A D B D) (A D B D) ( A D B D) (A D B D)= (A D B D) (A D B D) = (A B D) (A B D)= m10 x1 m10 x0= m1001 m1011 m1000 m1010 所以，只有一人成所以，只有一人成绩最好的是绩最好的是甲。甲。甲、丁并列甲、丁并列成绩最好成绩最好甲、丙、丁并列甲、丙、丁并列成绩最好成绩最好甲、丙并列甲、丙并列成绩最好成绩最好极大项n 定义 n n个命题变项的个命题变项的简单析取式简单析取式，其中每个命题变项与其否，其中每个命题变项与其否定不同时出现，而二者之一必

6、出现且仅出现一次，这样定不同时出现，而二者之一必出现且仅出现一次，这样的的简单析取式简单析取式称为称为极大项极大项。n如：两个命题变元如：两个命题变元P和和Q，其极大项为：，其极大项为： P Q， P Q ， P Q ， P Qn 说明nn个命题变项产生个命题变项产生2n个极大项，它们互不等值个极大项，它们互不等值,n用用Mi表示第表示第i个极大项，每个小项的个极大项，每个小项的n个变元排序相同。个变元排序相同。（按下标或字典顺序），分别记为（按下标或字典顺序），分别记为n其中其中: 正变元：正变元：1，变元的否定：，变元的否定：0 M11 M10 M01 M00 1210, nMMM 由P,

7、 Q, R三个命题变项形成的极小项与极大项 极小项极小项 极大项极大项 公式公式 名称名称 公式公式 名称名称 P Q R P Q R P Q R P Q R P Q RP Q RP Q RP Q Rm0m1m2m3m4m5m6m7 P Q R P Q R P Q R P Q R P Q R P Q R P Q RP Q R M0M1M2M3M4M5M6M7 主合取范式n主合取范式n由极大项构成的合取范式由极大项构成的合取范式n如如n=3, 命题变项为命题变项为P, Q, R时，主合取范式时，主合取范式: (P QR) ( P QR) = M6 M2 n定理定理n任何命题公式都存在与之等值的主

8、合取范式任何命题公式都存在与之等值的主合取范式, 并且是惟并且是惟一的一的. . n求主合取范式的方法求主合取范式的方法n等值演算法和真值表法（按等值演算法和真值表法（按F列出）列出）1. 求求A的合取范式的合取范式A ； 2. 若若A 的某简单析取式的某简单析取式B中不含某命题变项或其否定中不含某命题变项或其否定，则将，则将B展成如下形式：展成如下形式： B = B F = B (Pi Pi ) = (B Pi) (B Pi)3. 将重复出现的命题变项、重言式及重复出现的极大项将重复出现的命题变项、重言式及重复出现的极大项都都“消去消去”。 4. 将极大项按由小到大的顺序排列，并用将极大项按

9、由小到大的顺序排列，并用 表示之，表示之，如如 M1 M2 M6 用用 (1,2,6) 表示。表示。用等值演算法求主合取范式的步骤求公式(PQ)R 的主合取范式解解1: ： (PQ)R = ( P Q) R = (P Q) R = (P R) (Q R) （合取范式）（合取范式） P R = (P R) (Q Q ) = (P Q R) ( P Q R) = M111 M101 = M7 M5 Q R =(Q R) (P P ) = (P Q R) ( P Q R) = M111 M011 = M7 M3 , 代入并排序，得主合取范式：代入并排序，得主合取范式： (PQ)R = M3 M5 M

10、7 = (3,5,7)解解2: (PQ)R = (P R) (Q R) (合取合取范式范式) = M1x1 Mx11 = M101 M111 M011 M111 = M3 M5 M7 = (3,5,7)求公式(PQ)R 的主合取范式 （析取范式）（析取范式） (PQ)R= (P Q) R = (1,3,5,6,7)u 主析取范式主析取范式与与主合取范式主合取范式的转换的转换 (1,3,5,6,7) = (0,1,2,3,4,5,6,7) (1,3,5,6,7)补补 = (0,2,4)补补= (7- 0,7- 2,7- 4) = (7,5,3)用真值表法求公式(PQ)R 的主析取、主合取范式 P

11、 Q R PQ (PQ)R F F FF F TF T FF T TT F FT F TT T F T T T TTTTTTF FFTFTFTTT (PQ)R = m1 m3 m5 m6 m7= (1,3,5,6,7) (PQ)R = M3 M5 M7 = (3,5,7)2.7 推理形式n 推理引例: (1) 正项级数收敛当且仅当部分和有上界正项级数收敛当且仅当部分和有上界. (2) 若若A C B D，则，则A B且且C D.n 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。n 推理从前提出发，应用推理规则推出结论的从前提出发，应用推理规则推出结论的思维过程思维过程n上面上面(1)是正确

12、的推理，而是正确的推理，而(2)是错误的推理是错误的推理. n 推理的组成n前提前提推理所根据的已知命题推理所根据的已知命题n结论结论从前提出发通过推理而得到的新命题从前提出发通过推理而得到的新命题n 证明 描述推理正确或错误的过程描述推理正确或错误的过程. . 推理形式n 例：如果我有时间，我就去上街；如果我有时间，我就去上街； 如果我上街，我就去书店买书；如果我上街，我就去书店买书； 但我没有去书店买书，但我没有去书店买书， 所以我没有时间。所以我没有时间。n 解：令 P：我有时间。 Q：我去上街。 R：我去书店买书。 根据题意，前提为：PQ，QR，R 结论为：P 推理的形式为： (PQ)

13、(QR)R P 反映了一类推理关系反映了一类推理关系重言蕴涵n 定义定义n 若若 (A1 A2 Ak ) B为为重言式重言式， 则称则称由由 A1, A2, , Ak推出结论推出结论B的的推理正确（有推理正确（有效结论）效结论） , 否则否则推理不正确（错误）推理不正确（错误）.n “A1, A2, , Ak 推出B” 的推理正确 当且仅当 A1 A2 AkB为重言式.n 推理的形式结构推理的形式结构: A1 A2 AkB 或或 前提：前提： A1, A2, , Ak 结论：结论： B n 若推理正确，则记作：若推理正确，则记作：A1 A2 Ak B例：判断下面推理是否正确?（1）若天气凉快，

14、小王就不去游泳。天气凉快，所以小王没去游泳。解题方法将命题符号化将命题符号化写出前提、结论和推理的形式结构写出前提、结论和推理的形式结构进行判断进行判断解： 设 P：天气凉快，Q：小王去游泳. 前提： P Q，P 结论： Q 推理的形式结构为： (PQ) P) Q 判断上式是否为重言式 。例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断 (PQ) P) Q 是否为重言式 方法1：真值表法PQP Q(P Q) P(P Q) P) QFFTFTFTTFTTFTTTTTFFT( (PQ)P) ) Q例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天

15、气凉快，所以小王没去游泳。判断 (PQ) P) Q 是否为重言式 方法2：等值演算法 (PQ) P) Q = ( PQ) P)Q = = (P Q) P Q = = (P Q) (P Q) = = T( (PQ)P) ) Q例：判断下面推理是否正确（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。判断 (PQ) P) Q是否为重言式 方法3：主析取范式法 (PQ) P) Q = ( PQ) P)Q = (P Q) P Q = m11 m0 x mx0 = m11 m00 m01 m00 m10 = (0,1,2,3) = T例：判断下面推理是否正确?（2）若我上街，我一定去书店。我

16、没上街，所以我没去书店。解： 设 P：我上街，Q：我去书店。 前提： PQ， P 结论： Q 推理的形式结构为： (PQ)P) Q 判断上式是否为重言式 (PQ) P) Q = ( P Q) P) Q = (P Q) P Q = m10 m1x mx0 = m10 m10 m11 m00 m10 = (0,2,3)不是重言式！不是重言式！所以推理不正确所以推理不正确重言蕴涵的几个结果n如果如果A B，A为重言式，则为重言式，则B也是重言式也是重言式n如果如果A B， B A同时成立，必有同时成立，必有A=Bn反之反之，如果，如果A=B，必有，必有A B，B An如果如果A B， B C，则，则

17、A Cn如果如果A B， A C，则，则A B Cn如果如果A C， B C，则，则A B C2.8 基本的推理公式n判断推理是否正确的方法n真值表法、等值演算法、主析取范式法真值表法、等值演算法、主析取范式法n推理演算法推理演算法一个描述推理过程的命题公式一个描述推理过程的命题公式序列序列n其中的每个命题公式是已知的其中的每个命题公式是已知的前提前提、或是由某些前、或是由某些前提依据提依据等值公式等值公式或或蕴涵关系式蕴涵关系式、应用、应用推理规则推理规则得到得到的结论的结论 n说明：说明：n当命题变项比较少时，用上面当命题变项比较少时，用上面3 3种方法比较方便种方法比较方便, , 此时此

18、时采用采用形式结构形式结构“A1 A2 AkB” . n而在推理演算时，而在推理演算时，采用下面形式：采用下面形式： 前提前提: A1, A2, , Ak 结论结论: B基本的推理公式1. P Q P 化简律化简律2. 2. (PQ) P3. 3. (PQ) Q4. P P Q 附加律附加律 5. 5. P PQ6. Q PQ7. P (P Q) Q 析取三段论析取三段论8. P (P Q) Q 假言推理假言推理9. 9. Q (PQ) P 拒取式拒取式10.(PQ) (QR) PR 假言三段论假言三段论基本的推理公式11.(PQ) (QR) P R 等价三段论等价三段论12. (PR) (Q

19、R) ( (P Q) R 13. 13. (PQ) (RS) (P R) Q S 构造性二难构造性二难14. (PQ) (RS) ( QS) ( PR) 破坏性二难破坏性二难15. (QR) (P Q) (P R) 16. (QR) (PQ) (PR) 证明推理公式的方法n定理2.8.1 AB成立的充分必要条件是成立的充分必要条件是 AB 是重言式。是重言式。n定理2.8.2 AB成立的充分必要条件是成立的充分必要条件是 A B 是矛盾式是矛盾式。n(AB)=( ( A B)= A B n说明：n可用可用AB是重言式是重言式或或A B 是矛盾式是矛盾式来来证明推理公式证明推理公式AB2.9 推

20、理演算推理规则 (1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 代入规则代入规则(4) 置换规则置换规则(5)假言推理假言推理(分离规则分离规则) PQ P Q(6) 附加规则附加规则 P P Q (7) 化简规则化简规则 P Q P (8) 拒取式规则拒取式规则 PQ Q P(9) 假言三段论规则假言三段论规则 PQ QR PR 推理规则(续) (12) 破坏性二难推理规则破坏性二难推理规则 PQ RS QS PR(13) 合取引入规则合取引入规则 P Q P Q (10) 析取三段论规则析取三段论规则 P Q Q P (11)构造性二难推理规则构造性二难推理规则 P

21、Q RS P R Q S使用推理规则的推理演算举例例1：证明：前提：前提：P Q, Q R, P 结论：结论：R 证： P 前提引入前提引入 P Q 前提引入前提引入 Q 分离（假言推理）分离（假言推理） Q R 前提引入前提引入 R 分离（假言推理）分离（假言推理） 推理演算直接证明法例2 证明：前提：前提： P Q， P R, Q S 结论：结论：S R证明：证明： P Q 前提引入前提引入 P Q 置换置换 Q S 前提引入前提引入 P S 假言三段论假言三段论 S P 置换置换 P R 前提引入前提引入 S R 假言三段论假言三段论 S R 置换置换( (PQ)()(RS)()(P R) ) Q S 构造性二难构造性二难 在大城市球赛中，在大城市球赛