第1部分 数理逻辑

1、 离 散 数 学 离 散 数 学第一部分 数理逻辑Discrete MathematicsLecturer： Email: mobile:ffice Address： 北7-1203D1引子：例：一位逻辑工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。（1）会计张某或邻居张某谋害了厂长。（2）如果会计张某谋害了厂长，则谋害不可能发生在半夜。（3）如果邻居张某的证词不正确，则在半夜时房里灯光未灭。（4）如果邻居张某的证词是正确的，则谋害发生在半夜。（5）在半夜房子里的灯光灭了，且会计张某曾贪污过。2数理逻辑逻辑学是一门研究思维概念、判断、推理及其结构和

2、相互关系的科学。分为形式逻辑和辩证逻辑。数理逻辑是用数学方法（即符号化）研究上述思维规律的科学。无论是计算机的雏形图灵机，计算机的设计工具布尔代数，计算机程序的语言和算法，还是计算机自身的运算和控制，都和数理逻辑有着千丝万缕的联系。利用计算机来实现数理逻辑所表述的人类大脑思维的形式和规律。数理逻辑包括古典数理逻辑和现代数理逻辑，其基础是逻辑演算。3第一章 命题逻辑基本概念1.1 命题与联结词1.2 命题公式及其赋值41.1 命题与联结词重点命题的概念五种基本的联结词命题符号化难点五种基本的联结词命题符号化5命题：非真即假的陈述句。例1.1 判断下列句子中哪些是命题。(1) 北京是中国的首都 (

3、2) 所有的树木都是植物。(3) 今天下雨。 (4) 请勿吸烟!(5) 这朵花多好看呀! (6) 请你把门关上!(7) 明天开会吗? (8) 你到哪里去?(9) x+y5。 (10) 地球外的星球上也有人。(11) (12)我正在说谎。用真值来描述命题是“真” 还是“假”。分别用“1”和“0”表示(1),(2),(3),(10)是命题。 (11)、 (12)？一、命题的概念6命题一般用小写字母p，q，r，p1，p2，等来表示。例1.2 命题表示。 p：地球外的星球上也有人。 q：小王是我的好朋友。理发师悖论 我只给不给自己理发的人理发。罗素悖论 我正在说谎。注意：悖论不是命题。一、命题的概念7

4、原子命题 ：基本的、原始的，不能再分解成更小的命题 。复合命题：由一个或几个原子命题通过联结词的联接而构成的命题。例1.3 下列命题都是复合命题 (1) 雪不是白的(并非雪是白的)。 (2) 今晚我看书或者去看电影。 (3) 你去了学校，我去了工厂(省略了逻辑联结词”且”)。 (4) 如果天气好，那么我去接你。 (5) 偶数a是质数，当且仅当a=2。一、命题的概念8二、命题联结词自然语言中常用的一些联结词：1、表示否定的：非、不、没有、无、并非2、表示同时的：并且、同时、和、也、同、与、不但而且 、虽然但是 、既又、一面一面3、表示或的：可能可能、或许或许、或4、表示条件的：若则、如果那么、只

5、有才、因为所以、仅当、除非才、除非否则 5、表示等价的：充分必要、当且仅当、有且只有9定义1.1 设p是命题，复合命题“非p”（或p的否定）称为命题p的否定式，记为p。符号称为否定联结词，并规定p为真当且仅当p为假。 pp1001二、命题联结词10自然语言中的“非”，“不”可符号化为。 例 1.4 设p：上海是中国的城市；q：每个自然数都是偶数。求 p， q表示的命题。则有 p：上海不是中国的城市; q：并非每个自然数都是偶数。二、命题联结词11定义1.2 设p，q是两个命题，复合命题“p并且q”称为命题p和q的合取式，记为pq。符号称为合取联结词，并规定 pq为真当且仅当p，q同时为真。 p

6、qpq000010100111二、命题联结词12 例1.5 设p：他喜欢运动。q：他喜欢读书。则pq表示的命题为？则pq表示“他即喜欢运动，又喜欢读书。” 自然语言中“即又”，“不仅而且”，“虽然但是”等，都可以符号化为 二、命题联结词例：李大和李二是亲兄弟。13定义1.3 设p，q是两个命题，复合命题“p或q”称为命题p和q的析取式，记为pq。符号称为析取联结词，并规定 pq为假当且仅当p，q均为假。 pqpq000011101111 例1.6 设p：他喜欢运动。q：他喜欢读书。则pq表示的命题为： 则pq表示：他喜欢运动或者喜欢读书。二、命题联结词14 注意： 析取式pq表示的是一种相容性

