交大数理逻辑课件2-2 命题逻辑的等值和推理演算.ppt

《交大数理逻辑课件2-2 命题逻辑的等值和推理演算.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件2-2 命题逻辑的等值和推理演算.ppt（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第2章 命题逻辑的等值和推理演算 2.1 等值定理2.2 等值公式2.3 命题公式与真值表的关系2.4 联结词的完备集2.5 对偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 归结推理法讨论讨论等值演算等值演算讨论讨论推理演算推理演算2.4 联结词的完备集n定义 n在一个联结词的集合中，如果一个联结词可由集合中的在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为其他联结词定义，则称此联结词为冗余的联结词冗余的联结词，否则，否则称为称为独立的联结词独立的联结词。n如：如：P Q=P Q P Q=(P Q)(P Q)n在在，中中、是冗余的

2、。是冗余的。n在，中，P Q=（P Q）n所以所以 是冗余的。是冗余的。n在在，中无冗余的联结词。中无冗余的联结词。n同理，同理，在在，中无冗余的联结词。中无冗余的联结词。联结词的完备集n定义 n设设C是联结词的集合，若对任一命题公式都由是联结词的集合，若对任一命题公式都由C中的联中的联结词表示出来的公式与之等值，就说结词表示出来的公式与之等值，就说C是是完备的联结词集合。n显然，全体联结词的无限集合是完备的。显然，全体联结词的无限集合是完备的。n，n，n ，n，等也是完备的。是完备的是完备的2.5 对偶式n定义定义n在在仅仅含含联联结结词词，的的命命题题公公式式A中中，将将联联结结词词，F，

3、T分分别别换换成成，T，F所得的公式称为公式所得的公式称为公式A的的对偶式对偶式，记为，记为A*n 如：如：P Q与与P Q 是对偶式是对偶式n(P Q)R与与(P Q)R是对偶式是对偶式n推广n在仅含有联结词在仅含有联结词，的命题公式的命题公式中，将联结词中，将联结词，F，T分别换成分别换成，T，F，就得到了它的对偶式。，就得到了它的对偶式。与对偶式有关的定理n设设A和和A*互为对偶式，互为对偶式，P1,P2,Pn是出现在是出现在A和和A*中的全部命题变项，中的全部命题变项，令 A=A(P1,P2,Pn),A=A(P1,P2,Pn)n定理定理2.5.1：(A*)=(A)*,(A)=(A)n如

4、：A=P(Q R)n则：则：A*=P (Q R)，A=P (Q R)A=P (Q R)n所以：(A)*=P (Q R)(A*)=P (Q R)n所以：(A)=P (Q R)(A)=P (Q R)(A*)=(A)*(A)=(A)与对偶式有关的定理n定理2.5.2：(A*)*=A,(A)=An定理2.5.3：A=A*n如：A=P(Q R)n则则：A=P (Q R)A*=P (Q R)所以：A*=P (Q R)=A此定理为摩根律：此定理为摩根律：(A B)=AB(A B)=AB的另一种形式的另一种形式，与对偶式有关的定理n定理2.5.4 若A=B，必有A*=B*n证：A=B AB 永真 AB 永真

5、A*B*永真 A*B*永真 A*=B*n定理2.5.5 若AB永真，必有B*A*永真（作业）n定理2.5.6 A与A同永真，同可满足 A与A*同永真，同可满足n对偶性是逻辑规律，给证明公式的等值和求否定带来方便依定理依定理2.5.3有，有，A=A*，B=B*2.6 范 式n简单析取式 n它是仅由有限个命题变项或其否定构成的析取式。它是仅由有限个命题变项或其否定构成的析取式。n如如:P，Q，P，Q，P Q，P Q，P Q n 它是它是重言式重言式当且仅当它同时含一个命题变项及其否定；当且仅当它同时含一个命题变项及其否定；n如：如：P Q P 是重言式是重言式n简单合取式n它是仅由有限个命题变项或

