析取（逻辑连接词）

析取

逻辑连接词

用连词∨把几个公式连接起来所构成的公式叫做析取，而此析取式的每一组成部分叫做析取项。一些合适公式所构成的任一析取也是一个合适公式。 恒假公式的主析取范式用0表示。定理2.4.2 对于命题公式G，都存在等价于它的主析取范式。定理2.4.4 对于任意公式G，存在唯一一个与G等价的主析取范式。极小项(extremal ~):小项中恰包含n个变量或其否定。

定理的证明思路

1、化成限定性公式；

2、将否定联结词移到命题变量的前面；

3、消除多余的否定联结词；

4、化成合取范式和析取范式。

定理1局限

1、标准化但仅仅是初步的。

2、能够判定是否为永真或永假公式但不方便。

定理2：一个命题公式是永真公式当且仅当与它等价的合取范式的每一个大项中包含了一个命题变量和它的否定；

一个命题公式是永假公式当且仅当与它等价的析取范式的每一个小项中包含了一个命题变量和它的否定；

定义2.4.5 设命题公式G中所有不同原子为P1，…，Pn，如果G的某个析取范式G’中的每一个短语，都是关于P1，…，Pn的一个极小项，则称G’为G的主析取范式。 恒假公式的主析取范式用0表示。

定理2.4.2 对于命题公式G，都存在等价于它的主析取范式。

定理2.4.3 设公式G，H是关于原子P1，…，Pn的两个主析取范式。 如果G，H不完全相同，则G，H不等价。

定理2.4.4 对于任意公式G，存在唯一一个与G等价的主析取范式。令A（a1、a2、……、an）包含有n个变量的公式，极小项(extremal ~):小项中恰包含n个变量或其否定。极大项( extremal ~):大项中恰包含n个变量或其否定。

主合取范式（Unique conjunctive normal form):

若干个极大项的合取。

主析取范式（Unique disjunctive normal form):

若干个极小项的析取。

定理3：令A（a1、a2、……、an）包含有n个变量的公式，则有：

1、如果A存在与之等价的主析取范式，则必唯一；

2、如果A存在与之等价的主合取范式，则必唯一；

3、A是永真公式当且仅当与A等价的主析取范式恰有2n个极小项或没有主合取范式；

4、A是永假公式当且仅当与A等价的主合取范式恰有2n个极大项或没有主析取范式；

5、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。

参考资料

1.谓词演算·自动控制网