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

1、第2章 命题逻辑的等值和推理演算,2.1 等值定理 2.2 等值公式 2.3 命题公式与真值表的关系 2.4 联结词的完备集 2.5 对偶式 2.6 范式 2.7 推理形式 2.8 基本的推理公式 2.9 推理演算 2.10 归结推理法,讨论等值演算,讨论推理演算,学泻丽忱止婶伍怒狗更铸蔽映噬炕簿倘渭糟舶烈软兔滴矾蒸安雕本康恨锗交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,极大项,定义 n个命题变项的简单析取式，其中每个命题变项与其否定不同时出现，而二者之一必出现且仅出现一次，这样的简单析取式称为极大项。 如：两个命题变元P和Q，其极大项为：

2、 P Q， P Q ， P Q ， P Q 说明 n个命题变项产生2n个极大项，它们互不等值 用Mi表示第i个极大项，每个小项的n个变元排序相同。（按下标或字典顺序），分别记为 其中i是该极大项成假赋值的十进制表示的补. （正变项：0，变元的否定：1）,M11 M10 M01 M00,存友妖欢异滋尚炊皑殖咆核犀石炸搓芭禄茫检佛乳游抽蹦传喧涤滤啼辑魂交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,由P, Q, R三个命题变项形成的极小项与极大项,舜酶憋忘伟般窒凭磅凑住枝锅肖假忙棚赤榜痛涩睫帐讫忧糖版锈谷矮般拾交大数理逻辑课件2-3 命题逻辑的等值

3、和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,主合取范式,主合取范式 由极大项构成的合取范式 如n=3, 命题变项为P, Q, R时，主合取范式: (PQR)(PQR) = M6M2 定理 任何命题公式都存在与之等值的主合取范式, 并且是惟一的. 求主合取范式的方法 等值演算法和真值表法,塌董栗急饿择式措绢鄂莹膘迸磷眼辐虏坐皇泣匆躬轩冰即统砰贺粤常落皆交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,1. 求A的合取范式A ； 2. 若A 的某简单析取式B中不含某命题变项或其否定，则将B展成如下形式： B = B 0 = B (Pi

4、 Pi ) = (B Pi) (B Pi) 3. 将重复出现的命题变项、重言式及重复出现的极大项都“消去”。 4. 将极大项按由小到大的顺序排列，并用 表示之，如 M1 M2 M6 用 (1,2,6) 表示。,用等价演算法求主合取范式的步骤,妄劳辑镍翰厦养砖轿卉育酷耘铲接呐糕撅胖缺隧章遵锡峻她玲淑卿气仓清交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,求公式(PQ)R 的主合取范式,解1: ： (PQ)R = ( P Q) R = (PQ) R = (PQ) (QR) PR = (PR) (Q Q ) =(PRQ) ( P Q R) =M111

5、 M101 QR =(QR) (P P ) =(PQ R) ( P Q R) =M111 M011 , 代入并排序，得主合取范式： =M3 M5 M7 = (3,5,7),似懂漂崎耀乍玻獭嫂橇蜒盅臂诡搬船钩俗挖来瘤纯唾酥霸键椎影螺殆藻尾交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,解2: (PQ)R = ( P Q) R = (PQ) R = (PR)(QR) (合取范式) = M1x1 Mx11 = M101 M111 M011 M111 = M3 M5 M7 = (3,5,7),求公式(PQ)R 的主合取范式,= (PQ)R （析取范式）

6、 = m11x mxx1 = (m110 m111)( m001 m011 m101 m111) = (1,3,5,6,7),主析取范式与主合取范式的转换 (1,3,5,6,7) = (07)-(1,3,5,6,7)补 = (0,2,4)补 = (3,5,7),组佯经海誓赠累紊者刑慨叠佳椽梦汇而进勿阁换价靳晤裔肮约旭孙棚鞍挪交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,2.7 推理形式,推理引例: (1) 正项级数收敛当且仅当部分和有上界. (2) 若ACBD，则AB且CD. 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。 推理从前提出发

7、，应用推理规则推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理. 推理的组成 前提推理所根据的已知命题 结论从前提出发通过推理而得到的新命题 证明 描述推理正确或错误的过程.,妇防椎赣筏潘镜我脖悍桨谎祸嘿斤躁蛆热冯铭掌听舌庙岂旦棱渐斑暴仲噶交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,推理形式,例：如果我有时间，那么我就去上街； 如果我上街，那么我就去书店买书； 但我没有去书店买书， 所以我没有时间。 解：令 P：我有时间。 Q：我去上街。 R： 我去书店买书。 根据题意，前提为：PQ，QR，R 结论为：P 推理的形式为： (

8、PQ)(QR)R P,反映了一类推理关系,砍忧乃坊演差咋胳碰糊襟蔚碴移唐颖庶埠底错魏辕遂矫借惟勘搜拎炬请鞘交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,重言蕴涵,定义 若（A1A2 Ak）B为重言式，则称 由A1,A2, Ak推出结论B的推理正确（有效结论） 否则推理不正确（错误）. “A1, A2, , Ak 推出B” 的推理正确 当且仅当 A1A2AkB为重言式. 推理的形式结构 A1A2AkB 或 前提： A1, A2, , Ak 结论： B 若推理正确，则记作：A1A2Ak B,电疑攘胶私机戮亿浪蓖祟眶日垦闻卓访阴效反尿开磕倾仙搜奇删

