教学课件-离散数学(第二版)王宗传

离散数学是现代数学的一个重要分支,是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、代数系统和图论。本课程主要讲授以上四个方面的内容。

数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第一，二两章中介绍数理逻辑的内容。数理逻辑简介

内容：命题，逻辑联结词，命题符号化

(1)掌握命题概念

(2)掌握联结词含义及真值表

(3)掌握命题符号化方法

重点：第一章命题逻辑第一节命题与逻辑联结词一、命题的概念

命题：能判断真假的陈述句。

注：(1)命题必须是一个完整的陈述句．

（2）命题的真值具有唯一性，确定性．

（3）真值的唯一性并不一定要求现在就能判断出命题的真假，要是在将来某时候能判断出真假也行，真值是否唯一与是否知道其真值是两回事．真值真（记为T或1）假（记为F或0）例1、判断下列语句中哪些是命题．（1）人的血液是白色的．（2）x+y>5．（3）你的大学英语四级考试通过了吗？（4）明年六一儿童节是晴天．（5）2+3=5．（6）地球之外的星球上也有人类．（7）请讲普通话！（8）很多人喜欢中央3台的星光大道节目．（9）12是素数．（10）九寨沟的风景真是美丽啊！

判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。

表示。命题常项，命题变项均用二、逻辑联结词。

这五种常用的联结词有命题简单命题（不能再分解成更简单的命题）复合命题（由简单命题用联接词联接而成的命题）真值表

1、“非”称为的否定式，记作例如：：11是素数；：11不是素数取值1，取值0。真值表

2、“并且”称为的合取式，记作。

在例1．（2）中，设表示“2是素数”，表示“2是偶数”，则表示“2是素数和偶数”，由于的真值都是1，所以的真值也是1．例2、

将下列命题符号化．（1）王教授不仅研究经济学而且研究管理学．（2）王教授虽然研究经济学但不研究管理学．（3）王教授研究经济学及管理学．（4）王教授和李教授是大学校友．解：设：王教授研究经济学，：王教授研究管理学，则（1）（2）（3）分别符号化为,,.（4）是简单命题，符号化为：王教授和李教授是大学校友．

真值表

3、“或者”称的析取式，记作。例如，：小明学过英语，：小明学过日语，则小明学过英语或日语可表示为真值表：

4、“如果那么”称的蕴涵式，记作其中为前件，为后件。(1)如果天不下雨，我就骑车上班。

(2)只要天不下雨，我就骑车上班。

(3)只有天不下雨，我才骑车上班。

(4)除非天下雨，否则我就骑车上班。

(5)如果天下雨，我就不骑车上班。

(或

)例3、：天下雨，：我骑车上班。真值表：

5、“当且仅当”称的等价式，记作。是的充要条件，也是的充要条件。例4、：，：3是奇数(1)当且仅当3是奇数。(2)当且仅当3不是奇数。(3)当且仅当3是奇数。(4)当且仅当3不是奇数。6、逻辑联结词与自然语言中联结词的关系。

否定——不是，没有，非，不。

合取——并且，同时，和，既…又…，不但…而且…，虽然…但是…。

析取——或者，或许，可能。

蕴涵——若…则…，假如…那么…，既然…那就…，倘若…就…。

等价——当且仅当，充分必要，相同，一样。

7、运算顺序

逻辑联结词也称逻辑运算符，规定优先级的顺，若有括号时，先进行括号序为内运算。例如：三、命题符号化。

步骤：(1)找出各简单命题，分别符号化。

(2)找出各联结词，把简单命题逐个联结起来。例5、

将下列命题符号化．（1）小王不富有但很快乐．（2）小王现在乘坐公共汽车或坐飞机．（3）如果明天有雾，他就不能坐轮船而是乘车过江．（4）这个材料有趣，意味着这些习题很难，并且反之亦然．（5）如果这个材料无趣或者习题不是很难，那么这门课程就不会让人喜欢．（6）这门课程会让人喜欢，除非这个材料无趣并且习题很难．解：（1）设：小王富有，：小王很快乐，符号化为（2）设：小王现在乘坐公共汽车，：小王现在坐飞机，符号化为（3）设：明天有雾，：他坐轮船过江，：他乘车过江，符号化为对于（4）、（5）、（6），设：这个材料有趣，：这些习题很难，：这门课程会让人喜欢，则符号化分别为，，，．内容：命题公式，重言式，矛盾式，可满足公式。

重点：(1)掌握命题公式的定义及公式的真值表。

(2)掌握重言式和矛盾式的定义及使用真值表进行判断。

第二节命题公式与解释一、命题公式

通俗地说，命题公式是由命题常项，命题变项，联结词，括号等组成的字符串。

规定：公式中最外层的括号，及的括号可省略。

例1、判断以下字符串中哪些是命题公式。

(1)(2)(3)(4)(5)(6)解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。

二、，如公式，110(按字典序)为的成假赋值，111，011，010……等是的成真赋值。个命题变项的命题公式，共有含组不同赋值。公式的解释或赋值赋值成真赋值（使A为真的赋值）成假赋值（使A为假的赋值）三、真值表。

的真值表——指在所有赋值之下取值列成的表。

构造命题公式的真值表的具体步骤如下：（1）找出公式中包含的所有命题变项（若无下角标就按字典顺序给出），列出所有可能的赋值（个）；（2）按照优先级的运算顺序：，，，，，进行运算．如果出现括号，先进行括号中的运算，直到计算出公式的真值．例2、求下列命题公式的真值表。

(1)解：

(2)解：

四、命题公式的分类

2、判定方法:真值表法。1、定义：设是任意一个命题公式．（1）若在它的各种赋值下取值均为假，则称为永假式或矛盾式；（2）若在它的各种赋值下取值均为真，则称为永真式或重言式；（3）若至少存在一组赋值是成真赋值，则称为可满足式；例3、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？

