4-4-二元关系与函数-离散数学-教学课件.ppt

《4-4-二元关系与函数-离散数学-教学课件.ppt》由会员分享，可在线阅读，更多相关《4-4-二元关系与函数-离散数学-教学课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、作业讲评2P34.12(1)(p (q r)(p q r)(p (q r)(p q r)(p (q r)(p q r)(p q)(p r)(p q r)m00 x m0 x0 m111m000 m001 m000 m010 m111(0,1,2,7)(对应成对应成真真赋值赋值)(3,4,5,6)(对应成对应成假假赋值赋值)P34.13(1)p(qr)p (q r)m0 xx mx0 x mxx1 m000 m001 m010 m011 m000 m001 m100 m101 m001 m011 m101 m111(0,1,2,3,4,5,7)q(pr)q (p r)mx0 x m0 xx mx

2、x1(0,1,2,3,4,5,7)p(qr)q(pr)P34.13(2)p q(p q)p q m00 (0)p q(p q)p qm0 x mx0m00 m01 m00 m10 (0,1,2)p q(p 1)(q 1)(p (q q)(q (p p)P53.3(个体域为“全总个体域”)n在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的n“有的人很聪明。有的人很聪明。”x(M(x)F(x)n“每个人都有一双手每个人都有一双手”x(M(x)F(x)n“每个大学生不是文科生就是理科生”个体域为个体域为“全总个体域全总个体域”F(x):x是大学生，是大学生，G(x):x是文科生是文科生

3、H(x):x是理科生是理科生 x(F(x)(G(x)H(x)x(F(x)(G(x)H(x)(G(x)H(x)x(F(x)(G(x)H(x)P53.3(个体域为“全总个体域”)n“有些人喜欢所有的花”F(x):x是人，是人，G(y):y是花是花,H(x,y):x喜欢喜欢y x(F(x)y(G(y)H(x,y)n任何金属都可以溶解在某种液体中F(x):x是金属，是金属，G(y):y是液体是液体,H(x,y):x溶解于溶解于y中中 x(F(x)y(G(y)H(x,y)x(M(x)F(x)x(M(x)F(x)这只大红书柜摆满了那些古书。n解法1：设F(x,y):x摆满了y R(x):x是大红书柜 Q(

4、y):y是古书 a:这只 b:那些 F(R(a),Q(b)n解法2：设A(x):x 是书柜 B(x):x是大的 C(x):x是红的 D(y):y是古老的 E(y):y是图书 F(x,y):x摆满了y a:这只 b:那些F(A(a)B(a)C(a),D(b)E(b)有关量词的推理规则n全全 称称 量量 词词 消消 去去 规规 则则（UI规则规则）n存存 在在 量量 词词 消消 去去 规规 则则（EI规则规则）n全全 称称 量量 词词 引引 入入 规规 则则（UG规则规则）n存存 在在 量量 词词 引引 入入 规规 则则（EG规则）规则）构造下述推理证明:前提:(x)(A(x)B(x),(x)B(

5、x)结论:(x)A(x)证：证：(x)(A(x)B(x)前提引入前提引入 A(u)B(u)UI (x)B(x)前提引入前提引入 B(u)UI A(u)拒取式拒取式 xA(x)EG第4章 二元关系与函数4.1 集合的笛卡儿积与二元关系4.2 关系的运算4.3 关系的性质4.4 关系的闭包4.5 等价关系和偏序关系4.6 函数的定义和性质4.7 函数的复合和反函数相关概念nx与与 y 可比可比：n设设R为非空集合为非空集合A上的偏序关系上的偏序关系,x,y A,x与与y可比可比 x y y x.n全序关系全序关系：n R为非空集合为非空集合A上的偏序上的偏序,x,y A,x与与 y 都是可比的，都

6、是可比的，则称则称 R 为为全序全序（或（或 线序线序）n如：数集上的小于或等于关系是全序关系如：数集上的小于或等于关系是全序关系ny 盖住盖住xn设设R为非空集合为非空集合A上的偏序关系上的偏序关系,x,y A,如果如果 x y且且不存在不存在 z A 使得使得 x z y,则称则称 y 盖住盖住x.n如：如：1,2,4,6集合上的整除关系（不是全序关系）集合上的整除关系（不是全序关系）2 盖住盖住 1,4 和和 6 盖住盖住 2.4 不盖住不盖住 1.（因为存在（因为存在2）偏序集与哈斯图n定义定义n集合集合A和和A上的偏序关系上的偏序关系 一起叫做一起叫做偏序集偏序集,记作记作。n实例：

7、实例：n整数集和小于等于关系构成偏序集整数集和小于等于关系构成偏序集，n幂集幂集P(A)和包含关系构成偏序集和包含关系构成偏序集 n哈斯图哈斯图n利用偏序自反、反对称、传递性简化的利用偏序自反、反对称、传递性简化的关系图关系图哈斯图实例R=,IAA=a,b,c,d,e,f,g,h R=,IA 哈斯图实例例：已知偏序集的哈斯图如右图所示,试求出集合A和关系R的表达式.偏序集的特定元素1n定义:设为偏序集,BA,yB.n若若x(x B x y)成立成立,则称则称 y 为为B的的极小元极小元.n若若x(x B y x)成立成立,则称则称 y 为为B的的极大元极大元.n若若 x(x By x)成立成立

8、,则称则称 y 为为 B 的的最小元最小元.n若若 x(x Bx y)成立成立,则称则称 y 为为 B 的的最大元最大元.极小元：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与最大元没有最小元与最大元.已知：已知：A=a,b,c,d,e,f,g,h=B特殊元素的性质1n对有穷集，极小元和极大元必存在，可能存在多个.n最小元和最大元不一定存在，如果存在一定惟一最小元和最大元不一定存在，如果存在一定惟一.n最小元一定是极小元；最大元一定是极大元.n孤立结点既是极小元、也是极大元孤立结点既是极小元、也是极大元.极小元：极小元：a,b,c,g；极大元：极大元：a,f,h；没有最小元与

9、最大元没有最小元与最大元.已知：已知：A=a,b,c,d,e,f,g,h=B偏序集的特定元素2n定义 设为偏序集,BA,yA.n若若 x(x Bx y)成立成立,则称则称 y 为为B的的上界上界.n若若 x(x By x)成立成立,则称则称 y 为为B的的下界下界.n令令Cy|y为为B的上界的上界,则称则称C的最小元为的最小元为B的的最小上最小上界界 或或 上确界上确界.n令令Dy|y为为B的下界的下界,则称则称D的最大元为的最大元为B的的最大下最大下界界 或或 下确界下确界.上界上界:d,f B的下界和最大下界都不存在的下界和最大下界都不存在,最小上界最小上界:d.已知：已知：A=a,b,c,d,e,f,g,h,Bb,c,d例题n 集合1,2,3,4,5,6,7,8,9上整除关系的偏序集n极大元：极大元：5,6,7,8和和9；极小元：；极小元：1。n a,b,c的幂集上的包含关系的偏序集n有唯一极大元有唯一极大元a,b,c和唯一极小元和唯一极小元。作业 12P117：16