離散數學蓋住集怎麼求

1. 離散數學這個蓋住covA到底怎麼看的

去掉所有的<x,x>，再破壞掉傳遞性：若<x,y>，<y,z>，<x,z>都在，則去掉<x,z>。剩下的就是covA。

用R表示關系。

若aRb，且不存在c，使得aRc且cRb，則稱b蓋住a。

對於本題來說就是，1整除4，2整除4，但是1整除2，所以4不能蓋住1

求覆蓋，也即找哈斯圖中的兩個相鄰點之間的線段（中間不經過第三點）

即有：<1,2>,<1,3>,...,<6,12>

(1)離散數學蓋住集怎麼求擴展閱讀：

①若b|a，c|a，且b和c互質，則bc|a。

②對任意非零整數a，±a|a=±1。

③若a|b，b|a，則|a|=|b|。

④如果a能被b整除，c是任意整數，那麼積ac也能被b整除。

⑤對任意整數a，b>0，存在唯一的數對q，r，使a=bq+r，其中0≤r<b，這個事實稱為帶余除法定理，是整除理論的基礎。

2. 離散數學 給定集合S={A1,A2……,An}的覆蓋，如何才能確定此覆蓋的相容關系

相容關系是具有自反對稱性的關系，集合S的任何一個覆蓋X均能確定一個相容關系，反之也然。
X={S1,S2……,Sk}是集合S={A1,A2……,An}上的覆蓋，則由此覆蓋確定的S上的相容關系是
（S1*S1）U（S2*S2）U…U（Sk*Sk）
其中Sk*Sk是S的子集Sk的笛卡爾積。
如X={{1,2},{2,3}}是S={1,2,3}的覆蓋，則此覆蓋確定的S上相容關系是
{1,2}*{1,2}U{2,3}*{2,3}={<1,1>,<1,2>,<2,1>,<2,2>,<2,3>,<3,2>,<3,3>}

3. 離散數學中給定集合，給定相容關系且知道簡化矩陣，如何求此集合的覆蓋

集合上的相容關系是指具有自反和對稱的關系，由於它具有自反性，故它的關系矩陣的對角線上的元素均為1，由於它具有對稱性，故它的關系矩陣一定是對稱矩陣，集合X有6個元素，它的關系矩陣是6階矩陣，考慮到該矩陣是對稱矩陣且對角線上的元素均為1，故只要寫出對角線以下的元素即可，如果補上對角線上的1即是下面的簡化形式：
x1
1
x2
1
1
x3
1
1
1
x4
0
0
1
1
x5
0
1
1
1
1
x6
1
0
1
0
1
1
x1
x2
x3
x4
x5
x6
集合上的一個覆蓋是由集合的子集做為元素構成的集合，這些子集也稱為塊，集合的元素至少在一個塊（子集）中，同塊的元素必具有關系R，給定關系矩陣如何求覆蓋？下面給一種方法，
首先考慮元素x1所在的塊，從關系矩陣中看出x1與x2，x6有關系R，故{x1，x2，x6}是一個塊，該塊中沒有出現x3，x4，x5，接下來再考慮元素x3所在的塊，從關系矩陣中看出x3與x4，x5，x6有關系R，故{x3，x4，x5，x6}是一個塊，這兩塊已包含了X的所有元素，故這兩個塊構成的集合就是X的一個覆蓋，此時覆蓋是
{{x1，x2，x6}，{x3，x4，x5，x6}}

4. 什麼是離散數學中的「覆蓋關系」「全序關系」「擬序關系」「偏序關系」

形式定義：

設R是集合A上的一個二元關系，若R滿足：

Ⅰ 自反性：對任意x∈A，有xRx；

Ⅱ 反對稱性（即反對稱關系）：對任意x,y∈A，若xRy，且yRx，則x=y；

Ⅲ 傳遞性：對任意x, y,z∈A，若xRy，且yRz，則xRz。

則稱R為A上的偏序關系，通常記作≼。注意這里的≼不必是指一般意義上的「小於或等於」。

若然有x≼y，我們也說x排在y前面（x precedes y）。

舉例解釋:

對於上述提到的自反性和傳遞性的舉例解釋:

集合A={a,b,c...}上的關系R是自反 指的是R有(a,a),(b,b),(c,c)...

R是傳遞，指若有(a,b)和(b,c), 則必有(a,c).

偏序（Partial Order）的概念：

設A是一個非空集，P是A上的一個關系，若P滿足下列條件：

