离散数学期末复习总要

离散数学期末复习各个章节要点纲要（及定理）

离散数学定义定理

1.3.1命题演算的合式公式规定为： （1）单个命题变元本身是一个合式公式。 （2）如果A是合式公式，那么┐A是合式公式。

（3）如果A和B是合式公式，那么（A∨B）、（A∧B）、（A→B）、（A?B）、都是合式公式。 （4）当且仅当有限次地应用（1）（2）（3）所得到的包含命题变元，连接词和圆括号的符号串是合式公式。

1.3.2 设Ai是公式A的一部分，且Ai是一个合式公式，称Ai是A的子公式。

1.3.3 设P为一命题公式，P1,P2,……，Pn为出现在P中的所有命题变元，对P1,P2,……，Pn指定一组真值称为对P的一种指派。若指定的一种指派，使P的值为真，则称这组指派为成真指派。若指定的一种指派，使P的值为假，则称这种指派为成假指派。 含n个命题变元的命题公式，共有2n个指派。

1.3.4 给定两个命题公式A和B，设P1,P2,……，Pn为所有出现于A和B中的原子变元，若给P1,P2,……，Pn任一组真值指派，A和B的真值都相同，称A和B是等价的，记做A <=>B。

1.3.5 设A为一命题公式，若A在它的各种指派情况下，其取值均为真，则称A为重言式或永真式。 1.3.6 设A为一命题公式，若A在它的各种指派情况下，其取值均为假，则称A为矛盾式或永假式。 1.3.7设A为一命题公式，若A在它的各种指派情况下至少存在一组成真指派，则称A为可满足式。 1.4.1 设X式合式公式A的子公式，若有Y也是一个合式公式，且X<=>Y，如果将Ａ中的Ｘ用Ｙ置换，得到公式Ｂ，则A<=>B。

1.4.2 设A，B为两个命题公式，A<=>B，当且仅当A ←→B为一个重言式。 P=>Q称做P蕴含Q或蕴含式，又称永真条件式。 蕴含式有下列性质：

（1）对任意公式A，又A=>A；

（2）对任意公式A，B和C，若A=>B，B=>C，则A=>C； （3）对任意公式A，B和C，若A=>B，A=>C，则A=>(B∧C); （4）对任意公式A，B和C，若A=>C，B=>C，则A∨B=>C.

1.4.3设P，Q为任意两个命题公式，P<=>Q的充分必要条件式P=>Q,，Q=>P。 蕴含式推理 P∧Q=>P P∧Q=>Q P=>P∨Q 化简式 化简式 附加式 ┐P=>P→Q Q=>P→Q ┐(P→Q)=>P ┐(P→Q)=>┐Q p∧(P→Q)=>Q ┐Q∧(P→Q)=>┐P ┐p∧(P∨Q)=>Q (P→Q) ∧(Q→R)=>P→R (P?Q) ∧(Q?R)=>P?R (P→Q)∧(R→S)∧(P∧R)=>Q→S (P→Q)∧(R→S)∧(P∨R)=>Q∨S P→Q=>(P∨R) →(Q∨R) P→Q=>(P∧R) →(Q∧R) 变形附加式 变形附加式 变形简化式 变形简化式 假言推论 拒取式 析取三段式 条件三段式 双条件三段式 合取构造二难 析取构造二难 前后附加式 前后附加式 1.5.1 一个命题公式称为合取范式，当且仅当它具有形式：A1∧A2∧…∧An(n≥1)，其中A1，A2，…，An都是有命题变元及其否定所组成的析取式。

1.5.2 一个命题公式称为析取范式，当且仅当它具有形式：A1∨A2∨…∨An(n≥1)，其中A1，A2，…，An都是有命题变元及其否定所组成的合取式。

1.5.3 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与他的否定不能同时存在，但两者必须出现且仅出现一次。 小项有如下性质：

（1）每个小项具有一个相应的编码，当该编码与其真实指派相同时，该小项为T，在其余2n-1种指派情况下为F。

（2）任意两个不同小项的合取是永假。 （3）全体小项的析取式为永真。

定义1.5.4 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取组成，则该等价公式称作原公式的主析取范式。

定理1.5.1 在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式主析取范式。 定理1.5.2 任意含n个命题变元的非永假命题公式，其主析取范式是唯一的。