(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)解：列出各题真值表如下(步骤简略)(1)、(2)、(5)、(6)、(9)为重言式；(3)、(8)为矛盾式；(4)、(7)、(10)及以上的重言式均为可满足式。内容：等值关系，24个重要等值式，等值演算。

重点：(1)掌握两公式等值的定义。

(2)掌握24个重要等值式，并能利用其进行等值演算。

第三节公式的等值演算一、两命题公式间的等值关系。

2、判定

。1、定义：设为两命题公式，若等价式是重言式，则称与是等值的，记作。是否重言式

。是否等值，即判断判断两公式(1)

，

解：作真值表如下：

例1、判断两公式是否等值。解：作真值表如下：

(2)

，

二、重要等值式。

2、结合律，3、分配律，1、交换律，4、德

摩根律，6、吸收律，5、等幂律，7、零律，8、同一律，9、互否律(矛盾律)(排中律)，11、蕴涵等值式

12、等价等值式

13、假言易位

14、等价否定等值式

15、归谬论

10、双重否定律

三、等值演算。

例2、验证下列等值式。

置换定理：如果。

，则（1）（2）（3）（1）解：

蕴涵等值式分配律

蕴涵等值式（2）

蕴涵等值式

蕴涵等值式德·摩根律双重否定律与分配律

蕴涵等值式解：（3）解：

蕴涵等值式等价等值式

蕴涵等值式德·摩根律交换律

分配律

排中律与同一律

分配律

排中律与同一律

考虑问题:能否利用等值式来化简，或判断公式的类型(重言，矛盾，可满足)。

判断一个公式是否重言式，矛盾式，可满足式，或者判断两个命题公式是否等值。有两种方法，即真值表法和等值演算法。

例3、用两种方法证明:

[证法一]用真值表法

由最后两列真值完全相同，于是命题成立。[证法二]用等值式法

蕴涵等值式

双重否定律

交换律

结合律

吸收律

例4、将下图所示的逻辑电路简化

解：将上述逻辑电路写成命题公式：

利用等值式将公式化简

分配律

结合律

等幂律

所以，该电路可简化为下图

：内容：联结词的全功能集，极小功能集,对偶原理。了解：全功能集，极小功能集。

第四节联结词全功能集与对偶原理

重点：掌握对偶式，对偶原理。真值表

：由定义知：

一、联结词。记作1、“的排斥或(异或)，之间恰有一个成立”称。真值表

：的与非式，记作并且2、“的否定”称。真值表：

的或非式，记作3、“或者的否定”称。二、全功能集，极小功能集。

全功能集：若干个联结词的集合，其余的联结词均可由它们表示。

最小全功能集：不含冗余联结词的全功能集。

例如：

等都是全功能集。等都是极小全功能集。

三、对偶原理。

1、对偶式。

定义：设公式仅含联结词，则将分别用替代，所得的公式称的对偶式。

与互为对偶式。例如

：与，与，与2、对偶原理。

所以可得：

若。，则例如：已知(分配律)，与均为相互对偶式，

且，与内容：命题公式的范式。

(2)掌握析取范式和合取范式的定义和求法步骤。

(3)掌握极小项，极大项的概念及主范式的求法。

第五节命题公式的范式重点：（1）掌握简单合取式和简单析取式的概念。

一、简单析取式，简单合取式。

简单析取式:由有限个命题变项或其否定构成的析取式简单合取式:由有限个命题变项或其否定构成的合取式例如：等都是简单析取式。，，，例如：等都是简单合取式。

，，，二、析取范式，合取范式。

例如：

为析取范式，

为合取范式。

定义：

由有限个简单合取式构成的析取式称作析取范式。由有限个简单析取式构成的合取式称作合取范式。例如：

为析取范式，

显然，

为合取范式

，为合取范式。

例如：

为析取范式。

范式存在定理：任一命题公式都存在与之等值的析取范式和合取范式。求范式步骤：

(2)否定消去或内移。

(3)利用分配律。

(1)消去联结词

解：原式

消去

内移

消去

上式即析取范式

例1、求公式的析取范式。分配律

对(分配)解：原式

消去

内移

消去

上式即合取范式

例2、求公式的合取范式。分配律

(分配)对三、主范式。

1、极小项，极大项。

定义：设命题公式含这个命题变项，则和分别称为极小项和极大项，其中为或。都是极小项，

都是极大项，

例如，对只含变项的命题公式中，但不是极小项。但不是极大项。极大项，极小项

。下面分别讨论，即个命题变项的极小项

成真赋值(二进制数)000001010011100101110111对应十进制数

01234567记法

极大项

成假赋值(二进制数)000001010011100101110111对应十进制数

01234567记法

2、主析取范式，主合取范式。主析取范式——每个简单合取式都是极小项的析取范式。

主合取范式——每个简单析取式都是极大项的合取范式。

两种求法，等值式法和真值表法。

定理：任何命题公式的主析取范式、主合取范式

都存在且都是唯一的。步骤：

(3)消去重复的及永假项。2.1、利用等值式法求命题公式的主析取范式。(1)求，的析取范式(2)利用

补充变元，(4)按角码顺序排序，并用“”表示。解：由例1的析取范式为

例3、求公式的主析取范式。(吸收律)步骤：

(3)求每个成真赋值对应的十进制数，即极小项的角码，将极小项按序析取即成。2.2、利用真值表求命题公式的主析取范式。(1)列出的真值表，(2)找出的所有成真赋值，解：(1)列真值表

例4、用真值表求的主析取范式。(2)的成真赋值有010，100，101，110，111(3)对应的十进制数为2，4，5，6，7所以的主析取范式为

步骤：(3)消去重复的及永真项；

2.3、利用等值式法求命题公式的主合取范式。

(1)求；的合取范式(2)利用

补充变元；(4)按角码顺序排序，并用符号“”表示；如。记为解：由例2，

合取范式

例4、求公式的主合取范式。

2.4、利用真值表求命题公式的主合取范式。

步骤：

