离散数学知识汇总

1、离散数学笔记第一章命题逻辑合取析取定义1.1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义1.1.4条件联结词，表示“如果那么”形式的语句定义1.1.5双条件联结词，表示“当且仅当”形式的语句定义1.2.1合式公式(1)单个命题变元、命题常元为合式公式，称为原子公式。(2)若某个字符串A是合式公式，则A、(A)也是合式公式。若A、B是合式公式，则AaB>AvB>AtB、AHB是合式公式。(4)有限次使用(2)(3)形成的字符串均为合式公式。条件式的等值式、原命题O逆否命超 双条件的等值式1.3 等值式(l)p>qoipvqo-iq-ipp-qo<

2、;pfq)MqtpupAqMAq)(3 )p P(4)p<=>pApopvp(5)pvqo qvp, p/q。qAp(6) p v(q vr) <=>(p vq) v rp A(q ArJ o (p aq) a r(7) p v(q at) vq)A(p vr)p a(q vr) = (p aqMp at)(S) p v(p at) OppA(pvr) op Tpq) ip v.q<p vq)i p A-iq双重否定律事等律交换律结合律分配律德摩律注意;符号“uT不是一个联结词它表明两个公式的值相等.符号“c"是联结词.表示“当且仅当二“充分必要'

3、;定理1,3,1置换规则：当将公式A中的B换成C得到公式D后,若HoC.那么AoD.当将一个公式的局部进行等值替换后.仍与原公式等值,这也是能们在代数等散学最常见的方法，不断时局部进行等值替换的操作，称为“等值演算:1.4 析取范式与合取范式i定义141文字:命题变项(变元)及其否定称为文字。如:6q、Ap.q、-定义142筒单折取式：仪.由有限个文字构成的折取式&如:pvq、->pvq,pv->q.-»p”rq，pvqvr.定义1.4.3蔺单合取式:仅由有限介文字构成的合取式°如二pAq,-pq、p-q、rpa-pAqAr.定理L4.l(1)简单析取式

4、Ai是重；式。同时含有某命题变兀及其杳定式,如Ai-pv.p7q前单合取式Ai足矛周式。同时含有某个箭题变元及其否定式，如Ai=pyp八.定义144折取范式：由行限个向第合取式的所取构成的命题公式.如：(pAq)v(ipAq)(pa-q)p八一1q)¥(p八qat).由析取的性质可知，应当每个葡年合取式为假时，析取范式为假.范式中只出现T否定卜仪析取、M合取)三种符号,其中八八交替出现，因为最外层的运箕符号是析取，从而将这种范式林为缶析取范式,如果最外层的符号是合取则林为“合取范式:定义145合取范式：由有限个简单析取式的合取构成的命题公式.如：(pvq)A(>pvq)、(pv

5、-iq)A(-ipv-«q)a(pvqvr|由合取的性质可整，仅当每个筒单析取式为真时.合取范式才为真.定理L4.2U)析取范式是矛盾式。设范式中每个简单分取式是矛盾式.值)合取范式是重言式o诗范式中每个简单析取式是重音式.将一个普通公式转换为范式的基本步骤I,肯定转换T；利用AfBUlA“B,将条件式运算符转换为7、2、恰当转换1：利用AcBo(AtH)a(BTA0rA*H)a(AvrH)利用ABo(AaB)v(A3、否定到底：利用-1iAu>A、1(AvH)iAai(AaB),CX>»AvB4、适当分配；Aa(BvC)<XAaH)v(AaC)Av(Ba

6、C)«>(AvB)a(AvC)定理143(范式存在定理)(I)不是永联的命题公式.存在析取范式.(2)不是水声的命题公式，存在合取范式，定义144小项,在含有n个变元的简单合取式中.每个甜题变元或其否定仅出现一次，且各变元按其字母顺序出现,则读而单合取式为小项或极小项.如：p八qalp-iAqAr,p八qi八r,八1是小项，而pAJqr不是小项中定义1.4.5大中：在含有口个变元的倚单折取式中，每个命题变元或其否定仅出现一次，且善变元按其字母顺序出现.则该筒单析取式为大项或极大项，如；pvqvr,p-iVQvr,pvqivr,.pvqvr但p”r.Fq,r不是大项.【帮你记忆X

