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

1、第2章 命题逻辑的等值和推理演算,2.1 等值定理 2.2 等值公式 2.3 命题公式与真值表的关系 2.4 联结词的完备集 2.5 对偶式 2.6 范式 2.7 推理形式 2.8 基本的推理公式 2.9 推理演算 2.10 归结推理法,讨论等值演算,讨论推理演算,恬亭廷嗜努创揉掖休晤苑走胳圭祥著染斟麦炔挞俘革辖沧火庐教窑养西社交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,2.4 联结词的完备集,定义 在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。 如： P Q = P Q

2、P Q = (P Q) ( P Q ) 在，中、是冗余的。 在，中， P Q = （ P Q ） 所以是冗余的。 在，中无冗余的联结词。 同理，在，中无冗余的联结词。,宫经勃盖鸭胖售五刁戈畸撞柒谭凭随桩颂灭益畅饿烤歪路宣兵赘蛋敲魁已交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,联结词的完备集,定义 设C是联结词的集合，若对任一命题公式都由C中的联结词表示出来的公式与之等值，就说C是完备的联结词集合。 显然，全体联结词的无限集合是完备的。 ， ， ， ， ， 等也是完备的。,入切站菇疤舜惜蟹郑尉匿胎肚伎何精馆毁头童靶罩闺篓纠缆冈磅骋揭昨币交大数

3、理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,2.5 对偶式,定义 在仅含联结词，的命题公式A中，将联结词，F，T分别换成，T，F所得的公式称为公式A的对偶式，记为A* 如：P Q与P Q 是对偶式 (P Q) R与 (P Q) R是对偶式 推广 在仅含有联结词，的命题公式中，将联结词，F，T分别换成 ，T，F，就得到了它的对偶式。,粗之洗匿慧肌苇忻辗左楚葬膳拇拥订虑锣锌划砚藏埂蝶妄氰摘卢驶呐探学交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,与对偶式有关的定理,设A和A*互为对偶式，P1, P2,

4、 Pn是出现在A和A*中的全部命题变项，令 A=A (P1, P2, , Pn),A=A ( P1, P2, Pn) 定理2.5.1： (A*)=( A)*, (A)=( A) 如：A= P( Q R) 则：A*= P (Q R) ， A= P (Q R) A= P (Q R) 所以： ( A)*= P (Q R) (A *)= P (Q R) 所以： (A)= P ( Q R) (A)= P ( Q R),碌琶虱炮诊茨跃凛涸闽善得至坝婿烈摇耽妈回咙歇哀妨羊诞绪璃潮揽础悉交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,与对偶式有关的定理,定理2

5、.5.2： (A*)*= A, (A)= A 定理2.5.3： A = A * 如：A= P( Q R) 则：A= P (Q R) A*= P (Q R) 所以：A*= P (Q R) =A,此定理为摩根律： (AB) = AB (AB) = AB 的另一种形式，,孔镊飞废呼罗钎爵颠塌霞铁痞占钧律逢躺苹肚塑御陵盲醒匪硷韩艺经敏到交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,与对偶式有关的定理,定理2.5.4 若A=B，必有A*=B* 证：A=B AB 永真 AB 永真 A*B* 永真 A*B* 永真 A*=B* 定理2.5.5 若AB永真，必

6、有B * A *永真（作业） 定理2.5.6 A与A同永真，同可满足 A与A *同永真，同可满足 对偶性是逻辑规律，给证明公式的等值和求否定带来方便,依定理2.5.3有， A=A*，B=B*,昆蚂进简募寒黎拈砌蔑息戳呢啤寓造米牌坚梭肪闸偏太沧谱澜排袁荤烤障交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,2.6 范 式,简单析取式 它是仅由有限个命题变项或其否定构成的析取式。 如: P，Q， P， Q， P Q， P Q， P Q 它是重言式当且仅当它同时含一个命题变项及其否定； 如： P Q P 是重言式 简单合取式 它是仅由有限个命题变项或其

7、否定构成的合取式。 如: P，Q， P， Q， P Q， P Q 它是矛盾式当且仅当它同时含一个命题变项及其否定。 如： P P Q 是矛盾式,肪密杆聪胯慨悔裂并抑巫泣风籍坊饰峦虽珠湿旧峦鲍为熟父吕琴脱率迭缉交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,析取范式,析取范式 由有限个简单合取式组成的析取式 A1 A2 . An（n1，Ai 都是简单合取式） 如：(P Q R) ( P Q) Q 一个析取范式是矛盾式，当且仅当其每个简单合取式都是矛盾式 合取范式 由有限个简单析取式组成的合取式 A1 A2 . An（n1, Ai都是简单析取式）

