一道关于范式的证明证明主析取范式的否定式等价于主合取范式主合取范式的否定式等价于主析取范式

1个回答

  • 析取范式  定义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等价的主析取范式.

    析取范式

    Major disjunctive (or conjunctive) normal form,its applications

    合取范式(conjunctive normal form):

    若干个大项的合取.

    析取范式(disjunctive normal form):

    若干个小项的析取.

    标准句(standard sentence):合取范式或析取范式

    子句(clause):合取范式中的大项或

    析取范式中的小项.

    定理1:任意一个命题公式都存在与之等价的合取

    范式和析取范式.

    定理的证明思路:

    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、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式.

    例6 张先生手中有代号为A、B、C、D、E的五种股票,根据当前股市情况及张先生本人的经济需求,需要

    有若干个股票抛出,但又必须满足如下复杂的要求:

    (1)若A抛出,则B也抛出;

    (2)B和C要留一种股票且只能留一种;

    (3)C和D要么全抛,要么都不抛;

    (4)D和E两种股票中必然有一种或两种要抛出;

    (5)若E抛出,则A、B也抛出.上述五种条件全部满足,问有几种合理的方案供张先生选择