离散数学命题逻辑

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

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

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

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

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

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

7、计算启示q自然数n运算：+、*q整数n运算：+、-、*q有理数n运算：+、-、*、/n命题逻辑q真1，假0n运算：q？逻辑联结词n定义q0和1称为0元函数。设n0,称为0,1n到0,1的函数为n元函数，真值函数也称为联结词。n命题的操作符（联结词）q非 q与 q或 q如果,则。 q当且仅当 q异或 n真值表q真值形式可以用图表来说明。这种表称为真值图表。n0元函数q0，1n1元函数qn2元函数q、 、逻辑联结词 0110ppn命题p的否定记为p,读作非p真值表真值表n逻辑联接词的含义n自然语言中，并非的含义举例： ：每一种生物均是动物。F ：有一些生物不是动物。T 这里 不能讲成“每一种生物都

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

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

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

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

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

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

14、 q：老王准时到达了车站。 该命题符号化为：pq（4）首先用字母表示简单命题。 p：三角形的一个角是直角。 q：三角形是直角三角形。 该命题符号化为：p q37命题符号化（5）首先用字母表示简单命题。 p：老王去上海出差。 q：小李去上海出差。 该命题符号化为p q 也可符号化为：（pq）（pq）或者 （p q） （pq）38命题符号化约定：约定： （）我们只注意命题的真假值，而不再去注意命题的汉语意义。 （）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。391.2 命题公式命题公式命题公式命题常元：命题常元：表示确定的命题T，F。命题变元：命题变元：以真假为其变域之变元，

15、或没有指定真值的命题。常用大写英文字母表示。命题公式命题公式：由命题变元、常元、联结词、括号， 以规定的格式联结起来的字符串。40命题公式构造法则定义定义命题公式(wff)可按下述法则来生成： ）单个的命题变元是一个命题公式。 ）若是命题公式，也为命题公式。 ）若、是命题公式，则（）、 （）、（）、（）均为命题公式。 ）当且仅当有限次使用（）（）（）所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。 41命题公式的真值表例如：(PQ)，(P(QR)，(PQ)R)，P都是命题公式。而(P)，(P)都不是命题公式命题公式的真值表命题公式的真值表 :命题变元用特定的命题来取代，这一

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

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

18、。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式永假式。不是永假式的公式，则称此命题公式是可满足式可满足式。讨论： （）永真式的否定为永假式（）；永假式的否定为永真式（）。 （）二个永真式的析取、合取、蕴含、等价 均为永真式。第二章 命题逻辑等值演算 2.1 等值式n有哪些基本的等值式？n如何进行等值演算？n析取范式与合取范式，主析取范式与主合取范式的求解n什么是联结词完备集？482.1 等值式n定义2.1 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式n几点说明：1. 定义中，A, B, 均为元语言符号2. A或B中可能有哑元出现. 3. 例如 (pq) (

19、pq)(rr) r为左边公式的哑元. 4. 用真值表可检查两个公式是否等值n请验证： p(qr) (pq) r p(qr) 不与 (pq) r 等值49等值式例题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 50等值式例题n (2) p(qr) 与 (pq) r 01011101 11111101 11011101 0 0 0

20、0 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq)rp(qr)qr p q rpq11110011 结论结论: : p(qr) 与与 (pq) r 不等值不等值51基本等值式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)A52基本等值式8. 零律 A11, A009. 同一律 A0A. A1A10.排中律 AA111.

21、矛盾律 AA012.蕴涵等值式 ABAB13.等价等值式 AB(AB)(BA)14.假言易位 ABBA15.等价否定等值式 ABAB16.归谬论 (AB)(AB) An特别提示：必须牢记这16组等值式，这是继续学习的基础53等值演算与置换规则1. 等值演算由已知的等值式推演出新的等值式的过程2. 等值演算的基础： (1) 等值关系的性质：自反性、对称性、传递性 (2) 基本的等值式 (3) 置换规则（见3）3. 置换规则 设 (A) 是含公式 A 的命题公式，(B) 是用公式 B 置换 (A) 中所有的 A 后得到的命题公式 若 BA，则 (B)(A)54等值演算的应用举例n证明两个公式等值n