(3)求每个成假赋值对应的十进制数，即极大项的角码，将极大项按序合取即成。(1)列出的真值表，(2)找出的所有成假赋值，例5、用真值表求的主合取范式。解：(1)由例3知真值表，的(3)对应的十进制数为0，1，3。

(2)的成假赋值有000，001，011，所以的主合取范式：思考：命题公式间有什么联系，能否通过其中一个求另一个？(观察例3，例5)的主合取范式，主析取范式由例3、例5知：2.5、已知命题公式的主析取范式(主合取范式)，

求主合取范式(主析取范式)。

(2)写出与(1)中极小项角码相同的极大项，

由的主合取范式步骤：

的主析取范式求(1)写出的主析取范式未出现的极小项，(3)由以上极大项合取即成的主合取范式。例6、(1)已知命题公式的主合取范式。(主析取范式为：求含3个命题变项)

解：的主合取范式为：

例6、(2)已知命题公式主合取范式为：的主析取范式。(求含2个命题变项)解：的主析取范式为：3、主范式的用途。

(1)判断两命题公式是否等值。

(2)判断命题公式的类型。

重言式主析取范式含全部的极小项主合取范式不含任何极大项(主合取范式记为1)矛盾式主析取范式不含任何极小项(主析取范式记为0)主合取范式含全部的极大项3、主范式的用途。

(2)判断命题公式的类型。

可满足式主析取范式至少含一个极小项主合取范式至少缺一个极大项(3)求成真(假)赋值。

(4)求真值表。

例7、已知含3个命题变项的公式：

和(1)判断的类型。解：为矛盾式。为可满足式，(2)判断是否等值。解：不等值。的成假赋值有010，011，100，101。

例7、已知含3个命题变项的公式：

和(3)求的成真赋值和成假赋值。的成真赋值有000，001，110，111。

解：(4)求的真值表。解：真值表

内容：重点：

(1)理解推理的概念；

(2)掌握8条推理定律；

(3)掌握推理规则；

(4)掌握构造证明法。

了解：

附加前提证明法和归谬法。

推理规则，构造证明法。推理的概念，推理定律，第六节命题逻辑中的推理一、推理的形式结构。

2、判断推理的方法。

等值演算法，真值表法，主析取范式法。

1、定义：

记作则称前提若为重言式，推结论的推理正确，为的逻辑结论或有效结论。。例1、判断下面各推理是否正确。

(1)如果天气凉快，小王就不去游泳，天气凉快，所以小王没去游泳。

结论：

推理形式结构为：

判断此蕴涵式是否为重言式。

前提：，解：设小王去游泳。：：天气凉快，[方法一]用等值式法。

所以推理正确。

[方法二]用真值表法。

其真值表中最后一列全为1，

所以推理正确。

[方法三]用主析取范式法。

主析取范式含全部最小项，所以推理正确。

(2)如果我上街，我一定去新华书店，我没上街，所以我没去新华书店。前提：

结论：

推理的形式结构为：

解：设：我去新华书店，：我上街，[方法一]

其主析取范式中缺极小项所以推理不正确。

，[方法二]

蕴涵等值式

吸收律

[方法三]所以推理不正确。

列出真值表，其最后一列不全为1,由于01是推理不正确。的成假赋值，并非重言式，二、构造证明法。

1、推理定律有以下8条：

(1)附加(2)化简(3)假言推理(4)拒取式

(5)析取三段论

(6)假言三段论

(7)等价三段论

(8)构造性二难

2、推理规则。

(1)前提引入规则

(3)置换规则

3、构造证明法。

依照推理规则，应用推理规律。

(2)结论引入规则

例2、构造下列推理的证明。

(1)前提：

结论：

证明：前提引入

②

前提引入

前提引入

③

④

①②③构造性二难

①(2)前提：

结论：

证明：

①

前提引入

前提引入

②

③

①②拒取式

④

前提引入

⑤

③④假言推理

⑥

前提引入

⑦

⑤⑥拒取式

⑧

前提引入

⑨

⑦⑧析取三段论

例3、写出对应下面推理的证明。

(1)张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎．问张三、李四、王五3人，到底谁说真话，谁说假话？解：先将命题符号化．设：张三说真话；：李四说真话；：王五说真话前提：，，，,,推理过程：①前提引入②前提引入③①②假言三段论④前提引入⑤

③④假言三段论⑥⑤置换⑦⑥置换⑧前提引入⑨⑦⑧假言推理⑩

前提引入⑾⑨⑩假言推理⑿⑦⑨⑾合取引入因此，由上述推理可知：张三说假话，王五说假话，只有李四说真话．(2)如果小王是理科生，他的数学成绩必好．如果小王不是文科生，他必是理科生．小王数学成绩确实不好．所以小王是文科生．解：先将命题符号化．设：小王是理科生；：小王是文科生；：小王数学成绩好．

前提：；；结论：证明：①前提引入②前提引入③①②拒取式④前提引入⑤③④拒取式⑥

⑤置换3、附加前提证明法和归谬法。

(1)附加前提证明法。

例4

用附加前提证明法证明下面推理．前提：，，结论：证明：①前提引入②附加前提引入③①②析取三段论④前提引入⑤③④假言推理⑥前提引入⑦⑤⑥假言推理(2)归谬法。

因为即证明

(其中为任意命题公式)例5

构造下面推理的证明．前提：，，结论：证明:①否定结论引入

②①置换③②化简④前提引入⑤③④拒取式⑥前提引入⑦⑤⑥析取三段论⑧前提引入⑨⑦⑧假言推理⑩②化简⑾⑨⑩合取由⑾得出了矛盾，根据归谬法说明推理正确．一、命题与联结词。

1、基本概念。

2、应用。

(1)选择适当的联结词将命题符号化。

(2)判断命题(简单或复合)的真假。

命题与真值；简单命题和复合命题；

命题常项和变项；五个联结词真值表。

，第一章

小结与例题

