离散数学-命题逻辑2013下

离散数学中国石油大学（华东）计算机与通信工程学院计算机科学系06二月2023《离散数学》(DiscreteMathematics)课程学时：80裴振奎peizhk@126.com计算机与通信工程学院计算机科学系离散数学

DiscreteMathematics裴振奎peizhk@126.com离散数学研究离散数量关系和离散结构数学模型的数学分支统称为离散数学。离散数学是计算机科学中基础理论的核心课程。以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般地是有限个或可数个元素，它充分描述了计算机科学离散性的特点。计算机科学——离散数学数字电子计算机的飞速发展与广泛应用，极大地冲击了现代数学。无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临这样一些问题：

如何高速、有效地处理离散的对象和离散的数量关系，如何对离散结构建立离散数学模型，又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。离散数学——未来计算机系统的创新离散数学课程所提供的训练，十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。这些能力与态度是一切软、硬件计算机科学工作者所不可缺少的。就象20世纪30年代图灵机的提出为现代计算机奠定基础一样，未来计算机系统的创新也取决于人类对离散结构、计算（包括思维与推理）模型的研究取得新的突破。学习离散数学——学习微积分计算机求解基本模式:

实际问题数学建模算法设计编程实现离散数学的作用：◆为数学建模打下知识基础

◆为算法设计提供具体指导有人预计，未来社会将有越来越多的人学习离散数学,就象当今人们学习微积分教程一样。教材与教辅课程教材左孝凌,李为鉴,刘永才编著.离散数学.上海科学技术文献出版社，2006年12月第54次印刷．左孝凌,李为鉴,刘永才编著.离散数学理论.分析.题解.上海科学技术文献出版社，2002年1月.其它参考书《离散数学教程》

耿素云屈婉玲等编著北京大学出版社

DISCRETEMATHEMATICSANDITSAPPLICATIONS(FIFTHEDITION)离散数学及其应用，机械工业出版社(4小时出库)

(4小时出库)

目录第一篇数理逻辑第二篇集合论第三篇代数系统第四篇图论抽象代数结构——图灵机布尔代数——电子计算机硬件设计半群理论——自动机和形式语言关系代数理论——数据库的理论模型泛代数——程序设计方法学研究…………姚期智：图灵奖（TuringAward）1946年12月24日生，美籍华人，计算机科学家，2000年图灵奖得主，是目前唯一一位获得此奖项的华人及亚洲人。目前是清华大学理论计算机科学研究中心教授。图灵奖是世界计算机科学领域的最高奖项，与物理、化学、医学、经济学领域的诺贝尔奖齐名。姚期智:开华裔获图灵之先河姚期智对计算机科学技术所作出的贡献主要在计算理论方面。姚期智进入计算机科学领域最早的论文之一《寻找最小生成树的O(|E|log

log|V|)算法》一文就引起轰动，因为学术界原先认为，寻找最小生成树算法的时间复杂度的下界是O(|E|log|V|)，而姚期智的论文证明这个极限是可以打破的。课程考核考勤：10%平时作业:20%（作业每周周一下午交上周的作业，迟交作业的同学本次作业算没有交作业）期末考试：70%课程内容

本课程根据大纲的内容和相关独立性，可分为四大部分

第一部分数理逻辑包括命题逻辑;谓词逻辑

第二部分集合论包括集合与关系;函数第三部分代数系统包括代数结构;格与布尔代数第四部分图论

学习方法定义、定理多。本课内容＝定义＋定理＋例题为了学好这门课，要求：（１）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；（２）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。（3）做好课堂笔记。LuChaojun,SJTU1717什么是逻辑?逻辑(logic)是关于推理的科学.或:关于思维形式规律的科学.源自希腊文logos(言词,思想,理性等等)中文“逻辑”一词由严复首先译用过去又称名理学,名学,论理学,理则学,辩学等.西方逻辑起源于古希腊主要贡献来自亚里士多德和斯多葛学派古代东方逻辑中国的名辩之学,散见于名墨儒道各家古印度的因明LuChaojun,SJTU18为什么要学逻辑?思维必须符合规律才不会导致谬妄.推理是获得知识的一种途径逻辑研究怎样的推理是可靠的.逻辑还研究一组知识是否协调(一致,相容).各门科学都是在特殊领域的思维推理活动,故逻辑是一切科学的公共基础.Geology,biology,physiology,…逻辑思维能力是学习、工作乃至日常生活中的重要能力.18LuChaojun,SJTU19形式逻辑形式逻辑(formallogic)研究推理的形式,推理有效性由形式而非内容决定.例:“所有A是B,所有B是C,故所有A是C”是正确的推理形式,把ABC换成任何具体对象都有效.但“我喜欢吃辣,也喜欢吃鱼,故我喜欢吃辣子鱼”恐怕就不能得出一般的形式.19LuChaojun,SJTU20数理逻辑符号逻辑(symboliclogic):对逻辑推理的形式特征进行符号抽象.使用人工符号语言.分为命题逻辑和谓词逻辑.数理逻辑(mathematicallogic):是符号逻辑及其在其他数学领域的扩展.四论:集合论,模型论,递归论,证明论或说:符号逻辑=数理逻辑20LuChaojun,SJTU21数理逻辑发展简史逻辑发展史中的里程碑人物亚里士多德莱布尼茨布尔弗雷格希尔伯特罗素哥德尔21LuChaojun,SJTU22古典逻辑亚里士多德的三段论(syllogism)从两个前提推出一个结论的逻辑论证形式:1.大前提(majorpremise)人都是两足动物2.小前提(minorpremise)希腊人都是人3.结论(conclusion)希腊人都是两足动物斯多葛学派(Stoics)的命题逻辑芝诺(ZenoofCitium)于301BC创立克吕希波(Chrysippus)大大发展了Stoiclogic22LuChaojun,SJTU23亚里士多德Aristotle(384BC-322BC)形式逻辑的奠基人第一个逻辑学家第一个形式演绎逻辑系统:三段论三段论是传统演绎推理的核心,在西方逻辑中一直处于统治地位,直至19世纪被数理逻辑(一阶谓词逻辑)所取代.附注:欧几里德(Euclid,330BC-275BC)的《几何原本》第一次以公理化方式演绎地处理数学.23LuChaojun,SJTU24莱布尼茨GottfriedWilhelmLeibniz(1646-1716)数理逻辑的先驱首先使用“数理逻辑”这个术语Leibniz’sDream:推理归结为(符号)计算.两大思想:“普遍语言”和“思维演算”这正是数理逻辑的主导思想.“发生争论时我们可以简单地说:让我们计算一下吧,看谁正确.”罗素评价说:Leibniz未发表手稿中发展的逻辑的水平只在200年后才重新达到.24LuChaojun,SJTU25布尔GeorgeBoole(1815-1864)数理逻辑创始人之一如1847年的论文:逻辑的数学分析:论演绎推理的演算法.应用数学(代数)方法研究逻辑,发明了布尔代数(逻辑代数,命题代数,布尔逻辑)初步实现了Leibniz梦想.亦可解释成集合代数,开关代数是计算机数字逻辑的基础附注:AugustusdeMorgan(1806-1871)几乎同时独立地做出重要贡献. CharlesSandersPeirce(1839-1914)发展了这两人的工作. ErnstSchröder(1841-1902)进一步总结发展前三人的工作.25LuChaojun,SJTU26弗雷格FriedrichLudwigGottlob