6、其否定构成的合取式。它是仅由有限个命题变项或其否定构成的合取式。n如如:P，Q，P，Q，P Q，P Qn 它是它是矛盾式矛盾式当且仅当它同时含一个命题变项及其否定。当且仅当它同时含一个命题变项及其否定。n如：如：P P Q 是矛盾式是矛盾式 析取范式n析取范式n由有限个简单合取式组成的析取式由有限个简单合取式组成的析取式 A1 A2 .An（n 1，Ai 都是都是简单合取式简单合取式）n如：如：(P Q R)(P Q)Qn一个析取范式是一个析取范式是矛盾式矛盾式，当且仅当其每个简单合取式，当且仅当其每个简单合取式都是都是矛盾式矛盾式n合取范式n由有限个简单析取式组成的合取式由有限个简单析取式组

7、成的合取式A1 A2 .An（n 1,Ai都都是是简单析取式简单析取式）n如：如：(P Q R)(P Q)Qn一一个个合合取取范范式式是是重重言言式式，当当且且仅仅当当其其每每个个简简单单析析取取式式都是都是重言式重言式n范式范式析取范式与合取范式的总称析取范式与合取范式的总称命题公式的范式 n范式存在定理n任何命题公式都存在着与之等值的析取范式与合取范式任何命题公式都存在着与之等值的析取范式与合取范式n求公式A的范式的步骤：(1)消去消去A中的中的,（若存在）（若存在）A B=A B AB=(AB)(A B)(求析取范式求析取范式时时)=(A B)(AB)(求合取范式求合取范式时时)(2)否

8、定联结词否定联结词 的内移或消去（摩根定律）的内移或消去（摩根定律）(3)使用分配律使用分配律 对对 分配（析取范式）分配（析取范式）对对 分配（合取范式）分配（合取范式）n注意：n公式的范式存在，但公式的范式存在，但不惟一不惟一，这是它的局限性，这是它的局限性 求公式的范式举例 例:求下列公式的析取范式与合取范式(1)A=(PQ)R解解 (PQ)R =(PQ)R （消去消去）=PQR （结合律）结合律）这这既既是是A的的析析取取范范式式（由由3个个简简单单合合取取式式组组成成的的析析取取式）式）又是又是A的的合取范式合取范式（由一个简单析取式组成的合取式）（由一个简单析取式组成的合取式）求公

9、式的范式举例(2)B=(PQ)R解解 (PQ)R =(PQ)R （消去第一个（消去第一个）=(PQ)R （消去第二个（消去第二个）=(P Q)R （否定号内移否定号内移摩根律）摩根律）这已为这已为析取范式析取范式（两个简单合取式构成）（两个简单合取式构成）继续：继续：(P Q)R =(P R)(Q R)（对对 分配律）分配律）这一步得到这一步得到合取范式合取范式（由两个简单析取式构成（由两个简单析取式构成）极小项n定义 n n个命题变项的个命题变项的简单合取式简单合取式，其中每个命题变项与其否，其中每个命题变项与其否定不同时出现，定不同时出现，而二者之一必出现且仅出现一次而二者之一必出现且仅出

10、现一次，这样，这样的简单合取式称为的简单合取式称为极小项极小项。n如：两个命题变元如：两个命题变元P和和Q，其极小项为：，其极小项为：P Q，P Q，P Q，P Qn说明nn个命题变项产生个命题变项产生2n个极小项，它们互不等值个极小项，它们互不等值n用用mi表表示示第第i个个极极小小项项，每每个个小小项项的的n个个变变元元排排序序相相同同。（按下标或字典顺序），分别记为（按下标或字典顺序），分别记为n其中其中i是该极小项是该极小项成真赋值成真赋值的十进制表示的十进制表示.m11 m10 m01 m00 极小项n由由P,Q,R三个命题变项形成的极小项三个命题变项形成的极小项极小项极小项成真赋值

11、成真赋值名称名称PQR000m0PQR001m1PQR010m2PQR011m3PQR100m4PQR101m5PQR110m6PQR111m7主析取范式n主析取范式n设命题公式设命题公式A中含中含n个命题变项，如果个命题变项，如果A的析取的析取范式中的简单合取式全是范式中的简单合取式全是极小项极小项，则称该析取，则称该析取范式为范式为A的的主析取范式主析取范式n如：如：n=3,命题变项为命题变项为P,Q,R 时，主析取范式时，主析取范式：(PQ R)(P Q R)=m1 m3 n定理定理n任任何何命命题题公公式式都都存存在在与与之之等等值值的的主主析析取取范范式式,并并且且是是惟惟一的一的.