22、例2 证明 p(qr) (pq)r证 p(qr) p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq)r （蕴涵等值式，置换规则）今后在注明中省去置换规则注意：用等值演算不能直接证明两个公式不等值55n证明两个公式不等值n例3 证明 p(qr) 与 (pq)r 不等值等值演算的应用举例证 方法一 :真值表法, 见例1(2) 方法二 :观察法. 观察到000, 010是左边的成真赋值，是右边的成假赋值 方法三 :先用等值演算化简公式，然后再观察 p(qr) pqr (pq)r (pq)r(pq)r 更容易看出前面的两个赋值分别是左边

23、的成真赋 值和右边的成假赋值56n判断公式类型: A为矛盾式当且仅当A 0 A为重言式当且仅当A 1n例4 用等值演算法判断下列公式的类型 (1) q(pq) (2) (pq)(qp) (3) (pq)(pq)r) 等值演算的应用举例解解 (1) q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）矛盾式矛盾式57判断公式类型(2) (pq)( qp) ( p q)(qp) （蕴涵等值式）（蕴涵等值式） ( p q)( p q) （交换律）（交换律

24、） 1重言式重言式(3) (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）可满足式可满足式，101和和111是成真赋值，是成真赋值，000和和010等是成假赋值等是成假赋值. 582.2 析取范式与合取范式n基本概念(1) 文字命题变项及其否定的总称(2) 简单析取式有限个文字构成的析取式 p, q, pq, pqr, (3) 简单合取式有限个文字构成的合取式 p, q, pq, pqr, (4) 析取范式由有限个简单合取式组成的析取式 p, pq, pq, (pq)(pqr)(qr)(5) 合取范式由有限个简

25、单析取式组成的合取式 p, pq, pq, (pqp(pqr)(6) 范式析取范式与合取范式的总称59范式的性质n定理2.1 (1) 一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式. (2) 一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式.n定理2.2 (1) 一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式. (2) 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.60命题公式的范式n定理2.3（范式存在定理） 任何命题公式都存在与之等值的析取范式与合取范式n公式A的析取(合取)范式与A等值的析取(合取)范式n求公式A的范式的步骤： (1)

26、 消去A中的, （若存在） ABAB AB(AB)(AB) (2) 否定联结词的内移或消去 A A (AB)AB (AB)AB61命题公式的范式n (3) 使用分配律 A(BC)(AB)(AC) 求合取范式 A(BC) (AB)(AC) 求析取范式n公式范式的不足不惟一62求公式的范式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) （对分配律） 合取范式63极小

27、项与极大项n64实例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 1M0M1M2M365实例极小项极小项极大项极大项公式公式成真赋值成真赋值名称名称公式公式成假赋值成假赋值名称名称 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 m0m1m2m3m4m5m6

28、m7 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的关系：的关系： mi Mi, Mi mi 66主析取范式与主合取范式n主析取范式由极小项构成的析取范式n主合取范式由极大项构成的合取范式n例如，n=3, 命题变项为 p, q, r 时， (pqr)(pqr) m1m3 主析取范式 (pqr)(pqr) M1M7主合取范式n定理2.5 (主范式的存在惟一定理) 任

29、何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的需要说明n求任何一个公式的主析取范式和主合取范式不仅要取决于该公式，而且取决于该公式所包含的命题变元。如公式： G1(P,Q)= (PQ)Q， G2(P, Q, R) = (PQ)Q。前者是依赖于两个命题变元的，后者应依赖于三前者是依赖于两个命题变元的，后者应依赖于三个命题变元。个命题变元。 求主析取范式和主合取范式的方法等值推演法等值推演法利用基本等价公利用基本等价公式进行变换式进行变换主范式主范式真值表技术真值表技术对公式的真值结对公式的真值结果进行分解，分果进行分解，分解成等价的极小解成等价的极小项的析取或者极项的析取或者极大

30、项的合取大项的合取求公式A的主析取范式的方法与步骤n方法一、等值演算法(1)化归为析取范式。 (2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。n方法二、真值表法(1)写出A的真值表。(2)找出A的成真赋值。(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。(1)等值推演法求主析取范式(pq)r (pqr)(pr)(qr) pqr m4 pr p（qq）r (pqr)(pqr) m1m3 qr (pp)qr (pqr)(pqr) m3m7 (pq)r

31、m1m3m4m7实例71实例p q rpq(pq)r0 0 0100 0 1110 1 0100 1 1111 0 0011 0 1001 1 0101 1 111(2)真值表法求(pq) r的主析取范式。解 首先列出其真值表72实例将公式的真值进行分解，分解成一些子公式，该子公式仅有一组解释使其真值为真，此时的每一个子公式都对应了一个极小项。p q r(pq)rpqrpqrpqrpqr0 0 0000000 0 1110000 1 0000000 1 1101001 0 0100101 0 1000001 1 0000001 1 110001将极小项全部进行析取后，可得到相应的主析取范式：

32、(pq) r= (pqr)(pqr)(pqr)(pqr)求公式A的主合取范式的方法与步骤n方法一、等值演算法(1)化归为合取范式。 (2)除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。n方法二、真值表法(1)写出A的真值表。(2)找出A的成假赋值。(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序合取。(1)等值推演法求主合取范式(pq)r (pr)(qr)(pqr) pqr M5 pr p(qq)r (pqr)(pqr) M0M2 qr (pp)qr (pq

33、r)(pqr) M2M6 (pq)r M0M2M5M6 实例75实例p q rpq(pq)r0 0 0100 0 1110 1 0100 1 1111 0 0011 0 1001 1 0101 1 111(2)真值表法求(pq) r的主合取范式。解 首先列出其真值表76实例将公式的真值进行分解，分解成一些子公式，该子公式仅有一组解释使其真值为假，此时的每一个子公式都对应了一个极大项将极大项全部进行析取后，可得到相应的主合取范式： (PQ)R= (PQR)(PQR)(PQR)(PQR)p q r(pq)rpqrpqrpqrpqr0 0 0001110 0 1111110 1 0010110 1

34、1111111 0 0111111 0 1011011 1 0011101 1 111111真值表技术n利用真值表技术求主析取范式和主合取范式的简要方法： 从真值表知，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个成真解释所对应的极小项，将这些极小项的析取即可得到相应的主析取范式。 从真值表知，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个成假解释所对应的极大项，将这些极大项的合取即可得到相应的主合取范式。n从真值表按所给的算法求出主范式的方法，称为真值表技术（Technique of Truth Table）。77Try 1 Tryn设G= (pq)r，求

35、出它的主析取范式和主合取范式。（分别用等值推演和真值表法）7879主范式的应用n1.求公式的成真成假赋值 设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s 个赋值都是成假赋值 n例如 (pq)r m1m3m5 m6m7成真赋值为 001, 011, 101, 110, 111，成假赋值为 000, 010, 100. 类似地，由主合取范式也立即求出成假赋值和成真赋值. 802. 判断公式的类型 设A含n个命题变项. A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项, 记为1. A为矛盾式 A的

36、主合析取范式含全部2n个极大项 A的主析取范式不含任何极小项, 记为0. A为非重言式的可满足式 A的主析取范式中至少含一个、但不是全 部极小项 A的主合取范式中至少含一个、但不是全 部极大项.主范式的应用81例7 用主析取范式判断公式的类型:(1) A (pq)q (2) B p(pq) (3) C (pq)r解 (1) 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 非重言式的可满足式主范式的应用82n3. 判断两个公式是

37、否等值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显见，中的两公式等值，而的不等值.主范式的应用83n4. 解实际问题n例9 某单位要从A,B,C三人中选派若干人出国考察, 需满足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案?解 记 p:派A去, q:派B去, r:派C去(1) pr, (2) qr, (

38、3) (pq)(pq)求下式的成真赋值 A=(pr)(qr)(pq)(pq)主范式的应用84n求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结论: 方案1 派A与C去, 方案2 派B去主范式的应用852.3 联结词的完备集定义定义2.6 称称F:0,1n 0,1 为为n元真值函数元真值函数. 0,1n=000, 001, , 111，包含，包含 个长为个

39、长为n的的0,1符号串符号串. 共有共有 个个n元真值函数元真值函数. n22n221元真值函数元真值函数 p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF86真值函数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 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF

40、)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函数元真值函数87公式与真值函数)2(13F任何一个含任何一个含n个命题变项的命题公式个命题变项的命题公式A都对应都对应惟一的一个惟一的一个n元元真值函数真值函数 F , F 恰好为恰好为A的真值表的真值表. 等值的公式对应的真值函数相同等值的公式对应的真值函数相同. 例如：例如：pq, p q 都对应都对应88联结词完备集n定义2.7 设S是一个联结词集合，如果任何n(n1) 元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集n若S是联结词完备集, 则任何命题公式都可由S中

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

42、, 即 pq (pq), 称为与非联结词n(pq) 称作 p 与 q 的或非式, 记作 pq, 即 pq (pq), 称为或非联结词n定理2.7 与为联结词完备集. n证明 , , 为完备集 p pp (pp) pp pq (pq) pq (pp)(qq) pq (pq) (pq) (pq)(pq) 得证为联结词完备集. 对类似可证912.4 可满足性问题与消解法n不含任何文字的简单析取式称作空简单析取式,记作。规定是不可满足的. n约定:简单析取式不同时含某个命题变项和它的否定nS:合取范式, C:简单析取式, l:文字, :赋值, 带下角标或 文字l的补lc:若l=p,则lc=p;若l=p

43、,则lc=p.nSS:S是可满足的当且仅当S 是可满足的n定义2.9 设C1=lC1, C2=lcC2, C1和C2不含l和lc, 称C1C2为C1和C2(以l和lc为消解文字)的消解式或消解结果, 记作Res(C1,C2)n例如, Res(pqr, pqs)= qrs92消解规则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. 反之,

44、 假设C是可满足的, 是它的满足赋值. C必有l 使得(l )=1, 不妨设C1含l, 于是满足C1. 把扩张到l(和lc)上:若l=p, 则令(p)=0; 若lc=p, 则令(p)=1. 恒有(lc)=1, 从而满足C2. 得证C1C2是可满足的.注意: C1C2与Res(C1,C2)有相同的可满足性, 但不一定等值.C1=pqr, C2= p r, =01193消解序列与合取范式的否证n定义2.10 设S是一个合取范式, C1,C2,Cn是一个简单析取式序列. 如果对每一个i(1in), Ci是S的一个简单析取式或者是Res(Cj,Ck)(1jki), 则称此序列是由S导出Cn的消解序列.

45、 当Cn=时, 称此序列是S的一个否证.n定理2.9 一个合取范式是不可满足的当且仅当它有否证.n例11 用消解规则证明S=(pq)(pqs)(qs)q是不可满足的.证 C1=pq, C2= pqs, C3=Res(C1,C2)=qs, C4=qs, C5=Res(C3,C4)=q, C6=q, C7=Res(C5,C6)=, 这是S的否证.94消解算法消解算法n输入: 合式公式An输出: 当A是可满足时, 回答“Yes”; 否则回答“No”.1. 求A的合取范式S2. 令S0, S2, S1S的所有简单析取式3. For C1S0和C2S14. If C1, C2可以消解 then5. 计算

46、CRes(C1,C2)6. If C= then7. 输出“No”, 计算结束 8. If CS0且C S1 then9. S2S2C95消解算法10. For C1S1, C2S1且C1C211. If C1, C2可以消解 then12. 计算CRes(C1,C2)13. If C= then14. 输出“No”, 计算结束 15. If CS0且C S1 then16. S2S2C17. If S2= then 18. 输出“Yes”, 计算结束19. Else S0S0S1, S1S2, S2, goto 396消解算法例题n例12 用消解算法判断下述公式是否是可满足的: p(pq)(

47、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= Res(pq, q)=p97消解算法例题 Res(qr, pr)=pq Res(qr, pr)=pq Res(pr, pr)=p S2= 输出“Yes”98n主要内容q推理的形式结构q推理的正确与错误q推理的形式结构q判断推理正确的方

48、法q推理定律n自然推理系统Pq形式系统的定义与分类q自然推理系统Pq在P中构造证明:直接证明法、附加前提证明法、归谬法第三章 命题逻辑的推理理论993.1 推理的形式结构n定义3.1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论.定理定理3.1 由命题公式由命题公式A1, A2, , Ak 推推B的推理正确的推理正确当当且仅当且仅当A1 A2 AkB为重言式为重言式注意注意: 推理正确不能保证结论一定正确推理正确不能保证结论一定正确10

49、0推理的形式结构2. A1A2AkB 若推理正确, 记为A1 A2 Ak B3. 前提： A1, A2, , Ak 结论： B判断推理是否正确的方法: 真值表法 等值演算法 主析取范式法推理的形式结构1. A1, A2, , Ak B 若推理正确, 记为A1,A2,An B推理实例n例1 判断下面推理是否正确(1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号. 解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号. (1) 推理的形式结构推理的形式结构: (pq) pq用等值演算法用等值演

50、算法 (pq) pq ( p q) p) q pq q 1 由定理由定理3.1可知推理正确可知推理正确102推理实例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是是成假赋值成假赋值，所以推理不正确所以推理不正确103推理定律重言蕴涵式1. A (AB) 附加律 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 和 AA1043.2 自然推理系统P定义3.2 一个形式系统 I 由下面四个部分组成： (1) 非空的字母表，记作 A(