离散数学总结 1

1、解：,由真值表,主合取范式：,( PQ R) ( PQR) (P QR) (PQR),=M101 M100 M010 M000,主析取范式与主合取范式的简记式中的下标是 “互补”的.,Why?,例1.5.8 利用真值表求(P Q) ( P R)的主析取范式与主合取范式.,五、对 偶 与 范 式,解：,由真值表,主合取范式：,( PQ R) ( PQR) (P QR) (PQR),=M101 M100 M010 M000,主析取范式与主合取范式的简记式中的下标是 “互补”的.,Why?,例1.5.8 利用真值表求(P Q) ( P R)的主析取范式与主合取范式.,五、对 偶 与 范 式,解：,由

2、真值表,主合取范式：,( PQ R) ( PQR) (P QR) (PQR),=M101 M100 M010 M000,主析取范式与主合取范式的简记式中的下标是 “互补”的.,Why?,例1.5.8 利用真值表求(P Q) ( P R)的主析取范式与主合取范式.,五、对 偶 与 范 式,(7) 一切人都不一样高.,(x)(y)(F(x) F(y) H(x, y) L(x, y),解：,引入特性谓词 F(x) ： x是人.并设 L(x, y) ： x与y一样高. H(x, y)：x与y不是同一个人. 则命题符号化为：,(8) 每个自然数都有后继数.,解：,引入特性谓词 F(x) ： x是自然数.

3、并设 H(x, y)：y是x的后继数. 则命题符号化为：,(x)(F(x) (y) (F(y) H(x, y),一、谓词逻辑命题符号化的有关概念与方法,(9) 有的自然数无先驱数.,解：,引入特性谓词 F(x) ： x是自然数.并设 H(x, y)：y是x的先驱数.则命题符号化为：,(x)(F(x) (y)(F(y) H(x,y),(10) 有的有理数是整数. (个体域为实数集),解：,引入特性谓词 F(x) ： x是有理数.并设 G(x)：x是整数.则命题符号化为：,(x)(F(x) G(x),HW: 2-1, 2-2习题 (1)a,c,e,f,h (2)a,b,c,d,f,一、谓词逻辑命题

4、符号化的有关概念与方法,(7) 一切人都不一样高.,(x)(y)(F(x) F(y) H(x, y) L(x, y),解：,引入特性谓词 F(x) ： x是人.并设 L(x, y) ： x与y一样高. H(x, y)：x与y不是同一个人. 则命题符号化为：,(8) 每个自然数都有后继数.,解：,引入特性谓词 F(x) ： x是自然数.并设 H(x, y)：y是x的后继数. 则命题符号化为：,(x)(F(x) (y) (F(y) H(x, y),一、谓词逻辑命题符号化的有关概念与方法,(9) 有的自然数无先驱数.,解：,引入特性谓词 F(x) ： x是自然数.并设 H(x, y)：y是x的先驱数

5、.则命题符号化为：,(x)(F(x) (y)(F(y) H(x,y),(10) 有的有理数是整数. (个体域为实数集),解：,引入特性谓词 F(x) ： x是有理数.并设 G(x)：x是整数.则命题符号化为：,(x)(F(x) G(x),HW: 2-1, 2-2习题 (1)a,c,e,f,h (2)a,b,c,d,f,一、谓词逻辑命题符号化的有关概念与方法,解：,(2) (x)(P Q(x),又R(a)为F，所以, F,(2) (x)(P Q(x)R(a)，其中P:21. Q(x): x 3; R(x): x 5; a: 5;论域 -2,3, 6., (P Q(-2) (P Q(3) (P Q

6、(6), (T T) (T T) (T F), T T F,F F,(x)(P Q(x) R(a),F.,二、谓词公式,HW:2-3习题 (5);(7) 2-4习题 (2)c,d;(4) 2-5习题 (2) a,d,() 量词作用域的扩张与收缩等价式,(x)(A(x)B),(x)(BA(x), (x)A(x)B,B(x)A(x),(7),(8),由上述几个式子，可推得下列等价式也成立：,(x)(BA(x),(x)(A(x)B), (x)A(x)B, B(x) A(x),(5),(6),三、谓词演算的等价式与蕴含式,例2.3.3证明:(x)(A(x) B(x),(x)(A(x) B(x),(x)

7、( A(x)B(x),解：, (x)( A(x)(x)B(x), (x)A(x) (x)B(x),E20,量词的分配,E20,(x)A(x)( x)B(x).,(x)A(x) (x)B(x),量词转化律,三、谓词演算的等价式与蕴含式,公式,(三) 谓词演算中常见的蕴含式：,(2)(x)(A(x)B(x),(1)(x)A(x)(x)B(x),反例 设个体域为自然数集合， A(x): x为奇数. B(x): x为偶数.则,(2)(x)A(x)为真，,(x)B(x)为真，,故(x)A(x)(x)B(x)为真,但(x)(A(x)B(x)为假，,所以(2)式反过来也不成立.,而(x)A(x)为假，,(x

8、)B(x)为假，,(1)(x)(A(x)B(x)为真，,所以(1)式反过来不成立；,故(x)A(x)(x)B(x)为假，,(1), (2)两式反过来均不成立.,三、谓词演算的等价式与蕴含式,(x)(A(x)B(x),(x)A(x)(x)B(x),谓词演算中常见的蕴含式,(5)(x)(y)A(x,y),(y)(x)A(x,y),(6)(y)(x)A(x,y),(x)(y)A(x,y),(7)(x)(y)A(x,y),(y)(x)A(x,y),反例 设个体域为实数集合，A(x, y): x-y=1. 则,(x)(y)A(x, y)为真，,而(y)(x)A(x, y)为假，,所以(6)式反过来不成立

9、.,(5)(6)(7)三式反过来均不成立.下面以(6)式为例说明：,三、谓词演算的等价式与蕴含式,总结下就是任意可以改成存在，存在不能变成任意所以先做存在。 任意（推出）则先用德摩根律把推出给换了，在把量词放进去！ 有限集合中元素的个数称为集合的基数(cardinality). 集合A的基数表示为|A|(或card(A)=n). card(P(A)=2n)幂集 设A, B为两个集合，A=B当且仅当AB且B A. 即A=B(AB) (B A),例2.4.4 将谓词公式(x)P(x)(y)R(y)(x)F(x)化为前束范式.,解：,(x)P(x)(y)R(y)(x)F(x), (x)P(x)(y)

10、R(y)(x)F(x), (x)P(x)(y)R(y)(x)F(x), (x)P(x)(y)R(y)(z)F(z), (x)(y)(z)(P(x)R(y)F(z),消去多余联结词,否定符紧贴,更名,扩域,四、前束范式,例2.5.7 (2-7习题的(2)b) 证明：,证法一：,(x)(P(x)Q(x) (x)P(x)(x)Q(x).,(1) (x)P(x),P(附加前提),(2) ( x) P(x),(3) P(c),T(1), E,ES(2),(4) (x)(P(x)Q(x),P,(8) (x)P(x) (x)Q(x),CP 先ES后US,(6) Q(c),US(4),(7) (x)Q(x),

11、T(3)(5), I,注意到(x)P(x)(x)Q(x) (x)P(x) (x)Q(x) ，下面使用CP规则来证明.,(5) P(c)Q(c),EG(6),五、谓词演算的推理理论,解：,例3.1.4 设S=a1, a2, , a8，Bi是S的子集，由B17和B31所表达的子集是什么？应如何规定子集=a2, a6, a7和a1, a8.,(1)B17=,B00010001,= a4, a8;,B31=,B00011111,= a4, a5, a6, a7, a8.,= B70;,B01000110,(2)a2, a6,a7=,= B129.,B10000001,a1, a8=,一、集合的基本概念

12、,例：设A=1, 2, 3，B=1, 3, 5，则A B =,2, 5.,几种常见的运算,对称差(symmetric difference)(或称环和)： AB = (A B)(B A) = x | xA xB,二、集合的运算,A (BC) =,A (BC) =,(A B)(A C),(A B)(A C),(5) A B =AB,(9) A B = (AB)(B A),(15) AB = AC ,B = C (消去律),例3.2.1 证明A (BC) = (AB)(AC),证：,任取x，则,xA (BC), xA xBC, xA (xB x C), (xA xB) (xA xC), x AB

13、x AC, x (AB)(AC),二、集合的运算,|ABC |,|A|B|C|,三、集合中元素的计数,|AB |AC|BC|,|ABC |,(二)实例,例3.3.1 一个班里有50个学生，在第一次考试中有26人得5分，在第二次考试中有21人得5分。如果两次考试中都没得5分的有17人，那么在两次考试都得5分的有多少人？,解：,又因为 |AB| = |A| + |B| |AB|,所以 |AB| =,= 26 + 21 33,=33,设A、B分别表示第一和第二次考试中得5分学生的集合，则有,|E| =50,|A| =26,|B| =21,|AB| =17.,| AB| = |E-(AB)|,首先由A

14、B = (AB)知,= |E-AB|,= |E|-|AB|,|A| + |B| |AB|,= 14,三、集合中元素的计数,例3.3.2 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球，而6个会打网球的人都会打另外一种球(指篮球和排球)，求不会打这三种球的人数？,解：,|A|=12，,|AC |=6，,|B|=6，,|E|=25,|C|=14，,|BC |=5，,|ABC |=2.,用A、B、C分别表示会打排球、网球、篮球的学生集合，则有 ：,由于AB C = (AB C),先求,= |A|+|B|+|C| |AB| |AC |

15、 |BC | + |ABC |,|ABC |,=12+6+146 5+2|AB|,= |A|+|B|+|C| |AB| |AC | |BC | + |ABC |,|ABC |,又因为6个会打网球的人都会打另外一种球，即,B AC ，,所以，B=,B(AC),= B(A(CA),=(AB) (B C A),从而， |AB|=,= 6 ( 5 2 ),|B|- |BCA|,=|B|- (|BC |- |ABC |),这样|AB C|=,25-|AB C|,=25-(23-3),=5,=23|AB|,= 3,HW: 3-3习题 (2),证：, (A C)-(BC), A C BC, (xAyC) (

16、xByC), (xAyC) (x ByC), (xAyC x B)(xAyC yC),所以， (A-B)C= (A C)-(BC).,例3.4.2 (3-4习题的(3) d) 证明(A-B)C= (A C)-(BC).,任取，则, (xAyC) (xB yC), (xAyC x B)F, xA x B yC, xA-B yC, (A-B)C,四、二元关系的基本概念,解：,例3.4.3 (3-4习题的(1) ) 设A=0, 1，B=1, 2，确定下面的集合. (1) A1B; (2) A2B.,(1)A1B=, , , .,(2) A2B =,AAB,=, , , , , , , .,一般地：如

17、果|A|=m，|B|=n，则|BA|=,|AB|= m n.,四、二元关系的基本概念,例3.4.6 设A=1, 2, 3, 4，求A上的“小于等于”关系LA.,解：,LA =,|xA yAxy ,=, , , , , , , , , .,例3.4.7(3-5习题的(2) 在一个有n个元素的集合A上，可以有多少种不同的二元关系？,解：,集合A上的二元关系的个数与AA的子集个数相同.,现card(A)=n，则,card(AA)=,n2,所以，AA的子集个数就有 个.,即A上不同的二元关系有 个.,若card(A)=m, card(B)=n, 问A到B可以有多少种不同的二元关系？,答案：2mn个.,

18、四、二元关系的基本概念,用关系矩阵表达关系运算后的新关系 设MR=aik, MS=bkj，新关系的(i, j)元为cij ,则 MRS=MR MS, 其中cij=aij bij. MRS=MR MS, 其中cij=aij bij. MR =cij, 其中cij= aij. MR-S=MR MS , 其中cij=aij (bij).,若例3.4.10中关系R改为R=| xy x是质数呢？,例3.4.10(3-5习题的(6) 对P=0, 1, 2, 3, 4, 5, 6上的二元关系 R=| xy x是质数 ，写出关系矩阵.,HW: 3-4习题 (1)c;(3)e;(4);(5) 3-5习题 (4)

19、;(5)c,d;(7),代表逻辑乘，满足00=0, 01=0, 10=0, 11=1.,反对称(antisymmetric)性,设集合A=R|R为对称的关系， B=R|R为反对称的关系，则A和B的关系如右图所示：,存在某种关系，既是对称的，又是反对称的吗？,存在.,例如，,五、二元关系的性质,例3.6.2设A=1, 2, 3, 4, B=2, 3, 4, C=1, 2, 3，R1是从A到B的二元关系， R2是从B到C的二元关系：,R1=|x+y=6,分别用列举法、图示法、关系矩阵法表示关系的合成R1 R2 .,=, , ,R2=|y-z=1,=, , ,(3)关系矩阵法,解：,六、复合关系和逆

20、关系,前行乘后列，第i行第j列=前面第i行*第j列加起来,关系的幂,设R是集合A上的二元关系，nN为任一自然数，则R的n次幂记为Rn，定义为： (1)R0为A上的恒等关系， R0=|xA. (2)Rn+1= Rn R.,从a到b有一条长度为2的路径.,在R2的图形上，有一条a到b的弧，则在R的图形上,从a到b有一条长度为n的路径.,在Rn的图形上，有一条a到b的弧，则在R的图形上,六、复合关系和逆关系,(1) R在A上自反，当且仅当,例3.6.5 设R为A上的二元关系，证明：,(2) R在A上反自反，当且仅当,(3) R在A上传递，当且仅当,证明：,IA R.,RIA = .,R R R.,(

21、1)必要性：,任取 IA ,如果R在A上自反，必有, IA, x A, R ,从而IA R.,充分性：,当IA R时，,xA, IA, R ,因此R在A上是自反的.,从关系矩阵角度看，,R是自反的，则MR的主对角元全为1. 所以IA R .,任取xA , 有,六、复合关系和逆关系,结论可直接用,构造闭包的方法,利用关系矩阵求闭包：(设R是有限集X上的二元关系，card(X)=n，MR为R的关系矩阵),(1) Mr(R) =,(2) Ms(R) =,(3) Mt(R)=,其中“+” 均表示“逻辑加 ”,MR + I,MR + MRT (MRT是MR的转置),单位矩阵,MR+ MR2+ +MRn,

22、七、二元关系的闭包运算,例3.7.1 设A=a,b,c， R 是A上的二元关系，R=, , ，求 r (R)，s (R) 和 t (R),解一：,=, , , , ,= R,r(R) =,RIA,s(R) =,=, ,= R,RRc,t(R) =,RR2R3,七、二元关系的闭包运算,而R2 = R R,R3 =,R4 = R3 R,=, , ,= ,= , ,故 t(R) =,=, , , , , , ,例3.7.1设A=a,b,c， R 是A上的二元关系，R=, , ，求 r (R)，s (R) 和 t (R),R2 R,= R,由R= R4可得：,R=R4=R3n+1,R2=R5=R3n+

23、2,R3 =R6=R3n+3(n为正整数),RR2R3,七、二元关系的闭包运算,性质二：设R1是从X到Y的二元关系， R2是从Y到Z的二元关系， 则,(R1 R2)c=,R2c R1c.,Warshall 提出了求有限集上关系R的传递闭包t(R)=R+的一个有效算法：,对第i列中出现1的各行，分别被+上第i行,性质一：设R是集合X上的二元关系，则,(2)证：,（必要性）,设R是对称的，,则R满足对称闭包的定义：,(1)R是对称的；,(2)R R；,(3)对任何对称的二元关系R，若R R,若s(R) =R，,（充分性）,由对称闭包定义知R是对称的.,(1) R是自反的，当且仅当,r(R) =R.

24、,(2) R是对称的，当且仅当,s(R) =R.,(3) R是传递的，当且仅当,t(R) =R.,七、二元关系的闭包运算,则R R .,性质二：设R是集合X上的二元关系，则,(1) 若R是自反的，则s(R)和t(R),(2) 若R是对称的，则r(R)和t(R),(3) 若R是传递的，,也是自反的.,也是对称的.,则r(R)是传递的，s(R)不一定是传递的.,七、二元关系的闭包运算,闭包运算的性质,性质三：设R1, R2是集合X上的二元关系， 且R1R2，则,(1) r(R1)r(R2);,(2) s(R1)s(R2);,(3) t(R1)t(R2).,证：,(3)由t(R1)R1，,又R1R2

25、，,所以t(R1)R2.,又t(R1)是传递的，,而t(R2)是包含R2的最小传递关系，,所以t(R1)t(R2).,七、二元关系的闭包运算,闭包运算的性质,性质四：设R是集合X上的二元关系，则,(1) rs(R)=sr(R);,(2) rt(R)=tr(R);,(3) ts(R) st(R).,ts(R) st(R).,反例：,R=整数集Z上的“”关系., s(R)=,“ ”关系，,t(R)=,“ ”关系，, st(R)=,“ ”关系，,ts(R)=,ZZ上的全域关系.,HW: 3-8习题 (1);(4);(7);(8),七、二元关系的闭包运算,例3.8.2 给定一个玩具积木的集合,按颜色得划分：,按形状得划分：,同时考虑颜色和形状，得交叉划分：,划分的加细,从这个例子可以看到： 交叉划分也是原集合的一种划分； 交叉划分是原来各划分的加细.,HW: 3-9习题 (1);(