离散数学-命题逻辑【稻谷书苑】

《离散数学-命题逻辑【稻谷书苑】》由会员分享，可在线阅读，更多相关《离散数学-命题逻辑【稻谷书苑】（115页珍藏版）》请在装配图网上搜索。

1、离散数学离散数学第第一部分一部分-命题逻辑命题逻辑1教学运用课程性质离散数学离散数学（又称计算机数学计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。2教学运用课程目标离散数学离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。3教学运用与其他课程的关系离散数学离散数学与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切的联系。它是这些课程的先导和基础课程。4教学运用n离散数学q高等教育出版社,2008

2、n屈婉玲著nDiscrete Mathematics and Its Applications 6th Edition qKenneth H Rosen教材与参考书5教学运用课程内容本课程根据大纲的内容和相关独立性，可分为四大部分第一部分 数理逻辑数理逻辑包括命题逻辑;谓词逻辑第二部分集合论集合论包括集合与关系;函数6教学运用课程内容第三部分代数系统代数系统 包括代数结构;格与布尔代数第四部分图论图论 7教学运用学习方法课程特点：定义、定理多本课内容定义定义定理定理习题习题为了学好这门课，要求：（）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；（）在复习基础上，做好课外作业。同学之间可以讨

3、论，但要弄懂弄通。（3）做好课堂笔记。（4）结合专业实践，做到融会贯通。8教学运用学习建议平时考勤20%平时作业20%期末考试60%考核方式课前预习+课上笔记+课下习题+经典文献阅读9教学运用第一篇 数理逻辑n数理逻辑是用数学语言表述的推理形式有效性的学问。n命题逻辑、谓词逻辑n数理逻辑使用特制的表意符号，亦称为符号逻辑。n逻辑研究对象逻辑真值q真，表示为T或1q假，表示为F或0n正确的推理形式q正确前提q正确的推理形式q必然得出正确的结论10教学运用第一章 命题逻辑 1.1 命题与联接词n什么是命题？n命题的运算符是什么？n如何表示命题？n有多少种命题的运算符？11教学运用语句表达n陈述句n

4、疑问句n祈使句n感叹句雪是白的。雪是白的。2 2是奇数。是奇数。X+Y5X+Y5。你是谁？你是谁？我正在说谎。我正在说谎。北京是中国的首都。北京是中国的首都。前进！前进！天空多漂亮天空多漂亮!特点：有的语句可以特点：有的语句可以判断真假。判断真假。12教学运用自然语言、命题n语言是人们思维和交际的工具，也是一种表达观念的符号系统。n自然语言由各种句式组成，如陈述句、疑问句、感叹句、祈使句等等。n陈述句是陈述一个事实或者说话人的看法，它包括肯定句和否定句两种。一般来说，仅有陈述句能够确定句子的意义是真还是假。n命题表达为具有确定真假意义的陈述句。13教学运用命题示例n雪是白的。n2是奇数。nX+

5、Y5。n你是谁？n我正在说谎。n北京是中国的首都。n每个不小于6的偶数都是两个奇素数之和（歌德巴赫猜想）n21世纪有人住在月球上。n他很高。n一个自然数不是合数就是素数命题，真命题，真 命题，假命题，假不确定，非命题不确定，非命题疑问句，非命题疑问句，非命题悖论，非命题悖论，非命题命题，真命题，真命题，真，有唯一真假值。命题，真，有唯一真假值。命题，真，有唯一真假值。命题，真，有唯一真假值。无法确定，非命题无法确定，非命题命题，假，命题，假，1 1不是合数和素数不是合数和素数14教学运用命题的抽象表示n自然语言具有二义性比如：郑州市长远规划n命题逻辑不关注语句的内容，也不关注语句为何是真或为假

6、，而是仅仅关注语句能够为真或假。n命题的抽象q用小写字母表示命题，取值为0,1。n命题真值q陈述句的意义为真，称为真命题，真值为1或T。q陈述句的意义为假，称为假命题，真值为0或F。n命题逻辑的研究对象命题。n数理逻辑从形式结构方面研究命题。15教学运用自然语言复杂语句构造n简单语句+联接词（连词、介词）=复杂语句n语句联接词q并且q或q否定q如果,则。q当且仅当q既不，也不。n运算思维16教学运用简单命题与复合命题n简单命题q由简单陈述句表述的命题称为简单命题。q命题逻辑不再进一步分析简单命题的内部结构np:孔子是圣人n语句联接词q并且q或q否定q如果,则。q当且仅当q既不，也不。n复合命题

