析取范式與合取范式

《析取范式與合取范式》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、命題常項(xiàng)與命題變項(xiàng)真值確定的命題稱為命題常項(xiàng)或命題常元。例如，下面的，都是命題常項(xiàng)。p：2是素數(shù)。q：雪是黑色的。簡單陳述句中，由于某個或某些成分取值不同而導(dǎo)致該句真值不確定，這種句子稱為命題變項(xiàng)，它不是命題，但這個或這些元素成分一旦取值定下來，句子就成為命題。例　不是命題，但當(dāng)給定與確定的值后，它的真值也就定下來了，它是命題變項(xiàng)。命題變項(xiàng)也用表示之。一個符號，例如，它表示的是命題常項(xiàng)還是命題變項(xiàng)，一般由上下文來確定。一個命題變項(xiàng)經(jīng)符號化后，如符號化為，就可以表示任意的命題。析取范式與合取范式析取用連詞∨把幾個公式連接起來所構(gòu)成的公

2、式叫做析取，而此析取式的每一組成部分叫做析取項(xiàng)。由一些合適公式所構(gòu)成的任一析取也是一個合適公式。合取用連詞∧把幾個公式連接起來而構(gòu)成的公式叫做合取，而此合取式的每個組成部分叫做合取項(xiàng)。一些合適公式所構(gòu)成的任一合取也是一個合取公式。定義命題變項(xiàng)及其否定統(tǒng)稱作文字。僅由有限個文字構(gòu)成的析取式稱為簡單析取式。僅由有限個文字構(gòu)成的合取式稱為簡單合取式。例如，文字：p，┐q，r，q。簡單析取式：p，q，p∨q，p∨┐p∨r，┐p∨q∨┐r。簡單合取式：p，┐r，┐p∧r，┐p∧q∧r，p∧q∧┐q。定理（1）一個簡單析取式是重言式當(dāng)且僅當(dāng)它同

3、時含某個命題變項(xiàng)及它的否定。（2）一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含某個命題變項(xiàng)及它的否定。矛盾式contradictory（矛盾式或永假式）設(shè)A為任一命題公式，若A在它的各種指派情況下，其取值均為假，則稱A是矛盾式或永假式。若命題公式A不是矛盾式，則稱A為可滿足式。重言式Tautology（重言式又稱為永真式）設(shè)A為任一命題公式，若A在它的各種賦值下取值均為真，則稱A是重言式。定義（1）由有限個簡單合取式構(gòu)成的析取式稱為析取范式。（2）由有限個簡單析取式構(gòu)成的合取式稱為合取范式。（3）析取范式與合取范式統(tǒng)稱為范式。例如，析取范

4、式：（p┐∧q）∨r，┐p∧q∧r，p∨┐q∨r。合取范式：(p∨q∨r)∧(┐q∨r)，┐p∧q∧r，p∨┐q∨r。定理（1）一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式。（2）一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式。在布爾邏輯中，析取范式(DNF)是邏輯公式的標(biāo)準(zhǔn)化（或規(guī)范化），它是合取子句的析取。作為規(guī)范形式，它在自動定理證明中有用。一個邏輯公式被認(rèn)為是DNF的，當(dāng)且僅當(dāng)它是一個或多個文字的一個或多個合取的析取。同合取范式（CNF）一樣，在DNF中的命題算子是與、或和非。非算子只能用做文字的一部分

5、，這意味著它只能領(lǐng)先于命題變量。例如，下列公式都是DNF：，，，但如下公式不是DNF：NOT是最外層的算子，一個OR嵌套在一個AND中把公式轉(zhuǎn)換成DNF要使用邏輯等價，比如雙重否定除去、德·摩根定律和分配律。注意所有邏輯公式都可以轉(zhuǎn)換成析取范式。但是，在某些情況下轉(zhuǎn)換成DNF可能導(dǎo)致公式的指數(shù)性爆漲。例如，在DNF形式下，如下邏輯公式有2n個項(xiàng)：在布爾邏輯中，一個公式是合取范式(CNF)的，如果它是子句的合取。作為規(guī)范形式，它在自動定理證明中有用。它類似于在電路理論中的規(guī)范和之積形式。所有的文字的合取和所有的文字的析取是CNF的，因

6、為可以被分別看作一個文字的子句的合取和一個單一子句的合取。和析取范式(DNF)中一樣，在CNF公式中可以包含的命題連結(jié)詞是與、或和非。非算子只能用做文字的一部分，這意味著它只能在命題變量前出現(xiàn)。例如，下列所有公式都是CNF：，，，而下列不是：，，上述三個公式分別等價于合取范式的下列三個公式：，，所有命題公式都可以轉(zhuǎn)換成CNF的等價公式。這種變換基于了關(guān)于邏輯等價的規(guī)則：雙重否定律、德·摩根定律和分配律。因?yàn)樗羞壿嫻蕉伎梢赞D(zhuǎn)換成合取范式的等價公式，證明經(jīng)?；谒泄蕉际荂NF的假定。但是在某些情況下，這種到CNF的轉(zhuǎn)換可能導(dǎo)致公

7、式的指數(shù)性爆漲。例如，把下述非-CNF公式轉(zhuǎn)換成CNF生成有個子句的公式：布爾變量（BooleanVariable）是有兩種邏輯狀態(tài)的變量，它包含兩個值：真和假。如果在表達(dá)式中使用了布爾型變量，那么將根據(jù)變量值的真假而賦予整型值1或0。要把一個整型變量轉(zhuǎn)換成布爾型變量，如果整型值為0，則其布爾型值為假；反之如果整型值為非0，則其布爾型值為真。布爾型變量在運(yùn)行時通常用做標(biāo)志，比如進(jìn)行邏輯測試以改變程序流程。