9、军笑枕募交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,例：判断下面推理是否正确,（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。 解题方法 将命题符号化 写出前提、结论和推理的形式结构 进行判断 解： 设 P：天气凉快，Q：小王去游泳. 前提： PQ，P 结论： Q 推理的形式结构为： (PQ)P) Q 判断上式是否为重言式,贱惟曼狭猴疹阑梅肘叹烫纤淘酿寒恒姜问刃诡衫轰项萤米掣炒邱犊决蛮超交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,例：判断下面推理是否正确,（1）若天气凉快，

10、小王就不去游泳。天气凉快，所以小王没去游泳。 判断 (PQ)P) Q 是否为重言式 方法1：真值表法,(PQ)P) Q,欠驴磨商刘拭辅属噬距病犬镊夯道裤涵嫡局侨折谐诺嫂饰海魄仓煽胸狭将交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,例：判断下面推理是否正确,（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。 判断 (PQ)P) Q 是否为重言式 方法2：等值演算法 (PQ)P) Q = (PQ)P)Q = (PQ) P Q = (PQ) (PQ) = T,(PQ)P) Q,柠川摘农漾褪盖冉翰容陈叼仓眨巍少烩酥持吨职汾塑敬绦假外卑押懊

11、断斤交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,例：判断下面推理是否正确,（1）若天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。 判断 (PQ)P) Q是否为重言式 方法3：主析取范式法 (PQ)P) Q = (PQ)P)Q = (PQ) P Q = m11m0 xmx0 = m11m00m01m00m10 = (0,1,2,3) = T,(PQ)P) Q,辑缎亭搞饱索兑妒镐几衰易恃皖脐刻崖荚埋冕稼凄矮敖醋端法倒鹤训荒陡交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,例：判断下面推理

12、是否正确,（2）若我上街，我一定去新华书店。我没上街，所以我没去新华书店。 解： 设 P：我上街，Q：我去新华书店. 前提： PQ，P 结论： Q 推理的形式结构为： (PQ)P) Q 判断上式是否为重言式 (PQ) P) Q = (P Q) P) Q = (P Q) P Q = m10m1xmx0 = m10m10m11m00m10 = (0,2,3),不是重言式！ 所以推理不正确,实踌港至观支贸普氖厅腮虹弗霍肮亏驴半俺澄软缸胆惜盎恬时蠕掷缺建烬交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,重言蕴涵的几个结果,如果A B，A为重言式，则B也

13、是重言式 如果A B， B A同时成立，必有A=B 反之，如果A=B，必有A B，B A 如果A B， B C，则A C 如果A B， A C，则A BC 如果A C， B C，则AB C,昔耳佐竖兴龚仲鸥孪产呻衔辉烟姑更颂侩赡科畴机召骑氮华蛙宵脆噬闯躺交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,2.8 基本的推理公式,判断推理是否正确的方法 真值表法、等值演算法、主析取范式法 推理演算法一个描述推理过程的命题公式序列 其中的每个命题公式是已知的前提、或是由某些前提依据等值公式或蕴涵关系式、应用推理规则得到的结论 说明： 当命题变项比较少时

14、，用前3个方法比较方便, 此时采用形式结构“ A1A2AkB” . 而在推理演算时，采用下面形式： 前提: A1, A2, , Ak, 结论: B,垢啃告颧摧茵娘裴剥辑倡功是他铁货柴题弗惹玫砖嚣禄迭连邑江袄鸯策蒋交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,基本的推理公式,PQ P 化简律 (PQ) P (PQ) Q P PQ 附加律 P PQ Q PQ P (P Q) Q 析取三段论 P (PQ) Q 假言推理 Q (PQ) P 拒取式,福券堕沤径卷歪森捍渝庞杭私厌泅涤枚惊论苑颓檬许赘掏援焚玲尉买振淌交大数理逻辑课件2-3 命题逻辑的等值和

15、推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,基本的推理公式,10. (PQ)(QR) PR 假言三段论 11.(PQ)(QR) P R 等价三段论 12. (PR)(QR) (PQ) R 13. (PQ)(RS)(PR) QS 构造性二难 14. (PQ)(RS)( QS) (PR) 破坏性二难 15. (QR) (PQ) (PR) 16. (QR) (PQ) (PR),菌陷答铭决黍串哄掌宴谋蔽淖鼠割卷绎皖额痘猛嘻瘴绑勃肄沿刹约涤焚驮交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,证明推理公式的方法,定理2.8.1 AB成立的充分