二、命题公式及分类。

1、基本概念。

命题公式的定义；公式的赋值；

重言式，矛盾式，可满足式。

2、应用。

(1)求给定公式的真值表，及成真赋值，成假赋值。

(2)用真值表判断给定公式的类型。

三、等值演算。

1、基本概念。

两个公式等值的含义；等值演算。

2、应用。

(1)灵活运用24个重要等值式。

(2)用等值演算判断公式的类型及两个公式

是否等值(也可用真值表)。

四、联结词全功能集与对偶原理

基本概念联结词的全功能集，极小全功能集对偶原理五、命题公式的范式

1、基本概念。

简单析取式，简单合取式；

析取范式，合取范式；极小项，极大项；

主析取范式，主合取范式。

2、应用。(1)求给定公式的主析取范式和主合取范式。

(2)用主析取范式或主合取范式判断两公式是否等值。(3)用主析取范式或主合取范式求公式的成真或成假赋值。

(4)用主析取范式或主合取范式判断公式的类型。

六、推理理论。

1、基本概念。

推理，推理规则，推理定律；构造证明法。

2、应用。

(1)判断推理是否正确：真值表法

等值演算法

主析取范式法(主合取范式法)。

(2)用8条推理定律构造推理的证明。

例1、判断下列各语句中，命题，简单命题，

复合命题，真命题，假命题，真值待定的命题各有哪些？

(2)2是素数或是合数，

(4)只有4是奇数，5才能被3整除。

(5)明年5月1日是晴天。

(1)，(3)若，则5是偶数，解：命题有(2)－(5)，其中(5)是简单命题，(2)，(3)，(4)是复合命题，

(2)，(4)为真命题，(3)为假命题，(5)真值待定。

例2、

设：天正在下雪；：我将进城；：我有空。用自然语言写出下列命题。

(1)解：我将进城去当且仅当我有空且天不下雪。

(2)解：虽然天正在下雪，但我将进城去。(3)解：我进城当且仅当我有空。(4)解：天不下雪且我没空。例3、

设试求下列命题的真值。的真值为0，

、的真值为1，

、(1)解：(2)解：(3)解：(4)解：例4、简化下列命题公式。(1)解：(2)解：(3)解：(4)解：例5、判断下列各命题公式，哪些是重言式，矛盾式，可满足式？(1)(2)(3)解：可用真值表法，等值演算法，主析取(主合取)范式等方法判断公式的类型，

(2)为重言式，(3)为矛盾式，(1)，(2)均为可满足式。

例6、求命题公式

的主析取范式，主合取范式，成真赋值和成假赋值。

解：先求主析取范式

故主合取范式为

成真赋值为极小项角码对应的二进制数，00，10，11。

成假赋值为极大项角码对应的二进制数，即01

例7、设(1)求的真值表。(2)求的主析取范式、主合取范式。解：例8、写出对应下面推理的证明。有红、黄、蓝、白四队参加足球联赛。如果红队第三，则当黄队第二时，蓝队第四；或者白队不是第一，或者红队第三；事实上，黄队第二。因此，如果白队第一，那么蓝队第四。

证明：设

：红队第三，：黄队第二，：蓝队第四，：白队第一。前提：结论：前提：结论：前提引入

附加前提引入①②析取三段论前提引入④

①

③

②

⑤③④假言推理前提引入⑤⑥假言推理⑦⑥由附加前提证明法知推理正确。

例9、一公安人员审查一件盗窃案，已知的事实如下：

(1)甲或乙盗窃了录音机；

(2)若甲盗窃了录音机，则作案时间不能发生在午夜前；(3)若乙的证词正确，则午夜时屋里灯光未灭；

(4)若乙的证词不正确，则作案时间发生在午夜之前；

(5)午夜时屋里灯光灭了。

问是谁盗窃了录音机。

：乙盗窃了录音机，

：作案时间发生在午夜前，

：乙的证词正确，

：午夜灯光未灭。

解：设：甲盗窃了录音机，

前提：，，，，结论：

或者①

前提引入

②

前提引入

③

①②拒取式

④

前提引入

⑤

③④假言推理

⑥

前提引入

⑦

⑤⑥拒取式

⑧

前提引入

⑨

⑦⑧析取三段论

所以是乙盗窃了录音机。

第二章

谓词逻辑

第一节谓词逻辑基本概念

内容：

个体词，谓词，量词，命题符号化。

重点：

1、掌握个体词，谓词，量词的有关概念，

2、掌握在一阶逻辑中的命题符号化。

一、谓词逻辑研究的内容。例如：判断以下推理是否正确：

凡人都是要死的，

苏格拉底是人，

所以苏格拉底是要死的。

这是著名的“苏格拉底三段论”，

若用推理形式为分别表示以上3个命题，，不是重言式。二、个体词，谓词，量词。

1、个体词，谓词

。例如：陈景润是数学家．。

是无理数。

小王比小李高2厘米。

(1)个体词——简单命题中表示主体或客体的词(由名词组成)。个体域(或称论域)——个体变项取值的范围。

(2)谓词——刻画个体词的性质或个体词之间关系的词。个体词个体常项

用个体变项

用表示表示谓词谓词常项谓词变项都用表示：小王，

：小明，

：小王比小明高。

元谓词(用表示)如高。比：其中为个体词。是二元谓词，例如：李华是大学生，

小明是大学生。

一元谓词

个体常项

个体常项

：李华

：小明

分别表示李华，小明是大学生，

它们是0元谓词。

：是大学生，

2、量词——表示数量的词。

全称量词量词存在量词使用量词时，应注意以下6点：

(1)在不同个体域中，命题符号化的形式可能不一样，

(2)一般，除非有特别说明，均以全总个体域为个体域，(3)在引入特性谓词后，使用全称量词用“使用存在量词用“”，”，(4)个量词，元谓词化为命题至少需要如(5)当个体域为有限集时，，则(6)多个量词同时出现时，

不能随意颠倒顺序。