7、或，即允许p与q同时为真。 例1.7 “王燕学过英语或法语”可符号化为pq，其中p：王燕学过英语，q：王燕学过法语。二、命题联结词但自然语言中，有时“或”表示排斥性或。 例1.8 派小王或者小李中的一个人去开会不能符号化为pq的形式，而是符号化为 (pq)(pq)15 结论： 对于命题p、q，若命题p与q可能同时为真，直接用析取式pq表示；否则，用(pq)(pq)表示。 例1.9 小王在图书馆或者宿舍原因：p与q不可能同时为真。不可以符号化为pq。二、命题联结词可以符号化为( pq)(pq）。又例：以下两句均为 “排斥性或”。 他通过电视看杂技或到剧场看杂技。 他乘火车去北京或乘飞机去北京。1

8、6 定义1.4 设p，q是两个命题，复合命题“若p则q”称为命题p和q的蕴涵式，记为pq。符号称为蕴涵联结词，并规定 pq为假当且仅当p为真而q为假。 pqpq001011100111 例1.10 设p：你的收入超过800元。 q：你得交纳所得税。 则pq表示的命题为？则pq：如果你的收入超过800元，那么你要交纳所得税。二、命题联结词17注意：1. 在自然语言中，“如果p，则q”中的p与q往往有某种内在联系，但在数理逻辑中“pq”中的p与q不一定有什么内在联系。 2. 在数学中，“如果p，则q”往往表示前件p为真，后件q为真的推理关系，但在数理逻辑中，当前件p为假时，pq也为真。二、命题联结

9、词3. 自然语言中， “只要p，就q”， “因为p，所以q” ， “当p,则q” “仅当q,才p” ， “只有q，才p”， “除非q，才p” ， “除非q，否则非p” 等等，都可以符号化为 pq。18几个容易混淆的例子只要p，就q只要天气好，我就上街。只有q成立，才有p成立只有天气好，我才上街。当p成立，则q成立当你的收入超过800元，你要交纳所得税。仅当q，才p仅当天气好时，我才上街。除非q成立，否则p不成立除非天气好，否则我不上街。 等可以符号化为pq的形式。19 定义1.5 设p，q是两个命题，复合命题“p当且仅当q”称为p等值q，记为pq。符号称为等值联结词，并规定 pq为真当且仅当p

10、与q同时为真或同时为假。 pqp q001010100111二、命题联结词20利用联结词可以把许多日常语句符号化。三、命题符号化基本步骤如下（1）从语句中分析出各原子命题，将它们符号化； （2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。21例1.12 将下列命题符号化（1）派小王或小李出差。（2）我们不能既划船又跑步。（3） 如果你来了，那么他唱不唱歌将看你是否伴奏而定。（4） 如果李明是体育爱好者，但不是文艺爱好者，那么李明不是文体爱好者。三、命题符号化22解 （1）令p：派小王出差；q：派小李出差。 则命题符号化为pq。 （2）令p：我们划船；q：我们跑步。

11、则命题可表示为(pq)。 （3）令p：你来了；q：他唱歌；r：你伴奏。 则命题可表示为p(qr) （4）令p：李明是体育爱好者；q：李明是文艺爱好者。 则命题可表示为(pq)(pq)三、命题符号化23例1.13 将下列各命题符号化(1) 张三与李四是好学生。(2) 张三与李四是好朋友。(3) 不管你努力与否，比赛定会取胜。(4) 小王现在在图书馆或在宿舍。(5) 如果我上街，我就去书店，除非我很累。三、命题符号化24解：(1) p：张三是好学生。q：李四是好学生则原命题符号化为:pq(2) p: 张三与李四是好朋友。则原命题符号化为:p(3) p:管你努.q:比赛取胜。则原命题符号化为:（pp

12、）q(4) p：小王现在在图书馆。q：小王现在在宿舍。则原命题符号化为:pq(5) p：我上街。q：我去书店。r：我很累。则原命题符号化为:（pq）r 或 r（pq）三、命题符号化25命题的概念五种基本的联结词命题符号化 总结26练习1. 判断下列语句哪些是命题。（1） 只有小孩才爱哭。（2） x+6=y。（3） 银是白的。（4） 起来吧，我的朋友。 2 将下列命题符号化（1）除非你已满16周岁，否则只要你身高不足4英尺就不能乘公园滑行铁道。 （2）学过“离散数学”或“数据结构”，但不是两者都学过的学生，必须再选学“计算机算法”这门课。 271.2 命题公式及其赋值重点公式、赋值和真值表的概念

13、公式的类型难点赋值的概念28命题常元 一个表示确定命题的小写字母命题变元 一个没有指定具体内容的命题符号一 、命题公式的概念 一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，它的真值就确定了。 29定义1.6 命题公式，简称公式，是按下列规则生成的: 命题常元和命题变元是公式 若G是公式，则G是公式(3) 若G，H是公式，则GH，GH，GH，GH都是公式(4) 只有有限次地应用(1)(3)组成的符号串才是公式。 命题公式（或简称公式）是由0、1和命题变元以及命题联结词按一定的规则产生的符号串。一 、命题公式的概念30约定：(1) 公式(G)的括号可以省略，即(G)

14、写成G。(2) 整个公式的最外层括号可以省略。例如(p(qr)可以写成p(qr)(3)公式中联结词的优先次序为：，。 在公式中，由于命题变元的出现，公式的真值是不确定的。只有将公式中的所有命题变元都解释成具体的命题时，公式才变成一个有真值的命题。例 下列符号串是否为命题公式。 （1） p(qpr)； （2）(pq)(qr)一 、命题公式的概念31定义1. 8 设p1，p2，pn是出现在公式G中的全部命题变元。指定p1，p2，pn的一组真值，则称这组真值为G的一个解释或赋值。记作I，公式G在I下的真值记作TI(G) 。若TI(G) =1，则称I为G的成真赋值，否则称为成假赋值有n个命题变元公式共

15、有的2n个解释例如： G (pq) r，则I：pqr011是G的一个解释，在这个解释下G的真值为1，即TI(G) 1二、赋值32定义1.9 将公式G在其所有解释下所取的真值列成一个表，称为G的真值表。公式G真值表的构造方法：开始，按二进制顺序一次写出各个赋值，直到(2)列出G的2n个解释，赋值从为止。然后按从低到高的顺序列出G的各层(3)根据赋值计算各个层次的真值并最终计算出G的真值 (1) 找出公式G中所有的命题变元，并按一定的顺序排列成p1，p2，pn 三、真值表33p q rpq(pq)prG=(pq) (pr)0 0 001000 0 101000 1 010010 1 110011

16、0 010011 0 110111 1 010011 1 11011例1.8 求出下列公式的真值表,并说明其所有的成真赋值。(1) G=(pq) (pr) (2) G=(pq) qr解： (1)公式G有3个命题变元，其真值表为：三、真值表34G=(pq) qr有3个命题变元，其真值表为：p q rpq(pq)(pq) qG= (pq) qr0 0 010000 0 110000 1 010000 1 110001 0 001001 0 101001 1 010001 1 11000三、真值表35定义 1.10 设G为公式:(1) 如果G在所有解释下都是真的，则称G是恒真的(或称G是重言式);(

17、2) 如果G在所有解释下都是假的，则称G是恒假的(或称G是矛盾式);(3) 如果G不是恒假的，则称G是可满足的。 注意：(1) 恒真公式的真值表的最后一例全为1，恒假公式的最后一例全为0，可满足公式的最后一例至少有一个1。(2) 恒真公式一定是可满足的，可满足的不一定是恒真的。 四、公式类型36例 判别下列公式的类型。 （1）q( p( pq) （2）(p q) p四、公式类型37总结公式、赋值和真值表的概念公式的类型38第二章 命题逻辑等值演算392.1 等值式重点等价式的概念基本等价式等价式的判别难点基本等价式等价式的判别40一、等价公式定义2.1 设G，H是两个公式，如果G，H在任意解释

18、下其真值都相同，则称G，H是等价的（等值的），记作GH。注意：(1) 符号“”与“”的区别与联系。 “”不是联结词，G H不表示一个公式，它表示两个公式间的一种关系，即等价关系。 “”是联结词，GH是一个公式。 G H当且仅当GH是永真公式。(2)当G是恒真式时，G 1；当G是恒假式时，则G 0。41例2.1 判断下列公式是否等价(1) pq与pq(2) p(qr)与(pq)r 解: (1)写出pq与pq的真值表：p qpqp qpq0 011 110 111 001 000 111 110 01表中第2列与第4列不尽相同，因此pq与pq不等价。一、等价公式42(2)写出p(qr)与(pq)r

19、的真值表：p q rqrp(qr)pq(pq)r0 0 011010 0 111010 1 001010 1 111011 0 011011 0 111011 1 000101 1 11111表中第3列与第5列完全相同，因此p(qr)与(pq)r等价。一、等价公式431. 双非律 (p) p 2. 幂等律 ppp ppp 3. 交换律 pqqp pqqp 4. 结合律 (pq) rp (qr) (pq) rp (qr) 5. 分配律 p (qr) (pq) (pr) p (qr) (pq) (pr) 6. 德摩根律 (pq) pq (pq) pq 二、基本的等价式447. 吸收律 p (pq)

20、 p p (pq) p 8. 零律 p00 p11 9. 同一律 p1p p0p 10. 排中律 pp1 11. 矛盾律 pp0 12. 蕴涵等价式 pqpq 13. 等值等价式 pq(pq) (qp) 14. 假言易位 pq qp 15. 归谬论 (pq) (pq) p 二、基本的等价式45 例 用真值表方法证明 ： (pq) pq解 令：A= (pq)，B= pq，构造A，B以及A B的真值表如下：由于公式AB所标记的列全为1，因此AB。 1、真值表方法pqpq(pq)pqpqAB00110101011110001100101010001111有两种方法：真值表方法，命题演算方法三、等价式

21、的判别46 (1) 代入规则 2等值演算方法 例如 F=（pq）（qp）是重言式，若用公式GH代换命题变元p得公式 F1=(GH)q)(q(GH)，F1仍是重言式。注意：因为G H当且仅当G H是重言式。所以，若对于等价式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等价式。代入规则 对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。三、等价式的判别47(2) 置 换规则 例如 设公式A=(pq)(pq)(rs)。 则pq，pq，(pq)(rs)等均是A的子公式， 但p，p和q等均不是A的子公式。 置换规则 设C是公式A的子公式，CD。如果将公式A中

22、的子公式C置换成公式D之后，得到的公式是B，则AB。 定义 设C是命题公式A的一部分（即C是公式A中连续的几个符号），且C本身也是一个命题公式，则称C为公式A的子公式。三、等价式的判别48(3) 等值演算 等值演算是指利用已知的一些等价式，根据置换规则、代入规则以及等价关系的可传递性推导出另外一些等价式的过程。 由代入规则知前述的基本等价式，不仅对任意的命题变元陪p，q，r是成立的，而且当p，q，r分别为命题公式时，这些等价式也成立三、等价式的判别49 例2.3 证明命题公式的等价关系： （pq）（rq）（pr）q；证明 （pq）（rq） （ pq）( rq) (等值等价式) （ p r）q

23、( 分配律) (pr)q (德.摩根定律) (pr) q (等值等价式) 所以（pq）（rq）（pr）q三、等价式的判别50 例2.4 证明下列命题公式的等价关系 (p q ) ( p ( p q ) ) p q 证明 (pq)( p(pq) (pq)( (p p ) q ) (结合律) (pq)( pq) (等幂律) (p q ) ( pq ) (交换律) p(q(pq) (结合律) pq (交换律，吸收律) 三、等价式的判别51例2.5 判别下列公式的类型。 （1） q (p(pq) （2）(pq)p解（1） q（p（pq） q（p（pq） q（pp）（pq） q（1（pq） q（pq）

24、qpq （qq）p 0 所以q (p (pq)是矛盾式。 （2） （pq）p （pq）p p 于是该公式是可满足式。 三、等价式的判别52 在自动控制和计算机中采用由电子元件组成和用信号控制的开关我们称之为门。基本的门电路有三种：非门、或门、与门。其功能完全对应于逻辑联结词， ，。 非门电路有一个输入端和一个输出端F=P四、应用53或门电路有两个或两个以上的输入端和一个输出端。 F= PQ 与门电路有两个或两个以上的输入端和一个输出端。 F= P Q四、应用54例 给定如下图的逻辑线路图，简化此逻辑线路图。四、应用55解：由图知，G=( P QR) (P Q) G( P Q) (R1) P Q

25、因此，原图的等效图为： 四、应用56 1判断下列等值式是否成立 （1）(pq) (r q)(pr) q （2）(pq)(p q)(pq)（2）（pq）（pq） (（pq）（qp）) (（pq）（qp）) （pq）解（1）（pq）（rq）（pq） （rq）（pr）q （pr）q（pr）q练习57总结 等价式的概念基本等价式等价式的判别真值表法等值演算582.2 析取范式与合取范式重点极小（大）项、范式、主范式的概念范式、主范式的求取难点范式、主范式的求取59 对偶公式：在只含有 ， ，3种联结词的公式G中，把， 互换，把0，1互换，其它符号不变，得到的新公式称为G的对偶公式，记作G*。 定理 设

26、G与G*是一对对偶公式，则(1) G (p1，p2，pn) G*( p1， p2， pn)(2) G( p1， p2， pn) G*( p1，p2，pn)一、对偶原理60例如： (pq) (pq) p( qq) p1p(pq) (pq) p ( qq) p0p 定理(对偶原理) 设G，H是两个公式，如果G H，则G* H*一、对偶原理61定义2.2 命题变元及其否定称为文字；有限个文字的析取式称为一个简单析取式(子句)； 有限个文字的合取式称为一个简单合取式(短语) 。例如 若p，q，r为命题变元，则p，q，r，p，q，r都是文字，pq， pqr，pqr都为子句， pq ，pqr都为短语。一个

27、文字即是子句也是短语。 二、析取范式与合取范式62定义2.3 有限个简单合取式的析取式称为析取范式； 有限个简单析取式的合取式称为合取范式。 例如 若p，q，r为命题变元，则(pq)(pqr) (pr)为析取范式；(pq) (pq r) (pr) 为合取范式。二、析取范式与合取范式63二、析取范式与合取范式 定理2.3 (范式存在定理) 任何公式都有与之等价的合取范式和析取范式。 求范式的步骤：(1) 用pqpq及pq(pq) (qp)消去G中的与，使G只含，三种联结词；(2) 用(p) p及德摩根律把移到命题变元的前面并化简；(3)反复使用分配律、交换律与结合律，得到G的合取与析取范式。64

28、 例2.7 求F1=(p(qr)s的合取范式和析取范式解 F1 (p(qr)s p(qr)s (析取范式)又 F1 p(qr)s (ps)(qr) (psq)(psr) （合取范式）二、析取范式与合取范式65例 求 F2= (pq) (pq)的析取范式、合取范式。解F2 (pq) (pq)(pq) (pq) (pq)(pq)(pq) (pq)(p(q(pq)(pq(pq) (pq)(pq) （合取范式）(p(pq)(q(pq)(pp) (pq)(pq)(qq) (pq)(pq) （析取范式）二、析取范式与合取范式66定义2.4 设有命题变元p1，p2，pn，称为p1，p2，pn的极小项，称为极

29、大项。其中，每一个pi*为pi或pi。注意：(1) n个变元有2n个不同的极小项；任一极小项在2n个解释下有且仅有一个解释使该极小项取值为1；在任一解释下，2n个极小项中有且仅有一个取值为1。 (2) n个变元有2n个不同的极大项，任一极大项在2n个解释下有且仅有一个解释使该极大项取值为0；在任一解释下，2n个极大项中有且仅有一个取值为0。三、极小项与极大项67解释极小项记法极大项记法0 0 0pqrm0pqrM00 0 1pqrm1pqrM10 1 0pqrm2pqrM20 1 1pqrm3pqrM31 0 0 pqrm4pqrM41 0 1pqrm5pqrM51 1 0pqrm6pqrM6

30、1 1 1pqrm7pqrM7例 写出命题变元p，q，r的所有的极小项m0，m1，m2，m3，m4，m5，m6，m7与所有的极大项M0，M1，M2，M3，M4，M5，M6，M7。三、极小项与极大项68定义2.5 设G为公式，p1，p2，pn为所有命题变元，若G的析取范式中的每个短语都是p1，p2，pn的一个极小项，则称该析取范式为G的主析取范式。恒假公式的主析取范式为0。 定理2.5 对任意的公式G存在唯一与其等价的主析取范式。 四、主析取范式69(1) 列出公式的真值表(2) 将真值表最后一列为1的解释的二进制数所对应的极小项写出(3) 将这些极小项析取起来用真值表法求主析取范式的求解步骤：

31、主析取范式的求解方法：等值演算法与真值表法四、主析取范式70例2.8 求(pq)r的主析取范式列出公式的真值表：p q rpq(pq)r对应的极小项记号0 0 0100 0 111pqrm10 1 0100 1 111pqrm31 0 001pqrm41 0 1001 1 0101 1 111pqrm7写出使得G取1的解释所对应的极小项。 G的主析取范式为m1 m3 m4 m7四、主析取范式71四、主析取范式用等值演算法求主析取范式用等值演算法求析取范式把析取范式中的每一个短语化为极小项的析取。例 用等值演算法求公式求pq的主析取范式pqpq(p(qq)(pp)q)(pq)(pq)(pq)(p

32、q)(pq)(pq)(pq) m0m1m372五、主合取范式 定义2.5 设G为公式，p1，p2，pn为所有命题变元，若G的合取范式中的每个子句都是p1，p2，pn的一个极大项，则称该合取范式为G的主合取范式。恒真公式的主合取范式为1。 定理2.5 对任意的公式G存在唯一与其等价的主合取范式。 73(1) 列出公式的真值表(2) 将真值表最后一列为0的解释的二进制数所对应的极大项写出(3) 将这些极大项合取起来用真值表法求主合取范式的求解步骤：主合取范式的求解方法：等值演算法与真值表法五、主合取范式74例2.8 求(pq)r的主合取范式列出公式的真值表：p q rpq(pq)r对应的极大项记号

33、0 0 010pqrM00 0 1110 1 010pqrM20 1 1111 0 0011 0 100pqrM51 1 010pqrM61 1 111写出使得G取0的解释所对应的极大项。 G的主合取范式为M0M2 M5 M6五、主合取范式75四、主合取范式用等值演算法求主合取范式用等值演算法求合取范式把合取范式中的每一个子句化为极大项的合取。例 用等值演算法求公式pq的主合取范式pq(p(qq)(pp)q)(pq)(pq)(pq)(pq)(pq)(pq)(pq) M0M1M276例2.9 求公式 F1= (pq)(pq)和 F2=p(p(qp)的主析取与合取范式解 F1 (pq)(pq) (

34、pq)(pq) 0 主析取范式 M0M1M2M3 主合取范式解 F2 p(p(qp) (pp) 1 主合取范式m0m1m2m3 主析取范式 五、主合取范式771. 利用主析取范式判定(1) 若公式 F(p1, p2，pn)的主析取范式包含所有2n个极小项，则 F是恒真公式。(2) 若F的主析取范式为0，则 F是恒假公式。(3) 否则，F为可满足的公式。六、利用主范式判定公式类型78 2 利用主合取范式判定 (1) 若公式F（p1, p2, , pn）的主合取范式包含所有2n个极大项，则F是恒假公式。 (2) 若F的主合取范式为1，则F是恒真公式。 (3) 否则，F为可满足公式六、利用主范式判定

35、公式类型79 例2.10 求公式F=(q(pq)p的主范式并判定公式的类型.解 (1) 求F的主析取范式F (q(pq)p q (pq)p (q(pp) (pq)(p(qq) （pq)(pq)(pq)(pq)(pq) (pq)(pq)(pq) 由此可知F是可满足公式。(2) 求F的主合取范式F （q(pq)p pq六、利用主范式判定公式类型80例 张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。请问3人到底谁在说谎？ 解 设 p：张三说真话。 q：李四说真话。 r： 王五说真话。题意可符号化为： G=(pq) (qr) (r(p q)。构造公式G的真值表： 七、应用 81p q

36、rpqqrp qr(p q)G0 0 0001000 0 1011100 1 0110110 1 1100001 0 0100101 0 1110001 1 0010101 1 100000 公式G只有在解释(0,1,0)下为真，即张三说谎话，李四说真话，王五说谎话。 七、应用82 例 某单位要从4位甲、乙、丙、丁中挑选两位职工去外地旅游，由于工作需要，选派时要考虑一下要求：(1) 甲、乙两人中去且仅去一人；(2) 乙和丁不能都去；(3) 若丙去，则丁必去；(4) 若丁不去，则甲也不去。问该单位派谁去符合要求？ 解 设 p：派甲去旅游。 q：派乙去旅游。 r：派丙去旅游。 s：派丁去旅游。则由

37、条件得到公式 G=(pq) (qs) (rs) ( sp)。 七、应用83G (pqrs) (psrs) (pqrs) m4 m9 m11公式G只有在解释(0,1,0,0) 、(1,0,0,1) 、(1,0,1,1)下为真。所以选派方案有：(1) 派乙去旅游；(2) 派甲、丁去旅游；(3) 派甲、丙、丁去旅游。由于只能派两人去旅游，所以只有方案(2)可行。 七、应用84 1判断公式F=(pQ)(pQ)是否为重言式或矛盾式？解 F (pQ)(pQ)(QpP) (pQ)(pQ)(Qp) (pq)(p(qp)(q(qp) (pq)(pq)(pp)(qq)(qp) (pq)(pq)(p q) F的主析

38、取范式既非空公式，又未包含22=4个项，故F不是重言式和矛盾式，只是可满足式。练习85总结对偶原理概念文字、句子（简单析取式）、短语（简单合取式）析取范式、合取范式极小项、极大项主析取范式、主合取范式范式、主范式的求取主范式的应用862.3 联结词的完备集重点真值函数的概念联结词完备集的概念联结词完备集的证明难点联结词完备集的证明87一、真值函数定义 称F:0,1n 0,1为n元真值函数。例如 F=pq就是0,12 0,1的2元真值函数，其定义域为00,01,10,11。n个命题变元共可构成 个不同的真值函数。其实这些个真值函数与 个不同的主析取范式一一对应。88二、联结词完备集定义 设S是一

39、个联结词集合，如果任何n(n1)n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。定理 S= , , 是联结词完备集。推论 以下联结词集都是完备集。(1) , , , (2) , , , , (3) ,(4) , (5) , 89二、联结词完备集定义 设p、q为两个命题，复合命题pq称为p与非q，称为与非联结词，并规定：当且仅当p和q的真值都是1时，pq的真值为0；否则pq的真值为1。定义设p、q为两个命题，复合命题pq称为p或非q，称为或非联结词，并规定：当且仅当p和q的真值都是0时，pq的真值为1；否则pq的真值为0。定理 , 都是联结词完备集。90第三章 命题逻辑

40、的推理理论913.1 推理的形式结构重点蕴涵与推理的概念基本蕴涵式蕴涵式的判定难点蕴涵式的判定92一、蕴涵的概念定理 设G，H是两个公式，则下列条件等价。(1) 对任意的解释I均有TI(G)TI(H);(2) 对任意解释I，若I满足G，则I满足H;(3) GH是恒真公式定义 设G，H是两个公式，若G，H满足上述定理的条件之一，则称G蕴涵H，记作GH。注意：和一样，不是逻辑联结词。虽然G，H是公式，但GH不是公式。推理是由前提出发推出结论的思维过程。93定义3.1 设G1，G2，Gn，H是公式，称H是G1，G2，Gn的逻辑结果。当且仅当G1G2Gn蕴涵H或(G1G2Gn) H是恒真的，记作(G1

41、G2Gn) H，也称G1，G2，Gn蕴涵H。此时，称由前提 G1，G2，Gn推出H的推理是有效的（或正确的），并称H为有效结论。说明：由前提G1，G2，Gn推结论H的推理是否正确与诸前提的排列次序无关。记G G1G2Gn，对于任意的解释，只要不出现G=1,H=0的情况，推理就是有效的。推理正确，并不能保证结论H一定为真。一、蕴涵的概念94一、蕴涵的概念定理3.1 G1，G2，Gn，PQ的充分必要条件是G1，G2，Gn (PQ)。 例3.1 判断下列推理是否正确(1)、p,pqq(2)、p,qpq(3)、下午马芳或者去看电影，或者去游泳；她没有去看电影。所以，她去游泳了。(4)、若下午气温超过3

42、0，则王小燕必去游泳；若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温必超过了30 。95化简 pqp 附加 ppq 假言推理 p，pqq 拒取式q， pq p 析取三段论 p，pqq 假言三段论 pq， qr pr 等价三段论 pq ， qr pr构造性二难 pq ， rs ， pr qs二、基本蕴涵式96判定“G H”是否成立的问题可转化为判定G H是否为重言式，有下述判定方法： （1）真值表； （2）等值演算； （3）假定前件为真 （4）假定后件为假1. 真值表方法例 证明 ：(pq)(p r)(q r) r证明 令公式 F =(pq)(pr)(qr)r， 其真值表如下：

43、三、蕴含式的判别97 公式F对任意的一组真值指派取值均为1，故F是重言式。p q rpqprqr(pq) (pr)(qr)F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10011111111110101110111010001010111111111三、蕴含式的判别982. 等值演算方法证明 (p(pq) q (p(pq)q (p(pq)q(pp)(pq)q(pq)q 因此 p(pq) q 三、蕴含式的判别例 证明 ：p(pq) q 993. 假定前件为真假定前件G为真，检查在此情况下，其后件H是否也为真。 例 证明 :q (pq) p证明令前件q(pq)为真

44、，则q为真, 且pq为真。于是q为假，因而p也为假。由此p为真。故蕴含式 成立。GHGH001101011101三、蕴含式的判别1004、 假定后件为假假定后件H为假，检查在此情况下，其前件G是否也为假. 例 证明蕴含式(pq) (rs) (pr) (qs)证明 令后件(pr)(qs)为假，则pr为真，qs为假,于是p、r均为真，而q和s至少一个为假。由此可知pq与rs中至少一个为假， 因此(pq)(rs)为假。故上述蕴含式成立。三、蕴含式的判别101例 分析下列推理的正确性条件：(1) 香烟有利于健康； (2) 如果香烟有利于健康，那么医生就会把香烟作为药品开给病人。结论：医生把香烟作为药品

45、开给病人。 解 设 p：香烟有利于健康 q：医生把香烟作为药品开给病人。则条件符号化为：p，pq。q是p，pq的逻辑结果，因此上述推理正确。四、应用102例 分析下列推理的正确性条件：(1) 如果你投资股票，那么你能发财； (2) 如果你发财了，你就会过的很幸福。结论：如果你投资股票，你就会过的很幸福。解 设 p：你投资股票 q：你发财了 r：你就过的很幸福。则条件可符号化为：pq，qr；结论符号化为pr。pr为pq，qr的逻辑结果，上述推理正确。 四、实例1031判定蕴含式p（qr） （pq）（pr）是否成立解假定后件（pq）（pr）为假，则pq为真，pr为假。由pr为假，得p为真，r为假。

46、又pq为真，于是q为真，qr为假。从而 p（qr）为假。因此蕴含式成立。练习104小结蕴涵与推理的概念基本蕴涵式蕴涵式的判定1053.2 自然推理系统重点推理规则及其应用形式证明反证法难点形式证明反证法1061. 双非律 (p) p 2. 幂等律 ppp ppp 3. 交换律 pqqp pqqp 4. 结合律 (pq) rp (qr) (pq) rp (qr) 5. 分配律 p (qr) (pq) (pr) p (qr) (pq) (pr) 6. 德摩根律 (pq) pq (pq) pq 一、推理规则基本等价式1077. 吸收律 p (pq) p p (pq) p 8. 零律 p00 p11

47、9. 同一律 p1p p0p 10. 排中律 pp1 11. 矛盾律 pp0 12. 蕴涵等价式 pqpq 13. 等值等价式 pq(pq) (qp) 14. 假言易位 pq qp 15. 归谬论 (pq) (pq) p 一、推理规则108一、推理规则化简PQP 附加 PPQ 假言推理 P，PQQ 拒取式Q， PQ P 析取三段论 P，PQQ 假言三段论 PQ ， QR PR 合取引入 P， Q PQ 构造性二难 PQ ， RS ， PR QS 基本蕴涵式109一、推理规则规则P在演绎过程中可以随便使用前提集合中任一公式。规则Q在演绎过程中可以随便使用前面演绎出来的某些公式的逻辑结果。规则D如

48、果需要演绎出的公式具有PQ的形式，则可以将P作为附加前提使用，设法演绎出Q来。110例 证明pq，pr，r蕴涵q。编号公 式依 据(1)(2)(3)(4)(5)rprppqq规则P规则P规则Q及(1)，(2)规则P规则Q及(3)，(4)证明:二、形式证明111例3.3 证明 r(pq)是前提pq，qr，ps ，s的结论。 所以pq，qr，ps， s r(pq)编号公 式依 据（1）（2）（3）（4）（5）（6）（7）（8）spsppqqqrrr（pq）规则P规则P规则Q及(1),(2)；规则P规则Q及(3),(4)规则P规则Q及(5),(6)规则Q及(4),(7)二、形式证明112证明 编号公

49、 式依 据(1)(2)(3)(4)(5)rprpp( qs)r(qs)r(qs)规则P规则Q及(1)规则P规则Q及(2),(3)规则Q及(4)(6)(7)(8)(9) q(rs)qrsrs规则Q及(5)规则P规则Q及(6),(7)规则Q及(8)例 试证 p(qs)，rp，q 蕴涵rs二、形式证明113 例 符号化下面语句的推理过程，并指出推理是否正确。“如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军，可知丁不能得亚军”。 解 设 p：甲得冠军；q：乙得亚军； r：丙得亚军；s：丁得亚军。 推理过程符号化为 p（qr），q p，sr，p

50、 s二、形式证明114 推理过程符号化为 p（qr），q p，sr，p s编号公 式依 据（1）（2）（3）（4）p(qr)pqrqp规则P规则P则Q及（1）,（2）规则P（5）（6）（7）（8）qrs rs则Q及（2）,（4）规则Q及（3）,（5）规则P规则Q及（6）,（7）二、形式证明115编号公 式依 据(1)rp规则P(2)r规则D(附加前提)(3)p规则Q及(1)，(2)(4)p(qs)规则P(5)qs规则Q及(3)，(4)(6)q规则P(7)s规则Q及(5)，(6)(8)rs规则D及(2)，(7)试证 p(qs)，rp，q 蕴涵rs证：三、附加前提证明法116反证法（间接证明法）定

51、义 设G1，G2，Gn是公式，若至少存在一个解释I使G1G2Gn在I下的值为1，则称公式G1，G2，Gn是相容的;若对任意解释I， G1G2Gn在I下的值为0，则称公式G1，G2，Gn是不相容的。 定理1 G1G2Gn H当且仅当 G1，G2，Gn ，H是不相容的。定理2 若存在一个公式R，使得 G1G2 Gn R R则公式G1，G2，,Gn是不相容的。四、反证法117思路 为了证明G1、G2、G nH，利用定理1，只需证明G1、G2、Gn、H是不相容的。 利用定理2，只需证明R，使得 G1G2GnH RR。四、反证法118例 证明：p q、qr、rs蕴涵 p 用反证法，将(p)作为附加前提，

52、添加到前提集合中，然后推出矛盾。编号公 式依 据(1)p规则D(附加前提)(2)p q规则P(3)q规则Q及(1)，(2)(4)qr规则P(5)r规则Q及(3)，(4)(6)rs规则P(7)r规则Q及 (6)(8)r r规则Q及(5)，(7)四、反证法119总结推理规则基本等价式基本蕴涵式规则P、Q、D形式证明附加前提法反证法1201.用形式证明方法证明：pq是前提（pq）r，rs，s的结论。 因此，（pq）r， rs， s p q编号公 式依 据（1）rs规则P（2）s规则P（3）r则Q及(1),(2)（4）(pq）r规则P（5）（pq）r则Q及(4)（6）（pq）规则Q及(3),(5)（7

53、）pq规则Q及(6)练习1212.张三说李四在说谎，李四说王五在说谎，王五说张三、 李四都在说谎。问张三、李四、王五三人，到底谁说真话，谁说假话？ 解 先将简单命题符号化。 令p：张三说真话；q：李四说真话； r：王五说真话， 由题意知推理的前提为： p q，pq，qr，qr， r（p q）， r（pq）。下面根据已知前提进行形式推理。练习122编号公 式依 据（1）p q规则P（2） qr规则P（3）pr规则Q及(1),(2)（4）r（pq）规则P（5）p（p q）则Q及(3),(4)（6）p（p q）规则Q及(5)（7）p规则Q及(6)（8）pq规则P（9）q规则Q及(7),(8)（10）

54、qr规则P（11）r规则Q及(9),(10)（12）pqr规则Q及(7),(9),(11)p q，pq，qr， qr，r（p q）， r（pq）。练习因此，由上述推理知张三说假话，王五说假话，只有李四说真话。123第四章 一阶逻辑基本概念124一阶逻辑（谓词逻辑）在命题逻辑中就无法表示这种推理过程。 逻辑学中著名的苏格拉底三段论 ：大前提p： 凡人都是要死的，小前提q: 苏格拉底是人，结 论r： 所以苏格拉底是要死的125一阶逻辑（谓词逻辑）命题逻辑命题被当作一个基本的，不可分割的单位。研究由原子命题和联接词所组成的复合命题。无法研究命题的内部结构及命题之间内在的联系。谓词逻辑对原子命题的成份

55、、结构和原子命题间的共同特性等作进一步分析。引入了个体词、谓词、量词、谓词公式等概念。研究谓词公式间的等值关系和蕴含关系。对命题逻辑中的推理规则进行扩充和进行谓词演算。1264.1 一阶逻辑命题符号化 重点谓词、量词、个体词的概念命题符号化难点命题符号化127一、个体词在谓词逻辑中，可将原子命题分解为个体词、谓词、量词三部分。例 在命题逻辑中 ，对下述论断无法判断其正确性。 苏格拉底三段论 ： 凡人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的。 128一、个体词定义 个体是指可以独立存在的客体个体可以是抽象的，也可是具体的。个体通常在一个命题里表示思维对象。将表示具体或特定的客体的个体词

56、称作个体常项，一般用小写英文字母a，b，c表示。将表示抽象或泛指的个体词称为个体变项，常用x，y，z表示。称个体变项的取值范围为个体域(或称论域)。有一个特殊的个体域，它是由宇宙间一切事物组成的，称它为全总个体域。在论述或推理中如没有指明所采用的个体域，都是使用全总个体域。129二、谓词定义 用来刻划个体的性质或个体之间关系的词称为谓词。刻划一个个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词。例4.1 （1）李明是学生； （2）张亮比陈华高； （3）陈华坐在张亮与李明之间。 在这三个命题中，李明、张亮、陈华都是个体；“是学生”是一元谓词， “比高”是二元谓词， “坐与之间”是三

57、元谓词。130二、谓词一、通常用大写字母表示谓词，小写字母表示个体。1、Q(x): x是学生；P(x,y): x比y高；R(x,y,z): x坐y与z之间；a:李明； b:张亮； c:陈华上述命题可分别表示为 Q(a), P(b,c), R(c,b,a)2、一般地，一个由n个个体和n元谓词所组成的命题可表示为F(a1,a2, ,an)，其中F表示n元谓词, a1,a2, ,an 分别表示n个个体。 3、注意：a1,a2, ,an的排列次序是重要的。二、谓词也有常项和变项之分。1、表示具体性质或关系的谓词称为谓词常项。2、表示抽象的、泛指的性质或关系的谓词称为谓词变项。131三、量词量词 在命题

58、里表示数量的词。对命题 “ 所有的正整数都是素数 ” 和“ 有些正整数是素数 ”仅用个体词和谓词是很难表达的。 132三、量词全称量词 “x”例4.2 所有人都是要死的。解 个体域为全体人的集合。D(x)：x是要死的。 命题可以表示为x D(x)存在量词 “x ” 例4.2 有些有理数是整数。解 个体域为有理数集合。令I(x)：x是整数。命题可以表示为x I(x)133四、命题符号化在命题符号化时，除特殊说明外，均使用全总个体域。而对个体变化的真正取值范围，用特性谓词加以限制。特性谓词 ：把命题的所讨论的个体从全总个体域中剥离出来的谓词。特性谓词的使用对全称量词，特性谓词作蕴含的前件。对存在量

59、词，特性谓词作合取项。134四、命题符号化例4.3 (1) 所有的人都是要死的。 (2) 有的人活百岁以上。当x的个体域E为全体人组成的集合时，符号化上述命题。令D(x)：x是要死的。则(1)可表示为x D(x)。令G(x)：x活百岁以上。则(2)可表示为xG(x)。当取x的个体域为全总个体域时，必须引入一个特性谓词将人从全宇宙的一切事物中分离出来。 令H(x)：x是人。（1）x( H(x)D(x) ) （2） x( H(x)G(x) ) 135四、命题符号化例4.4 将下列命题符号化，并讨论真值。1.所有的人都长着黑头发。2.有的人登上过月球。3.没有人登上过木星。4.在美国留学的学生未必都

60、是亚洲人。解：1.所有的人都长着黑头发。令 F(x)：x是人。G(x)：x长着黑头发。则命题符号化为：x( F(x)G(x) )。2.有的人登上过月球。令 F(x)：x是人。G(x)：x登上过月球。则命题符号化为： x( H(x)G(x) ) 。136四、命题符号化3.没有人登上过木星。令F(x)：x是人。G(x)：x登上过木星。则命题符号化为： x( H(x)G(x) ) 。4.在美国留学的学生未必都是亚洲人。令 F(x)：x在美国留学。G(x)：x是亚洲人。则命题符号化为：x( F(x)G(x) ) 。137四、命题符号化例4.5 将下列命题符号化。1.兔子比乌龟跑得快。2.有的兔子比所有