Frege(1848-1925)数理逻辑主要创始人分析哲学,语言哲学创始人重要著作:Begriffsschrift

(1879)《概念文字:一种模仿算术语言构造的纯思维的形式语言》.第一个公理化谓词逻辑系统自Aristotle以来逻辑的最重要进展基本实现了Leibniz梦想26LuChaojun,SJTU27数学基础危机(1)19世纪早期发现数学一直存在缺陷.如:非欧几何(Lobachevsky,Riemann)分析(微积分及其扩展)的基础19世纪后期的公理化运动:去除基于直觉或经验的朴素概念的模糊之处,使数学严密化.如:算术公理化(Dedekind1888,Peano1889)几何公理化(Hilbert1899)27LuChaojun,SJTU28数学基础危机(2)1900年国际数学大会Poincare:“借助集合论…可以建造数学大厦…今天我们可以宣称绝对的严密已经实现了!”随后发现了Cantor集合论中的一些悖论:如1901年的罗素悖论.弗雷格:当大厦竣工时基础却动摇了.28LuChaojun,SJTU29解决危机的四大派别逻辑主义:主张从逻辑推出数学.代表人物Russell形式主义:对全部数学进行形式化,并证明其协调性.代表人物Hilbert直觉主义:反对排中律,强调构造性.代表人物Brouwer公理化集合论代表人物Zermelo29LuChaojun,SJTU30罗素BertrandArthurWilliamRussell(1872-1970)逻辑主义创始人之一主张从逻辑推出全部数学.重要论著PrincipiaMathematica,1910与Whitehead合著PM系统是完备的命题演算和谓词演算.逻辑演算的经典系统.30LuChaojun,SJTU31希尔伯特DavidHilbert(1862-1943)数理逻辑中形式主义学派证明论创始人之一Hilbert’sprogram:将理论至于逻辑演算中加以形式化,重点研究系统中证明的逻辑性质,希望得出系统的协调性.强调证明要使用有穷方法.31LuChaojun,SJTU32Gödel不完备性定理Gödel于1931年发表的不完备性定理是对Hilbert’sprogram的致命一击.大意:任何足够强的形式系统都有无法证明的真命题.且系统自己不能证明自己无矛盾.显示了形式化方法的本质局限.20世纪数理逻辑的顶峰.也有评论说是20世纪最重要的数学定理32LuChaojun,SJTU33哥德尔KurtGödel(1906-1978)证明了一阶谓词演算的完备性.实现了Leibniz梦想.证明了更加重要的成果:不完备性定理.Einstein说:自己的工作不再要紧,来研究院只是为了享有和Gödel一起步行回家的特权.3334数理逻辑的分支基础的逻辑演算（命题逻辑，谓词逻辑）公理集合论模型论递归论证明论34LuChaojun,SJTU35公理集合论研究公理集合论,是整个数学的基础.Cantor的朴素集合论有缺陷Burali-Forti悖论,罗素悖论,Richard悖论,…ErnstZermelo:第一个公理化集合论(1908)经Fraenkel(1922)改进成为经典的ZF集合论避免了罗素悖论Gödel和PaulCohen(1963)在CH方面的工作CH在ZF系统中不可判定Cohen的新方法(力迫法)让人们证明了许多不可判定的问题.数学绝不是“非真即假”那么单纯!35LuChaojun,SJTU36模型论建立形式理论的模型,研究模型之间的关系等.模型是对形式理论进行具体解释的一种结构.语法与语义的关系AlfredTarski奠定了模型论的基础36LuChaojun,SJTU37递归论亦称(能行)可计算性理论,研究能行可计算的函数.从递归函数和图灵机的等价产生可计算函数的概念代表人物Gödel:递归函数AlonzoChurch(丘奇):演算AlanTuring(图灵):图灵机现代计算机设计思想的创始人之一3738证明论研究数学理论系统的形式证明问题,即以证明为研究对象,用数学方法分析之.主要关注系统的协调性.代表人物Hilbert:首先提出GerhardGentzen:发展了证明论的重要成果.证明了算术形式系统的协调性.是在系统外证明,且不是有穷主义的.与Gödel的结果不矛盾.3839数理逻辑与计算机科学计算机图灵机计算机能做什么,算法是什么可计算性理论计算机不能做什么算法不可解问题逻辑程序设计(Prolog)谓词逻辑程序设计语言的语义学模型论形式规格说明与程序验证模型论AI,知识表示,自动定理证明逻辑演算从形式证明产生程序证明论(Gentzen)……39LuChaojun,SJTU40戴克斯特拉Edsger

Wybe

Dijkstra(1930-2002)最伟大的计算机科学家(之一?)“搞了这么多年软件,错误不知犯了多少,现在觉悟了.我想,假如我早年在数理逻辑上好好下点功夫的话,我就不会犯这么多的错误,不少东西逻辑学家早就说了,可我不知道.要是我能年轻二十岁的话,就要回去学逻辑.”成就很多,如Dijkstra最短路径算法(见教材11.5)EWD手稿:/users/EWD/40第一篇数理逻辑

逻辑学:研究思维形式及思维规律的科学。逻辑学分为二类：辩证逻辑:是研究事物发展的客观规律。形式逻辑:对思维的形式结构和规律进行研究。数理逻辑：是用数学的方法研究概念、判断和推理的科学，属于形式逻辑。

研究推理的方法很多，用数学方法来研究推理的规律就称为数理逻辑第一篇数理逻辑在数理逻辑中，用数学的方法是指引进一套符号体系的方法来研究概念、判断和推理。即对符号进行判断和推理。数理逻辑分为四大分支：证明论、模型论、递归论和公理集合论。我们这里介绍的是属于四大分支的共同基础—古典数理逻辑(命题逻辑和谓词逻辑)。第一章命题逻辑§1.1命题§1.2命题联结词§1.3命题公式与翻译§1.4真值表与等价式§1.5重言式与蕴含式§1.6其他命题联结词§1.7对偶与范式§1.8推论理论第一章命题逻辑教学目的及要求：深刻理解和掌握命题逻辑中基本概念和基本方法。教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴涵式、对偶与范式、推理理论。教学重点：命题逻辑中的基本概念和基本推理方法。教学难点：推理理论。§1.1命题定义：客观上具有确定真假值的陈述句叫命题。讨论定义：（1）命题可以是真的，或者是假的，但不能同时为真又为假。（2）命题分类：

