离散数学中覆盖如何处理

① 离散数学问题： 求｛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,整除>的哈斯图。

② 离散数学划分和覆盖的区别

把A拆分为几个非空子集A1,A2,...,Am的并集A=A1∪A2∪...∪Am，那么S={A1,A2,...,Am}称为集合A的一个覆盖。A的划分是在覆盖的基础上，还要求任意两个子集的交集是空集。
比如A={a,b,c,d}，那么S1={{a},{a,b},{a,b,c},{d}}是A的覆盖，但不是划分。S={{a,b},{c,d}}是A的覆盖，也是划分。
划分必是覆盖，覆盖未必是划分。
覆盖与划分都不是唯一的。

③ 离散数学基本知识

总结 离散数学知识点 命题逻辑
→，前键为真，后键为假才为假；<—>，相同为真，不同为假；
主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；
求极小项时，命题变元的肯定为1，否定为0，求极大项时相反；
求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；
求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写；
真值表中值为1的项为极小项，值为0的项为极大项；
n个变元共有个极小项或极大项，这为(0~-1)刚好为化简完后的主析取加主合取；
永真式没有主合取范式，永假式没有主析取范式；
推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假)
10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 谓词逻辑
一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
全称量词用蕴含→，存在量词用合取^;
既有存在又有全称量词时，先消存在量词，再消全称量词； 集合
N，表示自然数集，1,2,3……，不包括0；
基：集合A中不同元素的个数，|A|；
幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)；
若集合A有n个元素，幂集P(A)有个元素，|P(A)|==；
集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)；
集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 关系
若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数为mn，A到B上可以定义种不同的关系；
若集合A有n个元素，则|A×A|=，A上有个不同的关系；

④ 离散数学这个盖住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>

(4)离散数学中覆盖如何处理扩展阅读：

①若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，这个事实称为带余除法定理，是整除理论的基础。

⑤ 什么是离散数学中的“覆盖关系”“全序关系”“拟序关系”“偏序关系”

形式定义：

设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。

实数集是最小的无界连通（序拓扑的意义下）的全序集合。

⑥ 离散数学中给定集合，给定相容关系且知道简化矩阵，如何求此集合的覆盖

集合上的相容关系是指具有自反和对称的关系，由于它具有自反性，故它的关系矩阵的对角线上的元素均为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}}

⑦ 在离散数学中已知相容关系和简化矩阵怎么求相应的覆盖呀麻烦你说一下解题思路，最好能举例子说明

参阅左孝凌主编的2000版离散数学自考教材第62页。

本题是63页的第一题

⑧ 离散数学关于覆盖划分的题

证明
注意到
{A1,
A2,
...,
.AK}
是
A
的一个划分必须满足两个条件：
1）∪Ai
=
A；
2）Ai∩Aj
=
Φ
(i≠j)。
1）是明显的。下面证明2）：
若有i,
j，使
Ai∩Aj
≠
Φ，即有
a
含于
Ai∩Aj
中，故对任意
b∈Ai，因
a∈Ai，应有∈R，但
a∈Aj，得知也应有b∈Aj，因而
Ai
包含于
Aj，与题设矛盾。得证。

⑨ 离散数学 给定集合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>}

⑩ 离散数学中已知相容关系的简化矩阵怎么求其覆盖