7、因为pq的结果是这两值中最小者.即口八q=mi"p,q卜所以将形如冲zf的公式称为小项.类似pvq结果是这两值中最大者.即pvqFwcgq),所以将附如的公式称为大项”定义1.4.6主合取1S式工一个合取范式中，如果所杓悯的所取式均为大项，则称为主介取范式.如(pvqvr)A(pv-iqvrH-ip-ivqvr)N-ip“q-i“r)是_E合取范式.又如tpvrMt-qwSjpvtvr)前2个图单析取式变元不全，因而不是大项，故不是主合取范式.定义1.4.7主折取范式：一个析取范式中,如果所有蒲单合取式均为小项.则称为上析取范式.如JpArNqAN(prqA-ir),因其前2个简单台

8、取式中少变无不是小项,从而不是主析取范式父如：(>pAqAr)v(rpA-1QAT)V(pAqAF)V(p-iAq-iAf)是主析取范式.现构造(pTq)一八其主析取范式、其主合取范式的真值表，其中mooiymum.VTDi为F(pAqAT)Y(_tpAQAAtQAipAqA卜MqqqAMqi口AMidiAMng为(pvqvrjAfpv-(qvr)a(-ipvqv-ir)a(->pv>qvr).表LI7Pqr(pTq)原式(记为A)7nv)ivn)to(jvmm主折取范式(记为即Mow)AMowAM|OAMi。主合取范式<记为。00000v0v0vtk=O0A1,A1A

9、IN0011Iv0v0vg】1AIA1A1=101000v0v0vIW)1AOA1A1=001110”1v0v0=1IA1A1A1=11001OvOv1v0=1IA1AIA1=110】0Oy0v0v0=0IA1A0A1=011000v0vOv0=0IAAA0=011110v0vOv11IAIA1A1-1从表L17可发现(piqj与其主析取范式、主合取范式的真值表完全一样.说明三者互相等值，因此我们得到如卜定理.定理144”,不是永假的命题公式,其主析取范式等值F原公A.口)不是永真的命卷公式，其主合取范式等值F原公式。iii1.6推理例 .'：15定义1.6.1设A与C是两个命题公式，

