定理的證明思路
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、兩個命題公式等價當且僅當它們有相同的主合取範式或相同的主析取範式。