离散数学定义定理（上）

离散数学定义定理

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)，称量 …… 此处隐藏：3484字，全部文档内容请下载后查看。喜欢就下载吧 ……