第一章 命题逻辑2013-8-26.pptVIP

* 大项的性质： (a) 没有两个大项是等价的。 (b) 任何两个不同大项之析取是永真的，即 Mi ∨Mj ?T，i≠j。 (c) 所有大项之合取为永假，即 Mi ?F。 (d) 每个大项只有一个解释为假，且其真值0位于主对角线上。这表明每个大项与其成假指派建立了一一对应关系。 * （2）主合取范式的定义与其存在定理 定义1.8.4 在给定公式的合取范式中，若其所有简单 析取式都是大项， 称该范式为主合取范式。 定理1.8.3 任意含有n个命题变元的非永真命题公式A， 都存在与其等价的主合取范式。 定理1.8.4 任意含n个命题变元的非永真命题公式A， 其主合取范式是惟一的。 * （3）主合取范式的求法 真值表法 公式化归法 * 三、主析取范式与主合取范式之间的关系 由于主范式是由小项或大项构成，两者有下列关系： ┐mi ?Mi ┐Mi ?mi 因此，主析取范式和主合取范式有着“互补”关系。 设命题公式 A 中含有 n 个命题变元，且A的主析取范式中含有 k 个小项mi1,mi2,…mik，则┐A的主析取范式中必含有 个小项, 不妨含为 mj1, mj2 ,…, mj(2n-k)。 即： ┐A ? mj1 ∨mj2 ∨… ∨ mj(2n-k) 于是， A ? ┐┐A ? ┐(mj1 ∨mj2 ∨… ∨ mj(2n-k) ? ┐mj1 ∧ ┐ mj2 ∧… ∧ ┐ mj(2n-k) ? Mj1 ∧Mj2 ∧… ∧Mj(2n-k) * 从 A 的主析取范式求其主合取范式的步骤： (a) 求出A的主析取范式中没有包含的小项。 (b) 求出与(a)中小项的下标相同的大项。 (c) 做(b)中大项之合取，即为A的主合取范式。 (P?Q)∧Q ?m1∨m3，则 (P?Q)∧Q ?M0∧M2。 * （1）判定问题 根据主范式的定义和定理，也可以判定含 n 个命题变元的公式，其 关键是先求出给定公式的主范式Ａ；其次按下列条件判定之： (a) 若A ?Ｔ，或A可化为与其等价的、含 个小项的主析取范式， 则A为永真式。 (b) 若A?Ｆ，或A可化为与其等价的、含 个大项的主合取范式， 则A为永假式。 (c) 若 A 不与Ｔ或者Ｆ 等价，且又不含 个小项或者大项，则A为 可满足式。 四、主范式的应用 * 例1：判定下列公式为何类公式： （1） (P?Q)∧Q （2） (P?Q)?(┐P∨Q) （2）(P?Q)?(┐P∨Q) ? ┐(┐P∨Q) ∨ (┐P∨Q) ? T 故其为永真式。 解 （1）(P?Q)∧Q?m1∨m3 可见，其主范式中，大、小项数目均不到4，故 其为可满足式。 * 例1：求证(P?Q)∧(P?R)?P?(Q∧R) 证明：(P?Q)∧(P?R) ? (┐P∨Q) ∧ (┐P∨R) ? (┐P∨Q ∨(┐R ∧ R) )∧ (┐P∨ (┐Q ∧ Q)∨R) ? (┐P∨Q ∨┐R )∧ (┐P∨Q∨R) ∧ (┐P∨ ┐Q ∨ R )∧ (┐P∨ Q ∨ R ) ? (┐P∨Q∨R) ∧ (┐P∨Q∨┐R )∧ (┐P∨┐Q∨R ) ? M4 ∧ M5 ∧ M6 （2）证明等价式成立 若给定两公式的主范式相同，则给定两公式是等价的。 P?(Q∧R) ? ┐P ∨(Q ∧R) ? (┐P∨Q) ∧ (┐P∨R) ? (┐P∨Q ∨(┐R ∧ R) )∧ (┐P∨ (┐Q ∧ Q) ∨ R) ? (┐P∨Q ∨┐R )∧ (┐P∨Q∨R) ∧ (┐P∨ ┐Q ∨ R )∧ (┐P∨ Q ∨ R ) ? (┐P∨Q∨R) ∧ (┐P∨Q ∨┐R )∧ (┐P∨ ┐Q ∨ R ) ? M4 ∧ M5 ∧ M6 * 在逻辑学中，把从前提（又叫公理或假设）出发，依据公认的推