定理的證明思路
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也拋出。上述五種條件全部滿足,問有幾種合理的方案供張先生選擇。