第2章 邏輯和證明

第二章邏輯和證明2.2 命題等價

命題演算：用真值相同的命題取代另一個 在證明時廣泛使用

定義1.永真式（重言式）：真值總是真 矛盾（式）：真值總是假 可能式：真值可真也可假

真值表判定法 例1pp和pp

表2-1永真式和矛盾的例子定義2命題邏輯等價：兩個復(fù)合命題在所有可能的情況下 都有相同真值 是永真式 記為真值表判定法例2證明命題 和 邏輯等價解在表2-2中構(gòu)造了這兩個命題的真值表，由于 和 的真值相同，它們是邏輯等價的。（接下頁）

表2-2 和 的真值表例3

證明命題p∨(q∧r)和(p∨q)∧(p∨r)邏輯等價。這是析取對合取的分配律。證明：表1-11中構(gòu)造了這兩個命題的真值表。因為p∨(q∧r)的真值和(p∨q)∧(p∨r)的真值一樣，它們是邏輯等價的。基本的邏輯等價關(guān)系（1）雙重否定律：

A=A（2）等冪律：AA=A，AA=A（3）交換律：AB=BA,AB=BA（4）結(jié)合律：(AB)C=A(BC) (AB)C=A(BC)（5）分配律：(AB)C=(A

C)(BC)

(AB)C=(AC)(BC)（6）德.摩根律：(AB)=A

B(AB)=A

B（7）吸收律：A(AB)=A A(AB)=A（8）零律： AF=F AT=T（9）一律： AF=A AF=A（10）排中律：A

A=T（11）矛盾律：A

A=F（12）蘊涵等值式：A→B=AB（13）假言易位：A→B=B→A（14）等價等值式：AB=(AB)(BA)基本(p1p2…pn)(p1p2…

pn)命題邏輯等價關(guān)系與基本的集合恒等式的相似性的結(jié)合律與pqrs的含義的結(jié)合律與pqrs的含義 德摩根律的擴展 (p1p2…

pn)(p1p2…

pn)

等值演算：將復(fù)合命題中的一個子命題用與它邏輯等 價的另一個命題替換，不會改變原命題的真值，從而 得到新的邏輯等價的命題例5證明（p（pq））和pq邏輯等價證明：我們有下列等價關(guān)系

（p（pq））=p（pq） 由第二得摩根定律

=p（（p）q） 由第一得摩根定律

=p（pq） 由雙非律

=（pp）（pq） 由分配律

=F（pq）

=pq

由F的恒等律例6

證明(p∧q)→(p∨q)為永真式。證明： 為證明這個命題是永真式，我們將用邏輯等價證明它邏輯上等價于T。（注意：這也可以用真值表來完成。）

(p∧q)→(p∨q)=?(p∧q)∨(p∨q) =(?p∨?q)∨(p∨q) =?(p∨p)∨(?q∨q) =T∨T =T對偶原理：若兩個命題等價，則它們的對偶命題也等價只含邏輯運算符、和的命題的對偶命題：

、

TF主析取范式和主合取范式 范式：具有某種特殊形式（結(jié)構(gòu)）的命題公式 文字：命題變量或命題變量的否定（如p、p） 主析取范式：析取式，其中的每個析取項都是極小項 極小項：由文字構(gòu)成的合取式，且原命題公式中的每個命題變量都在合取式中出現(xiàn)一次 主合取范式：合取式，其中的每個合取項都是極大項 極大項：由文字構(gòu)成的析取式，且原命題公式中的每個命題變量都在析取式中出現(xiàn)一次任意命題公式都有與之等價的主析取范式和主析取范式從真值表構(gòu)造主析取范式 對應(yīng)于真值表中為真的每一行，在主析取范式中都有一個對應(yīng)的合取式 行中為F的變量在相應(yīng)的合取式中帶有從真值表構(gòu)造主合取范式 對應(yīng)于真值表中為假的每一行，在主合取范式中都有一個對應(yīng)的析取式 行中為T的變量在相應(yīng)的合取式中帶有例命題公式A= 的主析取范式與主合取范式。

真值表：主析取范式：主合取范式：習(xí)題

1.用真值表證明等價