离散数学复习

1、1,第二章 谓词逻辑,2.1谓词演算的基本概念 2.2谓词演算的关系式 2.3前束范式 2.4谓词演算的推理,2,2.1.1 谓词与个体,考察以下2个原子命题： （1）李华是工程师。 （2）何威是工程师。 若对这两个原子命题进行内部结构分析，就 会发现它们之间既有相异之处又有相同之处。 相异之处：主语不同 相同之处：谓语共享,将相同部分从这类命题中分离（抽象）出来进行研究并符号化。,引入一个符号表示“x是工程师”。,(x) 或 ( ),3,2.1.1 谓词与个体,像() 这样抽象形式，实际上就是上述几个语句中描述主语性质的谓语结构的抽象形式或描述主语所涉及对象之间的关系的抽象形式。 上述中的抽

2、象形式就是谓词。语句中的主语或对象称为个体。 个体是指可以独立存在的。谓词是用来刻划个体的性质或关系的。通常用大写字母F,G,H等表示谓词，用小写字母a,b,c等表示个体。 在原子命题中引进谓词和个体的概念，这种以命题中的谓词为基础的分析研究，称为谓词逻辑(或称谓词演算)。,4,2.1.1 谓词与个体,个体的变化范围，称为个体域。 将宇宙间一切事物（所有个体）所组成的个体域称为全总个体域。 以某一个个体域为变域的变元，称为个体变元。习惯用小写的x,y,z等表示。 与个体变元相对的是个体常元，它指某个确定的个体，习惯用小写的a,b,c等表示。,5,2.1.1 谓词与个体,仅含一个个体变元的谓词，

3、称为一元谓词。 含有n个个体变元的谓词，称为n元谓词。 含有0个个体变元的谓词（但可能包含多个个体常元），称为0元谓词。 一般地，一元谓词刻画了个体的性质，多元谓词刻画了个体之间的关系。 注意：谓词不是命题，只有当确定的个体“填入”后，才成为命题。,(x),(x，y),(a,b,c),“张华是大学生”可表示为F(a),6,2.1.2 量词,全称量词记作 “ x ”，其含意是：“所有的x ”、“每一个x ”、“凡是x ”、“任意的x ”等等。,表示对个体域中的所有个体其,谓词F(x)均为真。,7,2.1.2 量词,存在量词记作 “ ”，其含意是：“存在着x ”、“有些x ” 等等。,表示个体域中