定义1.5.5 n个命题变元的析取式称作布尔析取或大项。其中每个变元与它的否定不能同时出现，但两者必须出现仅出现一次。

定理1.5.3 在真值表中一个公式的真值为F的指派所对应的大项的合取，称为此公式的主合取范式。 定理1.5.4 任意含有n个命题变元的非永假命题公式A，其主合取范式是唯一的。

设命题公式中含有n个命题变元，且A的主析取范式中含有k个小项mi1,mi2,…，mik,则A的主合取范式比含有2n-k个大项。如果命题公式A的主析取范式为 ∑(i1,i2,……，ik)，

则A的主合取范式为： Π(0,1,2,…，i1-1,i1+1,…，ik-1,ik+1,……，2n-1)。 从A的主析取范式求其主合取范式的步骤为： （1）求出A的主析取范式中未包含小项的下标。 （2）把（1）中求出的下标写成对应大项。

（3）做（2）中县城大项合取，即为A的主合取范式。

根据主范式（主析取范式、主合取范式）的定义和定理，可以判定含n个命题变元的公式： （1）若A可化为与其等价的含2n个小项的主析取范式，则A为永真式。 （2）若A可化为与其等价的含2n个大项的主合取范式，则A为永假式。

（3）若A的主析取范式不含2n个小项，或A的主合取范式不含2n个大项，则A为可满足的。 定义1.6.1 设H1,H2,…Hn，C是命题公式，当且仅当H1∧H2∧…∧Hn=>C，称C是一组前提H1，H2，…，Hn的有效结论。

等值公式表 E1 E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 ┐┐p<=>P P∧Q<=>Q∧P P∨Q<=>Q∨P (P∧Q)∧R<=>P∧(Q∧R) (P∨Q)∨R<=>P∨(Q∨R) P∧(Q∨R)<=>(P∧Q)∨(P∧R) P∨(Q∧R)<=>(P∨Q)∧(P∨R) ┐(P∧Q)<=> ┐P∨┐Q ┐(P∨Q)<=> ┐P∧┐Q P∨P<=>P P∧P<=>P E12 E13 E14 E15 E16 E17 E18 E19 E20 E21 E22 R∨(P∧┐P)<=>R R ∧(P∨┐P)<=>R R∨(P∨┐P)<=>T R∧(P∧┐P)<=>F P→Q<=>┐P∨Q ┐(P→Q)<=> P∧┐Q P→Q<=>┐Q→┐P P→(Q→R)<=>(P∧Q)→R P?Q<=>(P→Q)∧(Q→P) P?Q<=>(P∧Q)∨(┐P∧┐Q) ┐(P?Q) <=> P?┐Q 常用的推理规则有：

（1）前提引入规则：在证明的任何步骤上，都可以引入前提，简称P规则。

（2）结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提，称为T规则。 （3）置换规则：在证明的任何步骤上，命题公式的任何子命题公式都可以用与之等值的命题公式置换，也记作T规则。

定理1.6.1 推理H1∧H2∧…∧Hn┣C是有效推理的充分必要条件是H1∧H2∧…∧Hn→C为永真式。 定义1.6.2 设H1，H2，…，Hn是可满足式，则称H1，H2，…，Hn是相容的，若H1，H2，…，Hn是永假式称H1，H2，…，Hn是不相容的。

定理1.6.2 若H1∧H2∧…∧Hn∧┐C为永假式，则H1∧H2∧…∧Hn┣C成立。 定理1.6.3 若H1∧H2∧…∧Hn∧R=>C，则H1∧H2∧…∧Hn =>R→C。

本定理即：若H1，H2，…,Hn，R┣C，则H1，H2，…，Hn┣R→C

定义2.1.1 由一个谓词，一些个体变元组成的表达式简称为谓词变项或称为命题函数。（命题函数不是命题，只有命题函数中的变元都取为特定具体的个体时，才是确定的命题。谓词变项摘，个体变元的数目为谓词变项的元数。）

定义2.2.1 由一个或几个原子命题函数以及逻辑联接词组合而成的表达式称为符合命题函数。 定义2.2.2 谓词演算的合式公式，可由下述各条组成（合式公式A记为WffA）:

（1）原子谓词公式是合适公式。

