命题逻辑等值演算

等值式

若等价式 $A\leftrightarrow B$ 式重言式, 则称 $A$ 与 $B$ 等值, 记作 $A\iff B$, 称为等值式.

基本等值式

双重否定律 $\neg \neg A\iff A$ 幂等律 $A\wedge A\iff A$, $A\vee A\iff A$ 交换律 $A\wedge B\iff B\wedge A$, $A\vee B\iff B\vee A$ 结合律 $(A\wedge B)\wedge C\iff A\wedge (B\wedge C)$, $(A\vee B)\vee C\iff A\vee (B\vee C)$ 分配律 $A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$, $A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$ 德摩根律 $\neg (A\vee B)\iff \neg A\wedge \neg B$, $\neg (A\wedge B)\iff \neg A\vee \neg B$ 吸收律 $A\wedge (A\vee B)\iff A$, $A\vee (A\wedge B)\iff A$ 零律 $A\wedge 0\iff 0$, $A\vee 1\iff 1$ 同一律 $A\wedge 1\iff A$, $A\vee 0\iff A$ 排中律 $A\vee \neg A\iff 1$ 矛盾律 $A\wedge \neg A\iff 0$ 蕴含等值式 $A\to B\iff \neg A\vee B$ 等价等值式 $A\leftrightarrow B\iff (A\to B)\wedge (B\to A)$ 假言易位 $A\to B\iff \neg B\to \neg A$ 等价否定等值式 $A\leftrightarrow B\iff \neg A\leftrightarrow \neg B$ 归谬论 $(A\to B)\wedge (A\to \neg B)\iff \neg A$

指向原始笔记的链接

指向原始笔记的链接

析取范式与合取范式

简单析取式与简单合取式

命题变项及其否定称为文字.

有限个文字构成的析取式称为简单析取式.

有限个文字构成的合取式称为简单合取式.

单个文字既是简单析取式又是简单合取式.

定理 一个简单析取式是重言式当且仅当其同时含有某个命题变项和它的否定式.

定理 一个简单合取式是矛盾式当且仅当其同时含有某个命题变项和它的否定式.

指向原始笔记的链接

由有限个简单合取式组成的析取式称为析取范式.

由有限个简单析取式组成的合取式称为合取范式.

定理 一个析取范式是矛盾式当且仅当每个简单合取式都是矛盾式.

定理 一个合取范式是重言式当且仅当每个简单析取式都是重言式.

定理 任何命题公式都存在与其等值的析取范式和合取范式.

主范式

极小项

在有 $n$ 个命题变项的简单合取式中, 若每个命题变项和否定式都只出现一次, 按二进制由小到大排列, 称为极小项.

极小项以 成真赋值 二进制表达命名.

指向原始笔记的链接

主析取范式

由 极小项 构成的析取范式.

指向原始笔记的链接

极大项

在有  个命题变项的简单析取式中, 若每个命题变项和否定式都只出现一次, 按二进制由小到大排列, 称为极小项.

极大项以 成假赋值 二进制表达命名.

指向原始笔记的链接

主合取范式

由 极大项 构成的合取范式.

指向原始笔记的链接

定理 任何命题公式都存在与之等值的主析取范式和主合取范式, 并且是唯一的.

根据主合取范式和主析取范式中的一项可求出另一项.

指向原始笔记的链接

指向原始笔记的链接

联结词的完备集

与非联结词 $\uparrow$ NAND 或非联结词 $\downarrow$ NOR 不可兼析取 $\bar{\vee }$ XOR

n 元真值函数

称 $F:\{0,1{\}}^n\to \{0,1\}$ 为 $n$ 元真值函数.

$n$ 个命题变项共有 $2^{2^n}$ 个 $n$ 元真值函数.

任何一个含有 $n$ 个命题变项的命题公式 $A$ 都对应唯一的一个 $n$ 元真值函数 $F$, $F$ 恰好为 $A$ 的真值表.

指向原始笔记的链接

定义 设 $S$ 是一个联结词集合, 如果任何 $n$ 元真值函数都可以由仅含 $S$ 中的联结词构成的公式表示, 则称 $S$ 为联结词完备集.

若 $S$ 是联结词完备集, 则任何命题公式都可以由 $S$ 中的联结词表示.

定理 $S=\{\neg ,\wedge ,\vee \}$ 是联结词完备集.

$\{\wedge ,\vee ,\to ,\leftrightarrow \}$ 不是联结词完备集, 因为 0 不能由其表示. 其子集也不是联结词完备集.

定理 $\{\uparrow \}$ 和 $\{\downarrow \}$ 为联结词完备集.

如果联结词完备集 $S$ 中任何一个联结词去掉后都不完备, 则称 $S$ 为最小联结词完备集.

指向原始笔记的链接

可满足性问题和消解法

命题公式的可满足性问题可归结为其 主合取范式 的可满足性问题.

不含有任何问题的简单析取式称为空简单析取式, 规定为不可满足的.

定义 设 $C_1,C_2$ 为两个简单析取式, 且 $C_1=l\vee C_1^{\prime },C_2=l^c\vee C_2^{\prime }$, 其中 $C_1^{\prime },C_2^{\prime }$ 不含 $l,l^c$, 则称 $C_1^{\prime }\vee C_2^{\prime }$ 为 $C_1,C_2$ 以 $l,l^c$ 为消解文字的消解式, 记为 $Res(C_1,C_2)$.

定理 $C_1\wedge C_2\approx Res(C_1,C_2)$.

$C_1\wedge C_2$ 与 $Res(C_1,C_2)$ 有相同的可满足性, 但是不一定等值.

消解序列

定义 设 $S$ 是一个合取范式, $C_1,...,C_n$ 是一个简单析取式序列, 如果对每一个 $i$, $C_i$ 是 $S$ 的一个简单析取式或是 $Res(C_j,C_k)$, 则称此序列是由 $S$ 导出 $C_n$ 的消解序列.

当 $C_n=\lambda$ 时, 称此序列是 $S$ 的一个否证.

指向原始笔记的链接

指向原始笔记的链接