〔第2讲)命题逻辑.ppt

定理1 设A和A*是对偶式。P 1, P2,…, Pn是出现于A和A *中的所有命题变元，于是 ┒A(P1, P2, …, Pn) ?A *(┒P1, ┒P2, …, ┒Pn) 例 A*(┒P, ┒Q, ┒R) ? ┒(┒P)∧(┒Q∨┒R) 所以, ┒A(P, Q, R) ? A *(┒P, ┒Q, ┒R) A(P，Q，R) ? ┒P∨Q∧R ┒A(P，Q，R) ? ┒(┒P∨Q∧R) ? ┒(┒P)∧ ┒(Q∧R) ? ┒(┒P)∧(┒Q∨ ┒R) A*(P, Q, R) ? ┒P∧(Q∨R) 三、命题公式的对偶原理 定理2 若A?B, 且A、B为命题变元P1, P2,….., Pn及联结词∧、 ∨、┒构成的公式, 则A* ?B*。此定理常称为对偶原理。 A(P1P2, …, Pn)? B(P1, P2, …, Pn) 永真。 故 ┒A(P1, P2, … , Pn) ? ┒B( P1, P2, … , Pn)  永真。由定理1得 A*(┒P1, ┒P2, … , ┒Pn) ? B* (┒P1, ┒P2, … , ┒Pn)  得A*(P1, P2, …, Pn) ? B*(P1, P2, …, Pn)  所以，A* ? B*。 证明 A?B意味着 永真 因上式是永真式, 故使用代入规则, 以┒Pi代Pi, 1≤i≤n, 例 若(P∧Q)∨(┒P∨(┒P∨Q)) ? ┒P∨Q 则由对偶原理立即可知下式成立： (P∨Q)∧(┒P∧(┒P∧Q)) ? ┒P∧Q * 通过公式G1 、G2 、G3 的真值表的特点 板书：重言式 * 通过公式G1 、G2 、G3 的真值表的特点 * 三中公式的定义 * 三中公式的关系 * 重言式的地位 * 强调恒等式在命题演算中的重要作用。 板书：恒等式 * C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ C S | S W U S T XDC 勿在浮沙筑高台！ 1.2.1 命题公式的一些基本概念 例 考虑：G1 ：┐(P→Q)→P； G2 ：(P→Q)∧P； G3 ：┐(Ｐ∧┐Ｑ)?┐(P→Q) 解：下面分别列出公式G1 、G2 、G3 的真值表。 P Q ┐(P→Q)→P P Q (P→Q)∧P 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 Ｇ1的真值表： Ｇ2的真值表： 一、命题公式的分类 P Q ┐(Ｐ∧┐Ｑ) ?┐(Ｐ→Q) 0 0 0 0 1 0 1 0 0 1 1 0 G3的真值表： 公式G1对所有可能的解释具有“真”值 公式G3对所有可能的解释均具有“假”值 公式G2则具有“真”和“假”值 定义 公式G1称为永真公式(重言式)，如果在它的所有解释之下都为“真”。 公式G3称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。 公式G2称为可满足的，如果它不是永假的。 从上述定义可知三种特殊公式之间的关系： 永真式G的否定┐G是矛盾式；矛盾式G的否定┐G是永真式。 永真式一定是可满足式,可满足式不一定是永真式。 可满足式的否定不一定为不可满足式(即为永假式)。 列出下列公式的真值表，并验证其是否是永真公式。 (1)．(P→Q) ? (┐P∨Q)； (2)．((P→Q)∧P)→Q。 (3). P?(Q∧R) 解：⑴、⑵、⑶的真值表如下： 例1 (1)、(2)的真值表如下： P Q (P→Q) ? (┐P∨Q) ((P→Q)∧P)→Q 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 例1 公式（1）、（2）都是永真公式 （3）的真值表为： P Q R P?(Q∧R) 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 例（续） 公式（3）是可满足公式。 (1) 永真式的否定是矛盾式, 矛盾式