离散数学 集合证明

1、2020/7/5,集合论与图论第4讲,1,第4讲 集合恒等式,内容提要 1. 集合恒等式与对偶原理 2. 集合恒等式的证明 3. 集合列的极限 4. 集合论悖论与集合论公理,2020/7/5,集合论与图论第4讲,2,集合恒等式(关于与),等幂律(idempotent laws) aa=a aa=a 交换律(commutative laws) ab=ba ab=ba,2020/7/5,集合论与图论第4讲,3,集合恒等式(关于与、续),结合律(associative laws) (ab)c=a(bc) (ab)c=a(bc) 分配律(distributive laws) a(bc)=(ab)(ac

2、) a(bc)=(ab)(ac),2020/7/5,集合论与图论第4讲,4,集合恒等式(关于与 、续),吸收律(absorption laws) a(ab)=a a(ab)=a,2020/7/5,集合论与图论第4讲,5,集合恒等式(关于),双重否定律(double complement law) a=a 德摩根律(demorgans laws) (ab)=ab (ab)=ab,2020/7/5,集合论与图论第4讲,6,集合恒等式(关于与e),零律(dominance laws) ae=e a= 同一律(identity laws) a=a ae=a,2020/7/5,集合论与图论第4讲,7,集

3、合恒等式(关于,e),排中律(excluded middle) aa = e 矛盾律(contradiction) aa = 全补律 = e e = ,2020/7/5,集合论与图论第4讲,8,集合恒等式(关于-),补交转换律(difference as intersection) a-b=ab,2020/7/5,集合论与图论第4讲,9,集合恒等式(推广到集族),分配律 德摩根律,2020/7/5,集合论与图论第4讲,10,对偶(dual)原理,对偶式(dual): 一个集合关系式, 如果只含有, , e,=, , 那么, 同时把与互换, 把与e互换, 把与互换, 得到的式子称为原式的对偶式.

4、 对偶原理: 对偶式同真假. 或者说, 集合恒等式的对偶式还是恒等式.,2020/7/5,集合论与图论第4讲,11,对偶原理(举例),分配律 a (b c) = (a b ) (a c ) a (b c) = (a b ) (a c ) 排中律 a a=e 矛盾律 a a= ,2020/7/5,集合论与图论第4讲,12,对偶原理(举例、续),零律 a e =e a = 同一律 a =a a e=a,2020/7/5,集合论与图论第4讲,13,对偶原理(举例、续),a b a a b a a e a,2020/7/5,集合论与图论第4讲,14,集合恒等式证明(方法),逻辑演算法: 利用逻辑等值式

5、和推理规则 集合演算法: 利用集合恒等式和已知结论,2020/7/5,集合论与图论第4讲,15,逻辑演算法(格式),题目: a=b. 证明: x, xa (?) xb a=b. #,题目: ab. 证明: x, xa (?) xb ab. #,2020/7/5,集合论与图论第4讲,16,分配律(证明),a(bc)=(ab)(ac) 证明: x, xa(bc) xa x(bc) (定义) xa (xb xc) (定义) (xaxb)(xaxc) (命题逻辑分配律) (xab)(xac) (定义) x(ab)(ac) (定义) a(bc)=(ab)(ac),2020/7/5,集合论与图论第4讲,1

6、7,零律(证明),a = 证明: x, xa xa x (定义) xa 0 (定义) 0 (命题逻辑零律) a = ,2020/7/5,集合论与图论第4讲,18,排中律(证明),aa = e 证明: x, xaa xa xa (定义) xa xa (定义) xa xa (定义) 1 (命题逻辑排中律) aa = e,2020/7/5,集合论与图论第4讲,19,集合演算法(格式),题目: a=b. 证明: a =(?) =b a=b. #,题目: ab. 证明: a (?) b ab. #,2020/7/5,集合论与图论第4讲,20,吸收律(证明),a(ab)=a 证明: a(ab) = (ae

7、)(ab) (同一律) = a(eb) (分配律) = ae (零律) = a (同一律) a(ab)=a,a,b,2020/7/5,集合论与图论第4讲,21,吸收律(证明、续),a(ab) = a 证明: a(ab) = (aa)(ab) (分配律) = a(ab) (等幂律) = a (吸收律第一式) a(ab) = a,a,b,2020/7/5,集合论与图论第4讲,22,集合演算法(格式,续),题目: a=b. 证明: () ab () a b a = b. # 说明: 分=成与,题目: ab. 证明: ab (或ab) =(?) = a (或b) ab. # 说明: 化成= ab=aa

