第三章 集合與關(guān)系

集合的概念：把具有相同性質(zhì)的不同對(duì)象的全體稱為集合。

• 集合的特性：互異性，無序性
• 集合間的關(guān)系：包含，相等，
• 全集，空集
• 文氏圖
• 冪集：有一個(gè)集合所有子集構(gòu)成的集合

[圖片上傳失敗...(image-8671c9-1604242121168)]

二項(xiàng)式展開證明

• 真子集個(gè)數(shù)為2^n-1個(gè)

在這里插入圖片描述

集合的運(yùn)算

• 交，并，補(bǔ)，對(duì)稱差
  

  [圖片上傳失敗...(image-b4d0d5-1604242121168)]
  在這里插入圖片描述
  
  [圖片上傳失敗...(image-7f7e5a-1604242121168)]
  在這里插入圖片描述
• 補(bǔ)集A-B，就是把A中屬于B的部分挖去。
• 對(duì)稱差，就是把A和B的交集挖去剩下的集合
• 在這里插入圖片描述
• tips
• 在這里插入圖片描述

序偶

• 概念：具有固定次序的客體ab組成的有序序列，
• 次序不同序偶也是不同的
• 笛卡爾積，兩個(gè)集合中的元素分別作為序偶的第一個(gè)元素和第二個(gè)元素A×B不滿足交換律若A中元素個(gè)數(shù)為m，B中元素個(gè)數(shù)為n，則A×B中元素個(gè)數(shù)為mn
  
  在這里插入圖片描述

關(guān)系

• 序偶：表示兩個(gè)客體之間的聯(lián)系
• 關(guān)系：由序偶構(gòu)成的集合

在這里插入圖片描述

• 關(guān)系矩陣和關(guān)系圖

在這里插入圖片描述

• 用有向線段來表示關(guān)系

第三

關(guān)系的性質(zhì)

在這里插入圖片描述

在這里插入圖片描述

復(fù)合關(guān)系和逆運(yùn)算

A）復(fù)合關(guān)系
R 為 X 到 Y 的關(guān)系，S 為 Y 到 Z 的關(guān)系，R S 稱為復(fù)合關(guān)系
∨ 代表邏輯加，0 ∨ 0 = 0，0 ∨ 1 = 1，1 ∨ 0 = 1，1 ∨ 1 = 1
∧ 代表邏輯乘，0 ∧ 0 = 0，0 ∧ 1 = 0，1 ∧ 0 = 0，1 ∧ 1 = 1
B）逆關(guān)系
R 為 X 到 Y 的二元關(guān)系，若將 R 每一序偶的元素順序互換，得到逆關(guān)系 Rc

在這里插入圖片描述

在這里述

關(guān)系的閉包運(yùn)算

• 自反閉包，傳遞閉包，對(duì)稱閉包

例如>=是>的自反閉包

劃分和覆蓋

• 定義：把集合A中的元素分成若干個(gè)叫做分塊的子集，使得A中每個(gè)元素至少屬于一個(gè)分塊，那么這些分塊的全體構(gòu)成的集合叫做A的一個(gè)覆蓋。如果A中的每一個(gè)元素只屬于一個(gè)分塊，那么這些分塊的全體構(gòu)成的集合叫做A的一個(gè)劃分
  例：A = { a, b, c }
  覆蓋：S1 = { {a, b}, {a, c} } 、S2 = { {a}, {a, b}, {b, c} }
  劃分：G = { {a, b}, {c} }
  最小劃分：G1 = { {a, b, c} } ，最大劃分：G2 = { {a}, , {c} }
  判斷依據(jù)：對(duì)于覆蓋而言,一個(gè)元素可以屬于兩個(gè)分塊,而對(duì)于劃分,一個(gè)元素僅屬于且必屬于一個(gè)分塊，劃分一定是覆蓋但覆蓋未必是劃分

等價(jià)類與等價(jià)關(guān)系

• 概念：一個(gè)定義在R上的關(guān)系，如果R是自反，對(duì)稱，傳遞的則R是等價(jià)關(guān)系，
• 等價(jià)類：
• 等價(jià)類的集合稱為商集
• [圖片上傳失敗...(image-88d869-1604242121168)]

序關(guān)系

• 定義：R是A上的關(guān)系滿足自反，反對(duì)稱，
• [圖片上傳失敗...(image-5ed5b3-1604242121168)]
• 蓋住
  [圖片上傳失敗...(image-c31845-1604242121168)]也就是說x與y之間直接有偏序，中間不能再添加其他元素構(gòu)成關(guān)系
• 哈斯圖
• 在這里插入圖片描述

• 鏈：定義：
  在這里插入圖片描述
• 從哈斯圖中容易看出每個(gè)鏈總可以從最高節(jié)點(diǎn)出發(fā)沿著蓋住方向遍歷該鏈中的所有結(jié)點(diǎn)
• 在這里插入圖片描述
• 極大元極小元
• [圖片上傳失敗...(image-c02c91-1604242121168)]
• 最大元最小元
• [圖片上傳失敗...(image-169ede-1604242121168)]
  當(dāng)子集a與b相等時(shí)，B的最大元就是偏序集<A,<>的最大元和最小元
• 在這里插入圖片描述
  在這里插入圖片描述

  [圖片上傳失敗...(image-30f6ea-1604242121168)]