理論基礎：

主合取正規化:若干個極大項的合取。

主析取正規化:若干個極小項的析取。

合取：同真取真，其餘取假，就相當於集合中的取交集；

析取：有真取真，同假取假，就相當於集合中的取並集。

定理：

（1）一個簡單析取式是重言式當且僅當它同時含某個命題變項及它的否定。

（2）一個簡單合取式是矛盾式當且僅當它同時含某個命題變項及它的否定。

定義：

（1）由有限個簡單合取式構成的析取式稱為析取正規化。

（2）由有限個簡單析取式構成的合取式稱為合取正規化。

（3）析取正規化與合取正規化統稱為正規化。

舉例說吧：

例1, 求公式(p∧q)∨r的主析取正規化及主合取正規化。

主析取正規化:

(p∧q)∨r

<==>(p∧q∧(r∨┐r))∨((p∨┐p)∧(q∨┐q)∧r)

<==>(p∧q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r)

<==>(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r

主合取正規化：

(p∧q)∨r

<==>(p∨r)∧(q∨r)

<==>(p∨(q∧┐q)∨r)∧((p∧┐p)∨q∨r)

<==>(p∨q∨r)∧(p∨┐q∨r)∧(p∨q∨r)∧(┐p∨q∨r)

<==>(p∨q∨r)∧(p∨┐q∨r)∧(┐p∨q∨r

從上面的例子你不難看出兩者之間的關係吧!

就是一個主析取正規化轉化為主合取正規化就是取其主析取正規化內不存在的最小項的標號的最大項進行析取,反過來求也是一樣的!

例2，文字：p,┐q,r,q.

簡單析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.

簡單合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q.