7、q用联接词可以将若干个简单句组合成复合句。q子命题17教学运用命题逻辑如何运算？n数计算启示q自然数n运算：+、*q整数n运算：+、-、*q有理数n运算：+、-、*、/n命题逻辑q真1，假0n运算：q？18教学运用逻辑联结词n定义q0和1称为0元函数。设n0,称为0,1n到0,1的函数为n元函数，真值函数也称为联结词。n命题的操作符（联结词）q非q与q或q如果,则。q当且仅当q异或n真值表q真值形式可以用图表来说明。这种表称为真值图表。n0元函数q0，1n1元函数qn2元函数q、19教学运用逻辑联结词 n命题p的否定记为p,读作非p真值表真值表n逻辑联接词的含义n自然语言中，并非的含义举例：每

8、一种生物均是动物。F ：有一些生物不是动物。T这里 不能讲成“每一种生物都不是动物”。20教学运用逻辑联结词 真值表真值表npq称为p和q的合取n读作p且qn逻辑联接词的含义n自然语言中，并且的含义n都真(p:1)才真(q:1)21教学运用n举例：q(1)p：王华的成绩很好q：王华的品德很好。则pq：王华的成绩很好并且品德很好。q(2)p：我们去种树q：房间里有一台电视机则pq：我们去种树与房间里有一台电视机。q(3)p：今天下大雨q：3+3=6则pq：今天下大雨和3+3=6由例(2)(3)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间

9、。逻辑联结词 22教学运用逻辑联结词 真值表真值表npq称为p和q的析取，读作p或qn逻辑联接词的含义n自然语言中，或的含义n都假(p:0)才假(q:0)n举例：今天晴天或者下雨23教学运用逻辑联结词 真值表真值表n逻辑联接词的含义n自然语言中，如果,则.的含义n真(1)假(0)才假(0)npq称为p蕴涵qn读作p则qnp称为前件nq称为后件24教学运用n举例：q(1)p：我拿起一本书q：我一口气读完了这本书pq：如果我拿起一本书，则我一口气读完了这本书。q(2)p：Alice当选总统q：Alice减税pq：如果Alice当选总统，那么Alice将减税q(3)p：今天打雷了q：1+1=2pq：

10、如果今天打雷，那么1+1=2逻辑联结词 25教学运用逻辑联结词 真值表真值表npq称为p与q等值，读作p当且仅当q,p与q互蕴含。npq=(pq)(qp)n逻辑联接词的含义n自然语言中，当且仅当的含义n相同才1，不同则026教学运用逻辑联结词 n举例设：ABC是等腰三角形：ABC有两只角相等：ABC是等腰三角形当且仅当有两只角相等。27教学运用逻辑联结词 nAlice是男孩或女孩。（不可兼或）比较李明学习英语或学习法语。(可兼或)真值表真值表npq称为p与q异或（不可兼或），读作p异或q。npq=(pq)(qp)n不同才1，相同则028教学运用区分“可兼或”与“不可兼或”“可兼或”即p或q为“

11、T”时（pq）为“T”，是析取。例如：灯泡有故障或开关有故障。今晚写字或看书。今天下雨或打雷。以上例句均为“可兼或”。29教学运用“不可兼或”即p和q的真值不同时，pq为T。（异或用“”表示）不是析取。区分“可兼或”与“不可兼或”例：Alice通过电视看杂技或或到剧场看杂技。Alice乘火车去北京或或乘飞机去北京。以上两句均为“不可兼或”。30教学运用命题联结词在使用中的优先级（）先括号内，后括号外（）运算时联结词的优先次序为：（由高到低）（）联结词按从左到右的次序进行运算（）最外层的括号一律均可省去（pqr）可写成pqr31教学运用命题联结词注意事项n（1）五个联结词的含义与日常生活中的联结

12、词的含义大致相同。n（2）“或”可分为可兼或（）和异或（）（不可兼或）n（3）“”为一元运算，其余四个均为二元运算。n（4）“”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。n（5）命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。32教学运用命题符号化以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。步骤如下：找出各简单命题，分别符号化。找出各联结词，把简单命题逐个联结起来。33教学运用命题符号化例.将下列命题符号

