资源描述：
《离散数学定义定理(上)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、离散数学定义定理1.3.1命题演算的合式公式规定为：（1）单个命题变元本身是一个合式公式。（2）如果A是合式公式，那么┐A是合式公式。（3）如果A和B是合式公式，那么（A∨B）、（A∧B）、（A→B）、（ADB）、都是合式公式。（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的值为真，则称这组指派为
2、成真指派。若指定的一种指派，使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
3、式合式公式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=
4、>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条件三段式(PDQ)∧(QDR)=>PDR双条件三段式(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∧
5、A2∧…∧An(n≥1)，其中A1，A2，…，An都是有命题变元及其否定所组成的析取式。1.5.2一个命题公式称为析取范式，当且仅当它具有形式：A1∨A2∨…∨An(n≥1)，其中A1，A2，…，An都是有命题变元及其否定所组成的合取式。1.5.3n个命题变元的合取式，称作布尔合取或小项，其中每个变元与他的否定不能同时存在，但两者必须出现且仅出现一次。小项有如下性质：（1）每个小项具有一个相应的编码，当该编码与其真实指派相同时，该小项为T，在其余2n-1种指派情况下为F。（2）任意两个不同小项的合取是永假。（3）全体小项的析取式为永真。定义1.5.4对于给定的命题公式，如果有一
6、个等价公式，它仅由小项的析取组成，则该等价公式称作原公式的主析取范式。定理1.5.1在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式主析取范式。定理1.5.2任意含n个命题变元的非永假命题公式，其主析取范式是唯一的。定义1.5.5n个命题变元的析取式称作布尔析取或大项。其中每个变元与它的否定不能同时出现，但两者必须出现仅出现一次。定理1.5.3在真值表中一个公式的真值为F的指派所对应的大项的合取，称为此公式的主合取范式。定理1.5.4任意含有n个命题变元的非永假命题公式A，其主合取范式是唯一的。设命题公式中含有n个命题变元，且A的主析取范式中含有k个小项mi1
7、,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可化为与其等
