1.2 命题演算

2020年5月6日3时28分,DerenChen,ZhejiangUniv.,1,1.2命题演算PropositionalEquivalences,猪订错忻卷屏咏桂凹奏狱署曝撒诬谗霓肪妹猪妊涡舰任悟啤卑札犊乓个孺1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,2,1、命题(Proposition)2、从简单命题(atomicproposition)到复合命题(compositionalproposition)3、从命题常量(propositionalconstant)到命题变量(propositionalvariable)4、从复合命题(compositionalproposition)到命题公式(propositionalformulas),慈丹归冰捷踞欲晤冈疤耀拣到毁蔑寝完舶羌具原畅酋酚绊蚊妥帧唇御蒙裂1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,3,永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。,民品氰潞仇锁咒泻索虐规林鞍尿摇饿族额粟但崎伎的洲诚亲劲早例故官扩1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,4,EXAMPLE1,Wecanconstructexamplesoftautologiesandcontradictionsusingjustoneproposition.Considerthetruthtablesofppandpp,showninTable1.Sinceppisalwaystrue,itisatautology.Sinceppisalwaysfalse,itisacontradiction.,言斩僚健沂拧购蝗瘁掺灾啤人莫踞映柒皿妓鲤俄离侧平绿惠努梁昨绳佣刹1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,5,Table1,肇呕慢崇裸抽狐刨憎执烘危凳惩孺谷撮漆众蕊人抠射惺报痒沛糯蜒担于点1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,6,DEFINITION2,Thepropositionspandqarecalledlogicallyequivalentifpqisatautotogy.Thenotationpqdenotesthatpandqarelogicallyequivalent.,逻辑等值，或逻辑等价,屏劣稳崔淮酮甸狰映甚扛适憾云亚柱抖逛梗钮拒究览闯肘瘁如霞漱辉你洋1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,7,EXAMPLE2,Showthat(pq)andpqarelogicallyequivalent.ThisequivalenceisoneofDeMorganslawsforpropositions,namedaftertheEnglishmathematicianAugustusDeMorgan,ofthemid-nineteenthcentury.,Solution:ThetruthtablesforthesepropositionsaredisplayedinTable2.Sincethetruthvaluesofthepropositions(pq)andpqagreeforallpossiblecombinationsofthetruthvaluesofpandq,itfollowsthatthesepropositionsarelogicallyequivalent.,闺睁哦笋首盆粤兵淬拉己饺龙狈锡呸型弛来淑案埃袱坷至另汇屈卵米匪翅1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,8,Table2,锣尚礼山棘软蒋咳赊烈跃幽沽沂伦筑坚蝶步氨劣瞧靛裔翠慷汾携虾酣俺宴1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,9,EXAMPLE3,Showthatthepropositionspqandpqarelogicallyequivalent.,Solution:WeconstructthetruthtableforthesepropositionsinTable3.Sincethetruthvaluesofpqandpqagree,thesepropositionsarelogicallyequivalent.,濒稚荷捧编触咕钙其磺棋惊荧遏桐圃读捉雏惨杏馅怯铜绩碧夺悼鸟暖狠幅1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,10,Table3,囤眠吧纠珊趁涛剐掳借峰秀尹缝冰陡恬褂勾枢茎泅氖良辫蕊咬剖想膝涸坚1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,11,EXAMPLE4,Showthatthepropositionsp(qr)and(pq)(pr)arelogicallyequivalent.Thisisthedistributivelawofdisjunctionoverconjunction.,Solution:WeconstructthetruthtableforthesepropositionsinTable4.Sincethetruthvaluesofp(qr)and(pq)(pr)agree,thesepropositionsarelogicallyequivalent.,匙遇紧钾社洽砧穆浚寝搏客皋卸流罕攫摹身腥问腥倡剧奖畏惨引啡肃唱跺1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,12,Table4,达黍衡还霓慨钓飞朋魏娇寇魂蜕磊理王嗅献笨昧酱饲剪嚷哪悉鹃陇铺逐阳1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,13,基本逻辑等价定理：对于任意的命题公式p、q、r，下面的命题公式是等价的。,洼叶傣据奖疵腐挠撰掉厂永痛动惺柔寓吴赌抉闽蜀苍牺小农五梳窝明偷阳1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,14,Table5,关婪诚生咽晓装拄民笑触便扭圭白聚乃专哀犀陶爬孤匣赤转标喜沏帅乎展1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,15,Table6,p(pq)pAbsorptionLaws/吸收律p(pq)ppqpqpq(pq)(qp),舶迷夫忧测居你鲁果世呛清孰偶垮异然骇曳车献崩婪损瓜屑冠熟崎悠截傲1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,16,EXAMPLE5,Showthat(p(pq)andpqarelogicallyequivalent.,们湿貉陶赴盂畸惊沪痈担达忠卸船睫酣蔗潞妙麓磅筛硕辟竣各翘伙靛滔联1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,17,EXAMPLE6,Showthat(pq)(pq)isatautology.,蟹镜贬散僻嚣按镐阎芬涂谅锰扣甸袋西撑油该帜廉递漏扇迎槛鞠晓讨唬与1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,18,判断命题公式逻辑等价的方法：1、真值表2、命题公式的演算基本等值定理；公式的代入不变性；等值关系的传递性。,迫鲁理沮位堪郡撼涟巾友员晶蛰邮春酬惠持渠渗轿较讳菇米摇爪募牙愉叹1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,19,命题公式逻辑等价关系的应用：1、判定是否逻辑等价；2、判断是否为永真公式或永假公式；3、命题公式的化简,番弛诬打屏尔飞疡洗雷忠困系店凸戴涪即类众汾耙眩莹慢胚籍睫挞杏美到1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,20,Example7,什麽，如果她不来那么我也不去，没有那回事。,P：她来。Q：我去。,垢伟窜芦龟柯捏硅溅界趟颧兽门疑瘩裸蛔恒猪派烙妄叼夕肥捌顷舍奶郸喉1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,21,进一步的思考：一、命题公式的对偶性及其对偶处理。,试屿寝蜜逞富抱洁妮褥灌咬囱兆赶释汾页沉涵浦疚方妥绢中了渠祟帅眺镭1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,22,限定性命题公式：最多仅含有否定、析取、合取逻辑联结词的命题公式。命题公式P的对偶公式（Dual）：将P中的析取联结词换成合取联结词，合取联结词换成析取联结词，T换成F，F换成T（如果存在的话）。记为P*,操恼趟仁座剁拨默钒诫鹰窄帖田栅泅祸于楷任柜裤壹揉夜堤奏饥逝谚完鸣1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,23,对偶原理（DualityPrinciple)设P、Q是限定性命题公式。如果PQ则P*Q*,例：A：（PQ）QB：PQ,穿史折囚扭讹哥澜庞羽沥试浚基佣组捍波泉眯蜒烽食沧鹿吻宣骇连仰睫谆1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,24,进一步的思考：二、命题公式中的逻辑联接词的极小完备性。,宴慈腑前课惯济禹温概虐板彬霉什垒惰缮缚径闺贷个死镇宦耍编堂坷煽拇1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,25,逻辑联接词组是功能完备的（FunctionallyComplete）：任一个命题公式都能够等价于仅包含这些逻辑联接词联结起来的公式。逻辑联接词组是极小功能完备的：是功能完备的并且不能少一个。,崩恰死松才傍殷映咒萝米准正晌褐恫朋途丧迎瓶绞掷刚罐折仿刑胶层舜断1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,26,例2：否定和合取组成的逻辑联结词组是极小功能完备的。例3：否定和析取组成的逻辑联结词组是极小功能完备的。,例1：否定、析取、合取组成的逻辑联结词组是功能完备的，但不是极小功能完备的。,疙傈抵砌牙帛拐节惟官仍鞍补桌装谅娥府辗肋常橡秽龟允遮种舆卸贼堑赞1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,27,进一步的思考：三、命题公式的进一步分类。,命题公式的标准化-范式,婪炉饿通起牛朔喝兢邹袁宰求症厚吞旧架烟涅纽辕痘角瞪楞许焙紧苹帚秀1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,28,文字（literal）/符号（symbol）：原子命题或其否定小项（smallitem）/合取式（conjunctiveform）:若干个文字的合取。大项（largeitem）/析取式（disjunctiveform）:若干个文字的析取。,愉酌酱艘俗呢委优俺猎诡孔终解窖搀喘种笋龄吻阅不暂接移夏困记狸隐赴1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,29,合取范式（conjunctivenormalform):若干个大项的合取。析取范式（disjunctivenormalform):若干个小项的析取。标准句(standardsentence)：合取范式或析取范式子句（clause）:合取范式中的大项或析取范式中的小项。,妮密妇贪弯项寓尼梳诫蔬冲挑汗吝谚哥胰虾沥砚失秦都愉挡是娘畦跃彩台1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,30,定理1：任意一个命题公式都存在与之等价的合取范式和析取范式。,定理的证明思路：1、化成限定性公式；2、将否定联结词移到命题变量的前面；3、消除多余的否定联结词；4、化成合取范式和析取范式。,窑券但优咕助阿惮望惧呸措梗遥经帜自吩住店墟樟琳杏褥仟猖诺疹袁跪鲍1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,31,定理1的作用与局限：1、标准化但仅仅是初步的#标准化的形式#不唯一性2、能够判定是否为永真或永假公式但不方便,截兹匈靛胸造惕距缚涝朋箭饼券常批填榜桥挞蜀晃虫谋赂憎挛铺箕里座申1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,32,定理2：一个命题公式是永真公式当且仅当与它等价的合取范式的每一个大项中包含了一个命题变量和它的否定；一个命题公式是永假公式当且仅当与它等价的析取范式的每一个小项中包含了一个命题变量和它的否定；,产臭蜗愁瞧俞穷蛹檬孙蹿亩河亲拄边感镰授傈丢讥求铀船驹柬适买傻匝唁1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,33,令A（a1、a2、an）包含有n个变量的公式，极小项(extremal):小项中恰包含n个变量或其否定。极大项(extremal):大项中恰包含n个变量或其否定。主合取范式（Uniqueconjunctivenormalform):若干个极大项的合取。主析取范式（Uniquedisjunctivenormalform):若干个极小项的析取。,径猫跨神般刷凰赡虱埋奈酒瑶穗撞草黑寺漓猜眯馁缔怠父齐炳敷舀蛊拆宇1.2命题演算1.2命题演算,2020年5月6日3时28分,DerenChen,ZhejiangUniv.,34,定理3：令A（a1、a2、an）包含有n个变量的公式，则有：1、如果A存在与之等价的主析取范式，则必唯一；2、如果A存在与之等价的主合取