13、化：（1）李明是计算机系的学生，他住在312室或313室（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了车站。（4）只有一个角是直角的三角形才是直角三角形。（5）老王或小李中有一个去上海出差。（6）除非今天下雨，否则我去踢球。34教学运用命题符号化解：（1）首先用字母表示简单命题。p：李明是计算机系的学生。q：李明住在312室。r：李明住在313室。该命题符号化为：p（qr）（2）张三和李四是朋友。是一个简单句该命题符号化为：p35教学运用命题符号化（3）首先用字母表示简单命题。p：交通堵塞。q：老王准时到达了车站。该命题符号化为：pq（4）首先用字母表示简单命题。p：三角形

14、的一个角是直角。q：三角形是直角三角形。该命题符号化为：pq36教学运用命题符号化（5）首先用字母表示简单命题。p：老王去上海出差。q：小李去上海出差。该命题符号化为pq也可符号化为：（pq）（pq）或者（pq）（pq）37教学运用命题符号化约定：约定：（）我们只注意命题的真假值，而不再去注意命题的汉语意义。（）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。38教学运用1.2 命题公式命题公式命题公式命题常元：命题常元：表示确定的命题T，F。命题变元：命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母表示。命题公式命题公式：由命题变元、常元、联结词、括号

15、，以规定的格式联结起来的字符串。39教学运用命题公式构造法则定义定义命题公式(wff)可按下述法则来生成：）单个的命题变元是一个命题公式。）若是命题公式，也为命题公式。）若、是命题公式，则（）、（）、（）、（）均为命题公式。）当且仅当有限次使用（）（）（）所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。40教学运用命题公式的真值表例如：(PQ)，(P(QR)，(PQ)R)，P都是命题公式。而(P)，(P)都不是命题公式命题公式的真值表命题公式的真值表:命题变元用特定的命题来取代，这一过程称为对该命题变元进行真值指派真值指派。命题公式可以看成是一个以真假值为定义域和真假值为值

16、域的一个函数。写成(x)41教学运用命题公式的真值表例如：公式P(QR)定义三元函数Y(P，Q，R)P(QR)定义定义命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。42教学运用命题公式真值表构造方法构造真值表的步骤如下：1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。2)按照从低到高顺序写出命题公式的各层次。3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。43教学运用命题公式真值表构造方法例构造命题公式（）R）的真值表例2构造命题公式P (PQ)的真值表例3构造命题公式(PQ)Q 的真值表个命题变元有组真值指派；个命题变元有23组真值指派，个

17、则有个2n个真值指派。44教学运用命题公式的永真式、永假式和可满足式定义定义设公式中有n个不同的原子变元p1,pn,(n为正整数)。该变元组的任意一组确定的值（u1,un）称为关于p1,pn的一个完完全指派全指派，其中ui或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于该变元组的部分指派部分指派。定义定义使公式取真的指派称为成真指派成真指派。45教学运用命题公式的永真式、永假式和可满足式定义如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式永真式。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式永假式。不是永假式的公式，

18、则称此命题公式是可满足式可满足式。讨论：（）永真式的否定为永假式（）；永假式的否定为永真式（）。（）二个永真式的析取、合取、蕴含、等价均为永真式。46教学运用第二章 命题逻辑等值演算 2.1 等值式n有哪些基本的等值式？n如何进行等值演算？n析取范式与合取范式，主析取范式与主合取范式的求解n什么是联结词完备集？47教学运用2.1 等值式n定义2.1 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式n几点说明：1.定义中，A,B,均为元语言符号2.A或B中可能有哑元出现.3.例如 (pq)(pq)(rr)r为左边公式的哑元.4.用真值表可检查两个公式是否等值n请验证：p(qr)(

19、pq)r p(qr)不与(pq)r 等值48教学运用等值式例题n例1 判断下列各组公式是否等值:n(1)p(qr)与(pq)r 11111101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1(p q)rp(qr)qr p q rp q00000011 结论结论:p(qr)(p q)r 49教学运用等值式例题n(2)p(qr)与(pq)r 01011101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1(pq)rp(qr)qr p q rpq1111001

