1.3 命題演算的關(guān)系式

1.3.1 等價(jià)關(guān)系式

定義1.3.1 設(shè)A和B是兩個(gè)命題（或命題公式），若A?B是永真式，則稱命題A和B邏輯等價(jià)，可記為A?B。

A?B是永真式表示命題公式A和B在所有的賦值下都有相同的真值，也就是說命題公式A和B有相同的真值表。因此，可以用真值表判定兩個(gè)命題是否等價(jià)。命題A和B等價(jià)當(dāng)且僅當(dāng)真值表中給出它們真值的兩列完全相同。

例1.3.1 證明p→q和等價(jià)。

證明 表1.3.1是公式p→q和的真值表。

對(duì)于p和q的所有賦值，p→q和的真值都一樣。見表1.3.1。

所以這兩個(gè)公式等價(jià)，即。

?

例1.3.2 證明p∧（q∨r）和（p∧q）∨（p∧r）邏輯等價(jià)。

證明 表1.3.2是公式p∧（q∨r）和（p∧q）∨（p∧r）的真值表。

可以看出公式p∧（q∨r）和（p∧q）∨（p∧r）有相同的真值表，所以它們是等價(jià)的。

?

下面列出了一些重要的等價(jià)關(guān)系，它們都可以通過構(gòu)造真值表來證明。在這些等價(jià)關(guān)系中，1表示真值為真的任意命題常量，0表示真值為假的任意命題常量。

德·摩根律的兩個(gè)邏輯等價(jià)公式很重要，它給出了否定合取和析取的方法。等價(jià)式說明命題變?cè)暮先〉姆穸ǖ葍r(jià)于命題變?cè)姆穸ǖ奈鋈　Ｍ恚葍r(jià)式說明命題變?cè)奈鋈〉姆穸ǖ葍r(jià)于命題變?cè)姆穸ǖ暮先　５隆つΩ蛇€可以擴(kuò)展到多個(gè)變?cè)腥缦卤磉_(dá)式

或

上式可以用數(shù)學(xué)歸納法進(jìn)行證明。

利用上面的等價(jià)關(guān)系式和置換規(guī)則，可以進(jìn)行命題公式的等價(jià)運(yùn)算、命題公式的化簡及推理問題的證明等。

置換規(guī)則 若公式G中的一部分A（包含G中幾個(gè)連續(xù)的符號(hào)）是公式，則稱A為G的子公式；用與A邏輯等價(jià)的公式B置換A不改變公式G的真值。

利用已知的等價(jià)關(guān)系式，將其中的子公式用和它等價(jià)的公式置換可以推出其他一些等價(jià)關(guān)系式，這一過程稱為命題的等價(jià)運(yùn)算。利用命題的等價(jià)運(yùn)算，可以判斷兩個(gè)命題是否等價(jià)，判斷命題公式的類型及進(jìn)行命題公式的化簡等。

例1.3.3 證明p→（q→r）?（p∧q）→r。

證明

例1.3.4 利用命題的等價(jià)運(yùn)算判斷下列公式的類型。

1）

2）p∧（p→q）

3）

解

因此，1）為永假式，2）為可滿足式，3）為永真式。

?

例1.3.5 化簡公式

解

例1.3.5是利用等價(jià)關(guān)系式對(duì)命題公式進(jìn)行化簡的示例，利用等價(jià)關(guān)系式還可以求邏輯電路的輸出及對(duì)邏輯電路進(jìn)行化簡。

例1.3.6 對(duì)于圖1.3.1所示的邏輯電路，可否用更簡單的電路實(shí)現(xiàn)該邏輯關(guān)系？

解 首先寫出圖1.3.1所示邏輯電路的邏輯表達(dá)式，化簡這個(gè)公式

因此，這個(gè)電路的輸出是，可以用更簡單的電路實(shí)現(xiàn)上面電路的邏輯功能，見圖1.3.2。