北京大学：《离散数学》系列课程之一《集合论与图论》第5讲 二元关系的基本概念

第5讲二元关系的基本概念 内容提要 1.有序对与卡氏积 2.二元关系 3.二元关系的基本运算 《集合论与图论》第5讲

《集合论与图论》第5讲 1 第5讲 二元关系的基本概念 内容提要 1. 有序对与卡氏积 2. 二元关系 3. 二元关系的基本运算

有序对与卡氏积 有序对(有序二元组) 有序三元组,有序n元组 秦卡氏积 卡氏积性质 《集合论与图论》第5讲

《集合论与图论》第5讲 2 有序对与卡氏积 有序对(有序二元组) 有序三元组, 有序n元组 卡氏积 卡氏积性质

有序对( ordered pair 有序对 a0>={l{ab}} 其中,a是第一元素,b是第二元素. 静也记作(ab) 定理1:=台a=Cb=d 推论:a≠b→≠ 《集合论与图论》第5讲

《集合论与图论》第5讲 3 有序对(ordered pair) 有序对: = { {a}, {a,b} } 其中, a是第一元素, b是第二元素. 也记作(a,b) 定理1: = ⇔ a=c∧b=d 推论: a≠b ⇒ ≠

有序对(引理1) 静引理1:{a}=xb}分→a=b 证明:(<=)显然 (→)分两种情况 (1 X=a. X, ax, b=a, a]a, b I →{a}ab}→a=b 2)X≠a.a∈{Xa}=xb}→a=b.# 《集合论与图论》第5讲

《集合论与图论》第5讲 4 有序对(引理1) 引理1: {x,a}={x,b} ⇔ a=b 证明: (⇐) 显然. (⇒) 分两种情况. (1) x=a. {x,a}={x,b} ⇒ {a,a}={a,b} ⇒ {a}={a,b} ⇒ a=b. (2) x≠a. a∈{x,a}={x,b} ⇒ a=b. #

有序对(引理2) 引理2:若=B≠⑦,则 (1)UA=UB (2)∩∩9 证明:(1)X,X∈U分→]2(∈AX∈2) 日z(z∈B∧X∈2)X∈UB 2)X,X∈n以(Z∈A→X∈Z 台Vz(z∈→X∈z)分X∈∩.# 《集合论与图论》第5讲

《集合论与图论》第5讲 5 有序对(引理2) 引理2: 若A=B ≠∅, 则 (1) ∪A=∪B (2) ∩A=∩B 证明: (1) ∀x, x∈∪A ⇔ ∃z(z∈A ∧ x∈z) ⇔ ∃z(z∈B ∧ x∈z) ⇔ x∈∪B. (2) ∀x, x∈∩A ⇔ ∀z( z∈A → x∈z ) ⇔ ∀z( z∈B → x∈z ) ⇔ x∈∩B. #

有序对(定理1) 秦定理1:=台a=Cb=d 证明:(=eaa,b,c, dyy BUaa, b=Uicc, d)a,b][c, d 又{aab}={cc.d →0{{ab}=∩{c{cQ→{a}={c分a=C. 再由引理1,得b=d.# 《集合论与图论》第5讲

《集合论与图论》第5讲 6 有序对(定理1) 定理1: = ⇔ a=c∧b=d 证明: (⇐) 显然. (⇒) 由引理2, = ⇔ {{a},{a,b}}={{c},{c,d}} ⇒∪{{a},{a,b}}=∪{{c},{c,d}}⇒{a,b}={c,d}. 又 {{a},{a,b}}={{c},{c,d}} ⇒∩{{a},{a,b}}=∩{{c},{c,d}} ⇒ {a}={c} ⇔ a=c. 再由引理1, 得b=d. #

有序对(推论) 推论:a≠b→≠ 证明:(反证)=a=b, 与a≠b矛盾.# 《集合论与图论》第5讲

《集合论与图论》第5讲 7 有序对(推论) 推论: a≠b ⇒ ≠ 证明: (反证) =⇔a=b, 与a≠b矛盾. #

有序三元组( ordered triple 有序三元组 =,C> 有序n(2)元组 =,a 鲁定理2:= a,=b,i=1,2,,n.# 《集合论与图论》第5讲

《集合论与图论》第5讲 8 有序三元组(ordered triple) 有序三元组: =,c> 有序n(≥2)元组: =,an> 定理2: = ⇔ ai = bi, i =1,2,…,n. #

卡氏积( Cartesian product 婚卡氏积 A×B={XEAy∈B} 例:A={a},B={1,2,3 A×B={,,,a,1>,,,,,,, A×A={,,,,,,, ,,}.# 《集合论与图论》第5讲

《集合论与图论》第5讲 9 卡氏积(Cartesian product) 卡氏积: A×B={|x∈A∧y∈B}. 例: A={∅,a}, B={1,2,3}. A×B={,,,,,}. B×A={,,,,,}. A×A={ , , , }. B×B={ ,,,,,, ,, }. #

卡氏积的性质 非交换:AXB≠BxA (除非A=BvA=④B=) 静非结合:(AXB)×C≠Ax(BxC) (除非A=②vB=⑧vC=∞) 分配律:Ax(BC)=(A×B(A×C)等 其他:AXB=⑦分A=VB=等 《集合论与图论》第5讲

《集合论与图论》第5讲 10 卡氏积的性质 非交换: A×B ≠ B×A (除非 A=B ∨ A=∅ ∨ B=∅) 非结合: (A×B)×C ≠ A×(B×C) (除非 A=∅ ∨ B=∅ ∨ C=∅) 分配律: A×(B∪C) = (A×B)∪(A×C)等 其他: A×B=∅ ⇔ A=∅∨B=∅等