ⅰ)原子命题（基本命题、本原命题）：不能分解成为更简单的命题。例：5是自然数。§1.1命题ⅱ)分子命题（复合命题）：若干个原子命题使用适当的联结词所组成的新命题例：2是偶数并且2也是素数。（3）命题标识符：用来表示命题的符号。

常用大写２６个英文字母(可以带下标)表示命题。（4）命题中所有的“真”用“Ｔ”(或1)表示，命题中所有的“假”用“Ｆ”(或0)表示。§1.1命题例：判断下列语句是否为命题。（1）十是整数。（Ｔ）（2）上海是一个村庄。（Ｆ）（3）火星上有生命存在。（4）加拿大是一个国家。（Ｔ）（5）２是偶数而３是奇数。（T）（6）2016年巴西奥运会上中国的金牌数超过美国。（7）在十进制中１＋１０１＝１１０（Ｆ）（8）今天是星期天。（Ｆ）§1.1命题命令句，感叹句，疑问句均不是命题。（1）把门关上！（2）你到哪里去？语句既为真，同时又为假的陈述句不是命题，这样的句子称为“悖论”。（3）日本首相安倍正在说谎。（在命题逻辑中不讨论这类问题）下列陈述句是否为命题？（1）赵本山很帅。（2）刘翔是高个子。（3）章子怡很漂亮。（4）姚明很富有。§1.2命题联结词在命题演算中也有类似的日常生活中的联结词称做：“命题联结词”,下面先介绍五个常用的命题联结词。１．否定词：（否定运算、非运算）（１）符号

,读作“非”，“否定”设命题为Ｐ，则在Ｐ的前面加否定词，变成Ｐ，Ｐ读做“Ｐ的否定”或“非Ｐ”§1.2命题联结词（２）定义P的真值表：（３）举例：Ｑ：每一种生物均是动物。FＱ：有一些生物不是动物。T

这里Ｑ不能讲成“每一种生物都不是动物”。对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。TFFTPP§1.2命题联结词２．合取词（“合取”、“积”、“与”运算）

(1)符号“Λ”

设Ｐ，Ｑ为两个命题，则ＰΛＱ称Ｐ与Ｑ的合取，读作：“Ｐ与Ｑ”、“Ｐ与Ｑ的合取”、“Ｐ并且Ｑ”等。

(2)定义（由真值表给出）：§1.2命题联结词TTTTFFFTFFTFFFFFQΛPPΛQQPＰΛＱ的真值表：§1.2命题联结词当且仅当Ｐ和Ｑ的真值均为“Ｔ”，则（ＰΛＱ）的真值为“Ｔ”。否则，其真值为“Ｆ”。注意：Ｐ和Ｑ是互为独立的；地位是平等的，Ｐ和Ｑ的位置可以交换而不会影响ＰΛＱ的结果。§1.2命题联结词(3)举例：

(a)P：王华是党员。

Q：王华是三好学生。则ＰΛＱ：王华是党员并且也是三好学生。

(b)P：我们去种树

Q：房间里有一台电视机则ＰΛＱ：我们去种树且房间里有一台电视机。§1.2命题联结词(c)P：今天下雪

Q：3+3=6

则ＰΛＱ：今天下雪和3+3=6由例(b)(c)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。§1.2命题联结词(d)P:王大和王二是亲兄弟。

Q:他打开箱子然后拿出一件衣服来。该语句不是合取联结词组成的命题。

§1.2命题联结词３．析取词（或运算）（１）符号“∨”设Ｐ、Ｑ为二个命题，则（Ｐ∨Ｑ）称作Ｐ与Ｑ的“析取”，读作：“Ｐ或Ｑ”。（２）定义（由真值表给出）：§1.2命题联结词当且仅当Ｐ、Ｑ均为“Ｆ”时，（Ｐ∨Ｑ）为“Ｆ”。否则，其真值为“Ｔ”．TTTTFTTTFFFFP∨QQPＰ∨Ｑ的真值表：§1.2命题联结词区分“可兼或”与“不可兼或（异或，排斥或）”“可兼或”即P或Q为“T”时（P∨Q）为“T”，是析取。例如：灯泡有故障或开关有故障。今晚写字或看书。今天下雨或打雷。以上例句均为“可兼或”。§1.2命题联结词“不可兼或”即P和Q的真值不同时，P▽Q为T。（异或用“▽”表示）不是析取。FTTTFTTTFFFFP▽QQPP▽Q的真值表：§1.2命题联结词例：他通过电视看杂技或到剧场看杂技。他乘火车去北京或乘飞机去北京。以上两句均为“不可兼或”。§1.2命题联结词４．单条件联结词：（１）符号“→”，读作：“如果…则…”

Ｐ、Ｑ为二个命题，（Ｐ→Ｑ）为新的命题，读作：“如果Ｐ则Ｑ”。（２）定义（由真值表给出）§1.2命题联结词Ｐ→Ｑ的真值表：TTTFFTTTFTFFP→QQP§1.2命题联结词

当Ｐ为“Ｔ”，Ｑ为“Ｆ”时，则（Ｐ→Ｑ）为“Ｆ”，否则（Ｐ→Ｑ）均为“Ｔ”。Ｐ：称为前件、条件、前提、假设Ｑ：称为后件、结论。（３）举例：

P：我拿起一本书

Q：我一口气读完了这本书§1.2命题联结词P→Q：如果我拿起一本书，则我一口气读完了这本书。(b)P：月亮出来了

Q：3×3=9P→Q：如果月亮出来了，则3×3=9。通常称：

(a)为形式条件命题——前提和结果有某种形式和内容上的联系。§1.2命题联结词(b)为实质条件命题——前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。所以,是形式条件命题一定是实质条件命题,反之不一定。“→”是实质条件命题。例：Ｐ：我买到了鱼；Ｑ:我吃鱼。Ｐ→Ｑ：如果我买到了鱼，则我吃鱼。但“如果我没买到鱼，则我吃鱼”，在日常生活中不可能，但在单条件命题的定义中是允许的。

§1.2命题联结词可以证明：Ｐ→Ｑ

¬Q→¬P

原命题逆反命题Ｑ→Ｐ

¬Ｐ→¬Ｑ逆命题反命题§1.2命题联结词列出真值表,由真值表得：原命题逆反命题；逆命题反命题。TTTTTTTTFFFTFFTTTFTTTTFF¬Ｐ→¬ＱＱ→P¬Q→¬P

