精华内容
下载资源
问答
  • 等价关系 、 二、等价关系示例 、 三、等价关系与闭包示例 、





    一、等价关系



    等价关系概念 :

    AA 集合是非空集合 , AA \not= \varnothing , 并且 RR 关系是 AA 集合上的二元关系 , RA×AR \subseteq A\times A ;

    如果 RR 关系是 自反 , 对称 , 传递 的 , 那么称 RR 关系是 等价关系 ;





    二、等价关系示例



    1. 关系 11 : xxyy 年龄相同 ;

    • 自反 : xxxx 年龄相同 ; 自反 成立 ;
    • 对称 : xxyy 年龄相同 , yyxx 年龄相同 ; 对称 成立 ;
    • 传递 : xxyy 年龄相同 , yyzz 年龄相同 , xxzz 年龄相同 ; 传递 成立 ;
    • 等价关系 : 该关系是 自反 , 对称 , 传递 的 , 因此该关系 等价关系 ;

    由上边可以看出 , 等价关系是用于分类的 , 同一年出生的人可以划分到一个等价类中 ;



    2. 关系 22 : xxyy 姓氏相同 ;

    • 自反 : xxxx 姓氏相同 ; 自反 成立 ;
    • 对称 : xxyy 姓氏相同 , yyxx 姓氏相同 ; 对称 成立 ;
    • 传递 : xxyy 姓氏相同 , yyzz 姓氏相同 , xxzz 姓氏相同 ; 传递 成立 ;
    • 等价关系 : 该关系是 自反 , 对称 , 传递 的 , 因此该关系 是等价关系 ;


    3. 关系 33 : xx 年龄大于等于 yy ;

    • 自反 : xx 年龄大于等于 xx ; 自反 成立 ;
    • 对称 : xx 年龄大于等于 yy , yy 年龄大于等于 xx ; 对称 不成立 ;
    • 传递 : xx 年龄大于等于 yy , yy 年龄大于等于 zz , xx 年龄大于等于 zz ; 传递 成立 ;
    • 等价关系 : 该关系是 自反 , 传递 的 , 不是对称的 , 因此该关系 不是等价关系 ;


    4. 关系 44 : xxyy 选修同一门课程 ;

    • 自反 : xxxx 选修同一门课程 ; 自反 成立 ;
    • 对称 : xxyy 选修同一门课程 , yyxx 选修同一门课程 ; 对称 成立 ;
    • 传递 : xxyy 选修同一门课程 , yyzz 选修同一门课程 , xxzz 选修同一门课程 ; 上述情况不一定成立 , x,yx,y 可能同时选修音乐 , y,zy,z 同时选修历史 , x,zx,z 没有选修相同的课程 ; 传递 不成立 ;
    • 等价关系 : 该关系是 自反 , 对称 的 , 不是传递的 , 因此该关系 不是等价关系 ;


    5. 关系 55 : xx 体重大于 yy ;

    • 自反 : xx 体重大于 xx ; 自反 不成立 ;
    • 对称 : xx 体重大于 yy , yy 体重大于 xx ; 对称 不成立 ;
    • 传递 : xx 体重大于 yy , yy 体重大于 zz , xx 体重大于 zz ; 传递 成立 ;
    • 等价关系 : 该关系是 传递 的 , 不是 自反 , 对称 的 , 因此该关系 不是等价关系 ;




    三、等价关系与闭包示例



    AA 集合是非空集合 , AA \not= \varnothing , 并且 RR 关系是 AA 集合上的二元关系 , RA×AR \subseteq A\times A ;

    RR 关系求三种闭包 , 有 66 种不同的顺序 , 讨论这些求闭包结果的性质 ;


    66 种求闭包的性质 :

    • rts(R)rts(R) : 先求对称闭包 , 再求传递闭包 , 最后求自反闭包 ;

    • trs(R)trs(R) : 先求对称闭包 , 再求自反闭包 , 最后求传递闭包 ;

    • tsr(R)tsr(R) : 先求自反闭包 , 再求对称闭包 , 最后求传递闭包 ;

    • rst(R)rst(R) : 先求传递闭包 , 再求对称闭包 , 最后求自反闭包 ;

    • srt(R)srt(R) : 先求传递闭包 , 再求自反闭包 , 最后求对称闭包 ;

    • str(R)str(R) : 先求自反闭包 , 再求传递闭包 , 最后求对称闭包 ;


    参考 : 【集合论】关系闭包 ( 关系闭包求法 | 关系图求闭包 | 关系矩阵求闭包 | 闭包运算与关系性质 | 闭包复合运算 ) 五、闭包复合运算

    • rs(R)=sr(R)rs(R) = sr(R) : 对称闭包 与 自反闭包 的复合运算 , 无论顺序如何 , 先求哪个都一样 ;
    • rt(R)=tr(R)rt(R) = tr(R) : 传递闭包 与 自反闭包 的复合运算 , 无论顺序如何 , 先求哪个都一样 ;
    • st(R)ts(R)st(R) \subseteq ts(R) : 传递闭包 与 对称闭包 的符合运算 , 顺序不同 , 其计算结果不同 ;


    因此这里分为两大类

    • ① 先求传递闭包 , 再求对称闭包
    • ② 先求对称闭包 , 再求传递闭包


    先求对称闭包 , 再求传递闭包 :

    • rts(R)rts(R) : 先求对称闭包 , 再求传递闭包 , 最后求自反闭包 ;
    • trs(R)trs(R) : 先求对称闭包 , 再求自反闭包 , 最后求传递闭包 ;
    • tsr(R)tsr(R) : 先求自反闭包 , 再求对称闭包 , 最后求传递闭包 ;

    固定 ts 运算的顺序 , 先 t 后 s , r 运算可以放在任意位置 ;

    自反与其它两个闭包运算没有冲突 , 在任意位置都可以 ;

    对称与传递 , 后求的传递 , 因此其结果是传递的 ;

    上述三个顺序产生的结果是 自反 , 对称 , 传递 的 , 其满足等价关系 , 结果是 等价闭包 ;



    先求对传递包 , 再求对称闭包 :

    • rst(R)rst(R) : 先求传递闭包 , 再求对称闭包 , 最后求自反闭包 ;
    • srt(R)srt(R) : 先求传递闭包 , 再求自反闭包 , 最后求对称闭包 ;
    • str(R)str(R) : 先求自反闭包 , 再求传递闭包 , 最后求对称闭包 ;

    固定 st 运算的顺序 , 先 s ( 对称闭包 ) 后 t ( 传递闭包 ) , r ( 对称闭包 ) 运算可以放在任意位置 ;

    自反与其它两个闭包运算没有冲突 , 在任意位置都可以 ;

    对称与传递 , 先求的传递 , 然后求对称 , 对称会破坏传递 , 因此其结果不是传递的 ;

    上述三个顺序产生的结果是 自反 , 对称 , 不传递 的 , 其不满足等价关系 ;



    rts(R)=trs(R)==tsr(R)rts(R)=trs(R)==tsr(R) rst(R)=srt(R)=str(R)rst(R) = srt(R) = str(R)
    自反 成立 成立
    对称 成立 成立
    传递 成立 不成立
    等价关系 成立 ( 该闭包称为等价闭包 ) 不成立
    展开全文
  • 等价关系与划分对应问题 第二类斯特林数计算公式 4元集等价关系计算 6元集等价关系计算



    等价关系与划分对应问题


    等价关系 与 划分 计算 :

    • 1.等价关于 与 划分 一一对应 : 非空集合 AA 上的等价关系 与 AA 上的划分是 一一对应 的 ;
      ( AA 上有多少个 不同的 等价关系 , 就产生同样个数的不同的划分 )
    • 2.数学模型 : nn 个不同的球 , 放入 rr 个相同的盒子中 , 并且不能出现空盒 , nrn \geq r ; 不同的放球方法对应不同的划分数 ;
    • 3.第二类 Stirling 数 : nn 个不同的球, 放入 rr 个相同的盒子中 , 方案数记做 S(n,r)S(n,r) , 或 {nr}\begin{Bmatrix} n \\ r \end{Bmatrix} ;



    第二类斯特林数计算公式


    第二类 Stirling 数计算方法 :

    • 1.Stirling 数计算公式 :
      • S(n,0)=0S(n,0) = 0
      • S(n,1)=1S(n,1) = 1
      • S(n,2)=2n11S(n,2) = 2^{n-1} - 1
      • S(n,n1)=C(n,2)S(n,n-1) = C(n, 2)
      • S(n,n)=1S(n,n) = 1
    • 2.Stirling 数递推公式 : S(n,r)=rS(n1,r)+S(n1,r1)S(n,r) = rS(n-1, r) + S(n-1, r-1)



    4元集等价关系计算


    题目 : 等价关系

    • 条件 : 集合 A={a,b,c,d}A = \{a,b,c,d\} ;
    • 问题 : 上述集合有多少等价关系 ;

    解答 :

    分析 :

    • 1.有序对个数 : 集合 AA 上有 4×4=164 \times 4 = 16 个有序对 ;

    • 2.二元关系个数 : 集合 AA 上的 二元关系 个数 是 2=2162^{有序对个数} = 2^{16} ;

      • ① 公式推演 : 每个二元关系有 001616 个不等的有序对个数 , 分别统计 有 00 个有序对 , 11 个有序对 , 22 个有序对 , \cdots ,1616 个有序对的 情况 ;
      • ② 计算过程 : C(16,0)+C(16,1)+C(16,2)++C(16,16)=216C(16, 0) + C(16, 1) + C(16,2) + \cdots + C(16, 16) = 2^{16} ;
    • 3.无法直接得出等价关系数 : AA 上有 2162^{16} 个二元关系 , 逐个验证 等价关系 要求的 自反 , 对称 , 传递 性质 , 肯定行不通 , 计算量巨大 ;

    • 4.求划分个数 : 集合 AA 的 等价关系个数 与 划分个数 是一一对应的 , 因此求其划分个数即可 ;


    分步求解 :

    ① 使用 第二类 Stirling 求其不同的划分个数 :
    S(4,1)+S(4,2)+S(4,3)+S(4,4)S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4)

    ② 根据公式 : S(n,1)=1S(n,1) = 1 , 计算 Stirling 数的值 :
    S(4,1)=1S(4, 1) = 1

    ③ 根据公式 : S(n,2)=2n11S(n,2) = 2^{n-1} - 1 , 计算 Stirling 数的值 :
    S(4,2)=2411=231=7S(4, 2) = 2^{4 - 1} - 1 = 2^3 -1=7

    ④ 根据公式1 : S(n,n1)=C(n,2)S(n,n-1) = C(n, 2) ( Stirling 数计算公式 ) , 根据公式2 : C(n,r)=n!(nr)!r!C(n, r) = \cfrac{n!}{(n-r)!r!} , 计算 Stirling 数的值 :
    S(4,2)=C(4,2)=(42)=4!(42)!2!=4×3×2×12×2=6S(4, 2) = C(4,2) =\dbinom{4}{2} =\cfrac{4!}{(4-2)!2!} = \cfrac{4 \times 3 \times 2 \times 1}{2 \times 2} = 6

    ⑤ 根据公式 : S(n,n)=1S(n,n) = 1 , 计算 Stirling 数的值 :
    S(4,4)=1S(4, 4) = 1

    ⑥ 最终划分结果 : AA 上有 15 个划分 ;
    S(4,1)+S(4,2)+S(4,3)+S(4,4)=1+7+6+1=15S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4) = 1 + 7 + 6 + 1 = 15




    6元集等价关系计算


    题目 :

    • 条件 : A={1,2,3,4,5,6}A=\{1,2,3,4,5,6\}
    • 问题 : 计算AA上的 二元关系 的 个数 和 AA 上等价关系的个数 ;

    解答 :

    二元关系个数 :

    • 1> 集合元素个数 : 集合 AA 中有 66 个元素 , A=6|A| = 6 ;
    • 2> 有序对个数 : A×A=6×6=36|A| \times |A| = 6 \times 6 = 36 ;
    • 3> 二元关系个数 :
      • ① 推演过程 : 二元关系 包含 003636 不等的有序对 , 那么需要考虑以上所有情况 , 分别统计 有 00 个有序对 , 11 个有序对 , 22 个有序对 , \cdots ,3636 个有序对的 情况 ;
      • ② 计算公式 :C(36,0)+C(36,1)+C(36,2)++C(36,36)=236C(36, 0) + C(36, 1) + C(36,2) + \cdots + C(36, 36) = 2^{36}

    等价关系个数 :

    • 1> 一一对应 : 等价关系的个数 与 集合的划分数 是一一对应的 ,
    • 2> 进行划分 : 将 集合 AA 划分成 11 块 , 22 块, 33 块, 44 块, 55 块, 66 块 ;
    • 3>写出对应式子 : 集合的划分数为 S(6,1)+S(6,2)+S(6,3)+S(6,4)+S(6,5)+S(6,6)S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6)

    逐个求出 S(6,1)+S(6,2)+S(6,3)+S(6,4)+S(6,5)+S(6,6)S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6) 每个 Stirling 数的值 ;

    ① 根据公式 : S(n,1)=1S(n,1) = 1 , 计算 Stirling 数的值 :
    S(6,1)=1S(6, 1) = 1

    ② 根据公式 : S(n,2)=2n11S(n,2) = 2^{n-1} - 1 , 计算 Stirling 数的值 :
    S(6,2)=2611=251=321=31S(6, 2) = 2^{6-1} - 1 = 2^5 - 1 = 32 - 1 = 31

    ③ 根据递推公式 : S(n,r)=rS(n1,r)+S(n1,r1)S(n,r) = rS(n-1, r) + S(n-1, r-1) , 计算 Stirling 数的值 :
    S(6,3)=3S(5,3)+S(5,2)S(6, 3) = 3S(5,3) + S(5,2)

    拆分成下面两部 进行计算 :

    ( 1 ) 先计算 S(5,3)=3S(4,3)+S(4,2)S(5, 3) = 3S(4,3) + S(4,2)

    • 1> 其中 使用公式 S(n,n1)=C(n,2)S(n, n-1) = C(n,2) 计算 S(4,3)S(4,3) :
      • S(4,3)=C(4,2)=(42)=4!(42)!×2!=4×3×2×12×2=6S(4,3) = C(4,2) = \dbinom{4}{2} = \cfrac{4!}{(4-2)! \times 2!} = \cfrac{4 \times 3 \times 2 \times 1}{2 \times 2} = 6
    • 2> 使用公式 S(n,2)=2n11S(n, 2) = 2^{n-1} - 1 计算 S(4,2)S(4,2) :
      • S(4,2)=2411=7S(4,2) = 2^{4-1} - 1 = 7
    • 3> S(5,3)S(5, 3) 结果 : S(5,3)=3S(4,3)+S(4,2)=3×6+7=25S(5, 3) = 3S(4,3) + S(4,2) =3\times 6 + 7 =25

    ( 2 ) 在计算 S(5,2)S(5,2) 的结果 , 使用公式 S(n,2)=2n11S(n, 2) = 2^{n-1} - 1 进行计算 :
    S(5,2)=2511=15S(5, 2) = 2^{5-1} - 1 =15

    ( 3 ) 最终结果 : S(6,3)=3S(5,3)+S(5,2)=3×25+15=90S(6, 3) = 3S(5,3) + S(5,2) = 3\times25 + 15 =90

    ④ 根据递推公式 : S(n,r)=rS(n1,r)+S(n1,r1)S(n,r) = rS(n-1, r) + S(n-1, r-1) , 计算 Stirling 数的值 :
    S(6,4)=4S(5,4)+S(5,3)=4×C(5,2)+25=4×5!3!×2!+25=4×5×4×3×23×2×2+25=65S(6, 4) = 4S(5,4) + S(5,3) = 4\times C(5,2) + 25 = 4\times \cfrac{5!}{3!\times2!}+25 = 4\times \cfrac{5\times4\times3\times2}{3\times2\times2}+25=65

    ⑤ 根据公式 : S(n,n1)=C(n,2)S(n, n-1)= C(n,2) , 计算 S(6,5)S(6,5) :
    S(6,5)=C(6,2)=6!(62)!×2!=6×5×4×3×24×3×2×2=15S(6,5) = C(6,2) = \cfrac{6!}{(6-2)! \times2!} = \cfrac{6\times5\times4\times3\times2}{4\times3\times2 \times2} =15

    ⑥ 根据公式 : S(n,n)=1S(n, n) = 1 , 计算 S(6,6)S(6,6) ;
    S(6,6)=1S(6,6) = 1

    ⑦ 将上面计算的 66 个斯特林数相加 , 得到的结果 :
    S(6,1)+S(6,2)+S(6,3)+S(6,4)+S(6,5)+S(6,6)=1+31+90+65+15+1=203S(6, 1) + S(6, 2) + S(6, 3) + S(6, 4) + S(6, 5) + S(6, 6) = 1 + 31 + 90 + 65 + 15 + 1 =203


    展开全文
  • 算法学习——求一个集合有多少种等价关系(递归) 等价关系,举个栗子:集合A{1,2,3},求它的等价关系就是{{1},{2},{3}},{{1, 2}, {3}},{{1,3},{2}},{{2,3},{1}},{{1,2,3}},就是每个集合的并集为A...

    算法学习——求一个集合有多少种等价关系(递归)

    等价关系,举个栗子:集合A{1,2,3},求它的等价关系就是{{1},{2},{3}}{{1, 2}, {3}}{{1,3},{2}}{{2,3},{1}}{{1,2,3}},就是每个集合的并集为A,且每个集合彼此没有交集。

    以此计算集合B{1,2,3,4}就有15中等价关系。

    那么我们怎样求呢?

    思考这样一个方法,比如我们有4个苹果,我们要保证每个苹果都有地方落脚,一共有多少种落脚的情况呢?首先我们能看出最多我们要用到四个盘子(一个苹果一个盘子);四个盘子的情况下,我们可以先拿出来一号苹果,将它放入一个盘子里,让其他的苹果放到其余3个盘子里,这是一种情况,我们还可以将3个苹果放入4个盘子里,然后剩余的一个苹果就有了4种选择;这是外层循环,其余的苹果放到盘子中,也可以用这种方法来放,递归就形成了,那么问题来了,递归的出口在哪里?就像求全排列一样,当我们只剩下了一个盘子我们就没法再通过递归分了,所以出口就出现了!由于四个苹果放到四个盘子里的情况只有一种,也可以做出口。

    这是bell数,有兴趣的同学可以去搜一下了解、理解一下。

    #include<iostream>
    #include<string>
    using namespace std;
    int fun(int n,int m)
    {
        if(m==1||n==m)return 1;
        else
           return fun(n-1,m-1)+fun(n-1,m)*m;
    }
    int main()
    {
        int n;
        while(cin>>n&&n>=1)
        {
           int sum=0;
           for(int i=1;i<=n;i++)
            sum+=fun(n,i);
           cout<<sum<<endl;
        }
        return 0;
    }
    

    如有问题欢迎指正!

    wish you have a good day!

     

    展开全文
  • 集合论—等价关系与偏序关系

    千次阅读 多人点赞 2019-06-29 09:20:14
    定义:设RRR为非空集合AAA上的关系,若RRR是自反的、对称的和传递的,则称RRR为AAA上的等价关系。对任何x,y∈Ax,y\in Ax,y∈A,若&lt;x,y&gt;∈R&lt;x,y&gt;\in R<x,y>∈R,则记作x∼yx\sim ...

    等价关系

    等价关系的定义

    定义:设RR为非空集合AA上的关系,若RR是自反的、对称的和传递的,则称RRAA上的等价关系。对任何x,yAx,y\in A,若&lt;x,y&gt;R&lt;x,y&gt;\in R,则记作xyx\sim y

    例:

    1. 若有A={1,2,...,8}A=\{1,2,...,8\}R={&lt;x,y&gt;x,yAxy(mod3)}R=\{&lt;x,y&gt;|x,y\in A\land x\equiv y\pmod 3\}。则RRAA上的等价关系。
    2. 动物按种属进行分类后,“具有相同种属”的关系是动物集合上的等价关系。
    3. 集合上的恒等关系和全域关系都是等价关系。
    等价类

    RR是非空集合AA上的等价关系,则AA上互相等价的元素构成了AA的若干个子集,称作等价类。

    等价类的一般定义:设RR是非空集合AA上的等价关系,对任意的xAx\in A,令[x]R={yyA,xRy}[x]_R=\{y|y\in A, x\text{R}y\}则称[x]R[x]_Rxx关于RR的等价类,简称xx的等价类,简记为[x][x]

    例如:若有A={1,2,...,8}A=\{1,2,...,8\}R={&lt;x,y&gt;x,yAxy(mod3)}R=\{&lt;x,y&gt;|x,y\in A\land x\equiv y\pmod 3\},有等价类:[1]=[4]=[7]={1,4,7}[1]=[4]=[7]=\{1,4,7\}[2]=[5]=[8]={2,5,8}[2]=[5]=[8]=\{2,5,8\}[3]=[6]={3,6}[3]=[6]=\{3,6\}等价类具有如下性质:
    RR是非空集合AA上的等价关系,对任意的x,yAx,y\in A,下面的结论成立。

    1. [x][x]\neq\varnothing,且[x]A[x]\subseteq A
    2. xRyx\text{R}y,则[x]=[y][x]=[y]
    3. x̸Ryx\not \text{R}y,则[x][y]=[x]\cap[y]=\varnothing
    4. xA[x]=A\bigcup_{x\in A}[x]=A.

    其中,(1)表明任何等价类都是集合AA的非空子集;(2)和(3)表明在AA中任取两个元素,它们的等价类或是相等,或是不交;(4)表示所有等价类的并集就是AA.

    商集

    定义:设RR是非空集合AA上的等价关系,以RR的不交等价类为元素的集合称作AARR下的商集,记作A/RA/RA/R={[x]R  xA}A/R=\{[x]_R\ |\ x\in A\}例如:
    1、若有A={1,2,...,8}A=\{1,2,...,8\}R={&lt;x,y&gt;x,yAxy(mod3)}R=\{&lt;x,y&gt;|x,y\in A\land x\equiv y\pmod 3\},有商集:A/R={{1,4,7},{2,5,8},{3,6}}A/R=\{\{1,4,7\},\{2,5,8\},\{3,6\}\}

    2、非空集合AA上的全域关系EAE_AAA上的等价关系,对任意xAx\in A[x]=A[x]=A,商集A/EA={A}A/E_A = \{A\}

    划分与划分块

    AA是非空集合,若存在一个AA的子集族π(πP(A))\pi(\pi \subseteq P(A))满足以下条件:

    1. π\varnothing \notin \pi
    2. π\pi中任意两个元素不交
    3. π\pi中所有元素的并集等于AA,则称π\piAA的一个划分,且称π\pi中的元素为划分块

    例:考虑集合A={a,b,c,d}A=\{a,b,c,d\},则:

    1. {{a},{b,c},{d}}\{\{a\}, \{b,c\},\{d\}\}
    2. {{a,b,c,d}}\{\{a,b,c,d\}\}
    3. {{a,b},{c},{a,d}}\{\{a,b\}, \{c\},\{a,d\}\}
    4. {,{a,b},{c,d}}\{\varnothing, \{a,b\}, \{c,d\}\}
    5. {{a},{b,c}}\{\{a\},\{b,c\}\}

    中(1)、(2)是AA的划分;(3)不是AA的划分,因为子集{a,b}\{a,b\}{a,d}\{a,d\}有交;(4)不是AA的划分,因为\varnothing在其中;(5)不是AA的划分,因为所有子集的并集不为AA.

    由商集和划分的定义不难看出若有AA上的二元关系R={&lt;x,y&gt;  x,yπ}R=\{&lt;x,y&gt;\ |\ x,y \in\pi\},则可证明RRAA上的等价关系,称为有划分π\pi所诱导的等价关系,且该等价关系的商集为π\pi。所以集合AA上的等价关系与集合AA的划分是一一对应的。

    偏序关系

    在介绍偏序关系之前先了解一下什么是全序关系:
    全序集的定义:&lt;A,&gt;&lt;A,\preccurlyeq&gt;为偏序集,若对任意的x,yAx,y\in Axxyy都可比,则称\preccurlyeqAA上的全序关系,且称&lt;A,&gt;&lt;A,\preccurlyeq&gt;为全序集。

    例如:{1,2,3,4,5}\{1,2,3,4,5\}上的\leqslant关系就是全序关系,而整除关系就不是全序关系。

    偏序关系的定义

    RR为非空集合AA上的关系,若RR是自反的、反对称的、传递的,则称RRAA上的偏序关系。简称偏序,记作\preccurlyeq

    \preccurlyeqAA上的偏序关系,若有有序对&lt;x,y&gt;&lt;x,y&gt;属于偏序\preccurlyeq,可记作xyx\preccurlyeq y,读作xx小于等于yy,不过这里的“小于等于”不是指数的大小,而是指它们在偏序中的位置先后。

    例如在集合A={1,2,3}A=\{1,2,3\}中,偏序\preccurlyeqAA上的大于等于关系,则:={&lt;3,3&gt;,&lt;3,2&gt;,&lt;3,1&gt;,&lt;2,2&gt;,&lt;2,1&gt;&lt;1,1&gt;}\preccurlyeq = \{&lt;3,3&gt;,&lt;3,2&gt;,&lt;3,1&gt;,&lt;2,2&gt;,&lt;2,1&gt;&lt;1,1&gt;\}那么就有323\preccurlyeq 2313\preccurlyeq 1等,它们分别表示&lt;3,2&gt;&lt;3,2&gt;\in\preccurlyeq&lt;3,1&gt;&lt;3,1&gt;\in\preccurlyeq

    偏序集

    偏序集定义:一个集合AAAA上的偏序关系RR一起称作偏序集,记作&lt;A,R&gt;&lt;A,R&gt;

    可比与盖住:
    &lt;A,&gt;&lt;A,\preccurlyeq&gt;为偏序集,对于任意的x,yAx,y\in A,若果xyx\preccurlyeq yyxy\preccurlyeq x成立,则称xxyy是可比的,若xyx\prec y(即xyxyx\preccurlyeq y \land x\neq y),且不存在zAz\in A使得xzyx\prec z\prec y,则称yy盖住xx

    例如:&lt;A,&gt;&lt;A,\preccurlyeq &gt;是偏序集,其中A={1,2,3,4,5}A=\{1,2,3,4,5\}\preccurlyeq是整除关系。

    那么对任意xAx\in A都有1x1\preccurlyeq x,所以1和1,2,3,4,5都是可比的;但是2与3相互不能整除,所以2和3是不可比的:。

    对于1和2来说,121\prec 2,并且不存在zAz\in A使得1整除zz并且zz整除2,所以2盖住1,同样的有4盖住2,但4不盖住1因为有1241\prec 2\prec 4

    显然的,若xxyy不可比,则一定不会有xx盖住yy或反之。

    哈斯图

    对于又穷的偏序集&lt;A,&gt;&lt;A,\preccurlyeq&gt;可以用哈斯图来描述。在哈斯图中,每一个节点表示AA中的一个元素,节点位置按它们在偏序集中的次序从低向上排列。若yy盖住xx则在xyxy之间连一条直线。

    例如:&lt;A,&gt;&lt;A,\preccurlyeq &gt;是偏序集,其中A={1,2,3,4,5}A=\{1,2,3,4,5\}\preccurlyeq是整除关系,则该偏序集的哈斯图为:
    hast
    由哈斯图不能看出全序集的哈斯图是一条直线,因此,全序集也称做线序集

    元与界

    &lt;A,&gt;&lt;A,\preccurlyeq&gt;为偏序集,BAB\subseteq A

    1. yB\exists y\in B,使得x(xByx)\forall x(x\in B\to y\preccurlyeq x)成立,则称yyBB的最小元。
    2. yB\exists y\in B,使得x(xBxy)\forall x(x\in B\to x\preccurlyeq y)成立,则称yyBB的最大元。
    3. yB\exists y\in B,使得¬x(xBxy)\lnot\exist x(x\in B\land x\prec y)成立,则称yyBB的极小元。
    4. yB\exists y\in B,使得¬x(xByx)\lnot\exist x(x\in B\land y\prec x)成立,则称yyBB的极大元。

    &lt;A,&gt;&lt;A,\preccurlyeq&gt;为偏序集,BAB\subseteq A

    1. yA\exist y\in A,使得x(xBxy)\forall x(x\in B\to x\preccurlyeq y)成立,则称yyBB的上界。
    2. yA\exist y\in A,使得x(xByx)\forall x(x\in B\to y\preccurlyeq x)成立,则称yyBB的下界。
    3. C={y  x(xBxy)}C=\{y\ |\ \forall x(x\in B\to x\preccurlyeq y)\},则称CC的最小元为BB的上确界(最小上界)
    4. C={y  x(xByx)}C=\{y\ |\ \forall x(x\in B\to y\preccurlyeq x)\},则称CC的最大元为BB的下确界(最大下界)
    展开全文
  • 集合中的等价关系

    千次阅读 2019-09-12 21:37:42
    那究竟什么是等价关系呢?很简单,它是集合上的一个二元关系,满足下面三个条件: 自反性(reflexivity):集合中的每一个元素都与自身等价,即 对称性(symmetry):若集合中的元素与等价,则与等价,即 ...
  • 离散数学 等价关系
  • 、划分 、 二、划分示例 、 三、划分与等价关系定理 、
  • 离散数学:等价关系集合覆盖

    千次阅读 2020-03-11 20:52:53
    今天是离散数学打卡第二天 学习内容:等价关系集合覆盖 心得体会:看视频真的是种很好的学习方式
  • 一个集合定义一个等价关系相当于把这个集合划分成许多子集的集.(这里假如不懂请追问) 于是求等价关系的数目,就是求划分的数目. 这其实是个定理,这个数叫Bell数. Bell数没有通项公式,但我们有一个递推公式: B(n+...
  • 等价关系

    千次阅读 2015-08-21 02:03:30
    定义:集合S上的关系≡\equiv ,...可以使用等价关系集合S划分为等价类,S的两元素x和y属于同一等价类,当且仅当≡\equiv ,例如,有12编号为0至11元素: 0≡\equiv 4,3≡\equiv 1,6≡\equiv 10,8≡\equiv 9,7≡\
  • c语言程序判断关系R在集合A是否等价、相容、偏序

    千次阅读 多人点赞 2019-11-11 21:51:53
    这是我们离散老师布置的第二次程序作业,...判断关系R在集合A是否等价、相容、偏序,也就是判断关系R是否满足自反,对称,反对称,传递这些性质。 等价:自反,对称,传递 相容:自反,对称 偏序:自反,反对称,传...
  • 设R是非空集合A上的关系,R的自反(对称或传递)闭包是A上的关系R’,且R’满足以下条件: 1) R’是自反的(对称或传递) 2) R R’ 对A上任何包含R的自反(对称或传递)关系R’’有R’ R’’
  • 离散数学 等价类 等价关系 划分

    万次阅读 2014-12-11 14:34:18
    等价类:设R是集合A上的等价关系,与A中的一个元素a有关系的所有元素的集合叫做a的等价类 A的关于R的等价类记作[a]R 与元素a有关系的意思,即对于元素a,凡是满足aRb的元素b,都称之为有关系 例如:对于模4同余...
  • 一个等价关系的证明

    千次阅读 2019-05-15 20:43:06
    Our goal is to prove n−2nsin⁡1n∼n−2(n→∞)\boxed{{n^{-2n \sin\frac{1}{n}}}\sim{n^{-2}}(n \to \infty)}n−2nsinn1​∼n−2(n→∞)​ For this purpose, we are going to compute the limit as follows ...
  • 1.由集合 S 上的一个置换群 < G , ∗ > <G,*> < G , ∗ > 诱导的二元关系 R 是一个 等价关系 。证明参看 https://blog.csdn.net/qq_25847123/article/details/100253596 2. X a b X_{ab} X a b ​ ...
  • 目录 集合中的三种关系 等价关系举例 相容关系举例 偏序关系举例 ...等价关系与等价类的例题 ...集合中的三种关系 ...序关系(偏序关系):设A是一个集合,若A上的关系R是自反的,反对称的,传递...
  • 等价关系——离散数学

    千次阅读 2018-05-03 16:05:12
     例如:x=xx=y意味着y=xx=y且y=z意味着x=z 可以使用等价关系集合S划分为等价类,S的两元素x和y属于同一等价类,当且仅当≡≡,例如,有12编号为0至11元素: 0≡≡4,3≡≡1,6≡≡10,8≡≡9,7≡≡4,6≡≡8,3...
  • 设 RRR 是某个集合 XXX 上的一个二元关系。若 RRR 满足以下条件: 自反性:∀x∈X, xRx\forall x \in X,\ xRx∀x∈X, xRx 对称性:∀x,y∈X, xRy⇒yRx\forall x,y \in X,\ xRy \Rightarrow yRx∀x,y...
  • 离散数学之特殊关系之等价关系

    千次阅读 2020-06-10 14:41:36
    先引进集合的划分:给定非空集合A,若S = {S₁,S₂ ,…,Sn},且 ①Si ⊆ A,且Si ≠ Ø , i = 1,2,…n; ②Si ∩ Sj = Ø,i ≠ j,i,j = 1,2,…n;...设R是非空集合A上的一个等价关系,∀x∈A.
  • 离散--4.4 等价关系与偏序关系

    千次阅读 2016-01-08 17:48:06
    4.4 等价关系与偏序关系 • 4.4.1 等价关系 • 4.4.2 等价类和商集 ...4.4.3 集合的划分 ...等价关系的定义与实例 ...设R为非空集合上的关系. ...则称R为A上的等价关系. ...是一个等价 关系, 若x,y>∈R,
  • 次在CSDN上写文章,直接上代码了,这题目也不难,各个函数都非常的容易理解。(略显智障的函数名… #include<stdio.h> #include<stdlib.h> int Relation_matrix[15][15],Tmp[15][15]; int R_size,...
  • 离散数学 等价关系解释

    千次阅读 2011-11-09 08:02:10
    集合上每个等价关系对应集合的一种划分,集合的每一种划分又对应于该集合一个等价关系,不同的等价关系对应于集合的划分也不同,因此集合有多少不同划分,就有多少不同等价关系,三个元素的集合共有5种不同划分,(含有1...
  • 集合A{1,2,3},求它的等价关系就是{{1},{2},{3}},{{1, 2}, {3}},{{1,3},{2}},{{2,3},{1}},{{1,2,3}},就是每个集合的并集为A,且每个集合彼此没有交集。 所以集合B{1,2,3,4}就有15中等价关系。 ...
  • 才发现,以前木头一样的望文生义,或者以前...首先是命题,一个或真或假的陈述句,一个这样的句子,是不可能又真又假的。 命题的否定:非命题,标号可以是字母加上横线,也可以是横折。 命题的合取:叫得比较奇怪,我
  • 一行,一个整数n(1≤n≤100),表示集合A的元素个数。 输出格式: 集合A上不同等价关系的个数模109+7,即输出其个数模1000000007。(因为当∣A∣比较大时,A上的等价关系数是个巨大的数字,比如∣A∣=100时,其上...
  • 等价类 、 二、等价类示例 、 三、等价类性质 、 四、商集 、 五、商集示例 1 、 六、商集示例 2 、 七、商集示例 3 、
  • 命题公式的等价关系和蕴涵关系
  • 1. 等价关系的定义 2. 等价关系示例 3. 等价关系图 4. 以n为模的同余关系 ...7. 商集的定义——非空集合上某一等价关系所确定的一切等价类的集合 8. 计算商集的通用过程 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,196
精华内容 32,478
关键字:

一个集合的所有等价关系