10、效结论，或称 A可以逻辑推出 C,记为的有若A-C为永真式、重言式，则称C是AA=>C。(用等值演算或真值表)第二章谓词逻辑2.1、 基本概念?：全称量词？：存在量词带“全称量词”的谓词公式形如?x(H(x) VWL(x),即量词的后面为一般情况下，如果个体变元的取值范围不做任何限制即为全总个体域时，"?x(H(x)-B(x),即量词的后面为条件式，带“存在量词”的谓词公式形如合取式例题R(x)表示对象x是兔子，T(x)表示又象x是乌龟，H(x,y)表示x比y跑得快，L(x,y)表示x与y一样快,则兔子比乌龟跑得快表示为：？x?y(R(x)AT(y)-H(x,y)有的兔子比所有

11、的乌龟跑得快表示为：？x?y(R(x)AT(y)-H(x,y)2.2、 谓词公式及其解释22.定义非逻辑符号：个体常兀(如a,b,c)、函数常兀(如表布x+y的f(x,y)、谓词常兀(如表本人类的H(x)。定义定义定义R(x1xn)是n元谓词，t1.tn是项，则R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。定义2.2.5合式公式：(1)原子公式是合式公式；(2)若A是合式公式，则(A)也是合式公式；(3)若A,B合式,则AVB,AAB,AfB,A?B合式(4)若A合式，则？xA、?xA合式(5)有限次使用(2)(4)

12、得到的式子是合式。定义2.2.6量词辖域：？xA和？xA中的量词？x/?x的作用范围，A就是作用范围。定义2.2.7约束变元：在？x和？x的辖域A中出现的个体变元x,称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。定义2.2.8自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。定义2.2.9闭公式是指不含自由变元的谓词公式从本例(已省)可知，不同的公式在同一个解释下，其真值可能存在，也可能不存在，但是对于没

13、有自由变元的公式(闭公式)，不论做何种解释，其真值肯定存在谓词公式的类型：重言式(永真式)、矛盾式(永假式卜可满足公式三种类型定义在任何解释下，公式的真值总存在并为真，则为重言式或永真式。定义在任何解释下，公式的真值总存在并为假，则为矛盾式或永假式。定义存在个体域并存在一个解释使得公式的真值存在并为真，则为可满足式。定义代换实例设p1,p2，Pn是命题公式A0中的命题变元，A0A,An是n个谓词公式，用A代替公式A中的Pi后得到公式A,则称A为A的代换实例。如A(x)VA(x),?xA(x)V？xA(x)可看成pVp的代换实例，A(x)AA(x),?xA(x)A？xA(x)可看成pAp的代换实

14、例。定理2.2.1命题逻辑的永真公式之代换实例是谓词逻辑的永真公式，命题逻辑的永假公式之代换实例是谓词逻辑的永假式。(代换前后是同类型的公式)2.3、 谓词公式的等值演算定义2.3.1设A、B是两个合法的谓词公式，如果在任何解释下，这两个公式的真值都相等，则称A与B等值，记为ABo当AB时，根据定义可知，在任何解释下，公式A与公式B的真值都相同，故A?B为永真式，故得到如下的定义。定义2.3.2设A、B是两个合法谓词公式，如果在任何解释下，A?B为永真式，则A与B等值，记为ABo一、利用代换实例可证明的等值式(p?p永真，代换实例？xF(x)?？xF(x)永真)二、个体域有限时，带全称量词、存

15、在量词公式的等值式如：若D=a1，a2,，an，贝U?xA(x)A(a1)AA(a2)八AA(an)三、量词的德摩律1、？xA(x)?xA(x)2、？xA(x)?xA(x)四、量词分配律1、?x(A(x)AB(x)?xA(x)A?xB(x)2、?x(A(x)VB(x)?xA(x)V?xB(x)记忆方法：？与八，一个尖角朝下、一个尖角朝上，相反可才分配。2式可看成1式的对偶式五、量词作用域的收缩与扩张律A(x)含自由出现的个体变元x,B不含有自由出现的x,则有：1、？/?(A(x)VB)?/?A(x)VB2、？/?(A(x)AB)?/?A(x)AB对于条件式A(x)?B,利用“基本等值一”将其转

16、换为析取式，再使用德摩律进行演算六、置换规则若B是公式A的子公式，且BC,将B在A中的每次出现，都换成C得到的公式记为D,则AD七、约束变元改名规则将公式A中某量词的指导变元及辖域中约束变元每次约束出现，全部换成公式中未出现的字母，所得到的公式记为B,则AB证明步骤：V x(A(x)-> B) oVx(-i A(x)vB) >Vx -i A(x)vB xA(x)v B «>3xA(x)-> B命题公式pfq=«pvq的代换实例量词作用域的收缩与扩张律德摩律pOi-ip的代换实例2.4、 谓词公式的范式定义241一个谓词公式.如果量词均在全式的开头.它

17、们的作用域延伸到整个公式的末尾.末该公式称为附束范式L如；Vx3yF(x)aG(y卜Vy3x(>p(x,y)*G(y)是前一范式.但Vx(F(x)->my(G(yR不是前束范式:定理241任意一个谓词公式.都有与之等值的前束范式.从定理证明过程，可得到获取前束范式的步骤：剔除不起作用的量词；(2)如果约束变元与自由变元同名，则约束变元改名；(3)如果后面的约束变元与前面的约束变元同名，则后的约束变元改名;(4)利用代换实例，将一、?转换VA表示;(5)利用德摩律，将否定深入到原子公式或命题的前面；(6)利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边例题工4.1把公

18、式转换为前束范式oV xP( x h->3 yQ(y) o-tV xP(k)v 3 yQ( y) tt-3x ->P(x)v3)<Xy) =三 x 3 y(-i P(x)v3 yQ( y) 后方约束变元改名 条件式的代换实例 速摩律量伺辖域的扩张罄：由于没有空量词.即没有不约束任何变元的盘同.现行的约束变兀也不与门山变兀同名,但三乂的约束变元与前面Vx中的k同名.后者改名.2.5、 谓词推理定义2.5.1若在各种解释下A八4A.ATB只能为真即为永真，则称为前提A1AA2A.A可推出结论Bo定义2.5.2在所有使AAAA.An为真的解释下，B为真，则称为前提AAAA.A可推出

19、结论Bo谓词逻辑的推理方法分为以下几类：一、谓词逻辑的等值演算原则、规律：代换实例、量词的德摩律、量词的分配律、量词辖域的扩张与收缩、约束变元改名。二、命题逻辑的推理规则的代换实例，如假言推理规则、传递律、合取与析取的性质律、CP规则、反证法等。三、谓词逻辑的推理公理】)VxA(xvVxB(x)=>Vx(A(xJvB(x)全称量词展开可推出台外(2)3x(A(x)aB<x)=>3xA(x)a3xB(x)存在量词的合并可推出展开别记反了(3)全称量词的指定US或VxA(x)=>A(xO)K0是论域中的任意个体谏规则可理解为：谓词公式VXA0O在某个解释下为真，即论域中酶个

20、体都在此解释下使A为真时，论域中的江总生他在此解释下使A为真.(4)全称量词的推广U6或R+,A(xO)=>VxA(x)通是论域中的任意分体，它是由某个企称量词指定时确定个体,谟规则可理解为：在某个解郭卜，论域中的任弥卜体时都使公式A为直,那么论域中的所有个体在此解解卜都使A为真.意即谓词公式WxA(k)为真.5存在量词的指定ES或3r3xA(x)=>A(c)c为某个特定的个体.不是任意的个体.这是它与仝称量词的区方L谈规则可理解为工当WxAQO在某个解择下为真时，至少有一个个体常元c在读解拜卜使得公式A为真，即A依尸I.伯)存在量词的推广EG或三七A(c)=3xA(k)C为某个体

21、，可以是某个存在量词指定时确定的个体,也可以是全称量词指定时的个体.读费则可理解为工在某个解押下有1个个体c使公式A为真，就可认为mxAfx)该解弊下为真.例赳253证明卡虱F('卜氏封乂)3双F(k)aHx)3x(G(x)aH(x)(1>3x(F(x)aH(x),ZjH (2)F(c>aH(c)>sH (3)F)为真 (4)地。为真(5) VxfF(x)->G(K)为真 (6)E(cHG(u)为真Gc)为真得>g(caH©为真3x(G(x)aH鹏)为真(前提)(存在指称，至少存在c便K0为真,先使用存在指定)«2)人的定义)1人的定义

22、)(前提)(全称指定,任意刘都为真,尤其nOf时为直)(2卜楫)依再推理的代换室例)(4X7)合取)65)存在推广,有一个c使公式为真，则存在量词可加1第三章集合与关系3.1、 基本概念在离散数学称“不产生歧义的对象的汇集一块”便构成集合。常用大写字母表示集合，如R表示实数，N表示自然数，Z表示整数，Q表示有理数，C表示复数。描述一个集合一般有“枚举法”与“描述法”，“枚举法”。元素与集合之间有“属于三”或“不属于正”二种关系。定义3.1.1设A,B是两个集合，如果A中的任何元素都是B中的元素，则称A是B的子集，也称B包含于A,记为BA,也称A包含B,记为A3B。3.2、 合运算性质定义3.2

23、.1设A、B为集合，A与B的并集AuB、A与B的的交集AB、A-B的定义：AuB=x|xAAvx-B,AcB=x|x亡AxWB,A-B=x|xAaxB定义3.2.2设A、 B为集合，A与B的对称差，记为A®B=x|(xwAax更B)“(x正AAx三B)=ABB-AcB。定义3.2.3设A、B是两个集合，若AB、BCA则A=B,即两个集合相等。帚等律AA=A、AcA=A结合律A.B.C=A.(B_C尸(A一B)一CA-B'C=A'(B-C)=(A-B)-C交换律AuB=BuA、ACB=BCA分配律A一(B-C)=(A-B)(A一C)A'(B一C)=(A-B).(

24、A-C)同一/零律A5=A、A，n?=?排中/矛盾律A=_|A=E>Ac->A=?吸收律(大吃小)德摩律双重否定Ac(B=A)=A、A=(BcA尸A(A c B尸A uB、(A u B尸A=A3.3、 有穷集的计数定理3.3.1二个集合的包含排斥原理IA=4I=|A|+IA2|-lAAl3.4、 序偶定义3.4.2令<x,y>与<u,v>是二个序偶，如果x=u、y=v,那么<x,y>=<u,v>即二个序偶相等。定义3.4.3如果<x,y>是序偶，且<<x,y>,z>也是一个序偶，则称<x,y,

25、z>为三元组。3.5、 直积或笛卡尔积定义3.5.1令A、B是两个集合，称序偶白集合<x,y>|xWA,yWB为A与B的直积或笛卡尔积，记为A乂B。如：A=1,2,3,B=a,b,c则AMB=1,2,3父a,b,c=<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>直积的性质1、A*B=C尸A父B=A父C2、AM(Bc尸A父Bca父C3、（B=C）MA=B黑A=CMA4、（BCC）ma=bxaocxa5、A=BAM

26、C=BMCCxACcxB6、A=B,C=DAmC三BmD定义3.5.2令A，%A是n个集合，称n元组的集合<x1,x2，xn>|XiWA,X2WA，,.,XnwA,为A,A2,An的直积或笛卡尔积，记为A父4M父人。3.6、 关系定义3.6.1称直积中部分感兴趣的序偶所组成的集合为“关系”，记为Ro如在直积1,2,345,6,7,8x1,2,3,4,5,6,7,8中，只对第1个元素是第2个元素的因数的序偶感兴趣，即只对R=<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7&g

27、t;,<1,8>,<2,2>,<2,4>,<2,6>,<2,8>,<3,3>,<3,6>,<4,4>,<4,8>,<5,5>,<6,6>,<7,7>,<8,8>,R三AMA(A=1,2,3,4,5,6,7,8)定义3.6.2如果序偶或元组属于某个关系R,则称序偶或元组具有关系Ro关系图，关系矩阵133.7、 关系的复合定义3.7.1若关系FJAMA,关系GEAXA,称集合<x,y>|3t使得<x,t>WF,<t

28、,y>wG为F与G的复合，记为F=Go例题3.7.1令A=1,2,3,F=<1,1>,<1,2>G=<2,2>,<1,3>,<1,1>则解：F'G=<1,3>,<1,1>,<1,2>,G叩=<1,2>,<1,1>,因此关系的复合不满足交换律。采用复合的定义去计算，只适合于人工计算，为了编程实现，故采用矩阵表示关系。1My = 0 01 0一1 o r-1 10 000 1 00 00 00 0 00 。0一00a ,加法是析取如MF的1行与MG说明：Mf的第i行

29、与Mg的第j列相乘时，乘法是合取的第3列相乘是：(1A1)v(1A0)v(0A0),结果为1。定义3.7.2若关系FJAXA,称集合<y,x>|<x,y>WF为F的逆，记为F1例题3.7.2令A=1,2,3,F=<1,2>,<1,3>,<2,1>,则F=<2,1>,<3,1>,<1,2>。3.8、 关系的分类定义3.8.1若VXWA都有x,xWR,则R是自反关系。(自己到自己的关系全属于R)定义3.8.2若VXe A都有<x,x>皂R,则R是反自反的。(自己到自己的关系全不属于R)ro

30、o i 0 0 010 0 01 0 0Mw =01。0 0 0ri1oMlo1o1001自反关系RI的关系矩阵Mm的对角线全为L凡关系矩阵的对角线全是】是力反关系.反门反关系R2的关系矩阵M注的对角纹仝为。，凡关系矩阵的刖灯反殳是0的反.自反.而关系R3的美系矩阵的主角线不全是1,也不全是0,故既不是自反的.也不是反自定义3.8.4如果所有形如x,x的序偶都在关系R中，R也只有这种形式的序偶，则称R为恒等关系，记对于恒等关系而言，其关系矩阵是单位矩阵，即其主对角线全是1,其他位置全是0,对关系图是每个点都有自旋，仅只有自旋，没有其他边。定义3.8.5令关系R土AMA,如果当x,yWR时y,x

31、WR,则称R为对称关系。定义3.8.6令关系R=AMA,如果当x,yWR且x#y时y,x正R,则称R为反对称关系定义3.8.8令关系R R,y,z R R时有x,z运R,则称R为可传递关系从R 0R的关系矩阵可知，其非0元素在R的关系矩阵都出现，即 Mr丑E Mr,凡满足这个不等式的关系,肯定为可传递关系。00所以不可传递。从R OR的关系矩阵可知，其非。元素出现在(1,1), (1,3), (2,2), (2,4),在 R的关系矩阵都没出现，不满足 MR R工MR,不可传递关系。1回00tm oI OE-01。00；0;四 Io ,o00 E 0 0U 0 0 00 0 03.9、 关系的闭

32、包由前面的知1R可知，有自反关系,对称关系、可传递关系，对于反自反或既不是自反,也不是反百反的关系，是否适当添加一些序偶,使之变成自反的关系，同时也要使添加的序偶尽可能少.类似对关系进i“投入”.使之发育成对称关系与可传递美系，同时要求“投入”刚刚打.这样得到的自反关系、对称关系.可传递关系称为原美系的门反闭包(记为r(R)h对称闭包(记为8R)、可传递闭包(HR上严格的教学定义如下.定义191SRcAxA,若存在关系R±AxA,满足如下条件则称为门反用包.口阻，是自反关系.RcRI(3)任意R“gAmARH匚R。那么R±R意即次)是包含R的所有白反关系中，序偶最少的一个，

33、定义工9.2设RAmA,若存在美系R，=AxA,满足如下条件则称为对称闭包.是对称关系.(2>RcR'o(3)任意R”gAmA旦RqR那么R£R"*即£国)是包含R前所有对称关系中，序偶最少的一个。定义3,9.3设RuAkA,若存在美系R*qAxA,满足如下条件则称为可传递闭包.(1眼是可传递关系.(2>RcR0)任意父=AkA且R=RJ那么R匕R".即引R)是包含R的所仃可传递关系中.序偶最少的一个.将关系矩阵的主角线上全部变成1,即得到其自反闭包的关系矩阵，从而可得到其自反闭包。3.10、 等价关系与集合的划分定义3.10.1设R

34、三AMA,如果R是自反、对称、可传递的关系则称为等价关系。定义3.10.2设R2AMA,如果R是等价关系，B±A,B中任意二个元素之间都有关系R,则B是一个等价类。定义3.10.3设R2AMA,R是等价关系，A0,A1,.,人是基于R得到的等价类，则称集合A0，A，A为A关于R的商集，记为A/Ro定义3.10.3若入，A，A是A的子集，若i#j时A仆A=，并且A=%UA1U.UA，则称A,A,，Ak是A的一个划分。定理3.10.1设R£AMA,R是等价关系，A0,A,，Ak是利用R得到的k个不同的等价类，则A),A，人为集合A的划分。定理3.10.2设A0,A，是A的划分，

35、R=A0MA0Ua1MAU.UAk_1xAk_1,则R是等价关系。3.11、 偏序关系定义3.11.1设RJAmA,如果R是自反、反对称、可传递的关系则称为偏序关系。如：R是实数中小于等于关系，则R是偏序关系。定义3.11.2设RJAmA,R偏序关系，x与y是A中的元素，若序偶x,y与y,x至少有一个在R中，则称x与y可比。定义3.11.3设R=AMA,R偏序关系，若A中任意二个元素都可比，则称A为全序关系或线序关系。定义3.11.4设R=AmA,R偏序关系，将关系图绘制成所有箭头都朝上，然后去掉所有箭头、去掉自旋边、去掉复合边，得到关系图的简化形式，称为哈斯图。定义3.11.5在哈斯图中，如

36、果某个元素y在元素x的直接上方，则称y盖住了x。记COVA=x,y定义3.11.6设R土AXA,R偏序关系，将偏序关系与集合A一块称为偏序集，记为A,R,表示是A上的偏序关系。以后说偏序关系时，可简单地说偏序集A,R。定义3.11.7在偏序集A,R中，B三A,yWB,若VxWB者B有x,yWR,则称y是最大元。即最大元与B中每个元素都可比，并且都比其大。定义3.11.8在偏序集A,R中，B3A,yWB,若VxwB都有y,xwR,则称y是最小元。即最小元与B中每个元素都可比，并且都比其小。一个子集中没有最大元或最小元时，可能存在极大元或极小元。定义3.11.9在偏序集A,R中，B三A,yWB,若不存在xwB使得y,xwR,则称y是极大元，即B中不存在比y“大”的元素。即极大元与B中有些元素是否可比不做要求。定义3.11.10在偏序集A,R中，BWA,y三B,若不存在xB都有x,yWR,则称y是极小元，不存在比y小的元素。即极小元与B中元素是否可比不做要求。定义3.11.11在偏序集A,R中，B=A,yB,若任意x三B者B有x,yWR,则称y