交大数理逻辑课件2-2 命题逻辑的等值和推理演算.ppt

《交大数理逻辑课件2-2 命题逻辑的等值和推理演算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章命题逻辑的等值和推理演算2.1等值定理2.2等值公式2.3命题公式与真值表的关系2.4联结词的完备集2.5对偶式2.6范式2.7推理形式2.8基本的推理公式2.9推理演算2.10归结推理法讨论等值演算讨论推理演算2.4联结词的完备集定义在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。如：PQ=PQPQ=(PQ)(PQ)在{，，，，}中、是冗余的。在{，，}中，PQ=（PQ）所以是冗余的。在{，}中无冗余

2、的联结词。同理，在{，}中无冗余的联结词。联结词的完备集定义设C是联结词的集合，若对任一命题公式都由C中的联结词表示出来的公式与之等值，就说C是完备的联结词集合。显然，全体联结词的无限集合是完备的。{，，，，}{，，，，}{，，}{，}，{，}，{}，{}等也是完备的。是完备的2.5对偶式定义在仅含联结词¬，∧，∨的命题公式A中，将联结词∨，∧，F，T分别换成∧，∨，T，F所得的公式称为公式A的对偶式，记为A*如：PQ与PQ是对偶式(PQ)R与(PQ)R是对偶式推广在仅含有

3、联结词¬，∧，∨，↑，↓的命题公式中，将联结词∨，∧，↑，↓，F，T分别换成∧，∨，↓，↑，T，F，就得到了它的对偶式。与对偶式有关的定理设A和A*互为对偶式，P1,P2,…,Pn是出现在A和A*中的全部命题变项，令A=A(P1,P2,…,Pn),A—=A(P1,P2,…,Pn)定理2.5.1：(A*)=(A)*,(A—)=(A)—如：A=P(QR)则：A*=P(QR)，A—=P(QR)A=P(QR)所以：(A)*=P(QR)(A*)=P(QR)所以：(A)—=

4、P(QR)(A—)=P(QR)(A*)=(A)*(A—)=(A)—与对偶式有关的定理定理2.5.2：(A*)*=A,(A—)—=A定理2.5.3：A=A*—如：A=P(QR)则：A=P(QR)A*=P(QR)所以：A*—=P(QR)=A此定理为摩根律：(AB)=AB(AB)=AB的另一种形式，与对偶式有关的定理定理2.5.4若A=B，必有A*=B*证：A=BAB永真AB永真A*—B*—永真A*B*永真A*=B*定理2.5.5若A

5、B永真，必有B*A*永真（作业）定理2.5.6A与A—同永真，同可满足A—与A*同永真，同可满足对偶性是逻辑规律，给证明公式的等值和求否定带来方便依定理2.5.3有，A=A*—，B=B*—2.6范式简单析取式它是仅由有限个命题变项或其否定构成的析取式。如:P，Q，P，Q，PQ，PQ，PQ它是重言式当且仅当它同时含一个命题变项及其否定；如：PQP是重言式简单合取式它是仅由有限个命题变项或其否定构成的合取式。如:P，Q，P，Q，PQ，PQ它是矛盾式当且仅当它同时含一个命题变项及其否定。如：

6、PPQ是矛盾式析取范式析取范式由有限个简单合取式组成的析取式A1A2….An（n1，Ai都是简单合取式）如：(PQR)(PQ)Q一个析取范式是矛盾式，当且仅当其每个简单合取式都是矛盾式合取范式由有限个简单析取式组成的合取式A1A2….An（n1,Ai都是简单析取式）如：(PQR)(PQ)Q一个合取范式是重言式，当且仅当其每个简单析取式都是重言式范式——析取范式与合取范式的总称命题公式的范式范式存在定理任何命题公式都存在着与之等值的析取范式与合取范式求公式A的范式的步骤：

7、(1)消去A中的,（若存在）AB=ABAB=(A∧B)∨(A∧B)(求析取范式时)=(A∨B)∧(A∨B)(求合取范式时)(2)否定联结词的内移或消去（摩根定律）(3)使用分配律对分配（析取范式）对分配（合取范式）注意：公式的范式存在，但不惟一，这是它的局限性求公式的范式举例例:求下列公式的析取范式与合取范式(1)A=(PQ)R解(PQ)R=(PQ)R（消去）=PQR（结合律）这既是A的析取范式（由3个简单合取式组成的析取式）又是A的合取范式（由一个简单析取式

8、组成的合取式）求公式的范式举例(2)B=(PQ)R解(PQ)R=(PQ)R（消去第一个）=(PQ)R（消去第二个）=(PQ)R（否定号内移——摩根律）这已为析取范式（两个简单合取式构成）继续：(PQ)R=(PR)(QR)（对