课件代数结构第一章

1、离散数学离散数学 主讲主讲 谷淑化谷淑化 中国地质大学中国地质大学 计算机学院计算机学院一、学习离散数学课程的目的 离散数学是计算机专业的一门核心基础课程。离散数学是计算机专业的一门核心基础课程。 1 离散数学为计算机专业的后继课程如数据结构、操作系统、数离散数学为计算机专业的后继课程如数据结构、操作系统、数据库、编译原理、网络和算法设计等课程提供必要的数学基础。据库、编译原理、网络和算法设计等课程提供必要的数学基础。计算机科学的一个重要特点是计算机科学的一个重要特点是离散性离散性. .它能够处理的数据结构它能够处理的数据结构都是离散结构都是离散结构, ,所以学习离散数学是非常有必要的。所以学

2、习离散数学是非常有必要的。 2 2 离散数学是现代数学的一个重要分支，通过该课程的学习可离散数学是现代数学的一个重要分支，通过该课程的学习可以提高学生的抽象思维、严格推理以及综合归纳分析能力，培养以提高学生的抽象思维、严格推理以及综合归纳分析能力，培养出高素质的人才。出高素质的人才。 Edsger W. Dijkstra（19302002）我现在年纪大了我现在年纪大了, 搞了这么多搞了这么多年的软件年的软件, 错误不知道犯了多错误不知道犯了多少少, 现在觉悟了现在觉悟了, 我想假若我早我想假若我早年在数理逻辑上好好下点工夫年在数理逻辑上好好下点工夫的话的话, 我就不会犯这么多的错我就不会犯这么

3、多的错误。不少东西误。不少东西, 逻辑学家早就逻辑学家早就说了说了,可我不知道。要是我能年可我不知道。要是我能年轻轻20 岁岁, 我要回去学习逻辑。我要回去学习逻辑。二、离散数学课程的特点二、离散数学课程的特点 离散数学课程是应计算机科学和技术发展的离散数学课程是应计算机科学和技术发展的需要，综合了高等数学的多个分支而形成的。需要，综合了高等数学的多个分支而形成的。 其特点是其特点是以离散量为研究对象，内容丰富，以离散量为研究对象，内容丰富，涉及面较宽。因此概念多、定理多、推理多并且涉及面较宽。因此概念多、定理多、推理多并且内容较为抽象内容较为抽象。因此其学习有一定的难度。因此其学习有一定的难

4、度。 三、如何学好离散数学三、如何学好离散数学 要学好这门课程，首先必须充分认识到这门课程的上要学好这门课程，首先必须充分认识到这门课程的上述特点，需要做到以下几点：述特点，需要做到以下几点：1 熟读教材。熟读教材。 2 独立思考，大量练习。独立思考，大量练习。 3 注重抽象思维能力的培养。注重抽象思维能力的培养。四、四、 离散数学课程的主要内容离散数学课程的主要内容第四部分第四部分 图论。图论。包括图的基本概念，几种特殊的图。包括图的基本概念，几种特殊的图。离散数学课程的主要内容可以分为四个部分：离散数学课程的主要内容可以分为四个部分：第一部分第一部分 数理逻辑。数理逻辑。包括命题逻辑和谓词

5、逻辑。包括命题逻辑和谓词逻辑。第二部分第二部分 集合论。集合论。包括集合、关系和函数。包括集合、关系和函数。第三部分第三部分 代数系统。代数系统。包括代数系统的一般概念，几类典型包括代数系统的一般概念，几类典型的代数系统。的代数系统。五、五、 教材及参考书教材及参考书 1、教材：教材：离散数学离散数学，蔡之华主编，中国地质大学出，蔡之华主编，中国地质大学出版社版社。 2、参考教材、参考教材 马振华，离散数学导引，清华大学出版社，马振华，离散数学导引，清华大学出版社，1996. 王宪钧，数理逻辑引论，北京大学出版社，王宪钧，数理逻辑引论，北京大学出版社，1998，丘维丘维声声, 抽象代数基础，高

6、等教育出版社，抽象代数基础，高等教育出版社，2003. 离散数学习题集，耿素云，北大出版社离散数学习题集，耿素云，北大出版社 离散数学辅导及习题精解离散数学辅导及习题精解 汤光华编，上海科学技术文献汤光华编，上海科学技术文献出版社。出版社。 网络资源网络资源课程考核课程考核 平时成绩（到课情况、书面作业、平时平时成绩（到课情况、书面作业、平时测验）占测验）占30%，期末考试占，期末考试占70%。 形式化形式化 规范化规范化 推理推理 公理化公理化 1. 1. 命题逻辑的基本概念、命题联结词命题逻辑的基本概念、命题联结词 2. 2. 命题公式、自然语言的形式化命题公式、自然语言的形式化 3. 3

7、. 等值演算等值演算 4. 4. 范式范式 5. 5. 联结词的完备集联结词的完备集 6. 6. 推理理论推理理论 7. 7. 命题逻辑在计算机科学中的应用命题逻辑在计算机科学中的应用1 命题与命题变元命题与命题变元l命题？命题？能够分辨真假的陈述句。能够分辨真假的陈述句。 注：注： (1)(1)命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题；命题； (2)(2)这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假不真也不假，也不能既真又假

