《离散数学》课程教学课件（PPT讲稿）6b 集合等式

集合恒等式

析取范式与合取范式 集合恒等式

集合算律集合算律1．只涉及一个运算的算律：交换律、结合律、幂等律④U5交换A④B=BOAAUB=BUAAOB=BOA(AUB)UC结合(ANB)NC=(AB)田C=AU(BUC)AN(BNC)=A④(B④C)AUA=AAA=A幂等1

1 集合算律 集合算律 1．只涉及一个运算的算律： 交换律、结合律、幂等律    交换 AB=BA AB=BA AB=BA 结合 (AB)C =A(BC) (AB)C= A(BC) (AB)C =A(BC) 幂等 AA=A AA=A

集合算律BBY(a) (AOB)田CBB(b）AO（BC)2

2 集合算律

集合算律2.涉及两个不同运算的算律：分配律、吸收律n与④U与nAU(BNC)=AN(BOC)分配(AUB)N(AUC)=(ANB)④(ANC)AN(BUC)=(ANB)U(ANC)吸收AU(ANB)=AAN(AUB)=A3

3 2．涉及两个不同运算的算律： 分配律、吸收律 与 与 分配 A(BC)= (AB)(AC) A(BC)= (AB)(AC) A(BC) =(AB)(AC) 吸收 A(AB)=A A(AB)=A 集合算律

集合算律3。涉及补运算的算律：德摩根律，双重否定律德摩根律A-(BUC)=(A-B)n(A-C)~(BUC)=~BN~C~(BnC)=~BU~CA-(BNC)=(A-B)U(A-C)~~A=A双重否定4

4 3．涉及补运算的算律： 德摩根律，双重否定律 −  德摩根律 A−(BC)=(A−B)(A−C) A−(BC)=(A−B)(A−C) (BC)=BC (BC)=BC 双重否定 A=A 集合算律

集合算律4．涉及全集和空集的算律：补元律、零律、同一律、否定律0EAn~A=OAU~A=E补元律、排中律AQ=0零律AUE=E同一律AUO=AANE=A~Q=E~E=Q否定律5

5 4．涉及全集和空集的算律： 补元律、零律、同一律、否定律  E 补元律、排中律 AA= AA=E 零律 A= AE=E 同一律 A=A AE=A 否定律 =E E= 集合算律

集合算律求集合运算的结果1. 00(0)=02. (0]n(0] =[0]3.[0, (0))-0= (0, (0)4.{0, (0]-[0}=((0}]5. [0, (0]-{{0]]=[0]6

1. 2. 3. 4. 5. 求集合运算的结果 集合算律 6

集合证明题证明方法：命题演算法、等式置换法命题演算证明法的书写规范（以下的X和Y代表集合公式）(1) 证XCY任取x,XEX=... =>XEY(2) 证X=Y方法一分别证明XCY和YCX方法二任取X,XEX←...XEY注意在使用方法二的格式时。必须保证每步推理都是充分必要的7

7 集合证明题 证明方法：命题演算法、等式置换法 命题演算证明法的书写规范 (以下的X和Y代表集合公式) (1) 证XY 任取x， xX  .  xY (2) 证X=Y 方法一 分别证明 XY 和 YX 方法二 任取x，xX  .  xY 注意：在使用方法二的格式时，必须保证每步推理都是充 分必要的

集合等式的证明方法一：命题演算法例5 证明AU(AB)=A(吸收律）证任取X，XEAU(ANB) XEAVXEANBXEAV(XEAXEB)XEA因此得 AU(ANB) = A.例6 证明A-B=A~B证任取X,XE A-BXEAAXEBXEAΛXE~BXEAO~B因此得A-B=A~B8

8 集合等式的证明 方法一：命题演算法 例5 证明A(AB) = A （吸收律） 证 任取x, xA(AB)  xAxAB  xA(xAxB)  xA 因此得 A(AB) = A. 例6 证明 A−B = AB 证 任取x, x A−B  xAxB  xAxB  xAB 因此得 A−B = AB

等式代入法方法二：等式置换法例7假设交换律、分配律、同一律、零律已经成立，证明吸收律.证AU(ANB)(同一律）= (AnE)U(AnB)(分配律)= An(EUB)(交换律)= AN(BUE)(零律)= ANE= A(同一律)9

9 等式代入法 方法二：等式置换法 例7 假设交换律、分配律、同一律、零律已经成立，证明吸 收律. 证 A(AB) = (AE)(AB) （同一律） = A(EB) （分配律） = A(BE) （交换律） = AE （零律） = A （同一律）