三、命题符号化。

例1、在一阶逻辑中将下面命题符号化。

(1)所有的有理数均可表成分数。

解：因无指定个体域，则以全总个体域为个体域。：为有理数，：可表成分数，

(2)有的有理数是整数。

解：：为有理数，：为整数，注：若本题指定的个体域为有理数集，

则(1)，(2)分别符号化为和。例2、在一阶逻辑中将下列命题符号化。

(1)凡偶数均能被2整除。

(2)存在着偶素数。

解：

：是偶数，：能被2整除，：解：

是偶数，：是素数，(3)没有不犯错误的人。

原命题即：“每个人都犯错误”。

又可符号化为：

解：

：是人，：犯错误，(4)每列火车都比某些汽车快。

某些汽车比所有的火车慢。

第一句为：

或

解：

：是火车，：是汽车，

：快，比第二句为：

或

例3

设个体域为实数集，令是整数．是有理数．．．试用日常语言叙述下列命题，并指出其真值．（1）（2）（3）（4）

（2）存在着实数，使得对于任意实数，都有．该命题真值为0．（3）存在着实数和,使得且．该命题真值为1．（4）对于任意实数，存在着实数，使得且，解：（1）对于任意实数，存在着实数，使得．该命题真值为1．该命题真值为0．

内容：

合式公式，解释，逻辑有效式，矛盾式，可满足式。重点：

(1)掌握合式公式的概念，

(2)掌握量词的辖域，约束变项，自由变项的概念，(3)掌握逻辑有效式，矛盾式，可满足式的概念。第二节

一阶逻辑合式公式及解释

一般：

(1)换名规则，代替规则，

(2)解释的概念，

(3)代换实例。

了解：

(1)闭式的概念，

(2)判断合式公式的类型。

一、一阶逻辑中的合式公式。

1、字母表。

(1)个体常项：

(2)个体变项：

(3)函数符号：

(4)谓词符号：

(5)量词符号：

(6)联结词符：

(7)括号和逗号：(，)，

，

。

2、元的递归定义。

(1)个体常项和变项是元。

(3)只有有限次地使用(1)、(2)生成的符号串才是元。

例如：

等都是元。

(2)若是元，则元函数，是任意是元。3、原子公式。

4、合式公式的递归定义。

(1)原子公式是合式公式；

设是项，则称为原子公式。元谓词，是任意(3)若也是合式公式；

是合式公式，则是合式公式，则也是合式公式；(2)若(5)只有有限次地应用(1)－(4)构成的符号串

才是合式公式(也称谓词公式)，简称公式。

(4)若也是合式公式；是合式公式，则5、约束出现，自由出现。

在合式公式中，称为指导变项，称为相应量词的辖域，

约束出现，自由出现

例1、指出下列各合式公式中的指导变项，量词的辖域，个体变项的自由出现和约束出现。

（1）（2）（3）闭式(封闭的合式公式)——

无自由出现的个体变项的合式公式。

换名规则——指导变项，约束变项换名

例如：

换成

代替规则——自由变项代替

例如：

换成

二、合式公式的解释。

对公式中各种变项(个体变项，函数变项，

谓词变项)，指定特殊的常项去代替，就构成了公式的一个解释。

(1)非空个体域；(2)中一部分特定元素；1、解释由以下4部分组成：(3)上一些特定的函数；(4)上一些特定的谓词；例2给定解释如下：中特定元素；

(1);(2)函数为；(3)谓词为；(4)为为

．；在解释下，求下列各式的真值．（1）；（2）；（3）；（4）．解：设（1）、（2）、（3）、（4）中公式分别为．在解释下，．2、逻辑有效式(永真式)，矛盾式(永假式)，可满足式。

逻辑有效式——

在任何解释下都取值为真的合式公式。

矛盾式——

在任何解释下都取值为假的合式公式。

可满足式——

至少存在一种解释使其取值为真的合式公式。

有一些公式，可以利用命题公式的结论。

代换实例——

个命题变项将词公式称为设是含的命题公式，所得的谓取代个谓词的代换实例。

例如：

等都是的代换实例。

命题公式中重言式，矛盾式的代换实例在谓词公式中仍是重言式(逻辑有效式)，矛盾式。

例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。

(1)解：

设。是任意的解释，设其个体域为若存在为假，为假，则，从而为真；(2)解：

原公式是命题公式的代换实例，(重言式)，

而且所以原公式是逻辑有效的。

(3)解：

原公式是命题公式的代换实例，(重言式)，

而且所以原公式是逻辑有效的。

(4)而且(矛盾式)，

所以原公式是矛盾式。

解：

原公式是命题公式的代换实例，

内容：

一阶逻辑等值式，前束范式。

重点：

掌握基本等值式，

(量词否定等值式，量词辖域收缩与扩张等值式，量词分配等值式)的内容。

一般：

使用基本等值式进行等值演算。

了解：

前束范式的定义和求法。

第三节谓词逻辑等值式一、一阶逻辑等值式。

已有的等值式命题公式中的24个等值式及代换实例由换名规则及代替规则所得公式与原公式等值定义：

若为逻辑有效式，记定理2．1量词否定等值式。

(1)(2)定理2．2量词分配等值式。

(1)(2)定理2．3量词辖域收缩与扩张等值式。

(1)(2)(4)(3)(5)(6)(7)(8)定理2．4多个量词间的次序排列等值式。

(1)(2)二、前束范式。

前束范式：形式

例如：

，等都是前束范式，

而

等都不是前束范式。

任一合式公式都可表示为前束范式，其化归步骤如下：（1）消去公式中出现的多余量词；（2）将合式公式中出现的联结词都化为（3）利用双重否定律，德·摩根律及量词否定等值式将合式公式中的否定字符深入到谓词字母前；（4）利用代替规则和换名规则，使所有约束变元均不相同，并且使自由变元与约束变元不同．（5）利用量词辖域收缩与扩张等值式，扩大量词的辖域至整个公式．例2、求下列公式的前束范式。

