《《离散数学总复习》ppt课件》由会员分享，可在线阅读，更多相关《《离散数学总复习》ppt课件（29页珍藏版）》请在金锄头文库上搜索。
1、,本节小结,要熟练掌握这五个联结词在自然语言中所表示的含义以及它们的真值表的定义。,2. 定义：A、B是含有命题变元P1,P2, Pn的命题公式，如不论对P1, P2 , , Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB。 显然 PQPQQP 3. 重要的等价公式 对合律 PP 幂等律 PPP PPP 结合律 P(QR)(PQ)R P(QR)(PQ)R 交换律 PQQP PQQP,分配律 P(QR)(PQ)(PR) P(QR)(PQ)(PR) 吸收律 P(PQ)P P(PQ)P 底-摩根定律 (PQ)PQ (PQ)PQ 同一律 PFP PTP 零律 PTT PFF 互补
2、律 PPT PPF PQPQ PQQP PQ (PQ)(QP) PQ (PQ)(PQ) PQ (PQ)(PQ ),2.主析取范式定义 析取范式 A1A2.An, , 其中每个Ai (i=1,2n)都是小项，称之为主析取范式。 3.主析取范式的写法 方法：列真值表 列出给定公式的真值表。 找出真值表中每个“T”对应的小项。 (如何根据一组指派写对应的为“T”的项：如果变元P被指派为T，P在小项中以P形式出现；如变元P被指派为F,P在小项中以P形式出现(因要保证该小项为T)。 用“”联结上述小项，即可。,2.主合取范式定义 合取范式 A1A2. An, , 其中每个Ai (i=1,2n)都是大项，
3、称之为主合取范式。 3.主合取范式的写法 方法：列真值表 列出给定公式的真值表。 找出真值表中每个“F”对应的大项。 如何根据一组指派写对应的为“F”的大项： 如果变元P被指派为F，P在大项中以P形式出现； 如变元P被指派为T，P在大项中以P形式出现 (确保该大项为F)。 用“”联结上述大项，即可。,在一个谓词公式中，如果某个客体变元既以约束变元形式出现，又以自由变元形式出现，就容易产生混淆。为了避免此现象发生，可以对客体变元更改名称。 如 x(F(x,y)yP(y)Q(z) 约束变元的改名规则： (1).对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此客体变元出现的
4、各处同时换名。 (2).改名后用的客体变元名称，不能与该量词的辖域内的其它变元名称相同。,例如x(P(x)Q(x,y)(R(x)A(x) 此式中的x 就是以两种形式出现。可以对x改名成 z(P(z)Q(z,y)(R(x)A(x) 对自由变元也可以换名字，此换名叫代入。 对自由变元的代入规则： (1).对谓词公式中的自由变元可以作代入。代入时需要对公式中出现该变元的每一处，同时作代入。 (2).代入后的变元名称要与公式中的其它变元名称不同 上例也可以对自由变元x作代入，改成 x(P(x)Q(x,y)(R(z)A(z),2.前束范式的写法 给定一个带有量词的谓词公式， 1)消去公式中的联接词和(为
5、了便于量词辖域的扩充)； 2)如果量词前有“”，则用量词否定公式将“”后移。再用摩根定律或求公式的否定公式，将“”后移到原子谓词公式之前。 3)用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备) 4)用量词辖域扩充公式提取量词，使之成为前束范式形式。,本节要求： 1.准确掌握这五个性质的定义。 2.熟练掌握五个性质的判断和证明。 R是A中自反的x(xAxRx) R是A中反自反的x(xAR) R是A上对称的xy(xAyAxRy) yRx) R是A上反对称的 xy(xAyAxRyyRx) x=y) xy(xAyAxyxRy)y x) R在A上传递 xyz(xAyAzAxRy
6、yRz)xRz) 上述定义表达式都是蕴涵式,所以判断关系R性质时要特 别注意使得性质定义表达式的前件为F的时候此表达式 为T，即R是满足此性质的。 (自反和反自反性除外),从关系的矩阵,从关系的有向图,性质判定:,下面归纳这八个关系的性质：Y-有 N-无,实际上r(R)、(s(R) 、t(R) 就是包含R的“最小” 的自反(对称、传递)关系。 三.计算方法 定理1.给定 A中关系R,则 r(R)=RIA。 证明：令R=RIA,显然R是自反的和RR，下 面证明R是“最小的”：如果有A上自反关系 R”且RR”,又IAR”,所以 RIAR”,即RR”。 所以R就是R的自反闭包。即r(R)=RIA 。
7、 定理2.给定 A中关系R,则 s(R)=RRC 。 证明方法与1.类似。 定理3.给定 A中关系R,则 t(R)=RR2R3. 。 证明：令R= RR2R3., 显然有 RR ；,定理4.给定 A中关系R,如果A是有限集合，|A|=n 则 t(R)=RR2.Rn 。 证明：令R=RR2R3., R”=RR2.Rn 下面证明R=R” ， 显然有R”R。下面证明RR”： 任取R,由R定义得必存在最小的正整数i 使 得Ri , (下面证明in)如果in, 根据关系的复合得A中必存在i-1个元素e1, e2,.,ei-1， 使得 RR.R。 上述元素序列: x=e0, e1, e2,.,ei-1,y
8、=ei中共有i+1个元 素，i+1n , 而A 中只有n个元素，所以上述元素中 至少有两个相同，设ej=ek (jk)，于是R的关系图中 会有下面这些边：,四.性质 定理5. R是A上关系，则 R是自反的，当且仅当 r(R)=R. R是对称的，当且仅当 s(R)=R. R是传递的，当且仅当 t(R)=R. 证明略，因为由闭包定义即可得。 定理6. R是A上关系，则 R是自反的，则s(R)和t(R)也自反。 R是对称的，则r(R)和t(R)也对称。 R是传递的，则r(R)也传递。 证明: 因为R自反,由定理5得r(R)=R,即 RIA=R, r(s(R)=s(R)IA=(RRC)IA =(RIA
9、)RC=r(R)RC=RRC =s(R)s(R)自反,定理7：设R1、R2是A上关系，如果R1R2 ，则 r(R1) r(R2) s(R1) s(R2) t(R1)t(R2) 证明 r(R1)=IAR1IAR2= r(R2) ，类似可证。 定理8：设R是A上关系，则 sr(R)=rs(R) tr(R)=rt(R) st(R)ts(R) 证明： sr(R)=r(R)(r(R)c=(RIA)(RIA)c = (RIA)(RcIAc) =RIARcIA = (RRc) IA= s(R)IA=rs(R) 的证明用前边证明的结论： (RIA)k= IARR2.Rk 很容易证明，这里从略。,4-7 集合的
10、划分与覆盖,图书馆的图书，要分成许多类存放，学校的学生 要按照专业分成许多班，即对集合的元素划分 一.定义 设X是一个非空集合,A=A1, A2,. ,An, Ai AiX (i=1,2,.,n),如果满足 A1A2.An =X (i=1,2,., n) 则称A为集合X的覆盖。 设A=A1, A2,. ,An是X一个覆盖, 且AiAj= (ij,1i,jn)则称A是X的划分。每个Ai均称为 这个划分的一个划分块(类)。,二. 等价类,我们经常用等价关系对集合进行划分，得到的划 分块称之为等价类。 1.定义：R是A上的等价关系，aA,由a确定的集合aR: aR=x|xAR 称集合aR为由a形成的
11、R等价类。简称a等价类。 可见 xaR R 上例，A=1,2,3,4,5,6,7, R是A上的模3同余关系， 1R=1,4,7= 4R = 7R -余数为1的等价类 2R=2,5= 5R -余数为2的等价类 3R=3,6= 6R -余数为0的等价类 思考题：此例为什么只有三个等价类？,从上述模3同余关系例子中，可以归纳出等价类的性质：任 何两个等价类要么相等，要么不相交；那么在什么情况下 相等？那么在什么情况下不相交？ 3.等价类性质 R是A上等价关系，任意a,b,cA 同一个等价类中的元素，彼此有等价关系R。 即任意x,yaR，必有R 证明：任取x,yaR，由等价类定义得，R, R ,由R对
12、称得，R，又由R传递得R。 aRbR=， 当且仅当 R。 证明:设R，假设aRbR,则存在xaRbR， xaRxbR,R ,R,由R对称得 R又由R传递得R,产生矛盾。 若aRbR=,而R,由等价类定义得baR, 又因为bRb,所以bbR，所以baRbR，产生矛盾。, aR=bR 当且仅当 R。 证明：若R，则任何xaR，有R，由对 称性得R，再由传递性得R,xbR， 所以aRbR。 类似可证bRaR。 aR=bR。 如果aR=bR，由于有aRa,所以aaR ， abR ， 所以有R，由对称性得R. .A中任何元素a,a必属于且仅属于一个等价类。 证明：A中任何元素a,由于有aRa,所以aaR
13、 ，如果 abR ，所以有R.由性质得aR=bR 。 .任意两个等价类 aR、bR， 要么aR=bR ，要么aRbR= 。 (因为要么R，要么R。) R的所有等价类构成的集合是A的一个划分。 (由性质即得。) (这个划分称之为商集),三. 商集,“商”和除法有关，比如把一块蛋糕平均分成四份，从 两种不同的角度看这件事： 从算术角度看：1用4除,每份1/4,这就是“商”,于是: 1=1/4+1/4+1/4+1/4 从集合角度看： 集合A用模3同余关系R划分，得到三个等价类，所以 A 1,4,7,2,5,3,6=1R,2R,3R-商集 定义：R是A上等价关系，由R的所有等价类构成的集合 称之为A关
14、于R的商集。记作A/R。即 A/R=aR |aA,四.偏序集中的重要元素,在格和布尔代数中，要用到下面一些术语。 设是偏序集，B是A的非空子集。 一.极小元与极大元 y是B的极小元y(yBx(xBxyxy) (在B中没有比y更小的元素了，y就是极小元) 举例，给定的Hasse图如图所示： 从Hasse图找 极小(大)元：,2, 3,2, 3,1,2, 3,6,24,1,24,36,y是B的极大元y(yBx(xBxyyx) (在B中没有比y更大的元素了，y就是极大元),子集中处在最下 (上)层的元素是 极小(大)元。,二.最小元与最大元 y是B的最小元y(yBx(xB yx) (最小元y是B中元素，该元素比B中所有元素都小) 举例，给定的Hasse图如图所示： 从Hasse图找最小(大)元：,无,无,1,无,6,24,1,无,y是B的最大元y(yBx(xB xy) (最大元y是B中