P→QQP5．双条件联结词（等价联结词）：（１）符号“↔”，读作：“当且仅当”Ｐ、Ｑ为二个命题，（Ｐ↔Ｑ）为新的命题，读作：“Ｐ当且仅当Ｑ”。（２）定义（由真值表给出）§1.2命题联结词P↔Q的真值表:每当Ｐ和Ｑ的真值相同时，则（Ｐ↔Ｑ）的真值为“Ｔ”，否则（Ｐ↔Ｑ）的真值为“Ｆ”。TTTFFTFTFTFFP↔QQP§1.2命题联结词（３）举例：（a）设Ｐ：△ABC是等腰三角形Ｑ：△ABC有两只角相等Ｐ↔Ｑ：△ABC是等腰三角形当且仅当有两只角相等。§1.2命题联结词（b）下面均为等价联结词：春天来了当且仅当燕子飞回来了。平面上二直线平行，当且仅当二直线不相交。２＋２＝４当且仅当雪是白色的。§1.2命题联结词（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、Ｑ交换位置不会改变真值表中的值。（５）Ｐ当且仅当ＱＰ↔ＱＰ仅当ＱＰ→ＱＰ当且ＱＱ→Ｐ§1.2命题联结词６．命题联结词在使用中的优先级（１）先括号内，后括号外（２）运算时联结词的优先次序为：¬

Λ∨→↔

（由高到低）（３）联结词按从左到右的次序进行运算（４）最外层的括号一律均可省去（Ｐ→Ｑ∨Ｒ）可写成Ｐ→Ｑ∨Ｒ§1.2命题联结词例¬Ｐ∨（Ｑ∨Ｒ）可省去括号因为“Ｖ”运算是可结合的。而Ｐ→（Ｑ→Ｒ）中的括号不能省去，因“→”不满足结合律。§1.2命题联结词

７．命题联结词小结：

（1）五个联结词的含义与日常生活中的联结词的含义大致相同。

（2）“或”可分为可兼或（∨）和异或（▽）（不可兼或）（3）“¬”为一元运算，其余四个均为二元运算。§1.2命题联结词(4)“→”分为形式条件和实质条件命题，当前件为“Ｆ”时，不论后件怎样，则单条件命题的真值均为“Ｔ”。(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。§1.3命题公式与翻译约定：（１）我们只注意命题的真假值，而不再去注意命题的汉语意义。（２）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。§1.3命题公式与翻译１．命题公式命题常元：表示确定的命题｛T，F｝。命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母Ａ…Ｚ表示。命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。§1.3命题公式与翻译[定义]命题公式(wff)可按下述法则来生成：１）单个的命题变元是一个命题公式。２）若Ａ是命题公式，¬Ａ也为命题公式。３）若Ａ、Ｂ是命题公式，则（ＡΛＢ）、（Ａ∨Ｂ）、（Ａ→Ｂ）、（Ａ↔Ｂ）均为命题公式。４）当且仅当有限次使用（１）（２）（３）所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。§1.3命题公式与翻译例如：(¬(P∨Q))，(P→(Q→R))，((PΛQ)¬R)，P都是命题公式。而(P→)，(P∨¬)都不是命题公式§1.3命题公式与翻译以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。步骤如下：①找出各简单命题，分别符号化。②找出各联结词，把简单命题逐个联结起来。§1.3命题公式与翻译例.将下列命题符号化：（1）李明是计算机系的学生，他住在312室或313室。（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了车站。（4）只有一个角是直角的三角形才是直角三角形。（5）老王或小李中有一个去上海出差。§1.3命题公式与翻译解：（1）首先用字母表示简单命题。

P：李明是计算机系的学生。

Q：李明住在312室。

R：李明住在313室。该命题符号化为：P（Q▽R）（2）张三和李四是朋友。是一个简单句该命题符号化为：P§1.3命题公式与翻译（3）首先用字母表示简单命题。

P：交通堵塞。

Q：老王准时到达了车站。该命题符号化为：PQ（4）首先用字母表示简单命题。

P：三角形的一个角是直角。

Q：三角形是直角三角形。该命题符号化为：PQ§1.3命题公式与翻译（5）首先用字母表示简单命题。

P：老王去上海出差。

Q：小李去上海出差。该命题符号化为：P▽Q

也可符号化为：（PQ）（PQ）或者（PQ）（PQ）§1.4真值表与等价公式一．命题公式的真值表:命题变元用特定的命题来取代，这一过程称为对该命题变元进行真值指派。命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成ｙ＝ｆ(x)§1.4真值表与等价公式

例如：公式P(QR)定义三元函数

Y(P，Q，R)＝P(QR)[定义]命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。§1.4真值表与等价公式构造真值表的步骤如下：

1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。

2)按照从低到高顺序写出命题公式的各层次。

3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。§1.4真值表与等价公式FTTTTFTTFTTFTTFTFFFF¬（（Ｐ∨Ｑ）ΛＰ）（Ｐ∨Ｑ）ΛＰP∨QQP例１．构造命题公式¬（（Ｐ∨Ｑ）ΛＰ）的真值表：§1.4真值表与等价公式

例２．写出命题公式Ｐ∨（ＱΛＲ）的真值表TTTTTFTTTTFTTFFTTTTFFFTFFTFFFFFFＰ∨（ＱΛＲ)RQP§1.4真值表与等价公式由上二例可见，２个命题变元有４组真值指派；３个命题变元有23＝８组真值指派，ｎ个则有个2n个真值指派。§1.4真值表与等价公式３．命题公式的永真式、永假式和可满足式[定义]设公式Ａ中有n个不同的原子变元

p1,…pn,(n为正整数)。该变元组的任意一组确定的值（u1,…un）称为Ａ关于p1,…pn的一个完全指派，其中ui或为Ｔ，或为Ｆ。如果对于Ａ中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式Ａ的关于该变元组的部分指派。[定义]使公式取真的指派称为成真指派。§1.4真值表与等价公式[定义]如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式。既不是永真式，又不是永假式，则称此命题公式是可满足式。讨论：（１）永真式的否定为永假式（¬Ｔ＝Ｆ）；永假式的否定为永真式（¬Ｆ＝Ｔ）。（２）二个永真式的析取、合取、蕴含、等价均为永真式。§1.4真值表与等价公式二．等价式[定义]如果对两个公式Ａ，Ｂ不论作何种指派，它们真值均相同，则称Ａ，Ｂ是逻辑等价的，亦说Ａ（Ｂ）等价于Ｂ（Ａ）,并记作：ＡＢ§1.4真值表与等价公式例：Ｐ∨¬ＰＱ∨¬ＱTTTTTTTFTTFTTTFFQ∨¬QP∨¬PPQ§1.4真值表与等价公式例：判断公式A：(PQ)(PQ)与

