第2章 邏輯和證明

第二章邏輯和證明2.2 命題等價(jià)

命題演算：用真值相同的命題取代另一個(gè) 在證明時(shí)廣泛使用

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

真值表判定法 例1pp和pp

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

表2-2 和 的真值表例3

證明命題p∨(q∧r)和(p∨q)∧(p∨r)邏輯等價(jià)。這是析取對(duì)合取的分配律。證明：表1-11中構(gòu)造了這兩個(gè)命題的真值表。因?yàn)閜∨(q∧r)的真值和(p∨q)∧(p∨r)的真值一樣，它們是邏輯等價(jià)的?；镜倪壿嫷葍r(jià)關(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）蘊(yùn)涵等值式：A→B=AB（13）假言易位：A→B=B→A（14）等價(jià)等值式：AB=(AB)(BA)基本(p1p2…pn)(p1p2…

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

pn)(p1p2…

pn)

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

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

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

=p（pq） 由雙非律

=（pp）（pq） 由分配律

=F（pq）

=pq

由F的恒等律例6

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

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

、

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

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

1.用真值表證明等價(jià)