离散数学定义定理上.docxVIP

离散数学定义定理 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的值为真，则称这组指派为成真指派。若指定的一种指派，使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条件三段式(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∧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）