离散数学复习

思维导图

集合论

集合的基本概念

集合的定义

  • 具有某种特定性质事物的全体,通常,用大写的英文字母A,B,C,A, B, C,……表示集合

集合的元素

  • 组成一个集合的那些对象或单元称为这个集合的元素,通常,用小写的英文字母aa,bb,cc,…,或者a1a_1,a2a_2,b1b_1,b2b_2…表示集合中的元素

属于

  • 设A是一个集合,a是集合A中的元素,记以aAa \in A,读作aa属于AA;若aa不是集合AA中的元素,则记以aAa \notin A,读作aa不属于AA

有限集

  • 包含有限个元素的集合,称为有限集或有穷集(finite set)

无限集

  • 包含无限个元素的集合,称为无限集或无穷集(infinite set )

空集

  • 约定,存在一个没有任何元素的集合,称为空集(empty set) ,记为\varnothing,有时也用{}\{\}来表示

全集

  • 约定,所讨论的对象的全体称为全集(universal set),记作EEUU,我们所讨论的集合都是全集的子集

  • 全集是相对的

集合的元素数

  • AA是有穷集合,AA中元素的个数称为集合AA的元素数,记为A|A|特别,=0|\varnothing|=0

集合的表示法

列举法

  • 将集合中的元素一一列举,或列出足够多的元素以反映集合中元素的特征

描述法

  • 通过描述集合中元素的共同特征来表示集合

文氏图

  • 用一个大的矩形表示全集,在矩形内画一些圆或其它的几何图形,来表示集合,有时也用一些点来表示集合中的特定元素

集合的特征

确定性

  • 任何一个对象,或者是这个集合的元素,或者不是,二者必居其一

互异性

  • 集合中任何两个元素都是不同的,即集合中不允许出现重复的元素

无序性

  • 集合与其中的元素的顺序无关

多样性*

  • 集合中的元素可以是任意的对象,相互独立,不要求一定要具备明显的共同特征

集合间的关系

集合相等

  • 当两个集合AABB的元素完全一样,即AABB实际上是同一个集合时,则称集合AABB相等,记以A=BA=B

集合包含

子集

  • AABB是两个集合,若AA的元素都是BB的元素,则称AABB的子集(subset) ,也称BB包含AA,或AA包含于BB,记以ABA \subseteq B,或BAB \supseteq A

真子集

  • ABA \subseteq B,且ABA \neq B,则称AABB的真子集(proper subset),也称BB真包含AA,或AA真包含于BB,记以ABA \subset B,或BAB \supset A

重要结论

  • 对任意集合AA, 有AAA ⊆ A
  • \varnothing是任意集合的子集,且空集是唯一的
  • 对于任意两个集合AABBA=BA=B当且仅当ABA⊆BBAB⊆ A

幂集

定义

  • AA是集合,AA的所有子集为元素组成的集合称为AA的幂集,记以ρ(A)ρ(A)2A2^Aρ(A)={SSA}ρ(A)=\{S|S ⊆ A\}

性质

  • 若A为有穷集,A=n|A|=n,则2A=ρ(A)=Cn0+Cn1++Cnn=2n|2^A | = |ρ(A)|= C_n^0 + C_n^1 + … + C_n^n =2^n
  • xρ(A)x∈ρ(A)当且仅当xAx⊆A
  • AABB是两个集合,ABA⊆B当且仅当ρ(A)ρ(B)ρ(A)⊆ρ(B)

集合运算

集合的并集

  • AABB是两个集合。所有属于AA或者属于BB的元素组成的集合,称为AABB的并集,记以ABA∪B。即AB={xxAxB}A∪B=\{x|x∈A或x∈B\}

集合的交集

  • AABB是两个集合。由属于AA又属于BB的元素组成的集合,称为AABB的交集,记以ABA∩B。即AB={xxAxB}A∩B=\{x|x∈A且x∈B\}

并集和交集的推广

  • A1A_1A2A_2,…,AnA_nnn个集合,则:A1A2AnA_1∪A_2∪…∪A_n,简记为i=1nAi\bigcup\limits_{i=1}^nA_i

  • A1A2AnA_1∩A_2∩…∩A_n,简记为i=1nAi\bigcap\limits_{i=1}^n A_i

集合的补集

  • AA是一个集合,全集EEAA的差集称为AA的补集,记以A\sim A,即A=EA\sim A=E-A

  • 特别, =E\sim \varnothing=EE=\sim E= \varnothing

集合的差集

  • AABB是两个集合。由属于集合AA而不属于集合BB的所有元素组成的集合,称为AABB的差集,记以ABA-B。即AB={xxAxB}A-B=\{x|x∈A且x ∉B\}

集合的对称差

  • AABB是两个集合。则AABB的和(对称差),记以ABA⊕B, 定义为AB=(AB)(BA)A⊕B=(A-B)∪(B-A),即AB={x(xA)(xB)(xB)(xA)}A \oplus B=\{x|(x \in A)且(x \notin B)或(x \in B)且(x \notin A)\}
  • AABB的对称差还有一个等价的定义,即AB=(AB)(AB)A⊕B=(A∪B)-(A∩B)

集合的运算律

等幂律

  • AA=AA∩A=A
  • AA=AA∪A=A

交换律

  • AB=BAA∩B=B∩A
  • AB=BAA∪B=B∪A

结合律

  • (AB)C=A(BC)(A∩B)∩C=A∩(B∩C)
  • (AB)C=A(BC)(A∪B)∪C=A∪(B∪C)

分配律

  • A(BC)=(AB)(AC)A∩(B∪C)=(A∩B)∪(A∩C)
  • A(BC)=(AB)(AC)A∪(B∩C)=(A∪B)∩(A∪C)

吸收律

  • A(AB)=AA∩(A∪B)=A
  • A(AB)=AA∪(A∩B)=A

互补律

  • AA=\sim A∩A= \varnothing
  • AA=E\sim A∪A=E

德摩根律

  • (AB)=AB\sim (A∩B)=\sim A ∪ \sim B
  • (AB)=AB\sim(A∪B)=\sim A ∩ \sim B

同一律

  • EA=AE∩A=A
  • A=A\varnothing ∪A=A

零一律

  • A=\varnothing∩A=\varnothing

  • EA=EE∪A=E

双重否定律

  • (A)=A\sim (\sim A)=A

其他算律

  • AB=ABA-B=A∩ \sim B
  • AB=(AB)(BA)=(AB)(AB)A⊕B=(A-B)∪(B-A)=(A∪B)-(A∩B)
  • AA=A⊕A=\varnothing
  • =E\sim\varnothing=E
  • E=\sim E=\varnothing

有限集合的计数