8、怎样研究命题？怎样研究命题？简单命题简单命题“构造构造”复杂复杂命题命题l 命题的真值？命题的真值？作为命题的陈述句所表示的判断结果作为命题的陈述句所表示的判断结果 真值只取两个值：真或假。凡是与真值只取两个值：真或假。凡是与事实事实相符的陈述句是真相符的陈述句是真命题，而与事实不符合的陈述句是假命题。通常用命题，而与事实不符合的陈述句是假命题。通常用1 1（或（或字母字母T T）表示真，用）表示真，用0 0（或字母（或字母F F）表示假。）表示假。示例示例1.11.1 判断下列语句是否为命题，并指出其真值判断下列语句是否为命题，并指出其真值n一个语句本身是否能分辨真假与我们是否知道它的真假是

9、两回事。也就是说，对于一个句子，有时我们可能无法判定它的真假，但它本身却是有真假的，那么这个语句是命题，否则就不是命题。n悖论不是命题。“我只知道一件事，那就是什么都不知道。”“言尽悖”l 命题的分类命题的分类n原子命题：原子命题：是指不能再分解为更简单命题的命题；是指不能再分解为更简单命题的命题；n复合命题：复合命题：是指由若干命题用联结词组成的新命题。是指由若干命题用联结词组成的新命题。 l 命题常元？命题变元？命题常元？命题变元？真值确定与否的原子命题。真值确定与否的原子命题。 如果命题如果命题符号符号P P代表命题常元则意味它是某个具体命题的符号化，如代表命题常元则意味它是某个具体命题

10、的符号化，如果果P P代表命题变元则意味着它可指代任何具体命题。如果没有特别指代表命题变元则意味着它可指代任何具体命题。如果没有特别指明，通常来说命题符号明，通常来说命题符号P P等是命题变元，即可指代任何命题。等是命题变元，即可指代任何命题。 2 命题联结词及真值表命题联结词及真值表 否定词否定词“”（或（或“ ”）否定词是一元联结词。否定词是一元联结词。相当于自然语言中的相当于自然语言中的“非非”、“不不”等，真值表如右图。等，真值表如右图。例：例：设设P：上海是一个城市；：上海是一个城市； 则有则有 P：上海不是一个城市：上海不是一个城市; P P 0 1 1 0 合取词合取词“”合取词

11、是二元联结词。合取词是二元联结词。相当于自然语言中的相当于自然语言中的“与与” 、“并且并且” 、“而且而且” 、“也也”等，等，真值表如右图。真值表如右图。例例 设设P：我们去看电影。：我们去看电影。 Q：房间里有十张桌子。：房间里有十张桌子。 则则P Q表示表示“我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。” P Q P Q 0 0 0 0 1 0 1 0 0 1 1 1 析取词析取词“” 析取词是二元联结词。析取词是二元联结词。相当于自然语言中的相当于自然语言中的“或或”、“要么要么要么要么”等，真值表等，真值表如右图。如右图。 P Q PQ 0 0 0 0 1

12、1 1 0 1 1 1 1联结词联结词“”“”是自然语言中的是自然语言中的“或或”、“或者或者”等逻辑抽象（等逻辑抽象（可兼或可兼或）；）；但但“或或”可指可指 “ “可兼或可兼或”、“排斥或排斥或”；蕴含词蕴含词“” 蕴含词是二元联结词。蕴含词是二元联结词。相当于自然语言中的相当于自然语言中的“若若则则”、“如如果果就就”，真值表如右图。，真值表如右图。 P QP Q 0 0 1 0 1 1 1 0 0 1 1 1 在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但在在自然语言中，前件为假，不管结论真假，整个语句的意义，往往无法判断。但在数理逻辑中，当前件数理逻辑中，当前

13、件P P为假时，不管为假时，不管Q Q的真假如何，则的真假如何，则PQPQ都为真。都为真。实质蕴涵实质蕴涵意味着可从意味着可从假的前提推出任何命题来，或两个没有内在联系的命题之间存在蕴涵关系假的前提推出任何命题来，或两个没有内在联系的命题之间存在蕴涵关系 “PQPQ”是表示自然语言中的是表示自然语言中的“因为因为P P所以所以Q”Q”、“如果如果P,P,则则Q”Q”，“只有只有Q Q才才P”P”、“除非除非Q Q，否则，否则非非P”P”、“P P仅当仅当Q”Q”等的逻辑抽象。等的逻辑抽象。 等价词等价词“ ” 等价词是二元联结词。等价词是二元联结词。相当于自然语言中的相当于自然语言中的“等价等

14、价”、“当且仅当当且仅当”、“充要条件充要条件”等，等，真值表如右图。真值表如右图。 P Q PQ 0 0 1 0 1 0 1 0 0 1 1 1 例例 非本仓库工作人员，一律不得入内。非本仓库工作人员，一律不得入内。解解 令令P：某人不是仓库工作人员；：某人不是仓库工作人员； Q Q：某人不可以进入仓库。：某人不可以进入仓库。 则则 上述命题可表示为上述命题可表示为PQ。优先级顺序优先级顺序： 的优先级最高，接着依次是的优先级最高，接着依次是 ， ，和和。练习练习1.1 1.1 判断下列语句是否为命题判断下列语句是否为命题1.明年的中秋节的晚上是晴天2.地球外的星球上存在生物3.x + y