解：

(1)（定理2．1（2））（换名规则）（定理2．3

（1）①）（定理2．3

（1）①）(2)解：

（代替规则）（换名规则）（定理2．3（2）③）（定理2．3（2）④）（定理2．3（1）③）（定理2．3（1）④）内容：

谓词逻辑推理理论。

了解：

推理规则在推理中的正确使用。

重点：

掌握谓词逻辑推理的概念。

一般：

全称量词消去规则，全称量词引入规则，存在量词引入规则，存在量词消去规则。第四节谓词逻辑中的推理

一、谓词逻辑推理的概念。

1、概念。

已有的推理定律命题公式中的重言蕴涵式及代换实例一阶逻辑中的等值式(每个等值式可产生两条推理定律)若则称推理正确，记为

为逻辑有效式，2、量词分配定律。

(1)(2)(3)(4)二、推理规则。

1、全称量词消去规则

要求：

(1)中自由出现的个体变项，是(2)中约束出现的个体变项，

为任意的不在(3)为任意的个体常项。2、全称量词引入规则

要求：

(1)中自由出现，且在均为真，(2)取代中约束出现。不能在的取任何值时3、存在量词消去规则

要求：

(1)为真的特定的个体常项，

是使(2)中出现过，不曾在(3)个体变项时，不能用此规则。

外还有其他自由出现的

中除4、存在量词引入规则

要求：

(1)是特定的个体常项，(2)取代中出现过。

不能已在的：苏格拉底。

解：设：是人，：是要死的，前提：

结论：

例1证明苏格拉底三段论“凡人都是要死的．苏格拉底是人．所以苏格拉底是要死的．”证明：

①

前提引入

②

①

③

前提引入

④

②③假言推理

例2指出下面推理的错误．

①前提引入②①UI③②EI④

③UG⑤④EG解：

因中存在自由出现的个体变项，因而不能使用EI规则，所以②～③错误．例3构造下面推理的证明．前提：结论：证明：①前提引入②前提引入③①UI④②UI⑤④假言易位⑥

③⑤假言三段论⑦⑥假言易位⑧⑦UG一、谓词逻辑的基本概念。

1、基本概念。

个体，个体域，个体词，个体常项和变项；

谓词；量词，全称量词和存在量词。

2、应用。

在谓词逻辑中将命题符号化。

第二章

小结与例题

二、谓词逻辑合式公式及解释。

1、基本概念。

合式公式；辖域，约束变项，自由变项；

闭式；解释；代换实例；逻辑有效式，

矛盾式，可满足式。

2、应用。

(1)求某些公式在给定解释下的真值。

(2)判断某些简单公式的类型。

三、谓词逻辑等值式。

基本概念。

等值式，常用等值式；前束范式。

四、谓词逻辑推理理论。

1、基本概念。

推理；全称量词消去规则全称量词引入规则存在量词引入规则，，存在量词消去规则。，2、应用。

用构造法证明某些简单的推理。

例1、在一阶逻辑中将下列命题符号化。

(1)至少有一个实数不是自然数

(2)任何金属均可溶解于某种液体中。

：解：：是液体，：是金属，，符号化为溶解设是实数，是自然数，符号化为

解：例2、将下列命题译成自然语言，并确定其真值。

(个体域为)真值0。

真值0。

(1)，其中解：对任意正整数使得，，存在正整数。(2)，其中解：存在正整数满足，，使得对任意的正整数。真值0。

真值1。

(3)，其中解：对任意正整数使得，，存在正整数。(4)，其中解：对任意正整数使得，，存在正整数。设解释I为：个体域为，谓词例3根据解释I，求下列各式的真值：（1）；（2）；（3）．解：（1）（2）（3）例4

航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明这个人一定不是航海家．证明：设个体域是人的集合．谓词是航海家；教育他的孩子成为航海家．前提：结论：证明：①

前提引入②①EI③前提引入④③UI⑤②④拒取式⑥②⑤合取⑦⑥EG现代数学中，每个对象(如数，函数等)本质上都是集合，都可以用某种集合来定义，数学的各个分支，本质上都是在研究某一种对象集合的性质。集合论的特点是研究对象的广泛性，它也是计算机科学与工程的基础理论和表达工具，而且在程序设计，数据结构，形式语言，关系数据库，操作系统等都有重要应用。集合论是研究集合一般性质的数学分支，它的创始人是康托尔(，1845－1918)。在集合论简介

内容：

集合，元素，子集，幂集等。

重点：

(1)掌握集合的概念及两种表示法，

(3)掌握子集及两集合相等的概念，

(4)掌握幂集的概念及求法。

(2)常见的集合

和特殊集合，第三章

集合第一节

集合的基本概念

一、集合的概念。

1、集合——一些确定的对象的整体。

集合用大写的字母标记

其中的对象称元素，用小写字母标记

表示集合含有元素注意：

(1)或

(2)集合中的元素均不相同

表示同一个集合。

(3)集合的元素可以是任何类型的事物，

一个集合也可以作为另一个集合的元素。

例如：

2、集合的表示法。

(1)列举法(将元素一一列出)例如：

(2)描述法(用谓词概括元素的属性)例如：

一般，用描述法表示集合

3、常见的一些集合。

4、集合间的关系。

(1)的子集，记为为的真子集，记

5、特殊的集合。

空集