（2）若A是合式公式，则┐A是合式公式。

（3）若A和B都是合式公式，则（A∨B）、（A∧B）、（A→B）、（A?B）是合式公式。 （4）如果A是合式公式，x是A中出现的任何变元，则（?x）A和(üx)A都是合式公式。 （5）只有经过有限次应用规则（1）（2）（3）（4）所得到的公式是合式公式。

定义2.2.3 给定谓词合式公式A，其中一部分公式形式为（?x）(Bx)或(üx)(Bx)，称量词?，ü后面所跟的x为指导变元或作用变元。称B为相应量词的辖域（或作用域）。

在辖域中，x的一切出现称为约束出现。在B中除去约束出现的其他变项的出现称为自由出现。

（1）约束改名规则，将量词辖域中，某个约束出现的个体变元及其相应指导变元改成本辖域中未出现过的个体变元，其余不变。

（2）自由带入规则，对某个自由出现的个体变元可用个体常元或用与原子公式中与所有个体变元不同的个体变元取代入，且处处代入。

定义2.3.1 给定任何两个谓词公式WffA和WffB，设它们有共同的个体域E，若对A和B的任一一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上市等价的，记作A<=>B。

定义2.3.2 给定任意谓词公式WffA，其个体域为E，对于A的所有赋值WffA都为真，则称WffA在E上有效的（或永真的）。

定义2.3.3一个谓词公式WffA，对于A的所有赋值WffA都为假，则称WffA为不可满足的（或永假的）。 定义2.3.4一个谓词公式WffA，如果至少在一个赋值下为真，则称该WffA为可满足。 等值公式表 E23 E24 E25 E26 E27 E28 E29 ( x)((Ax)∨(Bx))<=>( x)(Ax)∨( x)(Bx) ( x)((Ax)∧(Bx))<=>( x)(Ax)∧( x)(Bx) ┐( x)(Ax)<=>( x)┐(Ax) ┐( x)(Ax)<=>( x)┐(Ax) ( x)(A∨(Bx))<=>A∨( x)(Bx) ( x)(A∧(Bx))<=>A∧( x)(Bx) ( x)((Ax)→(Bx))<=>( x)(Ax)→( x)(Bx) E30 E31 E32 E33 I17 I18 I19 ( x)(Ax) →B<=>( x) ((Ax)→B) ( x)(Ax) →B<=>( x) ((Ax)→B) A→( x)(Bx) <=>( x) (A→(Bx)) A→( x)(Bx) <=>( x) (A→(Bx)) ( x)(Ax)∨( x)(Bx) =>( x)((Ax)∨(Bx)) ( x)((Ax)∧(Bx)) =>( x)(Ax)∧( x)(Bx) ( x)(Ax)→( x)(Bx) =>( x)((Ax)→(Bx)) 定义2.4.1 一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公式叫做前束范式。

前束范式形式如下：（Q1V1）(Q2V2)……（QnVn）A。 其中Qi(1≤i≤n)为?或ü，A为不含有量词的谓词公式。 定理2.4.1 任意一个谓词公式，均和一个前束范式等价。 谓词演算推理规则 (1)全称指定规定，US.

∵( x)P(x) ∴P(c)

(2)全称推广规则，UG：∵P(x)∴( x)P(x) (3)存在指定规则，ES： ∵( x)P(x) ∴P(c) (4)存在推广规则，EG：∵：P(c) ∴( x)P(x)

定义3.1.1 设A，B是任意两个集合，若A=B，当且仅当它们有相同的成员。

定义3.1.2 设A，B是任意两个集合，加入A的每个元素都是B的元素，则称Ａ为Ｂ的子集，或Ａ包含在Ｂ内或Ｂ包含Ａ。记作： A B或B A

定理3.1.1 集合A和集合B相等的充分必要条件式两个集合互为子集。

定义3.1.3 如果集合A的每一元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集，记作A B。

定义3.1.4 不包含任何元素的集合称为空集，记作Φ或{ }。 定理3.1.2 对于任何集合A必有ΦA。(空集包含在A内)

定义3.1.5 设A为任意集合，以A的子集为元素所组成的集合，称为集合A的幂集。记作P(A)。

本文来源：https://www.bwwdw.com/article/bktd.html