15、104.但愿中国队能取胜。5.3 是有理数 练习练习1.2 1.2 符号化下列命题符号化下列命题1.今晚我上网2.今晚我去教室自习3.他已经回家度假去了4.今晚我上网或我去教室自习5.今晚我上网或者他已经回家度假去了6.如果今天下雨了，那么秋天就到了 联结词联结词“”、“”、“”与构成与构成电路电路的与门、或门和非门电路是相对应的，从的与门、或门和非门电路是相对应的，从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。 联结词联结词“”、“”、“”的的“联接联接运算运算”结果具有结果具有对称性对称性，而联结词，而联结词“”、“”没有

16、；没有； 真值表；注意真值表；注意“”、“”的含义的含义 联结词是句子与句子之间的联结词是句子与句子之间的联结联结；联结词连接的是两个命题真值之间的联结，而不是；联结词连接的是两个命题真值之间的联结，而不是命题内容命题内容之间的连接，因此复合命题的真值只取决于构成他们的各命题的真值，而与之间的连接，因此复合命题的真值只取决于构成他们的各命题的真值，而与它们的内容、含义无关，与联结词所连接的两命题之间是否有关系无关；它们的内容、含义无关，与联结词所连接的两命题之间是否有关系无关； 命题形式与命题意义命题形式与命题意义1 命题公式命题公式(Propositional Formula)(Propos

17、itional Formula)？构造构造- -归纳（计算机）归纳（计算机）Q)1 命题公式命题公式(Propositional Formula)(Propositional Formula)？构造构造- -归纳（计算机）归纳（计算机）P PQ,PQ,PQ),Q), R RP P是命题公式吗？是命题公式吗？命题公式是命题吗？命题公式是命题吗？如何符号化命题？如何符号化命题？示例示例1.31.3 (p (p q) q) ( ( p) p) (q (q r) r)是不是命题公式？是不是命题公式？它通过以下步骤生成：它通过以下步骤生成：1. p1. p是公式；是公式；2. q2. q是公式；是公式；

18、3. (p 3. (p q) q)是公式；是公式；4. (4. ( p)p)是公式；是公式；5. r5. r是公式；是公式；6. (q 6. (q r) r)是公式；是公式；7. (7. ( p) p) (q (q r) r)是公式；是公式；8. (p 8. (p q) q) ( ( p) p) (q (q r) r)是公式。是公式。示例示例1.2 1.2 命题公式命题公式(PQ) ( PR) IF P THEN Q ELSE R可以形象地用下面的一棵树来表示可以形象地用下面的一棵树来表示这种树在形式语言与自动机中就称为这种树在形式语言与自动机中就称为语法分析树。语法分析树。 例例 将下列命题