8、b ab=bab,2020/7/5,集合论与图论第4讲,23,集合恒等式证明(举例),基本集合恒等式 对称差()的性质 集族(as)的性质 幂集(p( )的性质,2020/7/5,集合论与图论第4讲,24,补交转换律,a-b = ab 证明: x, xa-b xa xb xa xb x ab a-b = ab. #,2020/7/5,集合论与图论第4讲,25,德摩根律的相对形式,a-(bc)=(a-b)(a-c) a-(bc)=(a-b)(a-c) 证明: a-(bc) = a(bc) (补交转换律) = a(bc) (德摩根律) = (aa)(bc) (等幂律) = (ab)(ac) (交换

9、律,结合律) = (a-b)(b-a) (补交转换律). #,2020/7/5,集合论与图论第4讲,26,对称差的性质,交换律: ab=ba 结合律: a(bc)=(ab)c 分配律: a(bc)=(ab)(ac) a=a, ae=a aa=, aa=e,2020/7/5,集合论与图论第4讲,27,对称差的性质(证明2),结合律: a(bc)=(ab)c 证明思路： 分解成 “基本单位”, 例如: 1. abc 2. a bc 3. a b c 4. abc,a,b,c,abc,1,2,3,4,2020/7/5,集合论与图论第4讲,28,对称差的性质(证明2、续1),结合律: a(bc)=(a

10、b)c 证明: 首先, ab = (a-b)(b-a) (定义) = (ab)(ba) (补交转换律) = (ab)(ab) (交换律) (*),ab,a,b,2020/7/5,集合论与图论第4讲,29,对称差的性质(证明2、续2),其次, a(bc) = (a(bc)(a(bc) (*) = (a(bc)(bc) (a(bc)(bc) (*) = (a(bc)(bc) (a(bc)(bc) (德摩根律),2020/7/5,集合论与图论第4讲,30,对称差的性质(证明2、续3),= (a(bc)(bc) (a(bc)(bc) = (a(bc)(bc) (a(bc)(bc) (德摩根律) = (

11、abc)(abc) (abc)(abc) (分配律),2020/7/5,集合论与图论第4讲,31,对称差的性质(证明2、续4),同理, (ab)c = (ab)c)(ab)c) (*) = (ab)(ab)c) (ab)(ab)c) (*) = (ab)(ab)c) (ab)(ab)c) (德摩根律),2020/7/5,集合论与图论第4讲,32,对称差的性质(证明2、续5),= (ab)(ab)c) (ab)(ab)c) = (ab)(ab)c) (ab)(ab)c) (德摩根律) = (abc)(abc) (abc)(abc) (分配律) a(bc)=(ab)c. #,2020/7/5,集合

12、论与图论第4讲,33,对称差的性质(讨论),有些作者用表示对称差: ab=ab 消去律: ab=ac b=c (习题一,23) a=bc b=ac c=ab 对称差与补: (ab) = ab = ab ab = ab 问题: abc=abc ?,2020/7/5,集合论与图论第4讲,34,对称差的性质(讨论、续),如何把对称差推广到n个集合: a1a2a3an = ? x, xa1a2a3an x恰好属于a1,a2,a3,an中的奇数个 特征函数表达: a1a2an(x) = a1(x)+a2(x)+an(x) (mod 2) = a1(x)a2(x)an(x) (mod 2),都表示模2加法