12、n求主析取范式的方法求主析取范式的方法n等值演算法和真值表法等值演算法和真值表法用等价演算法求主析取范式的步骤1.求求A的析取范式的析取范式A；2.若若A 的某简单合取式的某简单合取式B中不含某命题变项或其否中不含某命题变项或其否 定，则将定，则将B展成如下形式：展成如下形式：B=B 1 =B (Pi Pi)=(B Pi)(B Bi)3.将重复出现的命题变项、矛盾式及重复出现的极将重复出现的命题变项、矛盾式及重复出现的极小项都小项都“消去消去”。4.将极小项按由小到大的顺序排列，并用将极小项按由小到大的顺序排列，并用 表示之，表示之，如如 m1 m2 m6 用用 (1,2,6)表示表示。求公式

13、 A=(PQ)R 的主析取范式解法1：(PQ)R =(P Q)R,=(P Q)R （析取范式）析取范式）(P Q)=(P Q)(R R)=(P QR)(P Q R)=m6 m7 R =(P P)(Q Q)R =(PQ R)(P Q R)(PQ R)(P Q R)=m1 m3 m5 m7 ,代入代入并合并相同式，得主析取范式：并合并相同式，得主析取范式：(PQ)R =m1 m3 m5 m6 m7=(1,3,5,6,7)解法2：(PQ)R =(P Q)R,=(P Q)R （析取范式）（析取范式）=m11x mxx1 =(m110 m111)(m001 m011 m101 m111)=(1,3,5,

14、6,7)求公式 A=(PQ)R 的主析取范式主析取范式的用途(1)求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值n如前面例子中得到如前面例子中得到 (PQ)R=m1 m3 m5 m6 m7n其成真赋值为：其成真赋值为：001,011,101,110,111n则其余的赋值为成假赋值则其余的赋值为成假赋值000,010,100 主析取范式的用途(2)判断公式的类型判断公式的类型设设A含含n个命题变项，则个命题变项，则nA为重言式A的主析取范式含的主析取范式含2n个极小项个极小项n如命题变项为P,Q 时，nA=(0,1,2,3)nA为矛盾式A的主析取范式为的主析取范式为0n如A=0 nA为可满

15、足式nA的主析取范式中至少含一个极小项n如A=(2,3)(PQ)Q =(P Q)Q =P Q Q =F （矛盾式矛盾式）用主析取范式判断公式的类型如前面例子中得到 (PQ)R =m1 m3 m5 m6 m7=(1,3,5,6,7)(可满足式）(PQ)P)Q =(P Q)P)Q =(P Q)P Q =m10 m0 x mx1 =m10 m00 m01 m01 m11 =m0 m1 m2 m3 =(0,1,2,3)=T （重言式重言式）用主析取范式判断公式的类型主析取范式的用途(3)判断两个公式是否等值判断两个公式是否等值如如 PQ =P Q =m0 x mx1 =m00 m01 m01 m11

16、=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)定理定理 任何命题公式都存任何命题公式都存在与之等值的主析取范在与之等值的主析取范式式,并且是惟一的并且是惟一的.主析取范式的应用(4)举例例例：甲甲、乙乙、丙丙、丁丁四四人人参参加加考考试试，有有人人问问他他们们，谁谁的成绩最好，的成绩最好，甲说：甲说：“不是我不是我”乙说：乙说：“是丁是丁”丙说：丙说：“是乙是乙”丁说：丁说：“不是我不是我”四四人人的的回回答答只只有有一一人人符符合合实实际际，问问是是谁谁的的成成绩绩最最好好，

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