容斥原理

  • AB=A+BAB|A∪B|=|A|+|B|-|A∩B|
  • ABC=A+B+CABACBC+ABC|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
  • A1A2AnA_1,A_2,…,A_nnn个集合,则:i=1nAi=i=1nAii<jnAiAj+i<j<knAiAjAk+...+(1)n1A1A2A3...An|\bigcup\limits_{i=1}^n A_i|=\sum\limits_{i=1}^n|A_i|-\sum\limits_{i<j}^n|A_i\cap A_j|+\sum\limits_{i<j<k}^n|A_i\cap A_j \cap A_k|+...+(-1)^{n-1}|A_1 \cap A_2 \cap A_3 \cap ...\cap A_n|称为包含排斥原理,简称容斥原理

集合恒等式的证明

基本定义法

公式等价法

基本原则

  • 将集合运算表达式中其他运算符号转换为∩和∪;
  • 将补运算作用到单一集合上;
  •     \implies右,右    \implies左,左    \implies中间式,右    \implies中间式;
  • 根据基本运算符号的定义和运算定律转换。

集合成员表法*

关系

序偶和笛卡尔积

序偶

定义

  • 对于有序nn元组,当n=2n=2时,我们将其称作有序二元组,也称作有序对,或序偶。

特点

  • aba≠b,则(a,b)(b,a)(a,b)≠(b,a)
  • 两个有序对(a,b)(a,b)(c,d)(c,d)相等当且仅当a=ca=cb=db=d

特征

  • 成对出现、具有一定的顺序

笛卡尔积

定义

  • AABB是两个集合,所有有序对(x,y)(x, y)做成的集合(其中xAyB)(其中x∈A,y∈B),称为AABB的笛卡儿积,记为A×BA×BA×B={(xy)xAyB}A×B=\{(x,y)|x∈A且y∈B\}
  • A1,A2,...,AnA_1,A_2 , ...,A_nnn个集合,由所有有序nn元组(a1,a2,,ana_1,a_2,…,a_n)组成的集合(其中aiAii=1,2,,n)(其中ai∈A_i,i=1,2, … ,n),称为A1,A2,...,AnA_1,A_2,...,A_n的笛卡儿积,记以A1×A2×...×AnA_1×A_2 ×...×A_nA1×A2×...×An={(a1,a2,,an)aiAii=1,2,,n}A_1×A_2 ×...×A_n=\{(a_1,a_2 ,… ,a_n) | a_i∈A_i,i=1,2, … ,n \}

性质

  • A×B=A×B|A×B|=|A|× |B|

  • 对任意集合AA,有A×=A×\varnothing=\varnothing×A=\varnothing \times A=\varnothing

  • 笛卡儿积运算不满足交换律,即A×BB×AA×B≠B×A

  • 笛卡儿积运算不满足结合律,即(A×B)×CA×(B×C)(A×B)×C≠A×(B×C)

  • 笛卡儿积运算对并和交运算满足分配律, 即

    • A×(BC)=(A×B)(A×C)A×(B∪C)=(A×B)∪(A×C)
    • (BC)×A=(B×A)(C×A)(B∪C)×A=(B×A)∪(C×A)
    • A×(BC)=(A×B)(A×C)A×(B∩C)=(A×B)∩(A×C)
    • (BC)×A=(B×A)(C×A)(B∩C)×A=(B×A)∩(C×A)
  • AABBCCDD是集合,若ACA⊆CBDB⊆D,则A×BC×DA×B ⊆ C×D

二元关系

定义

  • 给定任意集合AABB,若RA×BR⊆A×B,则称RR为从AABB的二元关系,特别在A=BA=B时,称RRAA上的二元关系

补充

  • 关系是一个集合,是序偶的集合
  • RR是有序对的集合。若(x,y)R(x,y)∈R,则也表示为xRyx R y,即(x,y)R    xRy(x,y)∈ R \iff x R y
    • R=R =\varnothing,则称RRAABB空关系
    • R=A×BR =A×B,称RRAABB全域关系
    • R={(x,x)xA}R=\{(x,x)|x∈A\}AA上的恒等关系,记为IAI_A
  • 当集合A,BA,B都是有限集时,A×BA×B共有2AB2^{|A|\cdot|B|}个不同的子集,
    即从AABB的不同关系共有2AB2^{|A|\cdot|B|}

定义域、值域和域