13、,即相加除以2取余数),2020/7/5,集合论与图论第4讲,35,特征函数与集合运算:,ab(x) = a(x)b(x) a(x) = 1-a(x) a-b(x) = ab(x)=a(x)(1-b(x) ab(x) = (a-b)b(x) = a(x)+b(x)-a(x)b(x) ab(x) = a(x)+b(x) (mod 2) = a(x)b(x),a,b,2020/7/5,集合论与图论第4讲,36,对称差的性质(讨论、续),问题: abc = abc ? 答案: abc = (abc) = (abc) = abc abcd = abcd = abcd = (abcd) = a = (a

14、),2020/7/5,集合论与图论第4讲,37,对称差的性质(证明3),分配律: a(bc)=(ab)(ac) 证明 a(bc) = a(bc)(bc) = (abc) (abc),a,b,c,a(bc),2020/7/5,集合论与图论第4讲,38,对称差分配律(证明3、续),(续) (ab)(ac) = (ab)(ac)(ab)(ac) =(ab)(ac)(ab)(ac) =(abc)(abc) a(bc)=(ab)(ac). #,2020/7/5,集合论与图论第4讲,39,对称差分配律(讨论),a(bc)=(ab)(ac) a(bc)=(ab)(ac) ? a(bc)=(ab)(ac) ?

15、 a(bc)=(ab)(ac) ?,2020/7/5,集合论与图论第4讲,40,集族的性质,设a,b为集族, 则 1. ab a b 2. ab a b 3. a ab b a 4. ab b a 5. a a a,2020/7/5,集合论与图论第4讲,41,集族的性质(证明1),ab a b 证明: x, xa a(aa xa) (a定义) a(ab xa) (ab) xb (b定义) a b. #,2020/7/5,集合论与图论第4讲,42,集族的性质(证明2),ab a b 证明: x, xa ab xa (ab, 合取) a(ab xa) (eg) xb a b. #,2020/7/5

16、,集合论与图论第4讲,43,集族的性质(证明3),a ab b a 说明: 若约定=e, 则a的条件可去掉. 证明: x, xb y( yb xy ) y( ya xy ) (ab) xa b a . #,2020/7/5,集合论与图论第4讲,44,集族的性质(证明4),ab b a 证明: x, xb y( yb xy ) ab x a (ui) xa (ab) b a . #,2020/7/5,集合论与图论第4讲,45,集族的性质(证明5),a a a 说明: a的条件不可去掉! 证明: a y(ya), 设 aa. x, xa y( ya xy ) aa xa xa (aa) aa xa

17、 y( ya xy) x a a a . #,2020/7/5,集合论与图论第4讲,46,幂集的性质,ab p(a)p(b) p(a)p(b) p(ab) p(a)p(b) = p(ab) p(a-b) (p(a)-p(b),2020/7/5,集合论与图论第4讲,47,幂集的性质(证明1),ab p(a)p(b) 证明: () x, xp(a) xa xb (ab) xp(b) p(a)p(b),2020/7/5,集合论与图论第4讲,48,幂集的性质(证明1、续),ab p(a)p(b) 证明(续): () x, xa xp(a) xp(b) (p(a)p(b) xb ab. #,2020/7

18、/5,集合论与图论第4讲,49,幂集的性质(证明2),p(a)p(b) p(ab) 证明: x, xp(a)p(b) xp(a)xp(b) xaxb xab xp(ab) p(a)p(b) p(ab),2020/7/5,集合论与图论第4讲,50,幂集的性质(证明2、续),p(a)p(b) p(ab) 讨论: 给出反例, 说明等号不成立: a=1, b=2, ab=1,2, p(a)=,1, p(b)=,2, p(ab)= ,1,2,1,2 p(a)p(b) ,1,2 此时, p(a)p(b) p(ab). #,2020/7/5,集合论与图论第4讲,51,幂集的性质(证明3),p(a)p(b)

19、= p(ab) 证明: x, xp(a)p(b) xp(a) xp(b) xa xb x ab xp(ab) p(a)p(b) = p(ab). #,2020/7/5,集合论与图论第4讲,52,幂集的性质(证明4),p(a-b) (p(a)-p(b) 证明: x, 分两种情况, (1) x=, 这时 xp(a-b) 并且 x(p(a)-p(b) (2) x, 这时 xp(a-b) x a-b xaxb xp(a)xp(b) xp(a)-p(b) p(a-b) (p(a)-p(b). #,a,b,2020/7/5,集合论与图论第4讲,53,集合运算的优先级,分三级: 第一级最高, 依次降低 第一级: 补, 幂p() 第二级: 广义并, 广义交 第三级: 并, 交, 相对补-, 对称差 同一级: 用括号表示先后顺序,2020/7/5,集合论与图论第4讲,54,集合列的极限,2020/7/5,集合论与图论第4讲,55,集合列的极限,inf