第3章_命题逻辑解说.ppt

* DEFINITION 10. 命题公式P的对偶公式(Dual)：将P中的 析取联结词换成合取联结词， 合取联结词换成析取联结词， 1换成0，0换成1（如果存在的话）。 记为P*. 命题逻辑 对偶与范式 5 * 对偶原理(Duality Principle)： 设P，Q是两命题公式，如果 P ? Q， 则 P* ? Q*。 例：A： (P ∧﹁ Q)∨ Q B： P ∨ Q 这里， A? B，分析是否A*? B*。 对偶与范式 * 命题公式的标准化——范式 小项(small item)/合取式(conjunctive form): 若干个原子命题或其否定的合取。 大项(large item)/析取式(disjunctive form): 若干个原子命题或其否定的析取。 析取范式(disjunctive normal form)： 若干个小项的析取。 合取范式(conjunctive normal form)： 若干个大项的合取。 对偶与范式 * 定理的证明思路： 1、消去对?﹁、∧、∨?来说冗余的联结词； 2、将否定联结词移到命题变量的前面； 3、消除多余的否定联结词； 4、利用分配律化成合取范式和析取范式。 定理1：任意一个命题公式都存在与之等价的 合取范式和析取范式。 范式存在定理 对偶与范式 例：求?（Ｐ∨Ｑ）?（Ｐ∧Ｑ）的析取范式： 范式存在定理 * 令A(a1、a2、…、an)是包含有n个变量的公式， 极小项(extremal ~):小项中恰包含n个变量或其否定。 极大项(extremal ~):大项中恰包含n个变量或其否定。 主析取范式(Unique disjunctive normal form): 若干个极小项的析取。 主合取范式(Unique conjunctive normal form): 若干个极大项的合取。 对偶与范式 * 以三个命题变项p,q,r为例，可形成23=8个极小项，每个极小项对应一个二进制数，也对应一个十进制数，二进制数是该极小项的成真赋值，十进制数可做该极小项抽象表示法的角码。对应情况如下： ﹁p∧﹁q∧﹁r—— 000——0，记作m0； ﹁p∧﹁q∧r —— 001——1，记作m1； ﹁p∧q∧﹁r —— 010——2，记作m2； ﹁p∧q∧r —— 011——3，记作m3； p∧﹁q∧﹁r —— 100——4，记作m4； p∧﹁q∧r —— 101——5，记作m5； p∧q∧﹁r —— 110——6，记作m6； p∧q∧r —— 111——7，记作m7。 主析取范式：如m1∨m2∨m5可用?( 1,2,5 )表示。 对偶与范式 * 以三个命题变项p,q,r为例，可形成23=8个极大项，每个极大项对应一个二进制数，也对应一个十进制数，二进制数是该极大项的成假赋值，十进制数可做该极大项抽象表示法的角码。对应情况如下： p∨q∨r —— 000——0，记作M0； p∨q∨﹁r —— 001——1，记作M1； p∨﹁q∨r —— 010——2，记作M2； p∨﹁q∨﹁r —— 011——3，记作M3； ﹁p∨q∨r —— 100——4，记作M4； ﹁p∨q∨﹁r —— 101——5，记作M5； ﹁p∨﹁q∨r —— 110——6，记作M6； ﹁p∨﹁q∨﹁r—— 111——7，记作M7。 主合取范式：如M0∧ M3 ∧ M6可用?( 0,3,6 )表示。 对偶与范式 （1）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“Ｔ”的行，对应写出极小项的析取式，且一定是唯一的。 （2）若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2n个极小项。 （3）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。 （4）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“Ｔ”的个数。 对偶与范式 讨论 （5）与命题公式等价的主合范式中极大项的个数等于其真值表中真值为“Ｆ”的个数。由真值表找极大项的