析取的定理1侷限
- 2022-11-17
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的五種股票,根據當前股市情況及張先生本人的經濟需求,需要