第一章命题逻辑(5).ppt

1.5.3 主范式 1.5.3 主范式 1.5.3 主范式 1.5.3 主范式 1.5.3 主范式 P,Q,R形成的极小项与极大项（练习） 作业 课后习题8（奇数小题） 习题16 1.5 对偶与范式 任一命题公式都存在着与之逻辑等价的主析取和 主合取范式，并且是唯一的。 1.5.1 对偶 定义1.15 在给定的仅使用联结词﹁, ∧, ∨的命题公式A中，若把∧和∨互换，0和1互换而得到一个命题公式A*，则称A*是A的对偶式。 显然，A也是A*的对偶式。 可见，A*和A互为对偶式且(A*)*=A。 例1.36 写出下列公式的对偶式。 1）(A∨B)∧(A∨C ) 2）A∧0 解：所求得的对偶式为 1）(A∧B)∨(A∧C ) 2）A∨1 定理1.3 设A*和A互为对偶式，P1, P2, …, Pn是出现在A和A*中的命题变元，则 1）﹁A (P1, P2, …, Pn) ? A* (﹁P1,﹁P2, …, ﹁Pn) 2）A(﹁P1,﹁P2, …, ﹁Pn) ? ﹁A* (P1, P2, …, Pn) 1.5.1 对偶 定理1.4 设A和B是两个命题公式，若A?B，则A*?B*。 证：令P1, P2, …, Pn是出现在公式A和B中的所有命题变元，因为有 A (P1, P2, …, Pn) ? B (P1, P2, …, Pn) 故 ﹁A (P1, P2, …, Pn) ?﹁B (P1, P2, …, Pn) 根据定理1.3可得 ﹁A (P1, P2, …, Pn) ? A* (﹁P1,﹁P2, …, ﹁Pn ) ﹁B (P1, P2, …, Pn) ? B* (﹁P1,﹁P2, …, ﹁Pn 因此 A* (﹁P1,﹁P2, …, ﹁Pn) ? B*(﹁P1,﹁P2, …, ﹁Pn )证毕。 说明： 1）对于含有﹁,∧,∨之外联结词的公式，必须利用逻辑等价演算将其他联结词消去后，才能求其对偶式。 2）一般情况下，公式与其对偶式不是逻辑等价的。 1.5.2 范式 定义1.16 命题变元和命题变元的否定称为文字。 定义1.17 仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称作简单合取式。 一个文字既是简单析取式，又是简单合取式。 例1.37 判断以下公式是否为简单析（合）取式 1) ﹁P 2) ﹁ ﹁P 3) P ∧ ﹁Q 4) ﹁(P ∧ ﹁Q) 解： 1) 是简单析取式，也是简单合取式； 2) 不是； 3) 是简单合取式； 4) 不是。 1.5.2 范式 定理1.5 1）一个简单析取式是重言式当且仅当它同时含某个命题变元及它的否定式。 2）一个简单合取式是矛盾式当且仅当它同时含某个命题变元及它的否定式。 定义1.18 1）由有限个简单合取式构成的析取式称为析取范式。 2）由有限个简单析取式构成的合取式称为合取范式。 3）析取范式与合取范式统称为范式。 无论是简单析取式或是简单合取式，都既是析取范式又是合取范式。 定理1.6 1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。 1.5.2 范式 定理1.7（范式存在定理）任一命题公式都存在与之逻辑等价的析取范式与合取范式。 证：以下的步骤也是求公式范式的步骤（此为构造性证明方法之一）： 1）利用蕴涵律和等价律消去联结词?, ? 蕴涵律: A?B ? ﹁A∨B 等价律: A ?B ? (A→B)∧(B→A) 2）利用双重否定律消去连续的否定号 双重否定律： ﹁﹁A ? A 3）利用德摩根律内移否定号 德摩根律： ﹁(A∨B) ? ﹁A∧﹁B ﹁(A∧B) ? ﹁A∨﹁B 4）利用∨对∧的分配律求合取范式，∧对∨的分配律求析取范式。 ∨对∧的分配律： A∨(B∧C) ? (A∨B)∧(A∨C) ∧对∨的分配律：?A∧(B∨C) ? (A∧B)∨(A∧C) 由以上步骤，可将任一公式化成