關(guān)系的性質(zhì)-離散數(shù)學(xué)教學(xué)課件

離散敖學(xué)DiscreteMathematics2/25/2019DiscreteMathhuangliujia關(guān)系的性質(zhì)-離散數(shù)學(xué)離散敖學(xué)DiscreteMathematics2/25/2019DiscreteMathhuangliujia第七章元關(guān)系71有序?qū)εc笛卡兒積72二元關(guān)系73關(guān)系的運算74關(guān)系的性質(zhì)75關(guān)系的閉包76等價關(guān)系與劃分77偏序關(guān)系2/25/2019DiscreteMathhuangliujia§71有序?qū)εc笛卡爾積定義71由兩個元素x和y(允許x=y)按一定順序排列成的二元組叫做一個有序?qū)?記為<x,y>。注:有序?qū)Φ男再|(zhì)1.當x≠y時,<x,y>≠y,x>2.<x,y>=<u,v>的充分必要條件是x=u且y=v。定義7.2設(shè)A,B是集合。由A中元作為第一元素,B中元作為第二元素組成的所有有序?qū)Φ募?稱為集合A與B的笛卡爾積,記為AXB。即A×B={<x,y>x∈A∧y∈B}e2/25/2019DiscreteMathhuangliujia第七章元關(guān)系71有序?qū)εc笛卡兒積72二元關(guān)系73關(guān)系的運算74關(guān)系的性質(zhì)75關(guān)系的閉包76等價關(guān)系與劃分77偏序關(guān)系2/25/2019DiscreteMathhuangliujia§71有序?qū)εc笛卡爾積定義71由兩個元素x和y(允許x=y)按一定順序排列成的二元組叫做一個有序?qū)?記為<x,y>。注:有序?qū)Φ男再|(zhì)1.當x≠y時,<x,y>≠y,x>2.<x,y>=<u,v>的充分必要條件是x=u且y=v。定義7.2設(shè)A,B是集合。由A中元作為第一元素,B中元作為第二元素組成的所有有序?qū)Φ募?稱為集合A與B的笛卡爾積,記為AXB。即A×B={<x,y>x∈A∧y∈B}e2/25/2019DiscreteMathhuangliujia§71有序?qū)εc笛卡爾積注:笛卡爾積的性質(zhì)1.A×Φ=①,d×A=①;2.A×B≠B×A,除非A=或B=西或A=B3.(A×B)×C≠A×(B×C),除非A=西或B=①或C=①4.A×(B∪C)=(A×B)∪(A×C);(B∪C)xA=(B×A)∪(C×A);A×(BC(A×B)∩(4XC);(BC×A=(B×An(CXA);5.(ACCA(BCD)=(A)C(CXD).2/25/2019DiscreteMathhuangliujia§71有序?qū)εc笛卡爾積例證明A×(BUC)=(A×B)∪(A×C)證:任取<xy>:X,y>∈A×(BUC)分x∈A∧ye∈(BUC)∈A∧(y∈B∨y∈C臺(X∈A∧yeB)V(x∈A∧y∈C)∈AXB)V(<x,y<X,y>∈(A×B)U(A×C)A×(BUC)=(A×B)∪(AxC)例72設(shè)A={1,2},求P(A)×A。解:P(A)×AO,(1},{2},{1,2}}×{1,2}={<0,1>,<0,2>,<{1},1>,<{1},2>,<{2},1>,<{2},2>,<{1,2},1>,<{1,2,2>25/2019DiscreteMathhuangliujia5§71有序?qū)εc笛卡爾積例7.3設(shè)A,B,C,D為任意集合,判斷下列命題是否為真。(1)A×B=AXC→B=C(2)A-(BXC)=(A-B)X(A-C)(3)(A=B)∧C=D)→AXC=BXD(4)存在集合A,使AcA×A解:(1)不一定為真,當A=①,B={1},C={2,3}時,便不真。(2)不一定為真,當A=B=(1},C=(2時,A(B×C={1}{<1,2>}={1},而(A-B)X(AC=Φ×{1}=Φ(3)為真。等量代入。(4)為真。當A=①時,使AcA×A2/25/2019DiscreteMathhuangliujia§72二元關(guān)系基本概念定義7.3如果一個非空集合的元素都是有序?qū)?則稱該集合為一個二元關(guān)系。特別地,空集也是一個二元關(guān)系。注:對一個二元關(guān)系R,如果<x,y>∈R,則記為xRy;如果<xy>gR,則記為xRy定義7.4設(shè)A,B為集合,AXB的任何子集所定義的二元關(guān)系稱為從A到B的二元關(guān)系。特別地,當A=B時,稱為A上的二元關(guān)系。定義7.5對任何集合A(1)稱空集Φ為A上的空關(guān)系。(2)A上的全域關(guān)系EA={<X,y>|x∈A∧y∈A}=A×A(3)A上的恒等關(guān)系I={<Xx>x∈A}2/25/2019DiscreteMathhuangliujia§72二元關(guān)系關(guān)系的表達方式1.集合表達式:列出關(guān)系中的所有有序?qū)?。?4設(shè)A={1,2,3,4},試列出下列關(guān)系R的元素。(1)R={<Xy>x是y的倍數(shù)}2)R={<x,y>(x-y)2∈A}3)R={<X,y>xy是素數(shù)}(4)R={<x2y>A(5)R={<xy>(xy∈A)∧(x<y)}解:(1)R={<4,4>,<4,2>,<4,1>,<3,3>,<3,1>,<2,2>,<2,1>,<1,1>}(2)R={<2,1>3,2>,<4,3>,3,1>,<4,2><2,4,<1,3>,<3,4>,<2,3><1,2>}3)R={<2,1>,3,1>,4,2>}(4)R=EA1={<1,2><1,3,<1,4,<2,1>,2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<42>,<4,3>}(5)R={<1,2>,1,3>,1,4>,<2,3>,2,4>,3,4>}2/25/2019DiscreteMathhuangliujia§72二元關(guān)系2.關(guān)系矩陣法:設(shè)A={x1x2…xn},R是A上的關(guān)系。令《;1則矩陣17稱為R的關(guān)系矩陣。2/25/2019Discrete