19、符号化将下列命题符号化 （1）我们不能既划船又跑步；）我们不能既划船又跑步； （2）如果你来了，那么他唱不唱歌将看你是否伴奏而定；）如果你来了，那么他唱不唱歌将看你是否伴奏而定； （1） 令令P：我们划船；：我们划船；Q：我们跑步。则命题可：我们跑步。则命题可 表示为表示为( (PQ）。）。 （2） 令令P：你来了；：你来了；Q：他唱歌；：他唱歌；R：你伴奏。：你伴奏。 则命题可表示为则命题可表示为 P（QR） （3）如果李明是体育爱好者，但不是文艺爱好者，那么李明）如果李明是体育爱好者，但不是文艺爱好者，那么李明不是文体爱好者；不是文体爱好者； 令令P：李明是体育爱好者；：李明是体育爱好者；

20、Q：李明是文艺爱好者。：李明是文艺爱好者。 则命题可表示为（则命题可表示为（P Q）（P Q） 。注：注： 如果给出一个命题公式：（如果给出一个命题公式：（P Q）（PR） 求它的真值之前要给出真值指派。求它的真值之前要给出真值指派。 完全指派、部分指派、成真指派、完全指派、部分指派、成真指派、成假指派、真值表、子公式。成假指派、真值表、子公式。2 命题公式类型命题公式类型 重言式或永真式（重言式或永真式（TautologyTautology） 矛盾式或永假式（矛盾式或永假式（ContradictionContradiction） 可满足式（可满足式（ContingencyContingenc

21、y）公式的值？公式的值？指派指派真值表真值表判定公式类型判定公式类型命题公式的值？命题公式的值？真？假？真？假？真值函数真值函数示例示例1.31.3 教材教材P6P6例例1.61.6练习练习1.3 1.3 判断下列公式的类型判断下列公式的类型1 (p(q p) ) r2 ( (pq) q) r3 (p q)( p(q r)p pq qr rq q p pp p(q(q p)p)(p(p(q(q p)p) r r0 00 00 00 01 11 10 00 01 10 01 11 10 01 10 01 11 11 10 01 11 11 11 11 11 10 00 01 11 11 11 1

22、0 01 11 11 11 11 11 10 01 11 11 11 11 11 11 11 11 1( p(q p) r p pq qr rp pq q (p(pq)q)( ( (p(pq)q) q q( (p(pq)q) q)q) r r0 00 00 01 10 00 00 00 00 01 11 10 00 00 00 01 10 01 10 00 00 00 01 11 11 10 00 00 01 10 00 00 01 10 00 01 10 01 10 01 10 00 01 11 10 01 10 00 00 01 11 11 11 10 00 00 0( (pq) q) r

23、p pq qr rp p q q p pq q r r p pq q r r(p(p q)q)( ( p p(q(q r)r)0 00 00 00 01 10 00 01 10 00 01 10 01 10 00 01 10 01 10 01 11 10 00 00 00 01 11 11 11 11 11 11 11 10 00 01 10 00 01 11 11 10 01 11 10 00 01 11 11 11 10 01 10 00 01 11 11 11 11 11 10 01 10 00 0(p q)( p (q r)真值函数真值函数p pq qr r(p(p(q(q p)p)

24、r r( (p(pq)q) q)q) r r p pq q r r.0 00 00 01 10 00 0? ?0 00 01 11 10 00 0? ?0 01 10 01 10 00 0? ?0 01 11 11 10 01 1? ?1 10 00 01 10 01 1? ?1 10 01 11 10 01 1? ?1 11 10 01 10 01 1? ?1 11 11 11 10 00 0? ?1 等值式等值式函数相等？函数相等？命题公式相等？命题公式相等？定义定义1-8 设设 和和 是两个命题公式是两个命题公式, 若若 、 构成的等价式构成的等价式为永真式为永真式,则称公式则称公式 和

25、和 等值，记为等值，记为 ,称称 为等价式。为等价式。例如例如 代数中代数中令令F1(x, y) = (x + y)2, F2(x, y) = x2 + 2xy + y2 则则 F1(x, y) = F2(x, y) 类似地，在命题逻辑中类似地，在命题逻辑中例如例如 令令 F1(P1, P2) = P1 P2 F2(P1, P2) = P2 P1 则则 P1 P2 P2 P1 即即 F1(P1, P2) F2(P1, P2) 当且仅当 为重言式为重言式 ：一种关系比较，自然语言中的符号：一种关系比较，自然语言中的符号：运算符号，可以计算（从而用于判断等价关系）可以作：运算符号，可以计算（从而用

26、于判断等价关系）可以作为程序语言的符号为程序语言的符号示例示例1.41.4 阅读教材阅读教材P8P8例例1.71.7等值公式等值公式( (命题定律命题定律) )1 1 交换律、结合律、分配律交换律、结合律、分配律双否律、等幂律、德摩根律双否律、等幂律、德摩根律2 2 吸收律、零一律、同一律、排中律、矛盾律吸收律、零一律、同一律、排中律、矛盾律3 3 蕴含等值式蕴含等值式4 4 假言易位（逆否律）、假言易位（逆否律）、等价等价等值式、等值式、等价等价否定律、否定律、5 5 归谬论归谬论判断命题公式是否永判断命题公式是否永真真真值表方法？真值表方法？当命题变量增多时？当命题变量增多时？ 吸收律吸收

27、律 ( () )， ( () ) 零一律零一律 1 11 1， 0 00 0 同一律同一律0 0， 1 1 排中律排中律1 1 矛盾律矛盾律 0 0 蕴含等值式蕴含等值式 假言易位假言易位( (逆否律）逆否律） 等价等值式等价等值式( () ) ( () )， ( () ) ( () ) 等价否定等值式等价否定等值式 归谬论归谬论 ( () ) ( () ) 等值式证明示例等值式证明示例1.41.4 阅读教材阅读教材P9P9例例1.81.82 等值演算等值演算两个定理两个定理代入定理代入定理置换定理置换定理有两种方法：真值表方法，命题演算方法有两种方法：真值表方法，命题演算方法如何进行等值演算

28、如何进行等值演算1、真值表方法、真值表方法 例例1 用真值表方法证明用真值表方法证明 E10： (P Q) PQ 解解 令：令：A= (P Q)，B= PQ，构造，构造A，B 以及以及A B的真值表如下：的真值表如下： 由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB。 0PQP Q (P Q) P Q PQAB00111110110100111100101101000012等值演算方法等值演算方法例如例如 在初等代数中在初等代数中证明恒等式证明恒等式(x + 1)(x2 x + 1)(x - - 1)(x2 + x + 1)=x6 1证明证明 原式原式= (x + 1)(x

29、2 x + 1)(x - - 1)(x2 + x + 1) = (x3 + 1)(x3 1) = (x3)2 1 = x6 1 (1) 代入规则代入规则 代入规则代入规则 对于重言式中的任一命题变元出现的每一处均对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。用同一命题公式代入，得到的仍是重言式。 例如例如 F=（PQ）（ QP）是重言式，若）是重言式，若用公式用公式AB代换命题变元代换命题变元P得公式得公式 F1=（AB）Q）（ Q（AB），）， F1仍是重言式。仍是重言式。注意：注意：因为因为A B当且仅当当且仅当A B是重言式。所以，若对于等是重言式。所以，

30、若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。则得到的仍是等值式。例如例如 (P Q) ( P Q )，即即 (P Q) P Q是永真公式是永真公式于是，用于是，用PS对对P进行代入进行代入得得 (PS)Q) (PS) Q (2)(2)置换规则置换规则 设设C C是公式是公式A A的子公式，的子公式，C CD D。如果将公式如果将公式A A中的子公式中的子公式C C置换成公式置换成公式D D之后，得到之后，得到的公式是的公式是B B，则，则A AB B。 若若 A=(A=( PQ)PQ)(P(PQ)(RQ

31、)(R S)S) B=( B=( PQ)PQ)( ( ( PQ)PQ)(R(R S)S) 则则 A A B B 例如例如 (3)(3) 等值演算等值演算 等值演算是指利用已知的一些等值式，根据置换等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。一些等值式的过程。 由代入规则知前述的基本等值式，不仅对任意的命由代入规则知前述的基本等值式，不仅对任意的命题变元题变元P P，Q Q，R R是成立的，而且当是成立的，而且当P P，Q Q，R R分别为命题公分别为命题公式时，这些等值式也成立。式时，这

32、些等值式也成立。 例例 证明命题公式的等值关系：证明命题公式的等值关系： （PQ）（RQ）（PR）Q；证明证明 （PQ）（RQ） （ PQ）( RQ) E11（ P R）Q E3( 分配律分配律) (PR) Q E11 (PR)Q E10(德德.摩根定律摩根定律)所以（所以（PQ）（RQ）（PR）Q 例例 证明下列命题公式的等值关系证明下列命题公式的等值关系 (P Q ) ( P ( P Q ) ) P Q 证明证明 (P Q) ( P ( P Q) (P Q) ( ( P P ) Q ) (结合律结合律) (P Q) ( P Q) (等幂律等幂律) ( P Q ) ( P Q ) (交换律交

33、换律) P (Q (P Q) (结合律结合律) P Q (交换律，吸收律交换律，吸收律) 例例 判别下列公式的类型。判别下列公式的类型。 （1） Q ( P（ PQ）) 解解 Q （ P（ PQ） Q （P（ PQ）Q （P P）（PQ）Q （1（PQ）Q （PQ）Q P Q（Q Q） P0所以所以Q ( P ( PQ)是矛盾式。是矛盾式。（2）（）（PQ） P 解：解：（PQ） P （ PQ） P P于是该公式是可满足式。于是该公式是可满足式。 (3) (P Q)P) Q 定义定义1.10 如果命题公式如果命题公式 中只出现命题变元、命题中只出现命题变元、命题常元、命题连结词常元、命题连结词

34、“ ”、“”、“”，则称，则称 为限为限制性命题公式。制性命题公式。 定义定义1.111.11 在限制性命题公式在限制性命题公式 中，将连结词中，将连结词“”换成换成“”， 将将 “”换成换成 “”、将、将0换成换成1，1换成换成0，所得到的公式称为所得到的公式称为 的的对偶式对偶式，记为，记为 * *。 显然，显然， 和和 *互为对偶式。互为对偶式。例如，公式例如，公式 (P Q) ( R)与公式与公式 (P Q) ( R)需求需求 命题公式规范化？命题公式规范化？ AI (AI (自动推理，自动推理，RoughRough集数据约简集数据约简) ) 电路设计电路设计( (只根据真值表即可设计

35、电路）只根据真值表即可设计电路）可行可行联接词功能完备集：联接词功能完备集： , , , , 何为命题公式规范形式？何为命题公式规范形式？ 文字文字 P， P（P与与 P称为互补对）称为互补对） 质合取质合取/ /析取式析取式 P， P， P Q，PQ R P， Q，P Q， P QR 析取析取/ /合取范式合取范式 主析取主析取/ /合取范式合取范式 定理定理1.5 (1)质合取式为矛盾式的充要条件：它包含一个互补对。质合取式为矛盾式的充要条件：它包含一个互补对。 (2)质析取式为重言式的充要条件：它包含一个互补对。质析取式为重言式的充要条件：它包含一个互补对。析取范式析取范式（Disjun

36、ctive Normal FormDisjunctive Normal Form） 1 12 2 n n i i为质合取式为质合取式。 (P (P Q)Q) ( ( P PQ)Q)合取范式合取范式（Conjunctive Normal FormConjunctive Normal Form） 1 12 2 n n i i为质析取式为质析取式。 (P (P R)R) (P(P Q QR)R) ( ( P PR)R)定理定理1.6 1.6 任一命题公式存在任一命题公式存在析取范式析取范式 、合取范式。合取范式。 如何求解析取范式和合取范式？如何求解析取范式和合取范式？ (1)(1)消消去联结词去联

37、结词，； (2)(2)将联结词将联结词 向内深入，使之只作用于命题向内深入，使之只作用于命题变元；变元； (3)(3)利用利用分配律分配律将公式化为所需要的范式。将公式化为所需要的范式。示例示例1.41.4 阅读教材阅读教材P14P14例例1.121.12应用应用 教材教材P15P15定理定理1.71.7练习练习 求命题公式的析取范式和合取范式求命题公式的析取范式和合取范式(1).求求( PQ) (PR)的析取范式和合取范式的析取范式和合取范式(2).求求(PQ) (P R)的析取范式和合取范式的析取范式和合取范式解解 (1)求求( PQ) (PR)的析取范式：的析取范式：( PQ) (PR)

38、 (P Q) ( P R) / 蕴涵等值式蕴涵等值式(P Q) ( P R) / 双否律双否律(PP) (P R) (QP) (Q R)/分配律分配律(P R) (QP) (Q R) /(PP)是矛盾式是矛盾式显然显然( PQ) (PR)的合取范式为的合取范式为(P Q) ( P R)。(2)求求(PQ) (P R)的合取范式：的合取范式：(PQ) (P R)( P Q) (P R) ( P Q P) ( P Q R)显然显然(PQ) (P R)的析取范式为的析取范式为( P) Q R。注意到：注意到：一个命题公式的合取范式和析取范式不具有唯一性。一个命题公式的合取范式和析取范式不具有唯一性。

39、 定义定义 1.14 1.14 在含在含n n个命题变元的质合取式（质析取式）个命题变元的质合取式（质析取式）中，若每个命题变元与其否定不同时存在，而二者之一必中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第出现且仅出现一次，且第i i个命题变元或其否定出现在从个命题变元或其否定出现在从左算起的第左算起的第i i位上，这样的质合取式（质析取式）称为极位上，这样的质合取式（质析取式）称为极小项（极大项）。小项（极大项）。例如，例如，两个命题变元两个命题变元P,Q共可产生共可产生4个极小项，分别为：个极小项，分别为： P Q对应对应00，记为，记为m0； P Q对应对应01

40、，记为，记为m1；P Q对应对应10，记为，记为m2； P Q对应对应11，记为，记为m3；也可以产生也可以产生4个极大项，分别为：个极大项，分别为：P Q对应对应00，记为，记为M0； P Q对应对应01，记为，记为M1； P Q对应对应10，记为，记为M2； P Q对应对应11，记为，记为M3； 定理定理1.8 设设mi和和Mi是命题变元是命题变元P1 ,P2 , ,Pn形成的极形成的极小项和极大项，则小项和极大项，则 miMi ， Mi mi 定义定义1.15 设命题公式设命题公式 中含中含n n个命题变元，如果个命题变元，如果 的析的析取范式（合取范式）中的质合取式（质析取式）都是极小

41、取范式（合取范式）中的质合取式（质析取式）都是极小项（极大项），则称该析取范式（合取范式）为项（极大项），则称该析取范式（合取范式）为 的主析的主析取范式（主合取范式）。取范式（主合取范式）。 主析取主析取/ /合取范式合取范式如何如何求解？求解？极小项、极大项极小项、极大项1 1 真值表法真值表法 2 2 等值演算等值演算例例 求下列命题公式的主析取范式和主合取范式。求下列命题公式的主析取范式和主合取范式。 1）P(QR) 2）(PQ)RP Q R P (Q R) (P Q)R 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1

42、 1 1 1 0 0 0 1 1 1 1 1 根据真值表中根据真值表中P(QR)真值为真值为1的赋值，所对应的的赋值，所对应的极小项析取即为极小项析取即为P(QR)的主析取范式，所以有：的主析取范式，所以有：P(QR) m0 m1 m2 m3 m4 m5 m7(PQR) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) 根据真值表中根据真值表中P(QR)真值为真值为0的赋值，所对应的的赋值，所对应的极大项合取即为极大项合取即为P(QR)的主合取范式，的主合取范式，所以有：所以有：P(QR) M6 PQR同理，同理，(PQ)R的主析取范式为：的主析取范式为：(PQR)(PQR)(PQ

43、R)(PQR) (PQR)(PQ)R的主合取范式为：的主合取范式为：(PQR)(PQR)(PQR) 从上面的例题中可以看出：矛盾式没有主析取范式，重言式没有从上面的例题中可以看出：矛盾式没有主析取范式，重言式没有主合取范式。主合取范式。 定理定理1.9 任何一个不为矛盾式（重言式）的命题公式任何一个不为矛盾式（重言式）的命题公式都存在着与之等值的主析取范式（主合取范式），并且是都存在着与之等值的主析取范式（主合取范式），并且是唯一的。唯一的。示例示例 教材教材P17P17例例1.161.16应用应用 教材教材P18P18例例1.171.17真值表方法真值表方法等值演算方法等值演算方法如何求解主

44、析取范式和主合取范式？如何求解主析取范式和主合取范式？ (1)化为析取范式和合取范式；化为析取范式和合取范式； (2)利用同一律消去矛盾的质合取式（重言的质析取式）；利用同一律消去矛盾的质合取式（重言的质析取式）；（3）利用等幂律消去相同的质合取式（质析取式）以及质合取式）利用等幂律消去相同的质合取式（质析取式）以及质合取式（质析取式）中相同的合取项（析取项）；（质析取式）中相同的合取项（析取项）； （4）利用同一律、分配律将每一合取项（析取项）化为极小项）利用同一律、分配律将每一合取项（析取项）化为极小项（极大项）。（极大项）。示例示例 教材教材P17P17例例1.161.16求公式求公式(

45、 ( P PR)R) (P(PQ)Q)的主合取范式。的主合取范式。解解 ( ( P PR)R) (P(PQ) Q) (P(P R)R) ( ( P P Q)Q) (P(PQ)Q)(P(P (Q(QQ)Q) R)R) ( ( P P Q Q (R(RR)R) (P(PQ Q (R(RR)R)(P(P Q Q R)R) (P(PQ Q R)R) ( ( P P Q Q R)R) ( ( P P Q QR)R) (P(PQ Q R)R) (P(PQ QR)R)(P(P Q Q R)R) (P(PQ Q R)R) (P(PQ QR)R) ( ( P P Q Q R)R) ( ( P P Q QR) R

46、) M M0 0 M M2 2 M M3 3 M M4 4 M M5 5此即此即所求的所求的主合取范式。主合取范式。因此，上式的主析取范式因此，上式的主析取范式m1 1 m6 6 m7 7练习练习 求命题公式的主范式求命题公式的主范式(1).(1).求求( ( P PQ Q) ) (P(PR R) )的主析取范式和主合取范式的主析取范式和主合取范式(2).(2).求求(P(PQ Q) ) (P(P R R) )的主析取范式和主合取范式的主析取范式和主合取范式(1)(1)根据前例知根据前例知( ( P PQ)Q) (P(PR)R)的一个析取范式是的一个析取范式是(P(P R)R) (Q(QP)P

47、) (Q(Q R)R)，现在将其中的每个简单合，现在将其中的每个简单合取式展开为含有所有命题变元的极小项的析取：取式展开为含有所有命题变元的极小项的析取： (P(P R)R)展开为展开为(P(P Q Q R)R) (P(PQ Q R),(QR),(QP)P)展开为展开为( ( P P Q Q R) R) ( ( P P Q QR),(QR),(Q R)R)展开为展开为(P(P Q Q R)R) ( ( P P Q Q R)R)因此因此( ( P PQ)Q) (P(PR)R)的主析取范式为的主析取范式为(P(P Q Q R)R) (P(PQ Q R)R) ( ( P P Q Q R)R) ( (

48、 P P Q QR)R)，按极小项按极小项所对应的二进制数的大小重新排列为所对应的二进制数的大小重新排列为( ( P P Q QR)R) ( ( P P Q Q R)R) (P(PQ Q R)R) (P(P Q Q R),R),可记为可记为m m2 2 m m3 3 m m5 5 m m7 7。讨论讨论 范式一定存在，但主范式不一定存在？范式一定存在，但主范式不一定存在？ 如果命题公式是矛盾式（永真式），则其无主析取范式如果命题公式是矛盾式（永真式），则其无主析取范式（合取范式）？（合取范式）？ 如果命题公式存在主范式，则是唯一存在的？如果命题公式存在主范式，则是唯一存在的？ 如果已经求得某命

49、题公式的主析取范式，则可以根据主析如果已经求得某命题公式的主析取范式，则可以根据主析取范式求得该命题公式的主合取范式取范式求得该命题公式的主合取范式 只要给定真值表，则可以求出相应真值函数的主范式？只要给定真值表，则可以求出相应真值函数的主范式？1.5 1.5 联结词的完备集联结词的完备集 定义定义1.161.16 称称F F：0,10,1n n0,10,1为为n n元元真值函数真值函数（Truth Value FunctionTruth Value Function）。）。 在这个定义中，在这个定义中，F F的自变量为的自变量为n n个命题变元，个命题变元，定义域定义域0,10,1n n =

50、000,001,111 =000,001,111，即，即0,10,1n n中元素为由中元素为由0,10,1组成的全体长为组成的全体长为n n的符号串，的符号串，值域为值域为0,10,1。n n个命题变元共可构成个命题变元共可构成2 22 2n n个不同的个不同的真值函数。含命题变元真值函数。含命题变元P P的的1 1元真值函数共有元真值函数共有4 4个。个。含两个命题变元含两个命题变元P,QP,Q的真值函数共有的真值函数共有1616个。个。 1.5 1.5 联结词的完备集联结词的完备集 定义定义1.171.17 设设S S是一个联结词集合，如果任是一个联结词集合，如果任何何n(n1)n(n1)

51、元真值函数都可以由仅含元真值函数都可以由仅含S S中的联中的联结词构成的公式表示，则称结词构成的公式表示，则称S S是是联结词完备联结词完备集集（Adequate Set of ConnectivesAdequate Set of Connectives）。）。 定理定理1.101.10 S= S= ， ， 是联结词完备集。是联结词完备集。 证证 因为任何因为任何n(n1)n(n1)元真值函数都与惟一元真值函数都与惟一的一个主析取范式等值，而在主析取范式中的一个主析取范式等值，而在主析取范式中仅含联结词仅含联结词 ， ， ，所以，所以S=S= ， ， 是是联结词完备集。联结词完备集。 1.5

52、1.5 联结词的完备集联结词的完备集 推论推论1.11.1 以下联结词集都是完备集：以下联结词集都是完备集：（1 1）S S1= ， ， ， （2 2）S S2= ， ， ， （3 3）S S3= ， （4 4）S S4= ， （5 5）S S5= ， 1.5 1.5 联结词的完备集联结词的完备集 证证 （1 1），（），（2 2）的成立是显然的。）的成立是显然的。 （3 3）由于）由于S=S= ， ， 是联结词完备集，是联结词完备集，因而任何真值函数都可以由仅含因而任何真值函数都可以由仅含S S中的联结中的联结词的公式表示。同时对于任意公式词的公式表示。同时对于任意公式A A和和B B，A

53、A B B(A(A B)B) ( ( A AB)B)，因而任意，因而任意真值函数都可以由仅含真值函数都可以由仅含S S3 3= ， 中的联结中的联结词的公式表示，所以词的公式表示，所以S S3 3是联结词完备集。是联结词完备集。 1.5 1.5 联结词的完备集联结词的完备集 可以证明恒取可以证明恒取0 0值的真值函数（即与矛值的真值函数（即与矛盾式等值的真值函数）不能用仅含联结词盾式等值的真值函数）不能用仅含联结词集集 ， ， 中的联结词的公式表示，中的联结词的公式表示，因而因而 ， ， 不是联结词完备集。不是联结词完备集。由此可知，由此可知， ， ， ， ， ， ， ， ， ， 等也都不是联

54、结词完备集。等也都不是联结词完备集。所以，所以， ， ， 的任何子集都不是的任何子集都不是联结词完备集。联结词完备集。 1.5 1.5 联结词的完备集联结词的完备集 定义定义1.181.18 设设P P，Q Q为两个命题，复合命题为两个命题，复合命题“P P与与Q Q的否定式的否定式”（“P P或或Q Q的否定式的否定式”）称为称为P P，Q Q的的与非式与非式（或非式或非式），记作），记作PQPQ（PQPQ）。符号）。符号（）称作为）称作为与非联结与非联结词词（或非联结词或非联结词）。）。PQPQ为真当且仅当为真当且仅当P P与与Q Q不同时为真（不同时为真（PQPQ为真当且仅当为真当且仅当

55、P P与与Q Q同时同时为假）。为假）。 由定义不难看出由定义不难看出 PQPQ(P(P Q)Q)，PQPQ(P(P Q)Q) 1.5 1.5 联结词的完备集联结词的完备集 定理定理1.111.11 ，都是联结词完备集。都是联结词完备集。 证证 已知已知 ， ， 为联结词完备集，因而只需为联结词完备集，因而只需证明其中的每个联结词都可以由证明其中的每个联结词都可以由定义即可。而定义即可。而 P P(P(P P P）PP (a)PP (a) P P Q Q(P(P Q)Q)(PQ)(PQ) (PQ)(PQ) (b)(PQ)(PQ) (b) P P Q Q(P(P Q)Q)( ( P PQ)Q)

56、PP Q Q(PP)(QQ) (c)(PP)(QQ) (c) 由由(a)(a)(c)(c)可知，可知，是联结词完备集，类是联结词完备集，类似可证似可证是联结词完备集。是联结词完备集。 演绎推理演绎推理 数理逻辑中，应用公认的推理规则数理逻辑中，应用公认的推理规则(Rules (Rules of of I Inference)nference)从一些前提从一些前提( (P Premise)remise)中推中推导出结论来时，这种推导过程称之为演绎导出结论来时，这种推导过程称之为演绎推理推理(Deduction)(Deduction)或形式证明或形式证明(Formal (Formal Proof)

57、Proof)。1.6 1.6 命题逻辑的推理演算命题逻辑的推理演算1 1 推理形式推理形式定义定义1.191.19 设设1 1,2 2, ,n n,都是命题公式。都是命题公式。若若( (1 1 2 2 n)n)是重言式，是重言式，称由前提称由前提1 1,2 2, ,n n推推出出的推理是的推理是有效的有效的或或正确的正确的，并称，并称是是1 1,2 2, ,n n的的有效有效结论结论或或逻辑结果（逻辑结果（Logical ConsequenceLogical Consequence），当且仅当当且仅当(1 1 2 2 n n)是永真式是永真式记为记为1 1 2 2 n n或或1 1,2 2 ,

58、 ,n n（称为（称为重言蕴含重言蕴含或或推理形式推理形式）1.6 1.6 命题逻辑的推理演算命题逻辑的推理演算1.6 1.6 命题逻辑的推理演算命题逻辑的推理演算 关于定义关于定义1.191.19还需做以下还需做以下说明说明： （1 1）由前提）由前提1 1, ,2 2, , ,n n推结论推结论的推理的推理是否正确与各前提的排列次序无关，因而是否正确与各前提的排列次序无关，因而前提中的公式不一定是序列，而是一个有前提中的公式不一定是序列，而是一个有限公式集合。若推理是正确的，则记为限公式集合。若推理是正确的，则记为1 1 2 2 n n，否则记为，否则记为1 1 2 2 n n。1.6 1

59、.6 命题逻辑的推理演算命题逻辑的推理演算 （2 2）符号）符号与与是两个完全不同的符号，是两个完全不同的符号，它们的区别与联系类似于它们的区别与联系类似于和和的关系。的关系。不是命题联结词而是公式间的关系符号，不是命题联结词而是公式间的关系符号，而而是命题联结词。这两者之间有密切的是命题联结词。这两者之间有密切的联系，即联系，即的充要条件是公式的充要条件是公式为重言式。为重言式。 1.6 1.6 命题逻辑的推理演算命题逻辑的推理演算 （3 3）必须把推理的有效性和结论的真实性必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结区别开。有效的推理不一定产生真实的结论，产生真实结

60、论的推理过程未必一定是论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前的前提；而无效的推理却可能包含真的前提。提。1.6 1.6 命题逻辑的推理演算命题逻辑的推理演算 示例示例：教材教材例例1.181.18 写出下述推理关系的推理形式：写出下述推理关系的推理形式：“下午小王或去看电影或去游泳。他没去看电影。所以，下午小王或去看电影或去游泳。他没去看电影。所以，他去游泳了。他去游泳了。” 解解 设设 P P：小王下午去看电影；：小王下午去看电影；Q Q：小王下午去游泳。于是：小王下午去游泳。于是得到如