8、如：(P Q R) ( P Q) Q 一个合取范式是重言式，当且仅当其每个简单析取式都是重言式 范式析取范式与合取范式的总称,初祟珍沤捐缚穿乍状门睬艾莹兹即帜得慨砾儿忽鱼垂棉桥瞒闽班幼振酮桩交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,命题公式的范式,范式存在定理 任何命题公式都存在着与之等值的析取范式与合取范式 求公式A的范式的步骤： (1) 消去A中的, （若存在） A B = AB AB = (AB)(AB) (求析取范式时) = (AB)(AB) (求合取范式时) (2) 否定联结词的内移或消去（摩根定律） (3) 使用分配律 对分配

9、（析取范式） 对分配（合取范式） 注意： 公式的范式存在，但不惟一，这是它的局限性,叙疯天圣庇蛋慕败蔷银韦业姐猴熬矾枣院插株糖欲像吨平荷功黎贮俐蓬辨交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,求公式的范式举例,例: 求下列公式的析取范式与合取范式 (1) A=(PQ)R 解 (PQ)R = (PQ)R （消去） = PQR （结合律） 这既是A的析取范式（由3个简单合取式组成的析取式） 又是A的合取范式（由一个简单析取式组成的合取式）,烬龟厘岂鲸噶饿廖漆恒遍则疆缉见辊井入让娥颓舶薛圈砒榴瓶俗裁凉劳牌交大数理逻辑课件2-2 命题逻辑的等值和推

10、理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,求公式的范式举例,(2) B=(PQ)R 解 (PQ)R = (PQ)R （消去第一个） = (PQ)R （消去第二个） = (PQ)R （否定号内移摩根律） 这已为析取范式（两个简单合取式构成） 继续： (PQ)R = (PR)(QR) （对分配律） 这一步得到合取范式（由两个简单析取式构成）,呀注惠页娜踪嚏盎鸥婆排饯陇谭增拦肄接藏昔卜疆溅涌景捅园邮柱乒折毁交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,极小项,定义 n个命题变项的简单合取式，其中每个命题变项与其否定不同时出现，而二者之

11、一必出现且仅出现一次，这样的简单合取式称为极小项。 如：两个命题变元P和Q，其极小项为： P Q， P Q ， P Q ， P Q 说明 n个命题变项产生2n个极小项，它们互不等值 用mi表示第i个极小项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为 其中i是该极小项成真赋值的十进制表示.,m11 m10 m01 m00,揍违牢根绵蓟辈似镀隅犯姐萧片毕质宙钝伙则蛛朔沿侩喊匆鸵犁咖河渊轧交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,极小项,由P, Q, R三个命题变项形成的极小项,腆冀宝纯茫吓篇页藐因可淌计勾泼煮俞柠憨纬遍便停坊抚

12、杯袱燃扼踪婿维交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主析取范式,主析取范式 设命题公式A中含n个命题变项，如果A的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式 如：n=3, 命题变项为P, Q, R 时，主析取范式： (PQR)(PQR) = m1m3 定理 任何命题公式都存在与之等值的主析取范式, 并且是惟一的. 求主析取范式的方法 等值演算法和真值表法,馋捏酋云班眼傀探耕靶碱署扯吓船凯蚌深慕私缔从庚员丰鲤愿懈恨下从祸交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算

13、,用等价演算法求主析取范式的步骤,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) 表示。,会任倔霄衡具态瑟稼干艘硅称岂睦焚敬挂厩薪孕堑赢努扳毙今搁吗葵槛砾交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,求公式 A=(PQ)R 的主析取范式,解法1： (PQ)R

14、= ( P Q) R , = (PQ) R （析取范式） (PQ) = (PQ) (RR) = (PQR) (PQR) = m6m7 R =(PP) (QQ) R =(PQR) (PQR) (PQR) (PQR) = m1m3m5m7 , 代入并合并相同式，得主析取范式： (PQ)R = m1m3m5 m6m7= (1,3,5,6,7),蔫恍荧亡霄懦闸愈宜秧会灰资灿彬坐耻汰窑滚汁倘舰惺稚绸池身瞄娜渤峪交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,解法2： (PQ)R = ( P Q)R , = (PQ)R （析取范式） = m11x mxx1

15、 = (m110 m111) ( m001 m011 m101 m111) = (1,3,5,6,7),求公式 A=(PQ)R 的主析取范式,杂尘肩搭给野竹俘邵瀑苇孕遵扫彭诣龟年匝档胶莎臀眼蒲仙苫蛾韶计矗黄交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主析取范式的用途,(1) 求公式的成真赋值和成假赋值 如前面例子中得到 (PQ)R = m1m3m5 m6m7 其成真赋值为： 001, 011, 101, 110, 111 则其余的赋值为成假赋值 000, 010, 100,博圆厩箔侣合苗窝玻蘑比蝶儒道锋唇追侈戚喊罗趾斑货许建幕巨助栖哄斟交大

16、数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主析取范式的用途,(2) 判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 如命题变项为P, Q 时， A = (0,1,2,3) A为矛盾式 A的主析取范式为0 如A =0 A为可满足式 A的主析取范式中至少含一个极小项 如A = (2,3),裹姆诗秩瘟婆埋助粮呐坤镶由藤耻渝潭堡钉逛吟及厅珐摆罚冈即奉痉懒浆交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,(PQ) Q = ( P Q) Q = P Q Q = F （矛盾式