B：(PR)(PR)是否等价。解：列该公式的真值表：§1.4真值表与等价公式FFFTTFTTFFFFFTFFFTTTFFFFFTTTFFFTFFFTFFTFFTTFTTTTTTTTFFTTTTTFTTTTFTTTTTTTTFFTTTTTTFTTFTTTBAPRPRRPQPQQRQP§1.4真值表与等价公式[定理]

命题公式ＡＢ的充要条件是Ａ↔Ｂ为永真式。说明：“”为等价关系符，ＡＢ表示Ａ和Ｂ有等价关系。ＡＢ不为命题公式“↔”为等价联结词（运算符），Ａ、Ｂ为命题公式，则（Ａ↔Ｂ）也为一命题公式。

§1.4真值表与等价公式证明：（１）充分性：Ａ↔Ｂ为永真式，即Ａ、Ｂ有相同的真值，所以ＡＢ。（２）必要性：ＡＢ，即Ａ、Ｂ有相同的真值表，所以Ａ↔Ｂ为永真式。例：证明¬¬ＰＰ；Ｐ→Ｑ¬Ｐ∨Ｑ§1.4真值表与等价公式TTTTTTTTFTFTTTFTTTTFTFTFTTTFTFFFP→Q¬P∨Q¬¬PPQP由定理可知：ＡＡ若ＡＢ，则ＢＡ若ＡＢ，ＢC，则ＡＣ§1.4真值表与等价公式下面列出１５组等价公式（1）双重否定律¬¬ＰＰ（2）同等律Ｐ∨ＰＰ；ＰΛＰＰ（3）交换律Ｐ∨ＱＱ∨Ｐ；ＰΛＱＱΛＰ；ＰＱＱＰ（4）结合律（Ｐ∨Ｑ）∨ＲＰ∨（Ｑ∨Ｒ）；（ＰΛＱ）ΛＲＰΛ（ＱΛＲ）；（ＰＱ）ＲＰ（ＱＲ）§1.4真值表与等价公式（5）分配律ＰΛ（Ｑ∨Ｒ）（ＰΛＱ）∨（ＰΛＲ）；Ｐ∨（ＱΛＲ）（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ）（6）摩根律

¬（Ｐ∨Ｑ）¬ＰΛ¬Ｑ；