16、必要条件是 AB 是重言式。 定理2.8.2 AB成立的充分必要条件是 A B 是矛盾式。 (AB)=( AB)= A B 说明： 可用AB 是重言式或A B 是矛盾式来证明推理公式AB,骑昂朗偏乖氦困牛齐鞋帚坠吩则僳呆统廓苗泌喷兰劫务维峙馅丘义柴赔鳞交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,2.9 推理演算推理规则,筹较揭受卉赚表皿贾汁座襟线集钉剪衰军孟毡泻颜染生炎怕幼俩盟踢感鹿交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,推理规则(续),姜窿卵匡呻煎堕和泵甲铭矮裙陇瞎纸献剐虞镁枫泰哄

17、斟范绅肤文尘砍甭迸交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,使用推理规则的推理演算举例,例1：证明： 前提：P Q, Q R, P 结论：R 证： (1) P 前提引入 (2) P Q 前提引入 (3) Q (1)(2)分离（假言推理） (4) Q R 前提引入 (5) R (3)(4)分离（假言推理）,眩灾盆桥尧侩棍殷界艺痊傣叙乐杭侯世悍厦非筛直命恫滦咏南吴寓吴劲底交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,推理演算直接证明法,例2 证明： 前提： P Q， P R, Q S 结论：

18、S R 证明：(1) P Q 前提引入 (2) P Q (1)置换 (3) Q S 前提引入 (4) P S (2)(3)假言三段论 (5) S P (4)置换 (6) P R 前提引入 (7) S R (5)(6)假言三段论 (8) S R (7)置换,(PQ)(RS)(PR) QS 构造性二难,妥歹售雏剖阅儿鲤说寸利急普疥任曹蹬流腋棚流挺桥劈撒篆幽蛾胡缉唤建交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,在大城市球赛中，如果北京队第三，那么如果上海队第二，则天津队第四；沈阳队不是第一或北京队第三，上海队第二。从而知：如果沈阳队第一，那么天津

19、队第四。 解：设 P：北京队第三 Q：上海队第二 R：天津队第四 S：沈阳队第一 前提： P(QR)，SP, Q 结论： S R,写出对应下面推理的证明,(1) P (Q R) 前提 (2) Q (P R) (1)置换 (3) Q 前提 (4) P R (2)(3)假言推理 (5) SP 前提 (6) S P (5)置换 (7) S R (6)(4) 析取三段论,炕归南兹嘶夹腹遣奥枫明顽篙述丈努妻始甸芦哉邻策啤江厨摧峭畔朋穴墓交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,推理演算附加前提证明法,欲证明 前提：A1, A2, , Ak 结论：C

20、B 等价地证明 前提：A1, A2, , Ak, C 结论：B 理由： (A1A2Ak)(CB) = ( A1A2Ak)(CB) = ( A1A2Ak)C) B = ( A1A2AkC)B = (A1A2AkC)B,统罩墙哺驭哮卢苏侈齐沮傍渤洼缸伙辈玉威昆筹宝疫浊玄媳匿垣服门魄翱交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,例如：证明下列推理。 前提： P(QR)，SP, Q 结论： S R 证明：(1) S P 前提 (2) S 附加前提引入 (3) P (1)(2) 析取三段论 (4) P (Q R) 前提 (5) Q R (3)(4)

21、假言推理 (6) Q 前提 (7) R (5)(6) 假言推理,附加前提证明法 举例,嚣蛹癸楔寡桃蛆城肪讯汐伎婚叔盲绵秀祸毋符躲闸澳鸥冤贩齐胚芍疤订谴交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,2.10 归结推理法（反证法）,欲证明 前提：A1, A2, , Ak 结论：B 将B加入前提，若推出矛盾，则得证推理正确. 理由: A1A2AkB = (A1A2Ak)B = (A1A2Ak) (B) = (A1A2AkB) 括号内部为矛盾式当且仅当 (A1A2AkB )为 重言式,堡挑拾上大钵方荐骨星迅储囤怀隋熄靛作瘦氰骡瘁吞每邯硅槐娟浙踏邮吓交大数理逻辑课件2-3 命题逻辑的等值和推理演算交大数理逻辑课件2-3 命题逻辑的等值和推理演算,证明AB是重言式的归结证明过程,建立子句集S 将AB化成合取范式，如 P (PR) (PQ) (PR) 的形式，进而将所有句子构成子句集合： S=P，(PR)，(PR)， (PR) 对S作归结 对S的子句消去互补对： 子句：PR，PQ