离散数学知识

1.1.31.1.41.1.5定义1.2.1A是合式公式，则A、(A)A、BAB、AB、AB、AB1.6定义1.6.1设A与C是两个命题公式，AC，则称CA的有效结论，或称A可以逻辑推出C，记为A=>C（用等值演算或真值表）∀：全称量词∃一般情况下，如果个体变元的取值范围不做任何限制即为全总个体域时，带“全称量词”的谓词公式形如R(x)x是兔子，T(x)xH(x,y)xy跑得快，L(x,y)xy一样快，则兔子比乌龟跑得快表示为：∀x∀y(R(x)∧T(y)→H(x,y))定义2.2.1、非逻辑符号：个体常元(如a,b,c)、函数常元(如表示xH(x))

y2的f(x,y))、谓词常元(2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。定义2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。tnA∨BA∧BA→BA↔B合式(4)A合式，则∀xA、∃xA合式(5)有限次使用(2)~(4)得到的式子是合式。定义2.2.6量词辖域：∀xA和∃xA中的量词∀x/∃x的作用范围，A就是作用范围。2.2.7约束变元：在∀x和∃xAx，称为约束变元，这是与量词相关的变元，2.2.8自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一定义2.2.9闭公式是指不含自由变元的谓词公式从本例(已省)可知，不同的公式在同一个解释下，其真值可能存在，也可能不存在，但是对于没有自由变2.2.102.2.112.2.12定义2.2.13

p1,p2pn

A0,A1Ann词公式，用Ai代替公式

piAA为

A(x)∨﹁A(x)，∀xA(x)∨﹁xA(x)p∨p的代换实例，A(x)∧﹁A(x)，∀xA(x)∧∀xp∧p定理2.2.1命题逻辑的永真公式之代换实例是谓词逻辑的永真公式，命题逻辑的永假公式之代换实例是谓词2.3.1A、BAB等值，记为AB。当AB时，根据定义可知，在任何解释下，公式A与公式B的真值都相同，故A↔B为永真式，故得2.3.2A、BABABAB一、利用代换实例可证明的等值式(p↔﹁﹁p永真，代换实例xF(x)↔﹁﹁xF(x)永真

}，则∀xA(x)A(a1)∧A(a2)∧…∧Aan1、﹁∀xA(x)∃x﹁ 2、﹁∃xA(x)∀x﹁1、∀x(A(x)∧B(x)) 2、∃x(A(x)∨B(x))记忆方法：∀与∧，一个尖角朝下、一个尖角朝上，相反可才分配。21式的对偶式A(x)x，Bx1、∀/∃(A(x)∨B) 2、∀/∃(A(x)∧B)A(x)↔BBABCBACDAABA例2.5.1若在各种解释下结论B。

A1

...An

B

定义2.5.2

A1

A1

CPRNZQ表示有理数，C”或“不属于”二种关系。3.1.1A，BABABABAABAB定义3.2.1设A、B为集合，A与BAB、A与BAB、A-B的定义：AB={x|xAxB}，AB={x|xAxB}，A-B={x|xAxB}定义3.2.2设ABA与BAB={x|(xAxB(AxB)}=AB-AB定义3.2.3设A、B是两个集合，若AB、BA则A=B，即两个集合相等。 AA=A、AA=A ABC=A(BC)=(AB)CABC=A(BC)=(AB)C交换 AB=BA、AB=BA A(BC)=(AB)(AC)A(BC)=(AB)(A AØ=A、AØ= AA=E、AA=吸收律(大吃小 A(BA)=A、A(B德摩 (AB)=AB、(AB)=A双重否 3.3.1|

|=|A1|+|A2|-|

A23.4.2令<x,y>与<u,v>x=u、y=v，那么<x,y>=<u,v>即二个序偶相等。定义3.4.3如果<x,y>是序偶，且<<x,y>,z>也是一个序偶，则称<x,y,z>为三元组。定义3.5.1令AB{<x,y>|xA,yB}ABAB则1、A(BCABA2、A(BCABA3、(BC)ABAC4、(BC)ABAC5、ABACBCCAC6、AB,CDACB定义3.5.2

A1,A2,...Annn元组的集合x1,x2,...,xnx1A1,x

An}，为A1,A2,...An的直积或笛卡尔积，记为A1

...An3.6.1R如在直积{1,2,3,4,5,6,7,8}{1,2,3,4,5,6,7,8}1个元素是第2R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<1,8>,<2,2>,<2,4>,<2,6>,<2,8>,3.6.2RR。定义3.7.1若关系FAA，关系GAA，称集合{<x,y>|t使得<x,FGFG3.7.1A={1,2,3}，F={<1,1>,<1,2G={<2,2>,<1,3>,<1,1>}FG<1,3>,<1,1>,<1,2>}，GF={<1,2>,<1,1>}MFi行与MGj列相乘时，乘法是合取，加法是析取，如MF1的第3列相乘是：(11)(10)(00)，结果为1定义3.7.2若关系FAA，称集合{<y,x>|<x,y>F为F的逆，记为F3.7.2A={1,2,3}，F={<1,2>,<1,3>,<2,1>}，则F1<2,1>,<3,1>,<1,2>}定义3.8.1若xA都有<x,x>RR是自反关系。(定义3.8.2若xA都有<x,x>R,则R是反自反的。(3.8.4如果所有形如<x,x>RRR为恒等关系，记为IA。定义3.8.5RAA，如果当<x,y>R时<y,x>R，则称R为对称关系定义3.8.6RAA，如果当<x,y>Rxy时<y,x>R，则称R为反对称关系定义3.8.8RAA，若当<x,y>R,<y,z>R时有<x,z>RR为可传递关系RR0R的关系矩阵都出现，即MR

MRRR0元素出现在(1,1)，(1,3)，(2,2)，(2,4)R阵都没出现，不满足MRRMR1自反闭包3.10.1RAA，如果R是自反、对称、可传递的关系则称为等价关系定义3.10.2RAA，如果RBABR，则B是一个AR的商集A/R3.10.3若A0,A1Ak1A的子集，若i

j时

，并且

则称A0,A1AkA的一个划分定理3.10.1设RAA，RA0,A1Ak1是利用R得到的k个不同的等价类，则A0,A1Ak1A3.10.2设A0,A1Ak1AR

∪Ak1Ak1R3.11.1RAA，如果R是自反、反对称、可传递的关系则称为偏序关系。如：RR是偏序关系。定义3.11.2RAA，R偏序关系，x与yA中的元素，若序偶<x,y>与<y,x>至少有一个在R则称x与y可比定义3.11.3RAA，R偏序关系，若A中任意二个元素都可比，则称A为全序关系或线序关系。3.11.4RAA，R偏序关系，将关系图绘制成所有箭头都朝上，然后去掉所有箭头、去掉自旋边、3.11.5yxy盖住x定义3.11.6RAA，R偏序关系，将偏序关系与集合A一块称为偏序集，记为<A,R>A上3.11.7在偏序集<A,R>中，BA，yB，若xB都有<x,y>Ry是最大元3.11.8在偏序集<A,R>中，BA，yB，若xB都有<y,x>Ry是最小元定义3.11.9在偏序集<A,R>中，BA，yBxB使得<y,x>R，则称y是极大元B中不y“大”的元素。即极大元与B中有些元素是否可比不做要求。3.11.10在偏序集<A,R>中，BA，yBxB都有<x,y>Ry是极小元B定义3.11.11在偏序集<A,R>中，BA，yB，若任意xB都有<x,y>RyB的上界。与B中每个元素都可比，并且都B中的元素大。3.6.1给定集合Aρρ是自反的、对称的ρA定义3.6.3给定非空集合ASS1,S2,...,Sn}Si

i=1,2,…,mSi∩

j)，则称集合SA的3.6.1AS1,S2,...,Sn

Sn3.7.1RARR称为等价关系。(定义3.7.2设给定非空集合A，若有集合SS1,S2,...,Sn}，其中Si

A且Si(i=1,2,…,m)Si∩

mmj)

AS为A(A

拟序关系(反自反的，传