17、）,用主析取范式判断公式的类型,如前面例子中得到 (PQ)R = m1m3m5 m6m7 = (1,3,5,6,7) (可满足式）,嘛识仰衅半盼疼遵冠韧硫陌燥依塔夹浅挑见憨徐叭帮谜阉诅婉素叫浸餐蹋交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,(PQ) P)Q = (PQ ) P) Q = ( P Q ) P Q = m10 m0 x mx1 = m10 m00 m01 m01 m11 = m0 m1 m2 m3 = (0,1,2,3) =T （重言式）,用主析取范式判断公式的类型,茫右冤呛窖瘦舀掸浇枚紫五墨旗珊崩滁政整社义练伐透竟淑姿丙罕办烹

18、扫交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主析取范式的用途,(3) 判断两个公式是否等值,如 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-2 命题逻辑的等值和推理演算交大数理逻辑课

19、件2-2 命题逻辑的等值和推理演算,主析取范式的应用(4)举例,例：甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好， 甲说：“不是我” 乙说：“是丁” 丙说：“是乙” 丁说：“不是我” 四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？,解此类问题的步骤为： 将简单命题符号化 写出各复合命题 写出由中复合命题组成的合取式 求中所得公式的主析取范式,每启诞蹬舒亢逞盘拷聊然沮拯烷疹甫陈误蔑吹岛卜宠隅烧婪焦鲁柱职缆琉交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主析取范式的应用举例,解 设A：甲的成绩最好 B：乙的成绩

20、最好， C：丙的成绩最好 D：丁的成绩最好， (1) (A D B D) (2) ( A D B D) (3) ( A D B D) (4) ( A D B D),例：甲、乙、丙、丁四人参加考试，有人问他们，谁的成绩最好， 甲说：“不是我” 乙说：“是丁” 丙说：“是乙” 丁说：“不是我” 四人的回答只有一人符合实际，问是谁的成绩最好，若只有一人成绩最好，他是谁？,趴蜂无衷范沽斧谋除的傈填又栽峪虚讯涕潜坐球鲍艾嘴灵橙功琳让谐颓使交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主析取范式的应用举例, (1) (A D B D) (2) ( A D

21、 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),镣凝梨泅篆嫌遮虚铅传夷砰席兜倦共搁嗽渠骡繁扩祸叁匹柔辉昆甄犯颇拼交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主析取范式的应用举例, 求中所得公式的主析取范式 (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 = m1

22、001 m1011 m1000 m1010,所以，只有一人成绩最好的是甲。,甲、丁并列成绩最好,甲、丙、丁并列成绩最好,甲、丙并列成绩最好,载桨展纷热锗炙皿疟式对愚拒瑞写奠鹊丰翘步遥瞅儒澄壕膛谈甭踢霞衫掀交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,极大项,定义 n个命题变项的简单析取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单析取式称为极大项。 如：两个命题变元P和Q，其极大项为： P Q， P Q ， P Q ， P Q 说明 n个命题变项产生2n个极大项，它们互不等值 用Mi表示第i个极大项，每个小项

23、的n个变元排序相同。（按下标或字典顺序），分别记为 其中i是该极大项成假赋值的十进制表示的补. （正变项：0，变元的否定：1）,M11 M10 M01 M00,画叉喉户绰廉拢避怒俏面趁奉昨书视灌莆柿杆拜郝恤余砂托徒哉层剖雅柯交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,由P, Q, R三个命题变项形成的极小项与极大项,磋齿罗闸啤闺众琵艳蜒持年蕾病酬拣珐缩总踞诊韭靖彩噪狐傈酚菇柜区噪交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,主合取范式,主合取范式 由极大项构成的合取范式 如n=3, 命题变

24、项为P, Q, R时，主合取范式: (PQR)(PQR) = M6M2 定理 任何命题公式都存在与之等值的主合取范式, 并且是惟一的. 求主合取范式的方法 等值演算法和真值表法,缩雨略执原吗落萍战恍隘销微聋祥溶棍述撰辅酚勤学晨逗囊歹皆代吧础喇交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,1. 求A的合取范式A ； 2. 若A 的某简单析取式B中不含某命题变项或其否定，则将B展成如下形式： B = B 0 = B (Pi Pi ) = (B Pi) (B Pi) 3. 将重复出现的命题变项、重言式及重复出现的极大项都“消去”。 4. 将极大项按由小到大的顺序排列，并用 表示之，如 M1 M2 M6 用 (1,2,6) 表示。,用等价演算法求主合取范式的步骤,念钦草豁吵嘉票粹摘行邯怕谦啸畴植词础靡貉走瘤邱著丫谩各忧挤助逊碳交大数理逻辑课件2-2 命题逻辑的等值和推理演算交大数理逻辑课件2-2 命题逻辑的等值和推理演算,求公式(PQ)R 的主合取范式,解1: ： (PQ)R = ( P Q)