第1章 命题逻辑(二).ppt

离 散 数 学 戎 玫 2005－9 第1章 命题逻辑 1.1 命题及联结词 1.2 命题公式与翻译 1.3 真值表和等价公式 1.4 重言式 1.5 范式 1.6 全功能联结词集 1.7 对偶式与蕴含式 1.8 命题逻辑的推理理论 1.4 重言式 定义1.4.1 设A是任一命题公式。 ⑴ 若对A的任意赋值，其真值永为真，则称命题公式A为重言式或永真式。 ⑵ 若对A的任意赋值，其真值永为假，则称命题公式A为矛盾式或永假式。 ⑶ 若A不是矛盾式，则称命题公式A为可满足的。 由定义1.4.1可以看出，任何重言式都是可满足的。 1.4 重言式 【例1.18】用等价演算法判断下列公式的类型。 ⑴ q∨? ((?p∨q)∧p) ⑵ (p∨?p)→((q∨?q)∧r) ⑶ (p→q)∧?p 解：⑴ q∨?((?p∨q)∧p) ?q∨?((?p∧p)∨(q∧p)) (分配律) ?q∨?(0∨(q∧p)) (矛盾律) ?q∨?(q∧p) (同一律) ?q∨(?q∨?p) (德摩根律) ?(q∨?q)∨?p (结合律) ?1∨?p (排中律) ?1 (零律) 由此可知，⑴为重言式。 1.4 重言式 ⑵ (p∨?p)→((q∧?q)∧r) ?1→((q∧?q)∧r) (排中律) ?1→(0∧r) (矛盾律) ?1→0 (零律) ?0 (条件联结词的定义) 由此可知，⑵为矛盾式。 ⑶ (p→q)∧?p ?(?p∨q)∧?p (条件等价式) ??p (吸收律) 由此可知，⑶是可满足的。 1.4 重言式 定理1.4.1 任何两个重言式的合取或析取都是重言式。证明：设A、B是重言式，对A和 B的任何赋值，总有A为1，B为1，所以 A∧B?1，A∨B?1，故A∧B和A∨B都是重言式。 推论： 任何两个矛盾式的合取或析取是矛盾式。 定理1.4.2 一个重言式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式。 推论：一个矛盾式，对同一分量出现的每一处都用同一合式公式置换，其结果仍是矛盾式。 1.4 重言式 【例1.19】利用定理1.4.2证明((p∨q)∧r)∨?((p∨q)∧r)为重言式。证明：由排中律知p∨?p为重言式，以((p∨q)∧r)去置换其中的p，得公式((p∨q)∧r)∨?((p∨q)∧r)，根据定理1.4.2，这是重言式。 1.4 重言式 定理1.4.3 设A、B为两个命题公式，A?B当且仅当A?B是重言式。证明：设A?B，下证A?B是重言式。给A，B的任何赋值，因为A?B，所以A，B具有相同的真值，由双条件联结词的定义知A?B为真，所以A?B为重言式。设A?B为重言式，下证A?B给A，B的任何赋值，因为A?B为重言式，故A，B的真值相同，由命题公式等价的定义知A?B 1.5.1析取范式与合取范式 定义1.5.1由一些命题变元或其否定构成的析取式称为基本和，也叫简单析取式。约定单个变元或其否定是基本和。 例如，?p∨q、p∨?q、p∨q、?q、?p、q都是基本和。 定义1.5.2由一些命题变元或其否定构