18、成绩最好，的成绩最好，甲说：甲说：“不是我不是我”乙说：乙说：“是丁是丁”丙说：丙说：“是乙是乙”丁说：丁说：“不是我不是我”四四人人的的回回答答只只有有一一人人符符合合实实际际，问问是是谁谁的的成成绩绩最最好好，若若只只有有一一人人成成绩绩最最好好，他他是谁？是谁？主析取范式的应用举例 (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)主析取范式的应用举例 求求中所得公式的主析取范式中所得公式的主析取范式 (A D B D)(A D

19、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个命题变项的简单析取式，其中每个命题变项与其否个命题变项的简单析取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样定不同时出现，而二者之一必出现且仅出现一次，这样的简单析取式称为极大项。的

20、简单析取式称为极大项。n如：两个命题变元如：两个命题变元P和和Q，其极大项为：，其极大项为：P Q，P Q，P Q，P Qn说明nn个命题变项产生个命题变项产生2n个极大项，它们互不等值个极大项，它们互不等值n用用Mi表表示示第第i个个极极大大项项，每每个个小小项项的的n个个变变元元排排序序相相同同。（按下标或字典顺序），分别记为（按下标或字典顺序），分别记为n其中其中i是该极大项是该极大项成假赋值成假赋值的十进制表示的补的十进制表示的补.（正变项：（正变项：0，变元的否定：，变元的否定：1）M11 M10 M01 M00 由P,Q,R三个命题变项形成的极小项与极大项 极小项极小项 极大项极大

21、项 公式公式 成真成真赋值赋值名称名称 公式公式 成假成假赋值赋值名称名称 P Q R P Q R P Q R P Q R PQ RP Q RP Q RP Q R0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7 P Q R P Q R P Q R P Q R P Q R P Q R P Q RP Q R 1 1 11 1 01 0 11 0 00 0 10 1 00 0 10 0 0M0M1M2M3M4M5M6M7 主合取范式n主合取范式n由极大项构成的合取范式由极大项构成的合取范式n如如n=3,命题变项为命题变项为P,Q,R时，

22、主合取范式时，主合取范式:(P QR)(P QR)=M6 M2n定理定理n任任何何命命题题公公式式都都存存在在与与之之等等值值的的主主合合取取范范式式,并并且且是是惟惟一的一的.n求主合取范式的方法求主合取范式的方法n等值演算法和真值表法等值演算法和真值表法1.求求A的合取范式的合取范式A；2.若若A 的某简单析取式的某简单析取式B中不含某命题变项或其否定，中不含某命题变项或其否定，则将则将B展成如下形式：展成如下形式：B =B 0 =B (Pi Pi)=(B Pi)(B Pi)3.将重复出现的命题变项、重言式及重复出现的极大项将重复出现的命题变项、重言式及重复出现的极大项都都“消去消去”。4

23、.将极大项按由小到大的顺序排列，并用将极大项按由小到大的顺序排列，并用 表示之，表示之，如如 M1 M2 M6 用用 (1,2,6)表示。表示。用等价演算法求主合取范式的步骤求公式(PQ)R 的主合取范式解解1:：(PQ)R =(P Q)R =(P Q)R =(P Q)(Q R)P R=(P R)(Q Q)=(P R Q)(P Q R)=M111 M101 Q R=(Q R)(P P)=(P Q R)(P Q R)=M111 M011 ,代入代入并排序，得主合取范式：并排序，得主合取范式：=M3 M5 M7=(3,5,7)解解2:(PQ)R =(P Q)R =(P Q)R =(P R)(Q R

24、)(合取合取范式范式)=M1x1 Mx11 =M101 M111 M011 M111 =M3 M5 M7=(3,5,7)求公式(PQ)R 的主合取范式 =(P Q)R （析取范式）（析取范式）=m11x mxx1 =(m110 m111)(m001 m011 m101 m111)=(1,3,5,6,7)u 主主析析取取范范式式与与主主合合取取范式的转换范式的转换 (1,3,5,6,7)=(07)-(1,3,5,6,7)补补=(0,2,4)补补=(3,5,7)作业3P37:4(1)P37:5(3)(8)补充题：（主析取范式的应用）某勘探队有某勘探队有3名队员，有一天取得一块矿样，名队员，有一天取得一块矿样，3人人的判断如下：的判断如下：甲说：这不是铁，也不是铜；甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；乙说：这不是铁，是锡；丙说：这不是锡，是铁。丙说：这不是锡，是铁。经实验室鉴定后发现，经实验室鉴定后发现，其中其中一个人两个判断都正一个人两个判断都正确，一个人判对一半，另一个人全错了确，一个人判对一半，另一个人全错了。根据以上根据以上情况判断矿样种类。情况判断矿样种类。