20、1 结论结论:p(qr)与与(pq)r 不等值不等值50教学运用基本等值式1.双重否定律 AA2.幂等律 AAA,AAA3.交换律 ABBA,ABBA4.结合律 (AB)CA(BC),(AB)CA(BC)5.分配律 A(BC)(AB)(AC),A(BC)(AB)(AC)6.德摩根律 (AB)AB (AB)AB7.吸收律 A(AB)A,A(AB)A51教学运用基本等值式8.零律 A11,A009.同一律 A0A.A1A10.排中律 AA111.矛盾律 AA012.蕴涵等值式 ABAB13.等价等值式 AB(AB)(BA)14.假言易位 ABBA15.等价否定等值式 ABAB16.归谬论 (AB)

21、(AB)An特别提示：必须牢记这16组等值式，这是继续学习的基础52教学运用等值演算与置换规则1.等值演算由已知的等值式推演出新的等值式的过程2.等值演算的基础：(1)等值关系的性质：自反性、对称性、传递性 (2)基本的等值式 (3)置换规则（见3）3.置换规则 设(A)是含公式 A 的命题公式，(B)是用公式 B 置换 (A)中所有的 A 后得到的命题公式 若 BA，则(B)(A)53教学运用等值演算的应用举例n证明两个公式等值n例2 证明 p(qr)(pq)r证 p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r （结合律，置换规则）(pq)r （德摩根律，置换规则）(pq)r （蕴涵

22、等值式，置换规则）今后在注明中省去置换规则注意：用等值演算不能直接证明两个公式不等值54教学运用n证明两个公式不等值n例3 证明 p(qr)与(pq)r 不等值等值演算的应用举例证 方法一:真值表法,见例1(2)方法二:观察法.观察到000,010是左边的成真赋值，是右边的成假赋值 方法三:先用等值演算化简公式，然后再观察 p(qr)pqr (pq)r(pq)r(pq)r 更容易看出前面的两个赋值分别是左边的成真赋 值和右边的成假赋值55教学运用n判断公式类型:A为矛盾式当且仅当A 0 A为重言式当且仅当A 1n例4 用等值演算法判断下列公式的类型 (1)q(pq)(2)(pq)(qp)(3)

