1.5.1 对偶

对偶式:如果 $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)$ 为永真式

1.5.2 范式

如果将命题公式判断其为永真式、永假式还是可满足式,这类问题称为判定问题。

以前的真值表法和等值演算法不适用于命题变项过多的情况,应该先把命题公式化为标准形:主析取范式和主合取范式。

合取式: 仅由命题变元和 $\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)$

② 否定号的消去和内移(德·摩根律),使得。

③ 分配律,化成最终结果。

Untitled

因为范式是不唯一的,所以要想办法化成唯一的了——