(2)对任意集合有(3)两集合相等，记作全集)(或(为任一集合)例1、选择适当的谓词表示下列集合。

(1)小于5的非负整数集

(2)奇整数集合

(3)10的整倍数集合，

(4)例2、确定下面命题的真值：

(1)真值

真值

(2)(3)真值

(4)真值

(5)真值

(6)真值

(7)真值

(8)真值

例3、有可能，且为集合，若吗？吗，有可能解：两种情形都有可能。

设，则。，有又设，则。，但二、幂集。

1、子集。

元个元素的集合)的元集(例如：为3元集。0元子集：(只有一个)，1元子集：个)，(共2元子集：个)，(共3元子集：个)。(共一般，个。元集共有子集解：

2、集合的幂集，记的全体子集为元素的集合。——例4、。，求若个元素。有个元素，则有例5、求以下集合的幂集。

(1)解：

(2)解：

(3)解：

(4)解：

(5)解：

内容：

集合的运算，文氏图，运算律。

重点：

(1)掌握集合的运算

(2)用文氏图表示集合间的相互关系和运算，

(3)掌握基本运算律的内容及运用。

第二节

集合的运算一、集合的运算。

，相对补集集合，的并集交集，对称差。绝对补集，(当不交)时，称以上定义加以推广，

(其中为全集)，

(1)(2)(3)(4)，求出以下集合。

，例1、设，，(5)(6)(7)(8)1、文氏图。

(2)矩形内的圆表示集合，

(1)用大矩形表示全集，二、文氏图。(3)除特殊情形外，一般表示两个集合的圆是相交的，

(4)圆中的阴影的区域表示新组成的集合。

2、用文氏图表示集合的有关运算。

例2、用文氏图表示下列集合。

(1)(2)(3)(4)例3、用集合公式表示下列文氏图中的阴影部分。

(1)解：

(2)解：

三包含排斥定理

设和是两个有限集合，则，其中分别表示、的元数．

把包含排斥定理推广到个集合的情况可用如下定理表述：

设为有限集合，其元数分别为，则例4求从1到500之间能被2,3,7任何一个数整除的整数的个数．例5有100名程序员，其中47名熟悉FORTRAN语言，35名熟悉PASCAL语言，23名熟悉这两种语言．问有多少人对这两种语言都不熟悉？

1、幂等律：

，2、结合律：

,3、交换律：

,4、分配律：

,第三节集合的运算性质5、同一律：

,6、零律：

,7、互否律：

(排中律)，

(矛盾律)8、吸收律：

，9、德

摩根律：

10、双重否定律：

以上恒等式的证明思路：

欲证。，，即证对任意故

例4、证明分配律

。证明：

对任意，除基本运算外，还有以下一些常用性质(证明略)13、

14、

15、

12、11、，，16、

17、18、

19、

20、

“

”的交换律“

”的结合律故

例5、证明：(第14条)证明：

对任意，证明：

例6、证明。例7、化简

所以原式化简为

解：因为，所以，又因为所以，又

最后，原式化简为。例8、设为假的各有哪些？（1）（2）（3）的子集，以下命题中为真，均为真命题假命题真命题一、笛卡儿积。

1、有序对，记。特点：

(1)，时，(2)。有序。，记元组第四节序偶与笛卡儿积2、有序元组

是一个有序对，其中第一个元素是一个有序元组，一个有序元组记作

即2、笛卡儿积。

定义：集合。的笛卡儿积，记作和例1、

，

求。

，，，，解：

当且仅当

例2、设。，求解：

(2)笛卡儿积是集合，有关集合的运算都适合。

(3)一般，。注意：

(1)若则元集，是元集，是元集。为3、笛卡儿积。

阶特别，当记为时，。如，例3设

试求：（1）；（2）；（3）。解：

（1）（2）}（3）

笛卡儿积运算具有以下性质：

1．若中有一个空集，则它们的笛卡儿积是空集，即2．当且都不是空集时，有3．当都不是空集时，有4．笛卡儿积运算对或运算满足分配律，即(1)(2)(3)(4)例4、证明：

证明：

对任意

，

故。一、集合的基本概念。

1、基本概念。

元素和集合的属于关系；有限集和无限集；子集和真子集；集合的相等；空集和全集；幂集。2、应用。

(1)用集合的两种表示法表示集合。

(2)求给定集合的幂集。

第三章

小结与例题

二、集合的基本运算与性质。

1、基本概念。

交集，并集，差集，补集，对称差集；文氏图；基本运算律。

2、应用。

(1)用文氏图表示集合间的相互关系和运算。

(2)运用基本运算律进行证明，化简等。

三序偶与笛卡儿积表示计算机科学系学生的集合，

表示二年级大学生的集合，

表示数学系学生的集合，

表示选修离散数学的学生的集合，

表示爱好文学的学生的集合，

表示爱好体育运动的学生的集合，

用集合交集，并集和包含关系表示：

(1)所有计算机科学系二年级的学生都选修离散数学，

解：

例1、设表示一年级大学生的集合，

(2)数学系的学生或者爱好文学或者爱好体育运动，

解：

(3)数学系一年级的学生都没有选修离散数学，

解：

(4)只有一、二年级的学生才爱好体育运动，

解：

(5)除去数学系和计算机科学系二年级的学生外都不选修离散数学。

解：

(1)解：

解：

例2、设，，确定在以下条件下集合相等？

中哪个可能与，，(2)，但解：

或(4)若解：

或例2、设，，确定在以下条件下集合相等？

中哪个可能与，，(3)且解：

与其中任何集合都不相等

例2、设，，确定在以下条件下集合相等？

中哪个可能与，，(5)若且例3、简要说明：举出它们的元素和子集。

的区别，与子集有解：是无任何元素的集合，，是以集合为元素的集合，

元素为。，子集有例4、设

，，，，问上述集合中有哪些是相等的。

解：

(1)解：结论不一定成立。

例5、设是集合，证明或反驳下列断言。

若则有，，，，，但若则有，，，。(2)解：结论不一定成立。

例5、设是集合，证明或反驳下列断言。

若则有

，，，，，但若则有，，，。(3)解：结论成立。

由因。有知：

故。例5、设是集合，证明或反驳下列断言。(1)，有

证明：设

例6、设为任意集合，证明：

又，，即有，故所以。例6、设

为任意集合，证明：

(2)证明：设

，有

又，，故即，所以。例7、求下列集合的基数和每个集合的幂集。

(1)解：基数2，