¬（ＰΛＱ）¬Ｐ∨¬Ｑ（7）吸收律Ｐ∨（ＰΛＱ）Ｐ；ＰΛ（Ｐ∨Ｑ）Ｐ§1.4真值表与等价公式（8）蕴含律Ｐ→Ｑ¬Ｐ∨Ｑ（9）等价律ＰＱ（Ｐ→Ｑ）Λ（Ｑ→Ｐ）（10）零律Ｐ∨ＴＴ；ＰΛＦＦ（11）同一律Ｐ∨ＦＰ；ＰΛＴＰ（12）互补律Ｐ∨¬ＰＴ；ＰΛ¬ＰＦ（13）输出律ＰΛＱ→ＲＰ→（Ｑ→Ｒ）§1.4真值表与等价公式（14）归缪律（Ｐ→Ｑ）Λ（Ｐ→¬Ｑ）¬Ｐ（15）逆反律Ｐ→Ｑ¬Ｑ→¬Ｐ说明：（１）证明上述１５组等价公式的方法可用真值表法，把改为所得的命题公式为永真式，则成立。§1.4真值表与等价公式（2）Λ、∨、均满足结合律，则在单一用Λ、∨、联结词组成的命题公式中，括号可以省去。（3）每个等价模式实际给出了无穷多个同类型的具体的命题公式。例如：(PQ)(PQ)，((PQ)(RS))((PQ)(RS)，((PQ)R)((PQ)R)§1.4真值表与等价公式２．置换规则[定义]给定一命题公式Ｂ，其中P1、P2．．．Pn

是Ｂ中的原子命题变元，若（1）用某些命题公式代换Ｂ中的一些原子命题变元Pi

（2）用命题公式Ａi代换Pi，则必须用Ａi代换Ｂ中的所有Pi由此而得到的新的命题公式Ａ称为命题公式Ｂ的代换实例§1.4真值表与等价公式讨论定义：（１）用命题公式只能代换原子命题变元，而不能去代换分子命题公式。（２）要用命题公式同时代换同一个原子命题变元。（３）永真式的代换实例仍为永真式；反之代换实例为永真式时，则不能断定原公式也一定是永真式。§1.4真值表与等价公式例：Ｐ∨¬Ｐ为一永真式，若用任何命题公式代换Ｐ，则仍为永真式Ｐ→Ｑ为一个可满足的命题公式，若用Ｐ代换Ｑ，则得（Ｐ→Ｐ）为永真式，但（Ｐ→Ｑ）并不是永真式。（４）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式§1.4真值表与等价公式例１．设Ｂ：Ｐ→（¬QΛＰ）若用（ＲＳ）代换Ｂ中的Ｐ，得Ａ：（Ｒ↔Ｓ）→（¬QΛ（ＲＳ））是Ｂ的代换实例，而Ａ’：（Ｒ↔Ｓ）→（¬QΛＰ）不是B的代换实例。例２．Ｐ→¬Ｑ的代换实例有：（ＲΛ¬Ｓ）→¬Ｍ，（ＲΛ¬Ｓ）→Ｐ，Ｑ→¬（Ｐ→¬Ｑ）等所以，一个命题公式的代换实例有无限个。§1.4真值表与等价公式下面讨论取代过程（置换规则）：[定义]给定一命题公式Ａ，Ａ’是Ａ的任何部分，若Ａ’也是一命题公式，则称Ａ’是Ａ的子命题公式。例：Ａ：（Ｐ∨Ｑ）→（Ｑ∨（ＲΛ¬Ｓ））Ａ的子命题公式有：Ｐ、Ｑ、Ｒ、¬Ｓ、（Ｐ∨Ｑ）、ＲΛ¬Ｓ）、（Ｑ∨（ＲΛ¬Ｓ））、（Ｐ∨Ｑ）→（Ｑ∨（ＲΛ¬Ｓ））等。§1.4真值表与等价公式[定理]给定一命题公式Ａ，Ａ’是Ａ的子公式。设B’是一命题公式，若Ａ’

B’，并用B’取代Ａ中的Ａ’，从而生成一新的命题公式B，则ＡB。从定理可见：一个命题公式A，经多次取代，所得到的新公式与原公式等价。例：证明：Ｐ→（Ｑ→Ｒ）Ｐ→（¬Ｑ∨Ｒ）¬Ｐ∨¬Ｑ∨¬Ｒ§1.4真值表与等价公式¬（ＰΛＱ）∨Ｒ（ＰΛＱ）→Ｒ例：证明：（（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ）∨（¬ＰΛ¬Ｒ）为一永真式§1.4真值表与等价公式证明：原式：（（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ）∨（¬ＰΛ¬Ｒ）（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）））∨¬（Ｐ∨Ｑ）∨¬（Ｐ∨Ｒ）

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））Ｔ∵它是ＰΛ¬Ｐ（永真式）的代换实例，永真式的代换实例仍为永真式！§1.5重言式与蕴含式[定义]命题公式Ａ称为蕴含命题公式Ｂ，当且仅当Ａ→Ｂ是一个永真式，记作：ＡＢ说明：“ＡＢ”读作“Ａ永真蕴含Ｂ”，“Ａ蕴含Ｂ”，“Ａ能推得Ｂ”“”是关系符，ＡＢ不为命题公式。例：证明：ＰＰ∨Ｑ；ＰΛＱ

P

（１）列出真值表证明：Ｐ→（Ｐ∨Ｑ）和（ＰΛＱ）→Ｐ为永真式§1.5重言式与蕴含式（２）可用等价公式证：Ｐ→（Ｐ∨Ｑ）¬Ｐ∨（Ｐ∨Ｑ）

T（ＰΛＱ）→Ｐ¬（ＰΛＱ）∨Ｐ

¬Ｐ∨

¬Ｑ∨Ｐ

TTTTTTTTTFTTTTTFTFTFFTTTFFTFFTFFF（ＰΛＱ）→ＰＰ→（Ｐ∨Ｑ）QP§1.5重言式与蕴含式[定理]设Ａ、Ｂ是二个命题公式ＡＢ的充分必要条件是ＡＢ且ＢＡ。证明：若ＡＢ，则ＡＢ为一永真式由定律：（ＡＢ）（Ａ→Ｂ）Λ（Ｂ→Ａ）∴（Ａ→Ｂ）且（Ｂ→Ａ）也为一永真式即：ＡＢ且ＢＡ成立反之ＡＢ且ＢＡ则ＡＢ也成立此定理把“”和“”之间建立了相应的关系。§1.5重言式与蕴含式下面给出常用的永真蕴含式I1ＰＰ∨Ｑ（ＱＰ∨Ｑ）I2

ＰΛＱＰ（ＰΛＱＱ）I3ＰΛ（Ｐ→Ｑ）ＱI4（Ｐ→Ｑ）Λ¬Ｑ

¬ＰI5¬ＰΛ（Ｐ∨Ｑ）ＱI6（Ｐ→Ｑ）Λ（Ｑ→Ｒ）（Ｐ→Ｒ）I7（Ｐ→Ｑ）Λ（Ｒ→Ｓ）（ＰΛＲ→ＱΛＳ）I8（ＰＱ）Λ（ＱＲ）（ＰＲ）I9¬P

Ｐ→Ｑ§1.5重言式与蕴含式I10ＱＰ→ＱI11¬（Ｐ→Ｑ）ＰI12

¬（Ｐ→Ｑ）

¬ＱI13（Ｐ∨Ｑ）Λ（Ｐ→Ｒ）Λ（Ｑ→Ｒ）Ｒ证明上述永真蕴含式的方法有三种：（１）把“”关系符改为“→”联结词，证明它为永真式。

(a)真值表法

(b)命题演算法

§1.5重言式与蕴含式（２）找出使单条件命题前件为“Ｔ”的所有真值指派，试看能否导致后件均为“Ｔ”，若为“Ｔ”，则永真蕴含关系成立。TTTFFTTTFTFFP→QQP§1.5重言式与蕴含式例：ＰΛ（Ｐ→Ｑ）Ｑ前件为“Ｔ”的所有指派为Ｐ、（Ｐ→Ｑ）均为“Ｔ”，Ｐ→Ｑ为“Ｔ”，∵Ｐ为“Ｔ”，∴Ｑ也应为“Ｔ”，∴ＰΛ（Ｐ→Ｑ）Ｑ成立（３）＊找出使单条件命题的后件均为“Ｆ”的所有真值指派，试看前件的所有真值是否为“Ｆ”，若是，则蕴含成立。§1.5重言式与蕴含式例：¬ＱΛ（Ｐ→Ｑ）

¬Ｐ后件为“Ｆ”的所有条件是：Ｐ为“Ｔ”，代入前件得（ⅰ）若Ｑ为Ｔ，则¬ＱΛ（Ｐ→Ｑ）为“Ｆ”；（ⅱ）若Ｑ为Ｆ，则¬ＱΛ（Ｐ→Ｑ）为“Ｆ”；∴¬ＱΛ（Ｐ→Ｑ）

¬Ｐ成立若后件简单则可选用(3)；若前件简单则可选用(2)。二种方法是互为独立的，只需使用一种证明就行。§1.5重言式与蕴含式讨论一下永真式可得出三个结论：（１）若一个命题公式等价于一个永真式，则该公式一定为永真式。（２）若一个永真的命题公式永真蕴含一个命题公式，则此命题公式一定也为永真式。（３）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。§1.5重言式与蕴含式[定理]给定命题公式Ａ、Ｂ、Ｃ，若ＡＢ，且ＢＣ，则ＡＣ。证明：∵ＡＢ，且ＢＣ，∴（Ａ→Ｂ）Λ（Ｂ→Ｃ）为永真式，由I6：（Ａ→Ｂ）Λ（Ｂ→Ｃ）（Ａ→Ｃ），（Ａ→Ｃ）也为永真式；即，ＡＣ成立§1.5重言式与蕴含式[推论]若ＡB1

、B1

B2．．．．．．Bm

Ｂ，则ＡＢ。[定理]给定一个命题公式Ａ、Ｂ、Ｃ，若ＡＢ,ＡＣ，则Ａ（ＢΛＣ）证明：∵ＡＢΛＡＣ，∴（Ａ→Ｂ）Λ（Ａ→Ｃ）为永真式，由条件，若Ａ一定为“Ｔ”，则Ｂ、Ｃ均为“Ｔ”，∴Ａ→（ＢΛＣ）也为“Ｔ”，结论：Ａ（ＢΛＣ）为“Ｔ”。§1.5重言式与蕴含式上述也可用等价公式证明它：（Ａ→Ｂ）Λ（Ａ→Ｃ）（¬Ａ∨Ｂ）Λ（¬Ａ∨Ｃ）¬Ａ∨（ＢΛＣ）Ａ→（ＢΛＣ）也为永真式∴Ａ（ＢΛＣ）成立[定义]设H1,H2….Hm,Ｑ均为命题公式，若（H1ΛH2Λ…

ΛHm

）

Ｑ，则称H1,H2….Hm,共同蕴含Ｑ，并记作：

H1,H2….Hm

Ｑ。

§1.5重言式与蕴含式

[定理]若（H1ΛH2Λ…Hm

）,P

Ｑ，则（H1ΛH2Λ…Hm

）

（Ｐ→Ｑ）。

证明：（H1ΛH2Λ…ΛHm

ΛP）→Ｑ¬（H1ΛH2Λ…ΛHm

ΛP）∨Q（¬

H1∨

¬

H2∨

…

∨¬

Hm

）

∨（¬

P∨Q）¬（H1ΛH2Λ…ΛHm

）

∨（

P→Q）

H1Λ

H2Λ

….Λ

Hm→（Ｐ→Ｑ）也为永真式∴（H1Λ,H2Λ

….Λ

Hm

）（Ｐ→Ｑ）成立

§1.6其他联结词１．其他命题联结词：(1)不可兼或（异或，异）(a)符号:(⊕),ＰＱ,读作“Ｐ异或Ｑ”(b)定义:（由真值表）(c)异或的性质：ＰＱ（¬ＰΛＱ）∨（¬ＱΛＰ）（Ｐ∨Ｑ）Λ（¬Ｐ∨¬Ｑ）

¬（ＰＱ）ＱＰ(ＰＱ)ＲＰ(ＱＲ)FTTTFTTTFFFFP

QQP§1.6其他联结词ＰΛ（ＱＲ）（ＰΛＱ）（ＰΛＲ）（Λ对可分配的）ＰＰＦ，Ｐ

¬ＰＴ，ＦＰＰ，ＴＰ

¬Ｐ若ＰＱＲ，则有：ＰＲＱＲＰＲＱＰＱＲＱＰＲ，ＰＱＲＦ§1.6其他联结词(２)“与非”联结词：(a)符号↑,Ｐ↑Ｑ读作“Ｐ与Ｑ的否定”或“Ｐ与非Ｑ”(b)定义：（由真值表）（Ｐ↑Ｑ）¬（Ｐ∧Ｑ）FTTTFTTTFTFFP↑QQP§1.6其他联结词(c)性质：（Ｐ↑Ｑ）（Ｑ↑Ｐ）（Ｐ↑Ｐ）¬Ｐ（Ｐ↑Ｑ）↑（Ｐ↑Ｑ）（Ｐ∧Ｑ）（Ｐ↑Ｐ）↑（Ｑ↑Ｑ）（Ｐ∨Ｑ）Ｐ↑（Ｑ↑Ｒ）¬Ｐ∨（Ｑ∧Ｒ）不可结合（Ｐ↑Ｑ）↑Ｒ（Ｐ∧Ｑ）∨¬Ｒ不可结合Ｐ↑Ｔ¬Ｐ，Ｐ↑ＦＴ§1.6其他联结词(３)“或非”联结词：(a)符号：“↓”（Ｐ↓Ｑ）读作：“Ｐ或Ｑ的否定”或“Ｐ或非Ｑ”(b)定义（由真值表给出）：（Ｐ↓Ｑ）

¬（Ｐ∨Ｑ）FTTFFTFTFTFFＰ↓ＱQP§1.6其他联结词(c)性质：Ｐ↓ＱＱ↓Ｐ（可交换的）Ｐ↓Ｐ¬Ｐ（Ｐ↓Ｑ）↓（Ｐ↓Ｑ）Ｐ∨Ｑ（Ｐ↓Ｐ）↓（Ｑ↓Ｑ）Ｐ∧ＱＰ↓（Ｑ↓Ｒ）¬Ｐ∧（Ｑ∨Ｒ）不可结合（Ｐ↓Ｑ）↓Ｒ（Ｐ∨Ｑ）∧¬Ｒ不可结合Ｐ↓Ｆ¬Ｐ；Ｐ↓ＴＦ(d)由（２）和（３）中的性质可见，↑和↓是互为对偶的。§1.6其他联结词(4)“蕴含否定”联结词：(a)符号：(b)定义(由真值表给出）：PQ(PQ)“”cFFFFTFTFTFTTPQQPcc§1.6其他联结词(１)不同真值表的命题公式：按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表：(a)若命题变元只有一个Ｐ，则用联结词组成的命题公式由四种不同的真值表，即为：

TFTFTTTFFF3210P§1.6其他联结词所有依赖于Ｐ的命题公式均等价于这四个中的一个(b)若有二个命题变元Ｐ、Ｑ，则命题公式的不同真值表有：222=24=16种。推广到一般：若有ｎ个变元的命题公式，则可构成不同的真值表为22n（个）。§1.6其他联结词（２）二元运算中的全部联结词总结：

¬、∧、∨、→、是五个基本联结词。到此为止，一个符号系统已定义完毕，它们是：命题变元:Ａ、Ｂ…Ｘ、Ｙ、Ｚ值

:Ｆ、Ｔ

运算符:¬、∧、∨、→、、、↑、↓、括号:（）关系符:、。C§1.6其他联结词３．全功能联结词集合：[定义]一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出来，则称此联结词集合为全功能联结词集合。[定义]设有一联结词集合Ａ，若（１）用Ａ中的联结词的等价式能表达任何的一个命题公式；（２）删除Ａ中的任一联结词，从而形成一个新的联结词集合Ａ’，至少有一个命题公式Ｂ不能用Ａ’中的联结词的等价式来表示，则称A为最小的全功能联结词集合。§1.6其他联结词我们可以证明：{¬，∨}；{¬，∧}；{¬，→}；{↑}；{↓}均为全功能联结词集合，且均是最小的全功能联结词集合。例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：§1.6其他联结词（Ｐ→Ｑ）

¬Ｐ∨Ｑ{¬，∨}¬¬（¬Ｐ∨Ｑ）

¬（Ｐ∧¬Ｑ）{¬，∧}

¬¬（Ｐ→Ｑ）{¬，→}

¬(ＰＱ){¬，}

¬

¬

（¬Ｐ∨Ｑ）（（Ｐ↓Ｐ）↓Ｑ）↓（（Ｐ↓Ｐ）↓Ｑ）

{↓}

¬

¬

（¬Ｐ∨Ｑ）¬

（Ｐ∧¬Ｑ）Ｐ↑（Ｑ↑Ｑ）

{↑}→c→c§1.7对偶与范式３．对偶原理（对偶定律）[定义]给定二个命题公式Ａ和A*

，若用Λ代换∨，用∨代换Λ，用Ｔ代换Ｆ，用Ｆ代换Ｔ，其中一个命题公式由另一个命题公式得来，则称Ａ和A*是互为对偶的，而联结词Λ和∨也是互为对偶的例：写出下列命题公式的对偶式：Ｐ∨（ＱΛＲ）ＰΛ（Ｑ∨Ｒ）Ｐ∨ＦＰ对偶式A*ＰΛＴＰＰ∨ＴＴＰΛＦＦ

§1.7对偶与范式讨论定义：（１）若命题公式中有联结词，，则必须把化成由联结词Λ，∨，组成的等价的命题公式，然后求它的对偶式；例：求(PQ)(PR)的对偶式§1.7对偶与范式（２）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。例：（ＰΛＱ）∨Ｒ对偶式写成（Ｐ∨Ｑ）ΛＲ，而不能写成Ｐ∨ＱΛＲ§1.7对偶与范式[定理]（摩根推广定理）设Ａ和A*为对偶式P1,P2．．．Pn

是出现在Ａ和A*中的所有原子命题变元，，于是有：¬Ａ（P1，P2．．．Pn）A*

（¬P1，¬P2．．．¬Pn）——（1）Ａ（¬P1，¬P2．．．¬Pn）¬A*（P1，P2．．．Pn）——（２）§1.7对偶与范式证明：由摩根定理

¬（Ｐ∨Ｑ）¬ＰΛ¬Ｑ—（１）

¬（ＰΛＱ）¬Ｐ∨¬Ｑ—（２）∴不难看出：一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。 例：设Ａ（Ｐ，Ｑ，Ｒ）¬ＰΛ¬

（Ｑ∨Ｒ），验证上述定理：§1.7对偶与范式证明：(１)Ａ（Ｐ，Ｑ，Ｒ）¬ＰΛ¬ＱΛ¬Ｒ∴¬Ａ（Ｐ，Ｑ，Ｒ）Ｐ∨Ｑ∨ＲA*（Ｐ，Ｑ，Ｒ）¬Ｐ∨¬Ｑ∨¬ＲA*（¬Ｐ，¬Ｑ，¬Ｒ）Ｐ∨Ｑ∨Ｒ（２）Ａ（¬Ｐ，¬Ｑ，¬Ｒ）ＰΛＱΛＲ¬A*（Ｐ，Ｑ，Ｒ）¬（¬Ｐ∨Ｑ∨¬Ｒ）

ＰΛＱΛＲ有Ａ（¬Ｐ，¬Ｑ，¬Ｒ）

¬A*（Ｐ，Ｑ，Ｒ）§1.7对偶与范式[定理]若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若ＡＢ，则A*B*成立。证明：已知：Ａ、Ｂ为任一命题公式，且ＡＢ，要证明A*B*设：P1、P2．．．Pn

是出现在Ａ和Ｂ中的原子命题变元，§1.7对偶与范式由ＡＢ，即Ａ（P1，P2．．．Pn）Ｂ（P1，P2．．．Pn）∴¬Ａ（P1，P2．．．Pn）¬Ｂ（P1，P2．．．Pn）由摩根推广定理∴Ａ*（¬P1，¬P2．．．¬Pn）Ｂ*（¬P1，¬P2．．．¬Pn）§1.7对偶与范式∴Ａ*（¬P1，¬P2．．．¬Pn）

Ｂ*（¬P1，¬P2．．．¬Pn）为永真式＊前面讲过永真式的代换实例仍为永真式，所以用¬Pi代换A*和B*中的Pi

（1≤i≤n)则得：Ａ*（¬

¬P1，¬

¬P2．．．¬

¬Pn）

Ｂ*（¬

¬P1，¬

¬P2．．．¬

¬Pn）即为：Ａ*（P1，P2．．．Pn）

Ｂ*（P1，P2．．．Pn）§1.7对偶与范式例：证明：（１）¬（ＰΛＱ）→（¬Ｐ∨（¬Ｐ∨Ｑ））（¬Ｐ∨Ｑ）（２）（Ｐ∨Ｑ）Λ（¬ＰΛ（¬ＰΛＱ））（¬ＰΛＱ）证明：（１）左边¬¬(ＰΛＱ）∨（¬Ｐ∨（¬Ｐ∨Ｑ））

（ＰΛＱ）∨（¬Ｐ∨Ｑ）（Ｐ∨¬Ｐ∨Ｑ）Λ（Ｑ∨¬Ｐ∨Ｑ）（¬Ｐ∨Ｑ）§1.7对偶与范式（２）左边（Ｐ∨Ｑ）Λ（¬ＰΛＱ）（ＰΛ¬ＰΛＱ）∨（ＱΛ¬ＰΛＱ）（¬ＰΛＱ）结论：（１）和（２）是互为对偶的。§1.7对偶与范式如何判定命题公式为永真式、永假式和可满足式或二个命题公式等价，归纳有三种方法：（1）真值表法：对于变元的所有真值指派，看对应命题公式的真值。（2）命题演算方法：化简命题公式至最简式，看是否存在和（Ｐ∨¬Ｐ）、（Ｐ∧¬Ｐ）等价，若不则为可满足的。（3）范式方法：本节就介绍此法。§1.7对偶与范式什么叫范式把命题公式化归为一种标准的形式，称此标准形式为范式。什么叫判定以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。讨论范式和主范式的目的就是为了进行判定。

下面讨论如何求析取范式和合取范式同一命题公式可以有各种相互等价的表达形式。如：PQ

PQ(PQ)(P∧P)

(PQP)∧(PQP)。为了把命题公式规范化，下面讨论命题公式的范式。定义：一个命题公式称为合取范式，当且仅当具有形式：A1∧A2∧…∧An，(n≥1)

其中A1,A2,…,An都是由命题变元或其否定所组成的析取式。例如：(PQ)∧(PQ)∧(PQ)是合取范式定义：一个命题公式称为析取范式，当且仅当它具有形式：A1A2…An，(n≥1)

其中A1,A2,…,An都是由命题变元或其否定所组成的合取式。例如：(P∧Q∧R)(P∧Q∧R)(Q∧R)R是析取式。如何求析（合）取范式？将公式中的联结词化归成，∧，；利用德.摩根律将否定符号直接移到各个命题变元之前。利用分配律、结合律将公式归约为合取范式或析取范式。例：求公式P(P∧Q)的析取范式与合取范式解：合取范式

原式(P(P∧Q))

∧((P∧Q)P)(P(P∧Q))∧((P∧Q)P)

(PP)∧(PQ)∧(PQP)析取范式：原式(P∧(P∧Q))(P∧(P∧Q))(P∧P∧Q)(P∧(PQ))(P∧Q)(P∧P)(P∧Q)(P∧Q)P(P∧Q)

§1.7对偶与范式（１）利用等价公式：化去“→”、“”联结词，把命题公式变为与其等价的用{¬，∧，∨}表达的公式。

例:Ｐ→Ｑ¬Ｐ∨Ｑ，Ｐ↔Ｑ（Ｐ∧Ｑ）∨（¬Ｐ∧¬Ｑ）

（¬Ｐ∨Ｑ）∧（Ｐ∨¬Ｑ）（２）将“¬”深入到原子命题变元之前，并使变元之前最多只有一个“¬”词。例：¬（¬Ｐ∨¬Ｑ）¬

¬Ｐ∧¬

¬ＱＰ∧Ｑ§1.7对偶与范式