一、必要概念
簡單X取式
簡單析取式、簡單合取式，說白了就是不知道這個簡單是個啥？
簡單就是有限
你可以說是公式的長度有限，或者公式包含的命題變項有限，反正就是有限
當然，還都得是析(合)取聯結詞
這個概念有啥用嗎？大抵是沒啥用罷，
X取范式
析取范式、合取范式，這個范，又從何說起？
打個比方：
\[(\ \ \land \ \land \ \ )\ \lor \ (\ \ \land \ \ ) \]這就是個析取范式，( )里都是簡單合取式，再通過析取符號連接起來
由有限個 簡單合取式 組成的析取式，就是析取范式 (沒錯，又是有限)
合取范式同理
主X取范式、極小(大)項
這是激動人心的一步！步入正題了！
首先，主析取范式 比 析取范式 多了個主，它不同在哪呢？
主析取范式的每個簡單合取式中，每個變元都出現了一次，
我們舉個例子：
\[(\ A\land B\land C\ )\ \lor \ (\ \lnot A\land \lnot B\land C\ )\ \lor \ (\ A\land \lnot B\land \lnot C\ ) \]不難看出，在同一個( )內，每個變元都出現了一次
其中
- ( ∧ ∧ ) 是極小項
- ( ∨ ∨ ) 是極大項
記憶法：∧ 是一個不包容的符號，喜歡排斥他人的符號(必須兩邊都為1才為1，要求很苛刻)，因此這個符號越多，包容的越少，故稱極小項，
二、主X取范式的性質
1、每個命題公式都有其唯一主析取范式和主合取范式
2、每個命題公式的主析取范式和主合取范式互補
互補是什么？這會引出個很重要的概念
還記得上一篇文章講到的成真賦值可以用來干嘛嗎？
是的，這和角碼有關！但角碼又是什么？
讓我們先從角碼開始：
\[注意！！！ \]\[從接下來開始， \]\[一切一切的大前提是， \]\[極小項中的變項必須按照字母表順序排列！ \]\[極小項中的變項必須按照字母表順序排列！ \]\[極小項中的變項必須按照字母表順序排列！ \]極小項可以用一種方法來表示，那就是小寫字母m + 角碼
而極小項本身可以轉化為一個二進制數，例如：
\[\lnot P \land \lnot Q \land \lnot R \Longrightarrow 000 \]\[\lnot P \land \lnot Q \land \ \ \ R \Longrightarrow 001 \]再將二進制轉為十進制數，這個數值即為角碼
因此上面的兩個極小項就可以表示為
\[m_0 \]\[m_1 \]那這和成真賦值又有啥關聯呢?讓我們順便插入下一條性質——
3、極小項角碼 = 其公式的成真賦值(插入在第2條性質中講解)
還記得我們說成真賦值是一組數，能讓公式最終成真的一組數
這組數自然也是用二進制來表示每個變項的真與假
當然成真賦值可能有很多，那主析取范式也是由多個極小項析取而來的嘛
在書上說，通過成真賦值求主析取范式的方法，是求主析取范式的方法之一，
而我之所以把它搬到性質這里來，是因為我暫時沒見到什么例題用過這種方法，
我們講回第2條性質本身，既然極小項可以表示為小寫字母m + 角碼
那么極大項自然也可以，極大項可表示為 大寫字母M＋角碼
假設一個公式包含n個變項，那么則有2?種賦值，即2?個角碼
其中一部分屬于極小項，另一部分用于極大項
因此我們說主析取范式和主合取范式互補的意思就是說：
額……舉個栗子吧，
對于一個有3個變項的公式來說，假如主析取范式為
\[m_0 \ \lor \ m_1\ \lor \ m_2\ \lor \ m_7 \]則此公式的主合取范式即為
\[M_3\ \land \ M_4 \ \land \ M_5\ \land \ M_6 \]根據以上，我們也不難得出極大項角碼 = 其公式的成真賦值的反碼
三、求主析取范式
我們既然知道了主析取范式和主合取范式是互補的，那么我們還需要求出其中之一即可
我們可以先大致根據原式的"形狀"選擇出 求哪個更方便一些
不如直接來道例題吧!
我們能看出前面都是一些正常的演算，
其實第一步已經展示出了一些主析取范式的雛形，即從這里開始我決定先求主析取范式
演算到分配律那一行時是一個重要的轉折點
從這里開始主析取范式的框架已經完成，接下來要做的就是硬往里填充，讓簡單合取式被喂養成極小項，也就是讓每一個( )里都包括所有變項
這里有一個很重要的東西 ——怎么塞？
要主析，括號里的就是析取；要主合，括號里的就是合取
話不多說，看圖！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553649.html
標籤：其他
上一篇：📍 Pinpoint 01
下一篇：返回列表