Ⅰ 對任意的a∈A，（a,a）∈P;(自反性 reflexlve）

Ⅱ 若（a,b）∈P，且（b,a）∈P，則 a=b;（反對稱性，anti-symmentric）

Ⅲ 若（a,b）∈P，（b,c）∈P，則（a,c）∈P;（傳遞性，transitive）

則稱P是A上的一個偏序關系。

若P是A上的一個偏序關系，我們用a≤b來表示（a,b）∈P。

整除關系便是一個定義在自然數上的一個偏序關系|，3|6的含義是3整除6。大於或等於也是定義在自然數集上的一個偏序關系。

設集合X上有一全序關系，如果我們把這種關系用 ≤ 表述，則下列陳述對於 X 中的所有 a, b 和 c 成立：

如果 a ≤ b 且 b ≤ a 則 a = b (反對稱性)

如果 a ≤ b 且 b ≤ c 則 a ≤ c (傳遞性)

a ≤ b 或 b ≤ a (完全性)

配對了在其上相關的全序的集合叫做全序集合（totally ordered set）、線序集合（linearly ordered set）、簡單序集合（simply ordered set）或鏈（chain）。鏈還常用來描述某個偏序的全序子集，比如在佐恩引理中。

關系的完全性可以如下這樣描述：對於集合中的任何一對元素，在這個關系下都是相互可比較的。

注意完全性條件蘊涵了自反性，也就是說，a ≤ a。因此全序也是偏序（自反的、反對稱的和傳遞的二元關系）。全序也可以定義為「全部」的偏序，就是滿足「完全性」條件的偏序。

可作為選擇的，可以定義全序集合為特殊種類的格，它對於集合中的所有 a, b 有如下性質：

我們規定 a ≤ b 當且僅當。可以證明全序集合是分配格。

全序集合形成了偏序集合的范疇的全子范疇，通過是關於這些次序的映射的態射，比如，映射 f 使得"如果 a ≤ b 則 f(a) ≤ f(b)"。

在兩個全序集合間的關於兩個次序的雙射是在這個范疇內的同構。

嚴格全序

對於每個(非嚴格)全序 ≤ 都有一個相關聯的非對稱(因此反自反)的叫做嚴格全序的關系 <，它可以等價地以兩種方式定義：

a < b 當且僅當 a ≤ b 且 a ≠ b

a < b 當且僅當 ¬(b ≤ a) (就是說 > 是 ≤ 的補關系的逆關系)

性質：

關系是傳遞的： a < b 且 b < c 蘊涵 a < c。

關系是三分的： a < b, b < a 和 a = b 中有且只有一個是真的。

關系是嚴格弱序，這里關聯的等價是等同性。

我們可以其他方式工作，選擇 < 為三分的二元關系；則全序 ≤ 可等價地以兩種方式來定義:

a ≤ b 當且僅當 a < b 或 a = b

a ≤ b 當且僅當 ¬(b < a)

還有兩個關聯的次序是補關系 ≥ 和 >，它們構成了四元組 {<, >, ≤, ≥}。

我們可以通過這四個關系中的任何一個，定義或解釋集合全序的方式；由符號易知所談論的是非嚴格的，抑或是嚴格全序。

例子

字母表的字母按標准字典次序排序，比如 A < B < C 等等。

把一個全序限制到其全序集合的一個子集上。

所有的兩個元素都是可比較的任何偏序集合 X (就是說，如果 a,b 是 X 的成員，則 a≤b 或 b≤a 中的一個為真或二者都為真)。

由基數或序數(實際上是良序)組成的任何集合。

如果 X 是任何集合，而 f 是從 X 到一個全序集合的單射函數，則 f 誘導出 X 上的一個全序：規定 x1 < x2 當且僅當 f(x1) < f(x2)。

設有某個集族，其成員都是用序數為索引的全序集合，然後把這集族上取的笛卡爾積中的有序對按字典序排序，那麽，這字典序是一全序。例如，若有一個集合由一些詞語組成，按字母表把詞語排序的話會是一全序。舉個實例，我們規定"bird"先於"cat"。這可視為是向字母表加入空格符號""（定義""先於所有字母），得到集合A，然後對其自身取可數次笛卡爾積，得到Aω。"bird"可理解為Aω里的序對("b","i","r","d","","",...)，"cat"則是("c","a","t","","","",...)。從而{"bird","cat"}成為Aω的一個子集，把Aω上的字典序限制到這字集，便得出"bird"<"cat"。

實數集和自然數集、整數集、有理數集（作為實數集的子集），用平常的小於(<)或大於(>)關系排序都是（嚴格）全序的。它們都可以被證明是帶有特定性質的全序集合的唯一的（在同構意義下的）最小實例（一個全序 A 被稱為是帶有特定性質的最小全序，即意味著只要別的全序 B 有這個性質，就有從 A 到 B 的子集的一個序同構)：

自然數集是最小的沒有上界的全序集合。

整數集是最小的沒有上界也沒有下界的全序集合。

有理數集是最小的在實數集內稠密的全序集合，這里的稠密性是指對於任意實數a, b，都存在有理數q使得a<q<b。

實數集是最小的無界連通（序拓撲的意義下）的全序集合。

5. 離散數學問題： 求｛1,2,3,4,6,12｝上的偏序｛（a,b）|a整除b｝的覆蓋關系。可以的話

排序關系是整數，那就去，相當於求子集就是 2^n-1個。

寫出R的集合表示，先去掉所有的<a.a>形式的元素，再破壞傳遞性，若<a，b>，<b，c>，a，c>都在R中，則去掉<a，c>，最後把剩下的元素畫圖，<a，b>對應的邊的始點a在下，終點b在上，這樣得到的圖就是哈斯圖。

離散關系

（1）以「圓圈」表示元素；

（2）若x≤y，則y畫在x的上層；

（3）若y覆蓋x，則連線；

（4）不可比的元素可畫在同一層。

例題：畫出下列各關系的哈斯圖

P={1,2,3,4},<P,≤>的哈斯圖。

A={2,3,6,12,24,36},<A,整除>的哈斯圖。

A={1,2,3,5,6,10,15,30},<A,整除>的哈斯圖。

6. 離散數學中已知相容關系的簡化矩陣怎麼求其覆蓋