对偶式:如果 $A$ 式子(仅含 $\neg, \vee, \wedge$)中的 与 和 或 兑换、0 和 1 兑换,得到对偶式 $A^*$。
如:$(p\downarrow q)^* \Leftrightarrow p \uparrow q$ 。
对于命题变项的函数 $A$ ,满足:
$\neg A(p_1, p_2, \cdots p_n) \Leftrightarrow A^*(\neg q_1, \neg p_2, \cdots \neg q_n)$
德摩根律是该结论的特殊情况,可以用德摩根律为基础推出该定律(因为任意号处都满足两个德摩根律,所以整个就满足上述定理)
如 $A$ 和 $B$ 具有相同命题变项序列,若 $A \Leftrightarrow B$ ,则 $A^* \Leftrightarrow B^*$ 。
证明:用定理一可以证出。
$A(p_1\cdots p_n) \leftrightarrow B(p_1\cdots p_n)$ 为永真式
故 $A(\neg p_1\cdots \neg p_n) \leftrightarrow B(\neg p_1\cdots \neg p_n)$ 为永真式
故 $\neg A^(p_1\cdots p_n) \leftrightarrow \neg B^(p_1\cdots p_n)$ 为永真式
故 $A^(p_1\cdots p_n) \leftrightarrow B^(p_1\cdots p_n)$ 为永真式
如果将命题公式判断其为永真式、永假式还是可满足式,这类问题称为判定问题。
以前的真值表法和等值演算法不适用于命题变项过多的情况,应该先把命题公式化为标准形:主析取范式和主合取范式。
合取式: 仅由命题变元和 $\wedge$ 构成。
析取式: 仅由命题变元和 $\vee$ 构成。
定义-析取范式:
当且仅当命题公式的形式是: $A_1 \vee A_2 \vee \cdots \vee A_n$ ,其中 $A_i$ 为命题变元或其否定构成的合取式(称为项)。即: $(p_1 \wedge \neg p_2 \wedge \cdots) \vee (\neg p_1 \wedge p_2 \wedge \cdots) \vee \cdots$
定义合取范式:上述 $\vee$ 改成 $\wedge$ 。
任意命题公式都存在(但不唯一存在)与它等值的析取范式或合取范式。步骤如下:
① 消去其他联结词。
$p\rightarrow q \Leftrightarrow \neg p \vee q$
$p\nrightarrow q \Leftrightarrow p \wedge \neg q$
$p \leftrightarrow q \Leftrightarrow (\neg p \vee q) \wedge (p \vee \neg q)$
$p \veebar q \Leftrightarrow (\neg p \wedge q) \vee (p \wedge \neg q)$
$p \uparrow q \Leftrightarrow \neg(p \wedge q)$
$p \downarrow q \Leftrightarrow \neg(p \vee q)$
② 否定号的消去和内移(德·摩根律),使得。
③ 分配律,化成最终结果。
因为范式是不唯一的,所以要想办法化成唯一的了——