4、存在某些个体其,谓词F(x)均为真。,8,函数,在谓词逻辑中，个体与个体间有一定的关系，这种关系称为函数。,一元函数,二元函数,多元函数,例：李平的妈妈是医生。 D(x)：x是医生；a：李平；f(a)：李平的妈妈； 句子符号化为：D(f(a),9,用谓词和量词表示句子的步骤：,参考题目给出的个体域，如果没有指明，假设为全总个体域； 确定句子中的谓词和个体变元；在全总个体域下，句子中的名词（人、数、动物等）都需要使用特性谓词表示；多元谓词使用多个不同的个体变元。 根据句子中特性谓词前的修饰词选择量词； ：“所有的”、“凡是”、“一切”、“任意”、“每一个”等词，或省略的情况 ：“存在”、“有些”

5、、“某些”、“几个”等词 根据量词确定谓词之间的关系； 所限定的个体变元所在的特性谓词和其他谓词之间使用条件连接词。 所限定的个体变元所在的特性谓词和其他谓词之间使用合取连接词。,10,例1.没有不犯错的人,M(x)：x是人 W(x)：x犯错,11,例2.对于所有的正实数x,y，都有x+yx。,S(x)：x是正实数 P(x，y)：x+yx,12,练习,课后题1.29（8）（9）（10）,13,2.1.3 谓词逻辑公式（公式 ）,谓词逻辑公式中所使用的符号有以下七种:,(1)个体常量符:,(2)个体变量符:,(3)函数符:,(4)谓词符:,(5)联结词符:,(7)括号(,),(6)量词符:,一个

6、谓词逻辑公式中是由上述符号按一定规则所组成的符号串。,a,b,c, ,x,y,z ,f,g,h ,F,G,H,14,2.1.3 谓词公式（续）,例如，下列各式 是谓词公式。但下列各式 不是谓词公式。,15,练习：,下列哪些是谓词公式：,16,2.1.4 自由变元和约束变元,由于全称量词的作用，使得命题函数中的x不再起变元 的作用，或者说，量词约束了x的变元作用，在这种情况 下，称变量x为“约束出现”，并称x为约束变元。 又如 在这个谓词公式中，易见，x是约束元，但y不是约束元， 称y是“自由出现”，并称y为自由变元。量词 后括号 中的内容 称为量词 的作用域或辖域。,17,换名规则,在对约束元

7、换名时，应遵循以下两种规则（约束元换名规则）： （1）对约束元（如x）换名时，更改的名称范围是 或 中的x以及量词作用域中所出现的所有x，在量词作用域外的部分不换名。 （2）换名时一定要更改为作用域中没有出现的变量名称,18,例1,解：在这个谓词公式中，x既是约束元又是自由 元，y也是约束元又是自由元。若把约束元x换名 为u，约束元y换名为v，经换名后，谓词公式可 写成为 于是可知，u，v是约束元，x，y是自由元。,19,代入规则,对于谓词公式中的自由变元，也可以更改，这种更改称为代入，代入时应对谓词公式中出现该自由变元的每一处都进行。这称为自由元代入规则 例如， 可更改为,20,例1（续）,

8、对下列谓词公式中自由元进行代入，使得一个变量在谓词公式中只呈一种形式（约束元或自由元）出现。,21,谓词关系式,将命题公式的等价关系可以推广为谓词公式的等价关系：,例如：命题公式,将P和Q分别替换为：,公式就可变为：,22,谓词公式（等价或蕴含）关系式,由于量词的引入，谓词公式多了如下公式：,存在服从对的分配律全称服从对的分配律,全称量词变为存在量词 存在量词变为全称量词,否定 深入,5、6、7、8其中的A是没有出现约束变元x的谓词公式。,量词作用域的扩张和收缩,23,关系式,全称对不服从分配律 存在对不服从分配律,24,对偶,定义 设A是命题公式，且A中仅有联结词 ， ，量词 ， 。在A中把

9、，F，T， ， ，分别换成，T，F， ， 后所得的命题公式称为A的对偶公式。,25,对偶,例： 的对偶式：,26,练习：写出对偶式,27,2.3 前束范式,定义:一个公式，如果量词均非否定地在全式的开头，且公式除量词外，最多只含，则称此公式叫前束范式。 例： xyz( Q(x,y) R(z) (前束范式),(x) P(x)(y)Q(y), (x)(P(x)(y)Q(x,y),X,X,X,X,28,前束范式,求解的一般步骤（不唯一）： 1.运用基本等价公式，把各种联结词转换成基本联结词： 、和 2.运用E1、E8、E9、E24、E25、E26等将公式中的深入到各谓词变元的前面。 3.利用换名、代

10、入规则，使所有的约束变元均不同名，且自由变元与约束变元也不同名。 4.利用E27、E28 、E29 、E30 、E31 、E32扩大量词的作用域至整个公式。,29,前束范式,例：把xP(x) R(x)变成前束范式 xP(x) R(x) yP(y) R(x) y(P(y) R(x) 例：把xP(x) xQ(x) 变成前束范式。 xP(x) xQ(x) xP(x)xQ(x) xP(x) xQ(x) x(P(x) Q(x),30,前束范式,例. 将公式(x)P(x)(y)Q(y)(x)R(x)化归为前束范式 原式 (x)P(x)(y)Q(y)(x)R(x) (x)P(x)(y)Q(y)(x)R(x)

11、 (x)P(x)(y)Q(y)(z)R(z) (x)(y)(z)(P(x)Q(y)R(z) 量词前移,31,练习,课后题 1.32（2）,32,第三章 集合,3.1集合的基本概念 3.2集合的运算及基本公式 3.3幂集 3.4包含排斥原理 3.5集合的直积,33,3.1.1 集合的表示,一般用大写的英文字母A, B, C, 来代表集合，|A|表示集合中元素的个数； 用小写的英文字母a , b , c, 来代表集合中的元素。 一些特殊集合的表示： 代表自然数集合， 代表整数集合， 代表有理数集合， 代表实数集合， 代表复数集合,34,3.1.1 元素与集合的关系,如果b是集合A中的元素，称b属于

12、A，并记作 如果b不是集合A中的元素，称b不属于A，并记作,例如：,35,练习：列出下列集合的元素,(1) x,|xN t (t2,3 x=2t) (2) x,|xN ts (t0,1 s 3,4 txs) (3) x,|xN t (t整除2 xt),4,6,1,2,3,N-1,2,36,空集和全集,不含有任何元素的集合称为空集，记作 研究对象的全体称为全集，记作E。 E=x|P(x) P(x) 注意：全集是个相对性的概念，由于研究的问题不同，所取的全集也不同，即使是同一个问题也可以有不同的全集,37,【例】确定下列命题是否正确？,(1) (2) (3) (4) (5) (6) (7) (8)

13、,X,X,38,3.2 集合的运算及其基本公式,1.并运算 2.交运算 3.差集 4.补集 5.布尔和,39,3.2 集合的运算及其基本公式,3.差集： 设A，B是集合，由所有属于A但不属于B的元素构成的集合称为A对B的差集，记作：A-B,例如: A = 1，2，3，4，B = 3，4，5,差集 A B = 1 , 2 , B A,=5,40,3.2 集合的运算及其基本公式,4.补集 集合A的补集 A可定义为 A=E A =x| (xA),41,3.2 集合的运算及其基本公式,5.布尔和（对称差） 集合A,B的布尔和（对称差）A+B 定义为：,A+B=(A - B) (B - A),A+B=(

14、A B) -(A B),42,练习：,3.E=0,1,2,3,4,5,6,7,8,9,A=2,4,5,6,8, B=1,4,5,9,C=x|xZ+,2x5 求：AB,C-B,(CB)A,0,1,2,3,6,7,8,9,2,3,0,1,3,4,5,7,9,43,3.3 幂集,定义：设A是集合，由A的所有子集作为元素构成的集合称为A的幂集，记作,幂集的符号化表示 = x| ,例：设集合 A = 1, 2，则其幂集,例：设集合 A = a，b，c ，则其幂集,44,练习:,分别求下列集合的幂集,解：它们的幂集分别为,45,幂集,定理： 设集合A是由n个元素所组成的有限集，则A的幂集是有限集，且由,个

15、元素组成。也即|(A)|=,将集合中元素的个数称为基数。,46,3.5 笛卡尔乘积,1.有序对(有序偶)和有序n元组,定义：由两个客体a和b(允许a=b）按一定的顺序排列成的二元组称为一个有序对，记作（a , b）,其中a称为有序对的第一客体，b称为有序对的第二客体,如：平面直角坐标系中点的坐标(x,y)就是有序对,定义：有序偶(a，b)与(c，d) ，如果有a = c，b = d，则称(a，b)与(c，d)是相等的。,47,笛卡儿乘积,定义：设A, B 是集合，由所有以A中元素为第一客体，B中元素为第二客体的有序对构成的集合称为A到B的笛卡儿乘积(直积)，记作AB，即,48,笛卡儿乘积,例如

16、:设A = a, b , B = x, y,z,则 A到B的笛卡儿乘积 AB =(a, x),(a,y),(a, z),(b, x),(b, y), (b, z),B到A的笛卡儿乘积 BA=(x, a),(y, a),(z, a),(x, b),(y, b), (z, b),49,第四章 关系,4.1关系及其运算、关系的表示方式 4.2关系的有关性质 4.3关系的闭包运算 4.4等价关系和相容关系 4.5偏序关系,50,关系的实质,由于二元关系就是符合某种特定要求的有序对的集合. A上的二元关系应是A上的笛卡儿乘积A A的子集。 此A到B的二元关系应是笛卡儿乘积A B的子集,51,n元关系的定

17、义,定义 对于二元关系R,如果 (a, b) R，也可记作aRb，并称a 与b 有关系R。如果(a, b) R，也可记作a R b，并称a与b没有关系R。,52,二元关系的定义域和值域,定义 设S是A到B的二元关系，使(x, y) S的所有x组成的集合称为S的定义域，记作D(S)； 使(x, y) S的所有y组成的集合称为S的值域，记作C(S)或R(S)。 易知:D(S)就是S的所有有序偶的第一个元素构成的集合, C(S)就是S的所有有序偶的第二个元素构成的集合.,53,求关系的定义域和值域,例如:设 则R的定义域D(R) ， 值域C(R),54,三种特殊的关系,对于任意集合，空集和集合本身都

18、是它的子集，常称这两种子集为平凡子集。 定义 笛卡儿乘积A B的两个平凡子集，空集 和A B本身称为集合A到B的空关系和全域关系。 定义 设R是A上的二元关系且满足 则称R为A上的恒等关系，并记作 。,55,2 关系的表示方法,1.关系矩阵 设集合 ，R是A到B的二元关系，令 则 称为R的关系矩阵.,56,关系的表示方法,例1:设 R是A到B的二元关系，且 则R的关系矩阵为,A是行，B是列,57,复合关系,1. 复合关系的定义 定义 R是A到B的二元关系，S是B到C的二元关系，R和S的复合记作RS，它是A到C的二元关系，仅当 (a, b)R，且(b , c)S时，(a, c)RS。 例:设 ，

19、R是A到B的二元关系，S是B到C的二元关系，且 则R和S的复合,58,复合关系的矩阵表示,定理 R是A到B的二元关系，其关系矩阵为 ，S是B到C的二元关系，其关系矩阵为 ，复合关系RS是A到C的二元关系，其关系矩阵为 ，则 注意:按普通矩阵乘法求 ,只不过是将乘法改为布尔乘,加法改为布尔加.,运算法则与合取连接词一致,运算法则与析取连接词一致,59,例1,设A = 1，2，3，B = a, b, c, d, C = x, y, z，R是A到B的二元关系，R = (1, a), (1, b), (2, b), (3, c)，S是B到C的二元关系，S = (a, x), (b, x), (b, y

20、), (b, z)。求复合关系RS的关系矩阵. 解:因为 所以,60,4-2 关系的重要性质,关系的基本类型： 自反的二元关系 反自反的二元关系 对称的二元关系 反对称的二元关系 可传递的二元关系 或称为关系的性质： 自反性、反自反性、对称性、反对称性、可传递性,61,1. 自反的二元关系,定义 设R是A上的二元关系，如果对于A中每一个元素x ，都有(x, x )R，则称R是自反的，也称R具有自反性。 例1: A = a, b, c, A上的二元关系 R = (a, a), (b, b), (c, c), (a, c), (c, b) ，则R是自反的二元关系。 例2:设A=1,2,3,4, R

21、=(1,1),(2,2),(3,4),(4,2), 因为3A,但(3,3) , 所以R不是A上的自反关系.,62,2. 反自反的二元关系,定义 R是A上的二元关系，如果对于A中每一个元素x,都有(x, x ) ,则称R是反自反的，也称R具有反自反性。 例1:设A = a, b, c, R = (a, c), (b, a), (b, c), (b, b) 因为(b,b)R, 则R不是A上的反自反关系。 例2:设A = 1，2，3，R是A上的小于关系，即(1,2),(1,3),(2,3) 由于(1, 1), (2, 2), (3, 3)都不属于R，所以R是A上的反自反关系。,63,2. 反自反的二

22、元关系,例3:设A=1,2,3,R=(1,2),(2,3),(3,2),(3,3), S=(1,1),(2,2),(2,3),(3,3),则 R既不是A上的反自反关系(因(3,3)R), 也不是A上的自反关系(因(1,1) ) S是A上的自反关系,但不是反自反关系. 注意:一个关系R如果不是自反关系，不一定是反自反关系.,64,3. 对称的二元关系,定义 R是A上的二元关系，每当(x, y) R时，就一定有(y, x) R，则称R是对称的，也称R具有对称性。 例1:设A = a, b, c, R = (a, b), (b, a), (a, c), (c, a) ，所以R是对称的。 例2:设A=

23、1,2,3,4上的二元关系 R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4), 因为(4,3)R但(3,4) 。所以R不是对称的。,65,4. 反对称的二元关系,定义 R是A上的二元关系，当x y时，如果 (x, y) R，则必有(y, x) ，称R是反对称的，也称R具有反对称性。 例1: A=1,2,3,上的关系R=(1,2),(2,2),(3,1),则R是反对称的.但S=(1,2),(1,3),(2,2),(3,1)不是反对称的.因为13但(1,3)S,且(3,1)S,66,4. 反对称的二元关系,例2: 设A = 2，3，4，6，R是A上的整除关系(即当a, b

24、A且a能整除b时，（a, b）R)，问R是否是A上的反对称关系? 解:因为R = （2，2）,（2，4）,（2，6）,（3，3）,（3，6）,（4，4）,（6，6） 由定义知：R是反对称的. 例3: 实数集合上的小于关系和小于等于关系都是反对称的.,67,4. 反对称的二元关系,例4:设A=a, b, c, d上的关系 R=(a ,a) ,(b ,c) ,(c ,d) ,(d ,c) , S=(a ,a) ,(b ,b) ,(d ,d),则 R既不是对称的(因为(b ,c)R但(c ,b) ),也不是反对称的 (因为(c ,d)R且(d ,c)R) 而S既是对称的,也是反对称的.,68,4.

25、反对称的二元关系 小结,注意:对称关系和反对称关系不是两个相互否定的概念. 存在既是对称的也是反对称的二元关系, 也存在既不是对称的也不是反对称的二元关系.,69,5. 可传递的二元关系,定义 设R是A上的二元关系， 每当(x, y) R且(y, z) R时，必有 (x, z) R，则称R是可传递的，也称R具有可传递性。 例1:实数集上的小于关系和小于等于关系都是可传递关系.如：ab,bc 则ac,70,5. 可传递的二元关系,例2:设A=a ,b ,c上的关系R=(a ,a) ,(a ,b) ,(b ,c) ,(a ,c), S=(a ,b) ,(c ,b) , T=(a,b) ,(b ,b

26、) ,(b ,c),则 R,S,T是否可传递？ R,S是可传递的,T不是可传递的 因为T中有(a ,b)T ,(b ,c) T但(a ,c) ,所以T不是可传递关系,71,关系性质总结1,集合A上的自反关系中必包含A中由每个元素自身所组成的有序对。对应关系矩阵主对角线上所有元素都为1； 恒等关系是自反关系，但自反关系不一定是恒等关系。 集合A上的反自反关系中必不包含A中任意一个元素自身所组成的有序对。对应关系矩阵主对角线上所有元素都为0. 对应关系矩阵主对角线上元素有1，但不全为1的关系，既不是自反关系，也不是反自反关系。,72,关系性质总结2,集合A上的对称关系要求其中每个有序对两个客体前后

27、位置交换后的有序对仍在此关系中。对应关系矩阵一定是对称矩阵。 集合A上的反对称关系要求其中每个有序对两个客体前后位置交换后的有序对一定不在此关系中。对应关系矩阵一定不是对称矩阵，但是不对称的矩阵不一定就对应于反对称关系。 恒等关系即为对称关系，又为反对称关系。 关系中存在两个仅客体顺序不同的有序对，但又不全是的关系，既不是对称关系，又不是反对称关系。,73,等价关系的定义与实例,定义 设 R 为非空集合上的关系. 如果 R 是自反的、对称的和传递的, 则称 R 为 A 上的等价关系. 设 R 是一个等价关系, 若(x,y)R, 称 x 等价于y, 记做 xy. 实例 设 A=1,2,8, 如下

28、定义A上的关系 R： R = (x,y) | x,yAxy(mod 3) 其中 xy(mod 3) 叫做 x 与 y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等.,74,偏序关系,定义 非空集合A上的自反、反对称和传递的关系，称为A上的偏序关系. 实例 集合A上的恒等关系 IA 是A上的偏序关系. 小于等于关系, 整除关系和包含关系也是相应集合上的偏序关系.,75,偏序关系的定义,常常把集合A以及A上的偏序关系R合在一起统称为偏序集，记作（A，R）。 由于偏序关系是自反的、反对称的、传递的二元关系，所以一般用符号“”表示偏序。当(a, b)R，时，常记作ab，偏序集也常记作（A，

29、）。,76,例：,集合A=2，3，4，6，8 关系R=(x,y)|xA, yA, x整除y 即：R=(2,2),(3,3),(4,4),(6,6),(8,8),(2,4),(2,6),(2,8),(3,6),(4,8) R为偏序关系； (A,R)为偏序集。,77,线性次序,定义 设R是集合A上的偏序，如果对每个x,yA，必有xy或y x ，则称R是线性次序的(全序的)，或称R是集合A上的线性次序关系。 易知：在线性次序关系中，任意两个元素都是有关系的。,78,线性次序,例在整数集合中，大于等于关系是线性序关系。 例设1,3,6,12,24, 是整除关系 ,则是线性次序的,并且对A中元素有 1

30、3 6 12 24,79,偏序关系的哈斯图表示,定义 设R是集合A上的偏序关系，a和b是A中的元素，如果(a, b) R，且在A中没有其他元素c，使得 (a, c) R，(c, b) R，则称元素b盖住a。 例1:A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除关系，由“盖住”的定义可知，元素4盖住2；但元素8并不盖住2，因为有元素4，使得(2, 4)R和(4, 8)R，所以8不盖住2。 利用元素间的盖住关系，能较方便地画出偏序关系的哈斯图(即关系图的简化),80,画哈斯图的方法,用平面上的点代表集合中的元素，当b盖住a时，代表b的点应画在代表a的点的上方，并用直线段

31、连接否则不画线 上面例1:A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除关系，的哈斯图如下： 24 16 12 8 6 4 10 3 2 5 1,81,偏序集中的特殊元素,定义 设(A，)是偏序集，如果A中存在元素a，使得A中没有其他元素x，满足xa，则称a为A中的极小元。 定义 设(A，)是偏序集，如果A中存在元素a，使得A中没有其他元素x，满足ax，则称a为A中的极大元。,82,偏序集中的特殊元素,定义 设(A，)是偏序集，如果A中存在元素a，使得对于A中任何元素x，都有ax，则称a为A中的最小元。 定义 设(A，)是偏序集，如果A中存在元素a，使得对于A中任何

32、元素x，都有xa，则称a为A中的最大元。 注意:最大(小)元与极大(小)元的区别,83,偏序集中的特殊元素,例1:A = 2，3，4，6，8，12，16,24，是A上的整除关系。其哈斯图见图1。 由定义可知，(A，)的极小元为2和3，极大元为16和24。 24 16 12 8 6 4 3 2 图 1,最大元和最小元是？,84,偏序集中的特殊元素,例2:A = 1，2，3，4，6，12，是整除关系，其哈斯图见下图2。 12 4 6 2 3 1 图 2 由上图可知，1是最小元，12是最大元。,85,“极元”与“最元”的区别,只要偏序集中没有元素比a的“小”或“大”，a就是极小元或极大元。 如果a是偏序集中的最小元，则要求a“小于”偏序集中其他所有元素（暗含a与其他所有元素都有关系）。最大元的情况正好相反。,86,映射定义,一个映射函数f:X