離散數(shù)學(賈振華主編) 第四章 關(guān)系

《離散數(shù)學(賈振華主編) 第四章 關(guān)系》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第四章關(guān)系本章學習目標：在上一章討論了集合及集合的運算，在這一章中我們將要研究集合內(nèi)元素間的關(guān)系，這就是“關(guān)系”。關(guān)系是一個很重要的數(shù)學基本概念，它在計算機科學中的許多方面如數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫、情報檢索、算法分析等都有很多應(yīng)用。本章主要討論二元關(guān)系理論。通過本章學習，讀者應(yīng)該掌握以下內(nèi)容：（1）關(guān)系的表示（2）關(guān)系的性質(zhì)和運算（3）等價關(guān)系和集合的劃分（4）偏序關(guān)系第四章關(guān)系4.1序偶與笛卡兒積4.2二元關(guān)系及其表示4.3關(guān)系的運算4.4關(guān)系的性質(zhì)4.5關(guān)系的閉包4.6等價關(guān)系與集合的劃分4.7相容關(guān)系4.8偏序關(guān)系第四章關(guān)系4.1序偶與

2、笛卡兒積4.1.1有序n元組定義4.1由兩個固定次序的個體x，y組成的序列稱為序偶，記為，其中x，y分別稱為序偶的第一、二分量（或稱第一、二元素）。定義4.2兩序偶，是相等的，當且僅當a=c，b=d；記作=。第四章關(guān)系4.1序偶與笛卡兒積4.1.2笛卡兒積的概念定義4.3給定兩個集合A和B，如果序偶的第一個分量是A中的一個元素，第二個分量是B中的一個元素，則所有這種序偶的集合稱為集合A和B的笛卡兒積，簡稱為卡氏積，記為A×B，即A×B={?x∈A∧y∈B}。第四章關(guān)系4.1序偶

3、與笛卡兒積4.1.2笛卡兒積的概念例4.1（1）A={a，b}，B={c，d}，求A×B。（2）A={a，b}，B={c，d}，求B×A。（3）A={a，b}，B={1，2}，C={c}，求（A×B）×C和A×（B×C）。第四章關(guān)系4.1序偶與笛卡兒積4.1.2笛卡兒積的概念解（1）A×B={a，b}×{c，d}={，，，}。（2）B×A={c，d}×{a，b}={，，，}。（3）（A×B）={a，b}×{1，2}={，，，

4、，2>}。第四章關(guān)系4.1序偶與笛卡兒積4.1.2笛卡兒積的概念（A×B）×C={<，c>，<，c>，<，c>，<，c>}={，，，}。B×C={1，2}×{c}={<1，c>，<2，c>}。A×（B×C）={>，>，>，>}。第四章關(guān)系4.1序偶與笛卡兒積4.1.3笛卡兒積的性質(zhì)定理4.1設(shè)A，B，C為任意3個集合，則有（1）A×（B∪C）=（A×B）∪（A×C）（2）A×（B

5、∩C）=（A×B）∩（A×C）（3）（A∪B）×C=（A×C）∪（B×C）（4）（A∩B）×C=（A×C）∩（B×C）第四章關(guān)系4.1序偶與笛卡兒積4.1.3笛卡兒積的性質(zhì)定理4.3設(shè)A，B，C，D為四個非空集合，則A×B?C×D的充分必要條件是：A?C且B?D。定理4.2設(shè)A，B，C為任意3個集合，且C??，則有A?B?（A×C?B×C）?（C×A?C×B）第四章關(guān)系4.1序偶與笛卡兒積4.1.3笛卡兒積的性質(zhì)反之，如果A?C且B?D，設(shè)任意x∈C和y∈B，有∈A×B?x∈A∧y∈B?x∈C∧y∈D?x∈C∧y∈D?

6、>∈C×D所以，A×B?C×D。第四章關(guān)系4.2二元關(guān)系及其表示4.2.1二元關(guān)系的概念定義4.5設(shè)R是二元關(guān)系，由?R的所有x組成的集合稱為R的定義域，記作D（R），即D（R）={x??y（y?B∧?R）}。由?R的所有y組成的集合稱為R的值域，記作R（R），即R（R）={y??x（x∈A∧∈R）}。定義4.4設(shè)A，B是兩個集合，R是笛卡兒積A×B的任一子集，則稱R為從A到B的一個二元關(guān)系，簡稱關(guān)系。特別當A=B時，則稱R為A上的二元關(guān)系（或A上的關(guān)系）。第四章關(guān)系4.2二元關(guān)系及其表示4.2.

7、1二元關(guān)系的概念例4.3設(shè)A={1，3，5，7}，R是A上的二元關(guān)系，當a，b?A且a?R，求R和它的定義域和值域。解R={<1，3>，<1，5>，<1，7>，<3，5>，<3，7>，<5，7>}D（R）={1，3，5}，R（R）={3，5，7}。例4.2設(shè)A={a，b，c，d，e}，B={1，2，3}，R={，，}，求R的定義域和值域。解D（R）={a，b，c}，R（R）={2，3}。第四章關(guān)系4.2二元關(guān)系及其表示4.2.1二元關(guān)系的概念定義4.6設(shè)IA為集合A上的二元關(guān)系，且滿足IA

8、={?x?A}，則稱IA為集合A上的恒等關(guān)系。第四章關(guān)系4.2二元關(guān)系及其表示4.2.2二元關(guān)系的表示1．關(guān)系矩陣表示法設(shè)給定集合A={a1，a2，…，an}，集合B={b1，b2，…，bm}，R