定义

  • RA×BR \subseteq A \times B,且
    {D(R)={x(y)(xRy)}R(R)={y(x)(xRy)}F(R)=D(R)R(R)\begin{cases} D (R) = \{ x | (∃y) (x R y ) \}\\R (R) = \{ y | (∃x) (x R y ) \}\\F(R) = D(R)∪R(R)\end{cases}则称D(R)D(R)R(R)R(R)F(R)F(R)分别是二元关系RR的定义域、值域和域,显然D(R)AD(R) ⊆ AR(R)BR(R) ⊆ B

关系矩阵与关系图

关系矩阵

  • 给定集合A={a1,a2,,am}A=\{a_1,a_2,···,a_m \}B={b1,b2,,bn}B=\{b_1,b_2,···,b_n \},且RA×BR⊆A×B,若rij={1,aiRbj0,否则r_{ij}=\begin{cases} 1 ,& {a_i R b_j}\\0 ,& 否则 \end{cases}
    则称矩阵MR=(rij)M_R=(r _{i j})RR的关系矩阵

关系图

  • 给定集合A={a1,a2,,am}A=\{a_1,a_2,···,a_m \}AA上的关系RR,且RA×AR⊆A×A,若:以AA中的元素为结点;对RR中的元素(ai,aj)(a_i ,a_j ), 以aia_i为起点,以aja_j为终点,作有向边所构成的图,则称该图为RR的关系图

关系运算

关系的并、交、补、差

  • 关系是序偶(有序对)的集合,因此可以对关系进行运算。
    R,SA×BR, S⊆A×B,则RSR∪SRSR ∩SR\sim RRSA×BR-S⊆A×B

关系的复合

定义

  • RR是从集合XXYY的关系,SS是从YYZZ的关系,把XXZZ的关系定义为RSR\circ S。称RSR\circ S是关系RRSS的合成关系或复合关系,RS={(x,z)xX,zZ,至少存在一个yY(x,y)R(y,z)S}R\circ S=\{(x,z)|∃x∈X, ∃z∈Z, 至少存在一个y∈Y有(x , y)∈R且(y , z)∈S\}

定理

  • 已知集合X,Y,Z,WX,Y,Z,W,关系R1,R2,R3,R4R_1,R_2,R_3,R_4如下XR1YR2R3ZR4WX\stackrel {R_1}\longrightarrow Y \stackrel {R_2R_3}\longrightarrow Z \stackrel {R_4}\longrightarrow W,则有:

    • 𝑅1(𝑅2𝑅3)=(𝑅1𝑅2)(𝑅1𝑅3)𝑅_1∘(𝑅_2∪𝑅_3)=(𝑅_1∘𝑅_2)∪(𝑅_ 1∘𝑅_3)
    • R1(R2R3)(R1R2)(R1R3)R_1∘(R_2∩R_3)⊆(R_1∘R_2)∩(R_1∘R_3)
    • (𝑅2𝑅3)𝑅4=(𝑅2𝑅4)(𝑅3𝑅4)(𝑅_2∪𝑅_3)∘𝑅_4=(𝑅_2∘𝑅_4)∪(𝑅_3∘𝑅_4)
    • (𝑅2𝑅3)𝑅4(𝑅2𝑅4)(𝑅3𝑅4)(𝑅_2∩𝑅_3)∘𝑅_4⊆(𝑅_2∘𝑅_4)∩(𝑅_3∘𝑅_4)
  • 已知集合X,Y,Z,WX, Y, Z, W,关系R1,R2,R3R_1, R_2, R_3如下XR1YR2ZR3WX\stackrel {R_1}\longrightarrow Y \stackrel {R_2}\longrightarrow Z \stackrel {R_3}\longrightarrow W,则有:(R1R2)R3=R1(R2R3)(R_1 \circ R_2)\circ R_3=R_1\circ (R_2 \circ R_3) 结合律

  • RRRR=R(n)R\circ R\circ R \circ\dots\circ R=R^{(n)}

  • R(0)=IX={(x,x)xX}R^{(0)}=I_X=\{(x,x)|x\in X\}

逆关系

定义

  • RA×BR⊆A×B,则关系R={(y,x)(x,y)R}\overline R =\{(y,x)|(x,y)∈ R\}
    是集合BBAA的关系,R\overline R称为关系RR的逆关系

定理

  • R1,R2,RR_1, R_2, RXXYY的二元关系,则

    • R1R2=R1R2\overline{R_1∪ R_2} =\overline{R_1} ∪\overline{R_2}

    • R1R2=R1R2\overline{R_1 \cap R_2}=\overline {R_1} \cap \overline {R_2}

    • X×Y=Y×X\overline{X \times Y} = Y \times X

    • R=R\overline{\sim R}=\sim \overline{R}

    • R1R2=R1R2\overline{R_1-R_2}=\overline{R_1}-\overline{R_2}

    • SR    SRS \subseteq R \iff \overline{S}\subseteq\overline{R}

  • 已知集合X,Y,ZX, Y, Z,关系R,SR, S如下,XRYSZX \stackrel {R}\longrightarrow Y \stackrel {S}\longrightarrow Z,则有:RS=SR\overline{R\circ S}=\overline{S}\circ\overline{R}

注意

  • RR的关系矩阵转置即得R\overline R的关系矩阵,即RRR\overline R的关系矩阵互为转置矩阵
  • R\overline R的前域与后域正好是RR的后域和前域,即domR=ranRdomR=ran\overline RdomR=ranRdom\overline R=ranR
  • R=R|R|=|\overline R|

关系性质

自反性

  • RA×AR⊆A×A,若对AA中每个xx,都有xRxxRx,则称RR是自反的,即A上关系R是自反的    x(xAxRx)A上关系R是自反的\iff∀x(x∈A→xRx)
  • 该定义表明了,在自反的关系RR中,除其他有序对外,必须包括由每个xAx∈A所组成的元素相同的有序对

反自反性

  • RA×AR⊆A×A,若对于AA中每个xx,有(x,x)R(x,x) ∉R,则称RR是反自反的,即A上关系R是反自反的    x(xA(x,x)R)A上关系R是反自反的\iff∀x (x∈A→(x,x) ∉R)
  • 该定义表明了,一个反自反的关系RR中,不应包括有任何相同元素的有序对
  • 应该指出,任何一个不是自反的关系,未必是反自反的;反之,任何一个不是反自反的关系,未必是自反的。这就是说,存在既不是自反的也不是反自反的二元关系

对称性

  • RA×AR⊆A×A,对于AA中每个xxyy,若xRyxRy,则yRxyRx,称RR是对称的,即A上关系R是对称的    (x)(y)(x,yAxRyyRx)在A上关系R是对称的\iff(∀x)(∀y)(x,y∈A且xRy→yRx)
  • 该定义表明了,在表示对称的关系RR的有序对集合中,若有有序对(x,y)(x, y),则必定还会有有序对(y,x)(y, x)

反对称性

  • RA×AR⊆A×A,对于AA中每个xxyy,若xRyxRyyRxyRx,则x=yx=y,称RR是反对称的,即A上关系R是反对称的    (x)(y)(x,yAxRyyRxx=y)A上关系R是反对称的 \iff (∀x)(∀y)(x,y∈A且xRy且yRx→x=y)
  • 该定义表明了,在表示反对称关系RR的有序对集合中,若存在有序对(x,y)(x, y)(y,x)(y, x),则必定是x=yx=y。或者说,在RR中若有有序对(x,y)(x, y),则除非x=yx=y,否则必定不会出现(y,x)(y, x)

传递性

  • RA×AR⊆A×A,对于AA中每个x,y,zx, y, z,若xRyyRzxRy且yRz,则xRzxRz,称RR是传递的,即A上关系R是传递的    (x)(y)(z)(x,y,zAxRyyRzxRz)A上关系R是传递的 \iff (∀x)(∀y)(∀z)(x,y,z∈A且xRy且yRz→xRz)
  • 该定义表明了,在表示可传递关系RR的有序对集合中,若有有序对(x,y)(x, y)(y,z)(y, z),则必有有序对(x,z)(x, z)

结论

  • 关系RR是自反的    \implies RR不是反自反的
  • 关系RR是自反的    \iff关系图中每个结点都有环
  • 关系RR是反自反的    \iff关系图中每个结点都无环
  • 关系RR是自反的    \iff关系矩阵的主对角线上全为1
  • 关系RR是反自反的    \iff关系矩阵的主对角线上全为0
  • 关系RR是对称的    \iff关系图中任何一对结点之间,要么有方向相反的两条边,要么无任何边
  • 关系RR是反对称的    \iff关系图中任何一对结点之间,至多有一条边
  • 关系RR是对称的    \iff RR的关系矩阵为对称矩阵
  • 关系RR是反对称的    \iff RR的关系系矩阵满足rijrji0i,j=1,2,,nijr_{ij}\cdot r_{ji}=0,i,j=1,2,…,n,i≠j
  • 非空集合上的空关系是反自反的,对称的,反对称的和传递的,但不是自反的。空集合上的空关系则是自反的,反自反的,对称的,反对称的和传递的
  • 非空集合上的全域关系是自反的,对称的和传递的,但不是反自反的和反对称的
  • RA×AR⊆A×A,若RR是反自反的和传递的,则RR是反对称的

闭包运算

自反闭包

  • RRAA上的二元关系,若RR'RR的自反闭包,记作r(R)r(R),则:
    • RR'是自反的
    • RRR⊆R'
    • 对任意的自反关系RR''RRR⊆R'',则必有RRR'⊆R''

对称闭包

  • RRAA上的二元关系,若RR'RR的对称闭包,记作s(R)s(R),则:
    • RR'是对称的
    • RRR⊆R'
    • 对任意的对称关系RR''RRR⊆R'',则必有RRR'⊆R''

传递闭包

  • RRAA上的二元关系,若RR'RR的传递闭包,记作t(R)t(R),则:

    • RR'是传递的
    • RRR⊆R'
    • 对任意的传递关系RR''RRR⊆R'',则必有RRR'⊆R''

定理

  • R是 X 上的二元关系,则:
    • r(R)=R{(x,x)xX}=RIxr(R)=R∪\{(x,x)|x∈X\}=R∪I_x
    • s(R)=RRs(R) = R∪ \overline{R}
    • t(R)=RR(2)R(3)...R(n)t(R)=R∪ R^{(2)}∪ R^{(3)}...∪ R^{(n)}nn为集合XX的元素的个数
    • RR是自反的    \iff r(R)r(R)
    • RR是对称的    \iff s(R)=Rs(R)=R
    • RR是传递的    \iff t(R)t(R)

等价关系

定义

  • RR是集合XX上的二元关系,如果RR是自反的、对称的、传递的,那么称RR是等价关系

划分

  • 设集合A={S1,S2,,Sm}A=\{S_1, S_2 , …, S_m\},SiS_iSS的非空子集, 如果称AASS的一个划分,称SiS_i为划分的块,则:
    • SiS_i之间是不相交的
    • S1S2Sm=SS_1∪S_2∪…∪S_m = S

等价类

定义

  • RR是集合SS上的等价关系, 对任一xSx\in S,均可构造一个SS的非空子集[x]R={yySxRy}[x]_R= \{ y | y\in S 且 xRy \},也可记为[x][x],叫做xx关于RR的等价类:

性质

  • x[x]x\in[x]
  • y[x]y\in[x], 则[y]=[x][y]=[x]
  • y[x]y\in[x], 则[y][x]=[y]∩[x]=\varnothing

定理

  • 集合SS上的一个等价关系RR生成的等价类集合对应SS的一个划分
  • 集合SS上的一个等价关系RR生成的等价类集合对应SS的一个划分。此划分称为集合SS关于RR的商集,记为S/RS/R
  • 集合SS上的一个划分可产生SS上的一个等价关系

偏序关系

定义

  • RR是集合AA中的二元关系,如果RR是自反的、反对称的和可传递的,则称RRAA中的偏序关系。
  • 通常用符号“”来标记偏序关系RR

偏序集

  • 在偏序集合(A,)(A ,≼ )中,如果有元素x,yAx,y∈A,且xyx≼ y(或者写为(x,y)(x,y)∈≼)和xyx≠y,同时不存在其它任何元素zAz∈A,能使xzx≼ zzyz≼ y,则称元素yy盖住xx,若元素yy盖住xx,则可以将x,yx,y间的关系用图形表示,即:哈斯图

哈斯图

  • 用小圆圈表示AA中的元素
  • xyx≼yxyx≠y, 则xxyy的下方
  • xyx≼yxyx≠y, 并且AA中不存在另外的元素zz, 满足xzx≼z,zyz≼y, 则在xxyy之间画一直线

拟序关系

  • RR是集合AA中的反自反和传递的二元关系,则称RRAA中的拟序关系 (“”)

全序和全序集

  • AA中的偏序关系,若对任意的x,yAx,y∈A,必有xyx ≼ yyxy ≼ x,即xxyy可比较,则称AA中的线性次序关系或全序关系,又称全序或线性序。相应的偏序集(A,)(A,≼)称为线性序集或全序集
  • 显然,任一全序集也是偏序集,其哈斯图为一条链,
    但是任一偏序集不一定是全序集合

最大(小)元素

  • (X,)( X, ≼ )是偏序集,YYXX的子集。若存在元素yYy∈ Y,对于每一个yYy’ ∈ Y
    • 若有yyy’ ≼ y,则称yy是集合YY的最大元素
    • 若有yyy ≼y’,则称yy是集合YY的最小元素

性质

  • (X,)( X, ≼ )是偏序集,YYXX的子集,如果YY有最大(最小)元素,则必定是唯一的

极大(小)元素

  • (X,)( X, ≼)是偏序集,YYXX的子集,若yYy ∈ Y,且不存在yYy’ ∈ Yyyy≠ y’
    • 若有yyy ≼ y’,则称yyYY的极大元素
    • 若有yyy’ ≼ y,则称yyYY的极小元素

上(下)界

  • (X,)( X, ≼ )是偏序集,YXY\subseteq X,若xXx ∈ X,使得对任意yYy’ ∈ Y,
    • 若有yxy’≼x,则称xxYY的上界
    • 若有xyx ≼ y’,则称xxYY的下界

上(下)确界

  • (X,)( X, ≼ )是偏序集,YYXX的子集。
    • xxYY的上界,若对YY的任一上界xx’,都有xxx ≼x’,则称xxYY的上确界,记作LUBLUB YY
    • xxYY的下界,若对于YY的任一下界xx’,均有xxx’ ≼x,则称xxYY的下确界,记作GLBGLB YY

函数

函数及其分类

函数的定义

  • ff是集合AABB的关系
    若称ff是集合AABB的函数或映射,记作f:ABf: A→BABA → B
    (a,b)f(a,b)∈f时,通常记为b=f(a)b=f(a)bb称为aaff下的像,称aabb的原像。则ff满足下列两个条件:
    • 对每个aAa∈A,必存在bBb∈B,使得(a,b)f(a,b)∈f——存在性条件
    • 对每个aAa∈A,只存在一个bBb∈B,使得(a,b)f(a,b)∈f——唯一性条件
  • 即:值域为函数的像集合

函数相等

  • f:XYf:X→Yg:ZWg:Z→W,如果ffgg具有相同的定义域和值域,即X=ZX=ZY=WY=W,并且对于所有的xXx∈XxZx∈Z,都有f(x)=g(x)f(x)=g(x),则称函数ffgg相等,并记作f=gf=g

函数个数

  • AABB是非空有限集合,则从AABB共有BA|B|^{|A|} 个不同的函数
  • 因为函数是一种特殊的关系,所以一个函数确定一个关系;但一个关系不一定确定一个函数

函数的分类

  • f:ABf: A→B是一个函数:
    • 对任意的a1a_1a2Aa_2∈A,若a1a2a_1≠a_2,均有f(a1)f(a2)f(a_1)≠f(a_2),则称ffAABB单射函数一对一函数;否则,称ffAABB多对一函数
    • 如果对任意的bBb∈B,均有aAa∈A,使b=f(a)b=f(a),即Cf=BC_f=B,则ffAABB满射函数;否则,称ffAABB内射函数
    • 如果ff既是AABB单射,又是AABB满射,则称ffAABB双射函数一一对应函数。特殊地,在一一对应函数f:ABf: A→B中,若A=BA=B,则此函数叫做AA的变换。

函数分类结论

  • 设A,B为有限集合,f是从A到B的函数,则:
    • ff是单射的必要条件为AB|A|≤|B|
    • ff是满射的必要条件为BA|B|≤|A|
    • ff是双射的必要条件为AB|A|=|B|

特殊函数

  • ff是一个函数,若对任意的aAa∈A,均有f(a)=bf(a)=bbBb∈B,则称ff是从AABB常值函数常函数
  • ff是一个函数,若对任意的aAa∈A,均有f(a)=af(a)=a,则称ffAA上的恒等函数
  • f:RRf:R→R是一个函数,其中RR为实数集,
    • 对任意a,bRa,b∈R,若a<ba<b,必有f(a)f(b)f(a)≤f(b),则称ff为单调递增函数
    • 对任意a,bRa,b∈R,若a<ba<b,必有f(a)<f(b)f(a)<f(b),则称ff为严格单调递增函数
  • UU是全集,且AUA⊆U,函数ΨA:U{0,1}\Psi _A:U\to \{0,1\}定义为: ΨA={1,aA0,aA\Psi_A=\begin{cases} 1,& a \in A\\ 0,& a \notin A \end{cases} 则称ΨA\Psi_A是集合AA的特征函数

复合函数与逆函数

复合函数

复合函数定义

  • 函数的合成运算可定义如下:设f:XYf : X→Y, g:YZg : Y→Z是两个函数,于是合成函数记为gf:XZg\circ f : X→Z
    gf={(x,z)xXzZ且存在yYy=f(x)z=g(y)}\\g\circ f=\{(x,z)|x∈X且z∈Z且存在y∈Y且y=f(x)且z=g(y)\} 通常称为函数ffgg的合成,确切的说,gfg\circ f称为ffgg左合成,从ffgg求得gfg\circ f的运算“\circ”称为左合成运算
    关系的合成运算为fgf\circ g,函数的合成运算为gfg\circ f

复合函数定理

  • 函数的合成运算是可结合的
  • ffgg是函数,并且有合成函数gfg\circ f,则
    • 如果ffgg都是满射函数,则gfg \circ f也是满射函数
    • 如果ffgg都是单射函数,则gfg\circ f也是单射函数
    • 如果ffgg都是双射函数,则gfg\circ f也是双射函数

逆函数

逆函数定义

  • f:ABf : A→B是一个双射函数 , 称f1:BAf^{-1} : B→Aff的逆函数
  • 在关系部分,曾定义了从集合XXYY的关系RR的逆关系,但是对于函数来说,交换序偶中的成员次序并不一定能保证得到的仍然是个函数
  • f:ABf:A→B是一一对应的函数,则ff的逆关系 称为它的逆函数,记成f1:BAf^{-1}: B→A。这时称函数ff是可逆的

逆函数的定理

  • 函数f:ABf : A→B,若存在逆函数f1:BAf^{-1} : B→A,则必须满足:
    • 对任意的aAa∈A,必有唯一的bBb∈B与之对应;
    • 对任意的bBb∈B,必有唯一的aAa∈A与之对应;

代数系统

代数系统的基本概念

二元运算

定义

  • A,B,CA, B, C是非空集合,从A×BA×BCC的一个函数fA×BCf :A×B→C称为一个A×BA×BCC的二元代数运算,简称二元运算
  • 一个二元运算就是一个特殊的函数 ,该函数能够对aAa\in AbBb\in B进行运算,得到CC中的一个元素cc , 即 (a,b)c\circ (a, b)=c
    中缀方法表示为:abca \circ b=c

特点

封闭性

  • 如果“*”是A×AA×AAA的二元运算,则称运算“*”对集合AA是封闭的,或者称“*”是AA上的二元运算
  • 设“*”是一个A1×A2××AnA_1×A_2×…×A_nAAnn元代数运算,如果A1A2AnAA_1=A_2=…=A_n=A,则称代数运算“*”对集合AA是封闭的,或者称“*”是AA上的nn元代数运算

代数系统的定义

  • AA是非空集合,*是定义在AAkk元封闭运算,称集合AA*所组成的系统称为代数系统,简称代数,记为(A,)(A, *)
  • AA是有限集合时,该代数系统称为有限代数系统,否则称为无限代数系统
  • 注意:判断集合AA和其上的代数运算是否是代数系统,关键是判断两点:
    • 集合AA非空
    • 这些运算关于AA是否满足封闭性

同类型代数系统

  • (A,)(A, *)(B,)(B, \circ )是两个代数系统,若“\circ”和“*”都是kk元运算,i=1,2,,mi = 1, 2, …, m,则称这两个代数同类型

运算规律

结合律

  • (A,)(A, *)是二元代数系统,若对任意a,b,cAa, b, c∈A,都有
    (ab)ca(bc)(a*b)*c=a*(b*c)
    则称“*”在AA上是可结合的,或称满足结合律

交换律

  • (A,)(A, *)是二元代数系统,若对任意a,bAa, b∈A,都有
    abbaa*b=b*a
    则称“*”在AA上是可交换的,或称“*”满足交换律

消去律

  • (A,)(A, *)是二元代数系统,元素aAa∈A
    • 对任意x,yAx, y∈A,都有如果ax=aya*x = a*y,那x=yx = y,则称aaAA中关于“*”是左可消去元
    • 对任意x,yAx, y∈A,都有如果xa=yax*a = y*a,那么x=yx = y,则称aaAA中关于“*”是右可消去元
    • 如果aa既是AA左可消去元又是右可消去元,则称aaAA的可消去元
    • AA中所有元素都是可消去元,则称“*”在AA上可消去,或称“*”满足消去律

幂等律

  • (A,)(A, *)是二元代数系统,若元素aAa∈A,满足aa=aa*a=a则称aaAA中关于“*”的一个幂等元,简称aa为幂等元。若AA中的每一个元素都是幂等元,则称“*”在AA中是幂等的,或称“*”满足幂等律

  • 设“*”是集合AA上可结合的二元运算,aAa∈A,则aaAaaaAa*a∈A,a*a*a∈A,…,由此,可以归纳定义aa的正整数幂方:
    a1=aa2=aaa3=a2aan=an1aa^1 = a,a^2 = a*a,a^3 = a^2*a,… , a^n = a^{n-1}*a,…
  • 对任意正整数nnmm,有以下等式:anam=an+m(an)m=anma^n * a^m = a^{n+m}, (a^n)^m = a^{nm}

分配律

  • 设“*”、“\circ”是集合A上的二元运算,(A,,)(A,*, \circ)是一个代数系统, 对任意a,b,cAa,b,c\in A
    • a(bc)=(ab)(ac)a\circ (b*c)=(a\circ b)*(a\circ c)
      则称运算“\circ”对“*”在AA上满足左分配律(或第一分配律)
    • (bc)a=(ba)(ca)(b*c) \circ a=(b\circ a)*(c\circ a)
      则称运算“\circ”对“*”在AA上满足右分配律(或第二分配律)
    • 如果“\circ”对“*”既满足左分配律又满足右分配律,则称“\circ”对“*”在AA上满足分配律

吸收律

  • 设“*”、“\circ”是集合AA上的二元运算,(A,,)(A,*, \circ )是一个代数系统,如果对任意x,yAx, y∈A,都有x(xy)=xx(xy)=xx *(x \circ y) = x,x \circ(x*y) = x
    则称“*”和“\circ”满足吸收律

特殊元

特殊元的定义

  • 在代数系统中,有些元素有特殊性质,叫特殊元

单位元

  • (A,)(A, *)是二元代数系统,
    • 若存在eAe∈A,对任意aAa∈A,都有 ae=ea=aa *e = e* a = a,则称eeAA中关于运算“*”的一个单位元
    • 若存在elAe_l∈A,使得对任意aAa∈A,都有 ela=ae_l *a = a,则称ele_lAA中关于运算“*”的一个左单位元
    • 若存在erAe_r∈A,使得对任意aAa∈A,都有 aer=aa *e_r = a,则称ere_rAA中关于运算“*”的一个右单位元

零元

  • (A,)(A, *)是一个二元代数系统,
    • 若存在θAθ∈A,使得对任意aAa∈A,都有aθ=θa=θa *θ = θ* a =θ,则称θθAA中关于运算“*”的一个零元
    • 若存在θlAθ_l∈A,使得对任意aAa∈A,都有θla=θlθ_l *a = θ_l,则称θlθ_lAA中关于运算“*”的一个左零元
    • 若存在θrAθ_r∈A,使得对任意aAa∈A,都有aθr=θra *θ_r = θ_r,则称θrθ_rAA中关于运算“*”的一个右零元。

逆元

  • (A,)(A, *)是二元代数系统,ee是幺元,aAa∈A,若存在一个元素bAb∈A
    • 使得:ab=ba=ea *b = b* a = e,则称aa可逆,并称bbaa的一个逆元,记为a1a^{-1}
    • 使得:ba=eb*a = e,则称aa左可逆,并称bbaa的一个左逆元,记为al1a_l^{-1}
    • 使得:ab=ea*b = e,则称aa右可逆,并称bbaa的一个右逆元,记为ar1a_r^{-1}

定理

  • (A,)(A, *)是一个代数系统,“*” 满足结合律,aAa∈Aaa可逆,则aa是可消去元
  • (A,)(A, *)是二元代数系统,
    • 如果(A,)(A, *)存在单位元,则单位元唯一
    • 如果(A,)(A, *)存在单位元,则该单位元一定是左、右单位元
    • 如果(A,)(A, *)存在左、右单位元,则该左、右单位元相等,且是单位元。
  • (A,)(A, *)是二元代数系统,
    • 如果(A,)(A, *)存在零元,则零元唯一
    • 如果(A,)(A, *)存在零元,则该零元一定是左、右零元
    • 如果(A,)(A, *)存在左、右零元,则该左、右零元相等,且是零元。
  • (A,)(A, *)是二元代数系统,“*”满足结合律且设ee是单位元,则对任意aAa∈A
    • 如果aa存在逆元,则逆元唯一
    • 如果aa存在逆元,则该逆元一定是左、右逆元
    • 如果aa存在左、右逆元,则该左、右逆元相等,且是逆元。
  • (A,)(A, *)是二元代数系统,“*”满足结合律,a,bAa, b∈A
    • 如果a,ba, b分别有逆元a1,b1a^{-1}, b^{-1},则(ab)1=b1a1(a*b)^{-1} = b^{-1}*a^{-1}
    • 如果aa是左(或右)可逆的元素,则aa是左(或右)可消去的元素
    • 如果aa是可逆的元素,则aa是可消去的元素

同构

同构的定义

  • 在现实社会中,存在着很多代数系统,但仔细分析这些众多的代数系统发现,有些代数系统,他们之间表面上似乎不相同,但他们本质上是“相同”的

同构的条件

  • 必须是同型代数系统
  • 两个集合的元素个数应相等
  • 运算定义法则相同,即对应元素运算后的结果也对应

同态

同态的定义

  • (A,)(A, *)(B,)(B, \circ)为两个二元代数系统,ggAABB的函数。对任意x,yAx, y∈A,都有g(xy)=g(x)g(y)g(x*y) = g(x) \circ g(y),则称gg是从(A,)(A, *)(B,)(B, \circ)同态映射,称g(A)g(A)同态像,其中g(A)={g(x)xA}g(A) = \{g(x) | x∈A\}。如果存在一个从(A,)(A,*)(B,)(B, \circ )的同态映射,则称(A,)(A, *)(B,)(B, \circ )同态,记为(A,)(B,)(A,*)∽(B, \circ )。当(A,)=(B,)(A, *)= (B, \circ )时,称其同态为自同态
  • 当同态映射gg分别是单射满射双射时,分别称gg单一同态映射满同态映射同构映射
  • 如果存在一个从(A,)(A, *)(B,)(B, \circ )同构映射(单一同态映射、满同态映射),则称代数系统(A,)(A,*)(B,)(B, \circ )同构(单一同态、满同态)。
    (A,)(B,)(A, *)≌(B, \circ )表示(A,)(A,*)(B,)(B, \circ )同构

命题逻辑

命题与命题联结词

命题

  • 具有真假意义的陈述句称为命题
  • 命题可以取一个“值”,称为真值
  • 真值只有“真”和“假”两种,分别用“”(或“”)和“”(或“)表示

命题的分类

  • 原子命题(简单命题):不能再分解为更为简单命题的命题
  • 复合命题:可以分解为原子命题的命题,这些原子命题之间通过如“或者”、“并且”、“不”、“如果…则…”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。(优先级:否定→合取→析取→蕴涵→等价

命题联结词

否定¬\neg

  • PP是任一命题,复合命题“非PP”(或“PP的否定”)称为PP的否定式(Negation),记作¬P\neg P,“¬\neg”为否定联结词

合取\wedge

  • PPQQ是任两个命题,复合命题“P并且QP并且Q”(或“PQP和Q”)称为PPQQ的合取式(Conjunction),记作PQP∧Q,“”为合取联结词

析取\vee

  • PPQQ是任两个命题,复合命题“P或者QP或者Q”称为PPQQ的析取式(Disjunction),记作PQP∨Q,“”为析取联结词

蕴涵

  • PPQQ是任两个命题,复合命题“如果P,则Q如果P,则Q”称为PPQQ的蕴涵式(Implication),记作PQP→Q,“”称为蕴涵联结词,PP称为蕴涵式的前件,QQ称为后件

等价\leftrightarrow

  • PQP、Q是任两个命题,复合命题“P当且仅当QP当且仅当Q”称为PPQQ的等价式(Equivalence),记作PQP\leftrightarrow Q,“\leftrightarrow”称为等价联结词

说明

  • 联结词与自然语言之间的对应并非一一对应:
    • 合取联结词“”对应自然语言的“既…又…”、“不仅…而且…”、“虽然…但是…”、“并且”、“和”、“与”等
    • 蕴涵联结词“”,“PQP→Q”对应自然语言中的“如P则Q” , “只要P就Q”,“P仅当Q”,“只有Q才P”,“除非Q否则¬\neg P”等
    • 等价联结词“”对应了自然语言中的“等价”、“当且仅当”、“充分必要”等
    • 析取联结词“\vee”对应的是相容(可兼)的或
    • 否定联结词“¬\neg”是自然语言中的“非”、“不”和“没有”等
  • 当前件PP为假时,不管QQ的真假如何,则PQP→Q都为真。此时称为“善意推定
  • 复合命题的真值只取决于构成他们的各原子命题的真值,而与它们的内容、含义无关,与联结次所连接的两原子命题之间是否有关系无关

命题公式与符号化

命题公式的定义

  • 一个特定的命题是一个常值命题,它不是具有值“T”(“1”),就是具有值“F”(“0”)
  • 一个任意的没有赋予具体内容的原子命题称为命题变量(或命题变元),该命题变量无具体的真值,它的变域是集合{TF}\{T,F\}(或{01}\{0,1\})
  • 当原子命题是命题变元时,此复合命题也即为命题变元的“函数”,且该“函数”的值仍为“真”或“假”值,这样的函数可形象地称为“真值函数”,或称为命题公式,此命题公式没有确切真值

公式的解释

定义

  • P1P2PnP_1、P_2、…、P_n是出现在公式GG中的所有命题变元,指定P1P2PnP_1、P_2、…、P_n一组真值,则这组真值称为GG的一个解释,常记为II

性质

  • 一般来说,若有个命题变元,则应有2n2^n个不同的解释
  • 如果公式GG在解释II下是真的,则称II满足GG;如果GG在解释II下是假的,则称II弄假GG

真值表

定义

  • 将公式GG在其所有可能解释下的真值情况列成的表,称为GG的真值表

公式的等价性

基本等价式

交换律

  • PQ    QPP∧Q\iff Q∧P
  • PQ    QPP∨Q\iff Q∨P
  • PQ    QPP\leftrightarrow Q\iff Q\leftrightarrow P

结合律

  • (PQ)R    P(QR)(P∧Q)∧R\iff P∧(Q∧R)
  • (PQ)R    P(QR)(P∨Q)∨R\iff P∨(Q∨R)
  • (PQ)R    P(QR)(P\leftrightarrow Q)\leftrightarrow R\iff P\leftrightarrow (Q\leftrightarrow R)

分配律

  • P(QR)    (PQ)(PR)P∧(Q∨R)\iff (P∧Q)∨(P∧R)
  • P(QR)    (PR)(PR)P∨(Q∧R)\iff(P∨R)∧(P∨R)

否定深入

  • ¬¬P    P\neg \neg P \iff P
  • ¬(PQ)    ¬P¬Q\neg (P∧Q) \iff \neg P∨ \neg Q
  • ¬(PQ)    ¬P¬Q\neg (P\vee Q) \iff \neg P\wedge \neg Q
  • ¬(PQ)    P¬Q\neg (P → Q)\iff P ∧ \neg Q
  • ¬(PQ)    ¬PQ    P¬Q\neg(P \leftrightarrow Q) \iff \neg P \leftrightarrow Q \iff P \leftrightarrow \neg Q

联结词化归

  • PQ    ¬¬P¬QP∧Q\iff \neg(\neg P∨\neg Q)
  • PQ    ¬¬P¬QP∨Q\iff \neg (\neg P∧\neg Q)
  • PQ    ¬PQP→Q\iff \neg P∨Q
  • PQ    (PQ)(QP)    (¬PQ)(¬QP)    (PQ)(¬P¬Q)P \leftrightarrow Q \iff (P→Q)∧(Q→P) \iff (\neg P∨Q) ∧(\neg Q∨P) \iff (P ∧ Q) ∨(\neg P ∧ \neg Q)

命题与集合的关系

  • GHG,H理解为某总体论域上的子集合,而规定GHG∧H为两集合的公共部分(交集),GHG∨H为两集合的全部(并集),¬G\neg G为总体论域(如矩形域)中GG的补集,将命题中的真值“1”理解为集合中的总体论域(全集),将命题中的真值“0”理解为集合中的空集

永真式、永假式与蕴含式

定义

  • 公式G称为永真式,如果在它的所有解释之下都为“真”
  • 公式G称为永假式,如果在它的所有解释之下都为“假”
  • 公式G称为可满足的,如果它不是永假的

公式等价

定义

  • 设G、H是公式,如果在任意解释I下,G与H的真值相同,则称公式G、H是等价的,记作G    HG\iff H

定理

  • G    HG\iff H等价的充分必要条件为G    HG\implies HH    GH\implies G
  • 公式G、H等价的充分必要条件是公式G    HG\iff H是永真公式

性质

  • 由于“    \iff”不是一个联结词,而是一种关系,为此,这种关系具有如下三个性质:
    • 自反性 G=G
    • 对称性 若G=H,则H=G
    • 传递性 若G=H,H=S,则G=S

命题逻辑推理

基本蕴含式

  • (PQ)(QR)    PR(P \to Q) \land (Q \to R) \implies P \to R (假言三段论)

定理

  • 若前提集合为{H1H2Hm}\{ H_1,H_2,…,H_m \}, 结论为PQP→ Q ,则{H1H2Hm}    PQ\{ H_1,H_2,…,H_m \}\implies P\to Q等价于{H1H2HmP}    Q\{H_1,H_2,…,H_m,P\}\implies Q (CP规则)

推理规则

  • PQ,QRPRP \to Q, Q \to R \vdash P \to R

公式蕴涵的证明方法

  • 真值表法
  • GHG \to H是恒真公式
  • 利用一些基本等价式及蕴涵式进行推导
  • 任取真值I,若I满足G,往证I满足H
  • 反证法,设结论假,往证前提假

三个基本推理规则

  • P规则(前提引入规则):前提总是可用
  • T规则(推理引入规则):推理中允许使用推理规则,所得结果在后面的推理中可用
  • CP规则(附加前提引入规则) :证明PQP\to Q时可将P作为附加前提引入

范式

定义

合取式

  • 在一公式中,仅由命题变元及其否定构成的合取,称该公式为合取式
  • 其中每个命题变元或其否定,称为合取项

析取式

  • 在一公式中,仅由命题变元及其否定构成的析取,称该公式为析取式
  • 其中每个命题变元或其否定,称为析取项

析取范式

  • 一个命题公式A称为析取范式可表示为:多个合取式的析取

合取范式

  • 一个命题公式A称为合取范式可表示为:多个析取式的合取

定理

  • 合取式为永假式的充要条件是:它同时含有某个命题变元及其否定
  • 析取式为永真式的充要条件是:它同时含有某个命题变元及其否定
  • 对于任何一命题公式,都存在与其等价的析取范式和合取范式

范式的应用

  • 公式A为永假式的充要条件是其析取范式中每个简单合取式至少包含一个命题变元及其否定
  • 公式A为永真式的充要条件是其合取范式中每个简单析取式至少包含一个命题变元及其否定

公式的主范式

最小项

  • 在含有n个命题变元的合取式中, 若每个命题变元与其否定不同时存在,而二者之一出现一次且仅出现一次,则称该合取式为最小项
  • n个命题变元共形成2n2^n个最小项
  • 任意两个不同的最小项的合取式是永假的:mimj    F,ijm_i∧m_j\iff F,i≠j
  • 所有最小项之析取为永真:i=1nmi    T\bigvee\limits_{i=1}^n m_i \iff T
  • 每个最小项只有一个真值组合为真

最大项

  • 在n个命题变元的析取式中,若每个命题变元与其否定不同时存在,而二者之一必出现一次且仅出现一次,则称该析取式为最大项
  • 任何两个不同最大项之析取是永真的,即:MiMj    T,ijM_i∨M_j\iff T,i≠j
  • 所有最大项之合取为永假,即:i=1nMi    F\bigwedge\limits_{i=1}^n M_i \iff F
  • 每个最大项只有一个真值组合为假,且其真值0位于主对角线上

主析取范式

  • 在给定公式的析取范式中,若其合取式都是最小项,则称该范式为主析取范式
  • 任意含n个命题变元的非永假命题公式A,都存在与其等价的主析取范式
  • 任意含n个命题变元的非永假命题公式,其主析取范式是惟一的

主合取范式

  • 在给定公式的合取范式中,若其所有简单析取式都是最大项,称该范式为主合取范式
  • 任意含有n个命题变元的非永真命题公式A,都存在与其等价的主合取范式
  • 任意含n个命题变元的非永真命题公式A,其主合取范式是唯一的

求法

  • 公式化归法
  • 真值表法

主析取范式与主合取范式之间的关系

  • 由于主范式是由最小项或最大项构成,由其定义,可知两者有下列关系:¬mi    Mi,¬Mi    mi\neg m_i\iff M_i, \neg M_i\iff m_i
  • 因此,主析取范式和主合取范式有着“互补”关系,即由公式的主析取范式可以求出其主合取范式

主范式的应用

  • 根据主范式的定义和定理,可以判定含n个命题变元的公式,其关键是先求出给定公式的主范式A;其次按下列条件判定之:
    • A    A\iff T,或A可化为与其等价的、含2n2^n个最小项的主析取范式,则A为永真式
    • A    A\iff F,或A可化为与其等价的、含2n2^n个最大项的主合取范式,则A为永假式
    • 若A不与T或者F等价,且又不含2n2^n个最小项或最大项,则A为可满足的
  • 由于任一公式的主范式是唯一的,所以将给定的公式求出其主范式,若主范式相同,则给定两公式是等价的

推理规则

    \implies”与“\to”的不同

  • ”仅是一般的蕴涵联结词,GHG→H的结果仍是一个公式,而“    \implies”却描述了两个公式G,H之间的一种逻辑蕴涵关系,G    HG\implies H的“结果”,是非命题公式
  • 用计算机来判断G    HG\implies H是办不到的。然而计算机却可“计算”公式GHG→H是否为永真公式

谓词逻辑

谓词逻辑基本概念

谓词

定义

  • 用以刻划客体的性质或客体之间的关系即是谓词

简单命题函数

  • 由一个谓词和一些客体变元组成的表达式.
    A(x1x2,,xn)A(x_1,x_2,…,x_n)称n元命题函数或n元原子谓词公式,n元谓词就是有 n 个客体变元的命题函数

复合命题函数

  • 由一个或 n个简单命题函数以及联结词组成的表达式

结论

  • 谓词中个体词的顺序是十分重要的,不能随意变更。如命题F(b,c)F(b, c)为“真”,但命题F(c,b)F(c, b)为“假”
  • 一元谓词用以描述某一个个体的某种特性,而n元谓词则用以描述n个个体之间的关系
  • 0元谓词(不含个体词的)实际上就是一般的命题
  • 具体命题的谓词表示形式和n元命题函数(n元谓词)是不同的,前者是有真值的,而后者不是命题,它的真值是不确定的。如上例中S(a)是有真值的,但S(x)却没有真值
  • 一个n元谓词不是一个命题,但将n元谓词中的个体变元都用个体域中具体的个体取代后,就成为一个命题。而且,个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响

客体

  • 客体变元在哪些范围内取值(称客体),对是否成为命题及命题的真值都有影响
  • 在命题函数中,命题变元的论述范围称作个体域,个体域可以是有限的,也可以是无限的,把各种个体域综合在一起作为论述范围的域称为全总客体域

量词

全称量词\forall

  • \forall称为全称量词,“对所有的” ,“每一个”, “对任一个”

存在量词\exists

  • \exists称为存在量词,“存在一个”,“有一个”,“对于一些”

特性谓词

  • 限定客体变元变化范围的谓词

注意

  • 由量词确定的表达式,都与个体域有关
  • 用全总个体域,对每个的客体变元变化范围,用特性谓词加以限制,一般地:
    • 对全称量词,特性谓词常作条件的前提条件
    • 对存在量词,特性谓词常作合取项

谓词逻辑符号化的两条规则

  • 统一个体域为全总个体域,而对每一个句子中个体变量的变化范围用一元特性谓词刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则:
    • 对于全称量词(x\forall x),刻划其对应个体域的特性谓词作为蕴涵式之前件加入
    • 对于存在量词(x\exists x