23、(pq)(pq)r)等值演算的应用举例解解 (1)q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德摩根律）（德摩根律）p(qq)（交换律，结合律）（交换律，结合律）p 0 （矛盾律）（矛盾律）0 （零律）（零律）矛盾式矛盾式56教学运用判断公式类型(2)(pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1重言式重言式(3)(p q)(pq)r)(p(qq)r （分配律）（分配律）p 1 r （排中律）（排中律）p r （同一律）（同一律）可满足式可满足式，101和和111是成真赋值，是成真赋值，000和和010等是成假赋值等是

24、成假赋值.57教学运用2.2 析取范式与合取范式n基本概念(1)文字命题变项及其否定的总称(2)简单析取式有限个文字构成的析取式 p,q,pq,pqr,(3)简单合取式有限个文字构成的合取式 p,q,pq,pqr,(4)析取范式由有限个简单合取式组成的析取式 p,pq,pq,(pq)(pqr)(qr)(5)合取范式由有限个简单析取式组成的合取式 p,pq,pq,(pqp(pqr)(6)范式析取范式与合取范式的总称58教学运用范式的性质n定理2.1(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式.(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式.n定理

25、2.2 (1)一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式.(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.59教学运用命题公式的范式n定理2.3（范式存在定理）任何命题公式都存在与之等值的析取范式与合取范式n公式A的析取(合取)范式与A等值的析取(合取)范式n求公式A的范式的步骤：(1)消去A中的,（若存在）ABAB AB(AB)(AB)(2)否定联结词的内移或消去 A A (AB)AB (AB)AB60教学运用命题公式的范式n (3)使用分配律 A(BC)(AB)(AC)求合取范式 A(BC)(AB)(AC)求析取范式n公式范式的不足不惟一61教学运用求公式的范式

26、n例5 求下列公式的析取范式与合取范式(1)(pq)r (2)(pq)r解 (1)(pq)r (pq)r （消去）pqr （结合律）(2)(pq)r (pq)r （消去第一个）(pq)r （消去第二个）(pq)r （否定号内移德摩根律)析取范式 (pr)(qr)（对分配律）合取范式62教学运用极小项与极大项63教学运用实例n由两个命题变项p,q 形成的极小项与极大项极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 pq p qpqp q 0 0 0 1 1 0 1 1 m0m1m2m3 p q pq p q pq 0 0 0 1 1 0 1 1M0M1M

27、2M364教学运用实例极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M4M5M6M7n由三个命题变项p,q,r形成的极小项与极大项.mi与与Mi的关系：的关系：m

28、i Mi,Mi mi 65教学运用主析取范式与主合取范式n主析取范式由极小项构成的析取范式n主合取范式由极大项构成的合取范式n例如，n=3,命题变项为 p,q,r 时，(pqr)(pqr)m1m3 主析取范式 (pqr)(pqr)M1M7主合取范式n定理2.5 (主范式的存在惟一定理)任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的66教学运用需要说明n求任何一个公式的主析取范式和主合取范式不仅要取决于该公式，而且取决于该公式所包含的命题变元。如公式：G1(P,Q)=(PQ)Q，G2(P,Q,R)=(PQ)Q。前者是依赖于两个命题变元的，后者应依赖于三前者是依赖于两个命题变元的

29、，后者应依赖于三个命题变元。个命题变元。67教学运用求主析取范式和主合取范式的方法等值推演法等值推演法利用基本等价公利用基本等价公式进行变换式进行变换主范式主范式真值表技术真值表技术对公式的真值结对公式的真值结果进行分解，分果进行分解，分解成等价的极小解成等价的极小项的析取或者极项的析取或者极大项的合取大项的合取68教学运用求公式A的主析取范式的方法与步骤n方法一、等值演算法(1)化归为析取范式。(2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。n方法二、真值表法(1)写出A

30、的真值表。(2)找出A的成真赋值。(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。69教学运用(1)等值推演法求主析取范式(pq)r(pqr)(pr)(qr)pqrm4prp（qq）r(pqr)(pqr)m1m3qr(pp)qr(pqr)(pqr)m3m7(pq)rm1m3m4m7实例70教学运用实例p q rpq(pq)r0 0 0100 0 1110 1 0100 1 1111 0 0011 0 1001 1 0101 1 111(2)真值表法求(pq)r的主析取范式。解首先列出其真值表71教学运用实例将公式的真值进行分解，分解成一些子公式，该子公式仅有一组解释使

31、其真值为真，此时的每一个子公式都对应了一个极小项。p q r(pq)rpqrpqrpqrpqr0 0 0000000 0 1110000 1 0000000 1 1101001 0 0100101 0 1000001 1 0000001 1 110001将极小项全部进行析取后，可得到相应的主析取范式：(pq)r=(pqr)(pqr)(pqr)(pqr)72教学运用求公式A的主合取范式的方法与步骤n方法一、等值演算法(1)化归为合取范式。(2)除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律

32、展开公式。n方法二、真值表法(1)写出A的真值表。(2)找出A的成假赋值。(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序合取。73教学运用(1)等值推演法求主合取范式(pq)r(pr)(qr)(pqr)pqrM5prp(qq)r(pqr)(pqr)M0M2qr(pp)qr(pqr)(pqr)M2M6(pq)rM0M2M5M6实例74教学运用实例p q rpq(pq)r0 0 0100 0 1110 1 0100 1 1111 0 0011 0 1001 1 0101 1 111(2)真值表法求(pq)r的主合取范式。解首先列出其真值表75教学运用实例将公式的真值进行分解，

33、分解成一些子公式，该子公式仅有一组解释使其真值为假，此时的每一个子公式都对应了一个极大项将极大项全部进行析取后，可得到相应的主合取范式：(PQ)R=(PQR)(PQR)(PQR)(PQR)p q r(pq)rpqrpqrpqrpqr0 0 0001110 0 1111110 1 0010110 1 1111111 0 0111111 0 1011011 1 0011101 1 11111176教学运用真值表技术n利用真值表技术求主析取范式和主合取范式的简要方法：从真值表知，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个成真解释所对应的极小项，将这些极小项的析取即可得到相应的主

34、析取范式。从真值表知，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个成假解释所对应的极大项，将这些极大项的合取即可得到相应的主合取范式。n从真值表按所给的算法求出主范式的方法，称为真值表技术（TechniqueofTruthTable）。77教学运用Try 1 Tryn设G=(pq)r，求出它的主析取范式和主合取范式。（分别用等值推演和真值表法）78教学运用主范式的应用n1.求公式的成真成假赋值 设公式A含n个命题变项,A的主析取范式有s个极小项,则A 有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s 个赋值都是成假赋值 n例如 (pq)r m1m3m5 m6m7成

35、真赋值为 001,011,101,110,111，成假赋值为 000,010,100.类似地，由主合取范式也立即求出成假赋值和成真赋值.79教学运用2.判断公式的类型设A含n个命题变项.A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项,记为1.A为矛盾式 A的主合析取范式含全部2n个极大项 A的主析取范式不含任何极小项,记为0.A为非重言式的可满足式 A的主析取范式中至少含一个、但不是全 部极小项 A的主合取范式中至少含一个、但不是全 部极大项.主范式的应用80教学运用例7 用主析取范式判断公式的类型:(1)A(pq)q (2)B p(pq)(3)C(pq)r解(1)

36、A (pq)q (pq)q 0 矛盾式(2)B p(pq)1 m0m1m2m3 重言式(3)C (pq)r (pq)r (pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3 m5m7 非重言式的可满足式主范式的应用81教学运用n3.判断两个公式是否等值n例8 用主析取范式判以下每一组公式是否等值 p(qr)与(pq)r p(qr)与(pq)r解 p(qr)=m0m1m2m3 m4m5 m7 (pq)r=m0m1m2m3 m4m5 m7 (pq)r=m1m3 m4m5 m7显见，中的两公式等值，而的不等值.主范式的应用82教学运用n4.解实际问题n例9 某单位要从A,B,C三

37、人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解 记 p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值 A=(pr)(qr)(pq)(pq)主范式的应用83教学运用n求A的主析取范式 A=(pr)(qr)(pq)(pq)(pr)(qr)(pq)(pq)(pq)(pr)(rq)(rr)(pq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pqr)(pqr)成真赋值:101,010n结论

38、:方案1 派A与C去,方案2 派B去主范式的应用84教学运用2.3 联结词的完备集定义定义2.6 称称F:0,1n 0,1 为为n元真值函数元真值函数.0,1n=000,001,111，包含，包含 个长为个长为n的的0,1符号串符号串.共有共有 个个n元真值函数元真值函数.1元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1 85教学运用真值函数p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0

39、1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 12元真值函数元真值函数86教学运用公式与真值函数任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应都对应惟一的一个惟一的一个n元元真值函数真值函数 F,F 恰好为恰好为A的真值表的真值表.等值的公式对应的真值函数相同等值的公式对应的真值函数相同.例如：例如：pq,p q 都对应都对应87教学运用联结词完备集n定义2.7 设S是一个联结词集合，如果任何n(n1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集n若S是联结词完备集,则任何命题公式都可由S中的联结词表示n定理2.6

40、 S=,是联结词完备集证明 由范式存在定理可证88教学运用联结词完备集n推论 以下都是联结词完备集 (1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,n证明(1),(2)在联结词完备集中加入新的联结词后仍为完备集(3)AB (AB)(4)AB (AB)(5)ABAB,不是联结词完备集不是联结词完备集,0不能用它表示不能用它表示它的子集它的子集,等都不是等都不是89教学运用复合联结词n定义2.8 设 p,q 为两个命题,(pq)称作p与q的与非式,记作pq,即 pq (pq),称为与非联结词n(pq)称作p与q的或非式,记作pq,即pq(pq),称为或非联结词n定理2.7 与

41、为联结词完备集.n证明,为完备集 p pp (pp)pp pq (pq)pq (pp)(qq)pq (pq)(pq)(pq)(pq)得证为联结词完备集.对类似可证90教学运用2.4 可满足性问题与消解法n不含任何文字的简单析取式称作空简单析取式,记作。规定是不可满足的.n约定:简单析取式不同时含某个命题变项和它的否定nS:合取范式,C:简单析取式,l:文字,:赋值,带下角标或 文字l的补lc:若l=p,则lc=p;若l=p,则lc=p.nSS:S是可满足的当且仅当S 是可满足的n定义2.9 设C1=lC1,C2=lcC2,C1和C2不含l和lc,称C1C2为C1和C2(以l和lc为消解文字)的

42、消解式或消解结果,记作Res(C1,C2)n例如,Res(pqr,pqs)=qrs91教学运用消解规则n定理2.8 C1C2Res(C1,C2)证:记C=Res(C1,C2)=C1C2,其中l和lc为消解文字,C1=lC1,C2=lcC2,且C1和C2不含l和lc.假设C1C2是可满足的,是它的满足赋值,不妨设(l)=1.C2必含有文字l l,lc且(l)=1.C中含有l,故满足C.反之,假设C是可满足的,是它的满足赋值.C必有l 使得(l)=1,不妨设C1含l,于是满足C1.把扩张到l(和lc)上:若l=p,则令(p)=0;若lc=p,则令(p)=1.恒有(lc)=1,从而满足C2.得证C1

43、C2是可满足的.注意:C1C2与Res(C1,C2)有相同的可满足性,但不一定等值.C1=pqr,C2=p r,=01192教学运用消解序列与合取范式的否证n定义2.10 设S是一个合取范式,C1,C2,Cn是一个简单析取式序列.如果对每一个i(1in),Ci是S的一个简单析取式或者是Res(Cj,Ck)(1jki),则称此序列是由S导出Cn的消解序列.当Cn=时,称此序列是S的一个否证.n定理2.9 一个合取范式是不可满足的当且仅当它有否证.n例11 用消解规则证明S=(pq)(pqs)(qs)q是不可满足的.证 C1=pq,C2=pqs,C3=Res(C1,C2)=qs,C4=qs,C5=

44、Res(C3,C4)=q,C6=q,C7=Res(C5,C6)=,这是S的否证.93教学运用消解算法消解算法n输入:合式公式An输出:当A是可满足时,回答“Yes”;否则回答“No”.1.求A的合取范式S2.令S0,S2,S1S的所有简单析取式3.For C1S0和C2S14.If C1,C2可以消解 then5.计算CRes(C1,C2)6.If C=then7.输出“No”,计算结束 8.If CS0且C S1 then9.S2S2C94教学运用消解算法10.For C1S1,C2S1且C1C211.If C1,C2可以消解 then12.计算CRes(C1,C2)13.If C=then

45、14.输出“No”,计算结束 15.If CS0且C S1 then16.S2S2C17.If S2=then 18.输出“Yes”,计算结束19.Else S0S0S1,S1S2,S2,goto 395教学运用消解算法例题n例12 用消解算法判断下述公式是否是可满足的:p(pq)(pq)(qr)(qr)解 S=p(pq)(pq)(qr)(qr)循环1 S0=,S1=p,pq,pq,qr,qr,S2=Res(pq,pq)=p Res(pq,qr)=pr Res(pq,qr)=pr Res(qr,qr)=q S2=pr,pr,q循环2 S0=p,pq,pq,qr,qr,S1=pr,pr,q,S2

46、=Res(pq,q)=p96教学运用消解算法例题 Res(qr,pr)=pq Res(qr,pr)=pq Res(pr,pr)=p S2=输出“Yes”97教学运用n主要内容q推理的形式结构q推理的正确与错误q推理的形式结构q判断推理正确的方法q推理定律n自然推理系统Pq形式系统的定义与分类q自然推理系统Pq在P中构造证明:直接证明法、附加前提证明法、归谬法第三章 命题逻辑的推理理论98教学运用3.1 推理的形式结构n定义3.1 设A1,A2,Ak,B为命题公式.若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1,A2,Ak推出结论B的推理是有效的或正确的,

47、并称B是有效结论.定理定理3.1 由命题公式由命题公式A1,A2,Ak 推推B的推理正确的推理正确当当且仅当且仅当A1 A2 AkB为重言式为重言式注意注意:推理正确不能保证结论一定正确推理正确不能保证结论一定正确99教学运用推理的形式结构2.A1A2AkB 若推理正确,记为A1 A2 Ak B3.前提：A1,A2,Ak 结论：B判断推理是否正确的方法:真值表法 等值演算法 主析取范式法推理的形式结构1.A1,A2,Ak B 若推理正确,记为A1,A2,An B100教学运用推理实例n例1 判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以,明天是5号.(2)若今天是1号，

48、则明天是5号.明天是5号.所以,今天是1号.解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号.(1)推理的形式结构推理的形式结构:(pq)pq用等值演算法用等值演算法 (pq)pq (p q)p)q pq q 1 由定理由定理3.1可知推理正确可知推理正确101教学运用推理实例n(2)推理的形式结构:(pq)qp 用主析取范式法用主析取范式法 (pq)qp (p q)qp (p q)q)p q p (pq)(pq)(pq)(p q)m0 m2 m3 结果不含结果不含m1,故故01是是成假赋值成假赋值，所以推理不正确所以推理不正确102教学运用推理定律重言蕴涵式1.A (AB)附

49、加律 2.(AB)A 化简律3.(AB)A B 假言推理4.(AB)B A 拒取式 5.(AB)B A 析取三段论6.(AB)(BC)(AC)假言三段论7.(AB)(BC)(AC)等价三段论8.(AB)(CD)(AC)(BD)构造性二难 (AB)(AB)B 构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难每个等值式可产生两个推理定律如,由AA可产生 AA 和 AA103教学运用3.2 自然推理系统P定义3.2 一个形式系统 I 由下面四个部分组成：(1)非空的字母表，记作 A(I).(2)A(I)中符号构造的合式公式集，记作 E(I).(3)E(I)中一些特殊的公式组成的公

50、理集，记作 AX(I).(4)推理规则集，记作 R(I).记I=自然推理系统:无公理,即AX(I)=公理推理系统 推出的结论是系统中的重言式,称作定理104教学运用自然推理系统P定义3.3 自然推理系统 P 定义如下:1.字母表 (1)命题变项符号：p,q,r,pi,qi,ri,(2)联结词符号：,(3)括号与逗号：(,),，2.合式公式（同定义1.6）3.推理规则(1)前提引入规则 (2)结论引入规则 (3)置换规则105教学运用推理规则n(4)假言推理规则 n(6)化简规则 n(8)假言三段论规则 AB AB AA B A B An(5)附加规则 n(7)拒取式规则 n(9)析取三段论规则

51、 AB B A AB BCACA B BA106教学运用推理规则n(10)构造性二难推理规则 (11)破坏性二难推理规则 n(12)合取引入规则 AB CD A C B D AB CD BD A C A BA C107教学运用在自然推理系统P中构造证明n设前提A1,A2,Ak,结论B及公式序列C1,C2,Cl.如果每一个Ci(1il)是某个Aj,或者可由序列中前面的公式应用推理规则得到,并且Cl=B,则称这个公式序列是由A1,A2,Ak推出B的证明n直接证明法、附加前提证明法、归谬法n例2 构造下面推理的证明：若明天是星期一或星期三，我明天就有课.若我明天有 课，今天必备课.我今天没备课.所以

52、，明天不是星期一、也不是星期三.解 (1)设命题并符号化 设 p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课108教学运用直接证明法(2)写出证明的形式结构 前提：(pq)r,rs,s 结论：pq(3)证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq)拒取式 pq 置换若明天是星期一或星期三，我明天就有课.若我明天有课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期三.设命题并符号化 p：明天是星期一q：明天是星期三r：我明天有课s：我今天备课109教学运用附加前提证明法n附加前提证明法 适用于结论为蕴涵式n欲证 前提：A1,A2,A

53、k 结论：CBn等价地证明 前提：A1,A2,Ak,C 结论：Bn理由：(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B (A1A2AkC)B110教学运用附加前提证明法实例例3构造下面推理的证明 2是素数或合数.若2是素数，则 是无理数.若 是无理数，则4不是素数.所以，如果4是素数，则2是合数.解 用附加前提证明法构造证明 (1)设 p：2是素数，q：2是合数，r：是无理数，s：4是素数 (2)推理的形式结构 前提：pq,pr,rs 结论：sq 111教学运用附加前提证明法实例 (3)证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式

54、pq 前提引入 q 析取三段论112教学运用归谬法（反证法）n归谬法(反证法)n欲证 前提：A1,A2,Ak 结论：Bn做法 在前提中加入B，推出矛盾.n理由 A1A2AkB (A1A2Ak)B (A1A2AkB)(A1A2AkB)0 A1A2AkB0113教学运用归谬法实例例4 前提：(pq)r,rs,s,p 结论：q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq)析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取114教学运用第一部分 命题逻辑 小结与习题n命题概念、联结词、命题公式、自然语言逻辑n真值表构造、命题公式等价形式n重言式、矛盾式、可满足式n等价推演方法n命题公式的范式、主范式、极大（小）项n联结词完备集、合式公式消解方法n自然语言推理系统115教学运用