幂集为：

(2)解：基数3，

幂集为：

(1){2，4，6，8}解：例8、设试用其中：表示下述集合。(2){3，6，9}解：例8、设试用其中：表示下述集合。(3){10}解：例8、设试用其中：表示下述集合。解：例8、设试用其中：表示下述集合。(4)是偶数例8、设试用其中：表示下述集合。(5)是奇数)是正偶数)解：例8、设试用其中：表示下述集合。(1)所有奇数的集合；

解：

(2)解：

例9、

都是表示下列集合。

和的子集，试用(3)解：

(4)解：

例9、

都是表示下列集合。

和的子集，试用内容：

二元关系，关系图，关系矩阵，关系的运算重点：

(1)二元关系的定义及三种表示法，

(2)一些特殊的二元关系。

第四章二元关系和函数第一节二元关系及其运算（3）二元关系的逆、复合、幂运算了解：关系的复合运算性质，矩阵法求幂运算一、二元关系。

1、定义：(1)若集合则称为空集或它的元素都是有序对，

为二元关系。

若否则，记作，，则记作。

(2)的关系，到的任何子集都称作从特别，当上关系。

时，称作设

则的关系。

到都是从例1、，2、上不同关系的数目。

若则，元集，记为，的子集共有个，元集个。上不同的关系共有3、特殊的关系。

空关系。，恒等关系，全域关系对任意集合，空关系，全域关系，恒等关系。4、常用关系。

(1)设上小于等于关系：

，(2)设上整除关系：

，(3)幂集：上的包含关系解：

例2、。，，求解：

，

例3、。上的包含关系，求有三种集合表示法矩阵表示法图形表示法5、上二元关系的表示法。

解：

关系图：

例4、已知求，上关系

，和关系图。的关系矩阵一般：设

，其中

关系图表示点(边(每个有序对对应一条有向弧)个顶点)二、逆关系，复合关系。

1、关系的逆。

(1)定义：关系的逆关系定义为解：

例5、为上小于等于关系，

为，。，上整除关系，分别求出即上大于等于关系。

为即上的倍数关系。

为2、关系的(复合

。(1)定义，关系R和S的合成关系定义为：

(2)，的关系矩阵与的关系矩阵满足的转置。的关系图只需将改向即得。

的关系图中的有向弧(3)。例6、设

求

，，，，，。解：

逻辑加法：

，，，。(2)满足的关系矩阵

与的关系矩阵。的关系图可将起来求得。

的关系图连接次幂的运算满足：

，(3)合成关系满足结合律：。(4)关系次幂。的定义：设的①

②

次幂规定为：

，上关系，为[解法一]用集合表示。

例7、

求。，[解法二]用关系图表示。

内容：关系的自反性，反自反性，对称性，

反对称性，传递性。

重点：(1)掌握自反性，反自反性，对称性，反对称性，传递性的定义及关系矩阵和关系图的特征，

(2)掌握关系五种性质的判断和验证。

第二节关系的性质和闭包关系的自反，对称，传递闭包（3）掌握关系的自反，对称，传递闭包的概念及求法。

一、关系的五种性质(自反，反自反，对称，反对称，传递)。

1、定义及关系矩阵，关系图特征由下表给出(上关系)为定义

关系矩阵的特点

关系图的特点

自反性

，都有

主对角线元素全为1图中每个顶点都有环反自反性

，都有

主对角线元素全为0图中每个顶点都无环定义

关系矩阵的特点

关系图的特点

对称性

对称矩阵

若两顶点间有

边，必是一对方向相反的边

反对称性

若两顶点间有边，

必是一条有向边

若则

，若则

，且若则

，且定义

关系矩阵的特点

关系图的特点

传递性

若，则且若顶点则有边，到有边，到必有边到(1)(2)解：是对称的，不是传递的。

既不是自反又不是反自反，

解：是反自反的，反对称的，传递的。

例1、如下所示，判断各有哪些性质。上关系，(3)(4)解：既是对称又是反对称的，传递的。

既不是自反又不是反自反的，

解：不是传递的。

是自反的，既不是对称又不是反对称的，

例2、判断下图中的关系分别具有哪些性质。

解：是反自反，反对称，不是传递的。

既是对称又是反对称的，传递的。是空关系，是反自反，既是对称又是反对称的，传递的。

是恒等关系，是自反的，传递的。是全域关系，是自反的，对称的，反对称的，传递的。

既不是自反也不是反自反的，

又不是反对称，不是传递的。

是反自反的，既不是对称则有以下文氏图。

2、若把上所有关系看成一个全集，

二、五种性质的其它判断方法。

设上恒等关系，则

为上关系，是1、，是自反的当且仅当2、，是反自反的当且仅当3、，是对称的当且仅当4、，是反对称的当且仅当5、。是传递的当且仅当例3、设判断是否传递的。

上关系，，解：因是传递的。

，所以因所以，不是传递的。

三、关系在各种运算下保持原有特性问题。

证明：对任意

例如：设证明上的对称关系，

为上的对称关系。

也是所以上是对称的。

在又如：设证明上反对称关系，

为上的反对称关系。

不一定是反例：

都是上的反对称关系，但的反对称关系。上不是四、闭包的定义。

(2)1、定义：设的自反闭包(对称闭包，传递闭包)也是上的关系，

是非空集合上关系，且满足：

(1)是自反的(对称的，传递的)，

(3)对传递关系)的自反关系(对称关系，上的任何包含。，都有2、记号。

3、性质。

——

的自反闭包，

——

的对称闭包，——

的传递闭包。

是自反的，是对称的

，是传递的。五、闭包的求法。

1、利用以下公式。

(1)，(2)，(3)。2、利用关系图。

(1)的关系图：在没有环的结点上加上环，

(2)的关系图：把单向边改为双向边，

(3)以到达的终点添加一条有向边，直到添加完毕。

，分别找出可的关系图：对每个结点没有有向边，则到，若[解法一