《邏輯學基礎教程》版課件-第十章 命題邏輯

第十章命題邏輯

第一章命題邏輯

第一節(jié)命題邏輯概述

命題邏輯是數(shù)理邏輯的基礎部分。它以簡單命題為單位，研究命題經(jīng)邏輯聯(lián)結詞構成的復合命題的邏輯性質以及關于復合命題之間的推理關系。概括地說，它研究邏輯聯(lián)結詞的邏輯性質和相應的推理關系。在命題邏輯中，研究命題時，只將命題分析到簡單命題為止，對于簡單命題中所包含的其他成分不再做分析。在命題邏輯中，重言式

（取值總為真的命題）為數(shù)無窮，它們表達了命題邏輯的邏輯規(guī)律。弄清這些重言式，對于掌握命題邏輯具有極為重要的意義。為了系統(tǒng)地掌握和研究這些邏輯規(guī)律，通常是將全部重言式包括在一個系統(tǒng)之中，用公理化的方法將全部命題邏輯規(guī)律系統(tǒng)化，從而得到一個形式系統(tǒng)。這個形式系統(tǒng)就是命題邏輯的公理系統(tǒng)，即命題演算。為了介紹命題邏輯的公理系統(tǒng)，

這一節(jié)我們需要下面的一些知識。一、命題邏輯聯(lián)結詞

一個有真假的語句稱為命題。凡與客觀情況符合的命題叫做真命題，否則稱為假命題。如：

5是偶數(shù)。王楠是一個乒乓球運動員。

這些都是命題。其中“王楠是一個乒乓球運動員”與客觀事實相符合，我們稱它為一個真命題。而“5是偶數(shù)”與客觀事實不符合，我們稱它為一個假命題。如果我們令p、q等代表命題，并稱它們?yōu)槊}變項，那么，p可以表示“王楠是一個乒乓球運動員”，也可以表示“5是偶數(shù)”。命題變項取值的集合是｛真，假｝——真值的集合。即

真和假統(tǒng)稱為真值。亦即真是真值，假也是真值。如果一個命題能正確反映客觀世界，它就是真命題并取真值。否則，它就是假命題并取假值。在下面的討論中，我們將撇開命題的其他屬性，只把命題看作或真或假的語句。一般說來，一個命題，如果其中不再包含其他的命題成分，那么就稱它為簡單命題。例如，在前面所舉的幾個

命題中，“王楠是一個乒乓球運動員”，“5是偶數(shù)”等都是簡單命題。一個命題，如果其中至少包含有一個其他命題，那么就稱他為復合命題。如“2是素數(shù)并且3也是素數(shù)”，“并非3是偶數(shù)”等等，這些都是復合命題。前一個例子中包含兩個簡單命題，即“2是素數(shù)”和“3也是素數(shù)”。后面的例子中包含一個簡單命題，即“3是偶數(shù)”。組成復合命題的那些命題叫作復合命題的支命題。

把幾個支命題聯(lián)結起來從而構成一個復合命題的詞項叫做真值聯(lián)結詞。在該課程中，經(jīng)常用到的真值聯(lián)結詞一共有五個。它們是：否定詞（并非）、合取詞（并且）、析取詞（或）、蘊涵詞（如果，則）和等值詞（當且僅當）。關于其他聯(lián)結詞與日常語言中對應的聯(lián)結詞之間的區(qū)別，我們不再討論。由于這五個聯(lián)結詞反映了思維中經(jīng)常

出現(xiàn)的五種復合命題的真假關系，所以我們把這五個聯(lián)結詞叫做基本的真值聯(lián)結詞。由它們構成的真值形式分別叫做否定式（即：┑p,讀作：并非p）、合取式（即：p

q，讀作：p并且q）、析取式（即：p

q，讀作：p或者q）、蘊涵式（即：p

q，讀作：p蘊涵q）和等值式（即：p

q，讀作：p等值于q）。它們所對應的真值表如下：

p┑p

真假假真pqp

qp

qp

qp

q真真真真真真真假假真假假假真假真真假假假假假真真二、真值形式

（一）真值形式任一真值形式都是由前面給出的五個真值聯(lián)結詞和五個基本的真值形式經(jīng)過各種各樣的相互組合所構成。反過來，利用五個真值聯(lián)結詞和五個基本的真值形式，我們可以構造出各種各樣復雜的復合命題形式，即真值形式。這些命題形式

表達了所有的復合命題。對于復合命題的結構和邏輯特征的研究就可以歸結到對這些復合命題的形式結構和邏輯規(guī)律的研究。下面給出一些稍復雜的真值形式的例子。例1┑（p

q）。它表示：并非，p并且q。例2（┑q

┑p）。

它表示：如果非q，那么非p。例3（（p

q）

r）。它表示：如果p或q，那么r。例4（p

┑p）。它表示：p或非p。這是傳統(tǒng)邏輯中排中律的形式結構。例5（p

q）

（q

p）。它表示：p且q，等值于，q且p。

還可以給出更多和更復雜的例子。但是更復雜的例子不容易解釋，我們不再討論了。一個具體的復合命題，不論它多么復雜，都有其形式結構，也都有相應的命題形式。如何求一個具體的復合命題的命題形式？下面將通過兩個例子來說明。

例6某城市只有處理好污水，某城市才能搞好環(huán)境衛(wèi)生。這是一個必要條件假言命題。解：令p：某城市能處理好污水；

q：某城市能搞好環(huán)境衛(wèi)生。上面的命題可以表示為：只有p才q。這等于說，某城市不能處理好污水，那么某城市就不能搞好環(huán)境衛(wèi)生。與此相應的命題形式為：（┑p

┑q）。

例7要么x＜y，要么x＞y，要么x=y。（這里x，y∈Q，Q是有理數(shù)集）這是一個不相容的析取命題。解：這個命題等于說：或者x＜y，或者x＞y，或者x=y，但是三者不能同時為真。與此相應的命題形式為：（（p

┑q

┑r）

（┑p

q

┑r）

（┑p

┑q

r））。這里，我們假設p：x＜y，q：x＞y，r：x=y。

綜合例6和例7，求一個復合命題的命題形式，需要注意兩點：第一，確定組成這個復合命題的命題成分即支命題，把不同的支命題代以不同的命題變項；第二，撇開語言方面比較豐富的內(nèi)容，撇開支命題之間各種具體內(nèi)容的關系，只以真假關系來分析給定的復合命題和它所含的支命題之間的聯(lián)系，然后用五個真值聯(lián)結詞把命題變項聯(lián)結起來，從而表示該復合命題與所含支命題之間的真假聯(lián)系。

在求一個復合命題的真值形式時，我們使用了括號。括號是用來表示復合命題形式中結構關系的，括號內(nèi)的命題形式是該復合命題形式的一個獨立單位。為了以后討論方便，我們約定最外層的一對括號可以省略。對于連續(xù)出現(xiàn)的→，我們采用右結合法。真值聯(lián)結詞的結合力依下列次序遞增：

，

，

，

，┑。

(二)真值表方法

前面，我們曾用真值表給出了五個聯(lián)結詞的定義。這些真值表說明了相應的復合命題與所含支命題之間真假的關系，它們只是一些簡單的形式。對于任一復雜的復合命題形式，我們可以利用五個基本聯(lián)結詞的真值表做出與其復合命題形式相應的真值表，從而說明它與所含的支命題之間的真假關系。任一復合命題，它的真值形式

都是由簡單命題和五個聯(lián)結詞，經(jīng)過有限次的各種各樣的聯(lián)結而逐步構成的。構成過程由簡單到復雜，最后得到所要構成得形式。構造真值表的方法和真值形式的構成過程有密切的聯(lián)系。（1）求作復雜命題形式的真值表真值表的構成包括以下三個步驟：1.找出給定形式里的所有簡單命題，根據(jù)構成過程，由簡而繁地將該形式

地各個組成部分排成一行，最后一個為此形式本身,從而決定該真值表的列數(shù)。2.列出該形式的所有簡單命題的各個取真假值的情況，從而決定真值表的行數(shù)。3.根據(jù)五個聯(lián)結詞的真值表，求出各個組成部分的真值，最后列出此形式的真值。例：求作┑（p

q）的真值表。解：

pqp

q┑（p

q）真真真假真假假真假真假真假假假真例：求作（┑q

┑p）的真值表。解：

pq┑p┑q┑q

┑p

真真假假真真假假真假假真真假真假假真真真例：求作（p

q）

（q

p）的真值表。解：pqp

qq

p（p

q）

（q

p）真真真真真真假假假真假真假假真假假假假真例:求作：p

q

┑（┑p

┑q）的真值表。解：pq┑p┑q┑p

┑q┑（┑p

┑q）p

q

真真假假假真真真真假假真假真真真假真真假假真真真假假真真真假假真（2）聯(lián)結詞的完備性①｛┑，

｝是完備的。pq┑p┑q┑p

┑q┑（┑p

┑q）p

q真真假假假真真真假假真假真真假真真假假真真假假真真真假假∴p

q=df┑（┑p

┑q）

pq┑qp

┑q┑（p

┑q）p

q

真真假假真真真假真真假假假真假假真真假假真假真真∴

p

q=df┑（p

┑q）

p

q=df（p

q）

（qp

）②｛┑，

｝是完備的。pq┑p┑q┑p

┑q┑（┑p

┑q）p

q真真假假假真真真假假真真假假假真真假真假假假假真真真假假∴p

q=df┑（┑p

┑q）

同理可得：

p

q=df┑p

q

p

q=df（p

q）

（qp

）

③｛┑，

｝是完備的。

p

q=df┑p

qp

q=df┑（┑p

┑q）

p

q=df（p

q）

（qp

）（3）從給定的真值表確定真值形式

怎樣從一個給定的真值表來確定該真值表所對應的真值形式呢?下面將介紹兩種方法，一種叫寫真法，另一種叫寫假法。寫真法：首先要在所給的真值表的最后一列里，找出所有取值為真的真值。如：

pqα

真真假真假真

假真真

假假假注：α表示該真值表對應的真值形式。

然后，在取值為真的這些行中，（1）如果命題變項的取值為真，則用合取號把它與其命題變項聯(lián)結起來；（2）如果命題變項的取值為假，

則用合取號把它的否定與其命題變項聯(lián)結起來。如：

pqα

真真假真假

真

---p

┑q

假真真

---┑p

q

假假假最后，再把所得的各部分的真值形式用析取號聯(lián)結起來，這就是該真值表所對應的一個真值形式。如：

（p

┑q）

（┑p

q）。

上式為α的一個表達式。寫假法：首先要在所給的真值表的最后一列里，找出所有取值為假的真值。如：

pqα

真真假真假真假真真假假假

然后，在取值為假的這些行中，（1）如果命題變項的取值為真，則用析取號把它的否定與其命題變項聯(lián)結起來；（2）如果命題變項的取值為假，則用析取號把它與其命題變項聯(lián)結起來。如：

pqα

真真假

---┑p

┑q

真假真假真真假假假

---p

q

最后，再把所得的各部分的真值形式用合取號聯(lián)結起來，這就是該真值表所對應的一個真值形式。如：（┑p

┑q）

（p

q）。

上式也是α的一個表達式。在使用寫真（假）法時，需要注意兩點：第一，采用寫真法時，不能寫出在真值表最后一列的值全為假的情況，即寫真法對此情況失效；采用寫假法時，不能寫出在真值表最后一

列的值全為真的情況，即寫假法對此情況失效。第二，寫真法常用于在真值表的最后一列的值中，真少于假的情況；寫假法常用于在真值表的最后一列的值中，假少于真的情況?，F(xiàn)在，對任意給定的真值形式，不管它多么復雜，我們都可以用真值表方法做出與它對應的真值表。反過來，對任意的真值表，我們可以采用寫真法或寫假法構造出相應的真值表達式。

例8構造下面真值表所對應的一個真值形式α。解：

pqrα

真真真假真真假真真假真假真假假假假真真真假真假假假假真假假假假真

用寫真法寫出的α的真值表達式為：（p

q

┑r）

（┑p

q

r）

（┑p

┑q

┑r）。用寫假法寫出的α的真值表達式為：

（┑p

┑q

┑r）

（┑p

q

┑r）

（┑p

q

r）

（p

┑q

r）

（p

q

┑r）。（三）真值函項

每一真值形式實際上都可以被看作一個函數(shù)，這個函數(shù)的自變元就是其中所含的命題變項，它的定義域和值域都是真值的集合，即｛真，假｝。也就是說，一個函數(shù)，如果其自身的值是真值，其自變元所取的值也是真值，這樣的函數(shù)被稱為真值函項。例如，p

q，┑（┑p

┑q）等都是真值函項。由此可知，每一個真值形式又都是一個真值函項。

現(xiàn)在，我們觀察函數(shù)f（x）=x（x≠0）和g（x）=x2／x（x≠0）。雖然f（x）和g（x）所對應的函數(shù)表達式不同，但它倆的定義域相同，值域也相同。習慣上，我們把f（x）和g（x）看成是一個函數(shù)，即f（x）=g（x）（x≠0）。同樣，雖然真值形式p

q和┑（┑p

┑q）不同，但它們的定義域和值域相同，即它們所含自變項的個數(shù)相同，并且真值表相同。

pqp

q

pq┑（┑p

┑q）真真真真真真真假假真假假假真假假真假假假假假假假我們把具有這種性質的兩個真值形式稱為同一類的真值函項。在同一類的真值函項中任意兩個真值形式都是相互等值的。因此有，p

q等值于┑（┑p

┑q）。

當命題變項的數(shù)目給定之后，不同真值函項類的數(shù)目是有限的。當命題變項的數(shù)目為1時，設命題變項為p，p的真值共有兩種，真和假。即

p

真假在p的每一種取值下，真值函項的取值各有兩種，由此產(chǎn)生不同真值函項

類的數(shù)目有且只有2×2=4種，即

pf1（p）f2（p）f3（p）f4（p）

真真真假假假真假真假其中，f1（p）是一個常真的真值函項，f4（p）是一個常假的真值函項，f2（p）的取值與自變項p的取值一致，f3（p）的取值與p的值恰好相反。

f1（p），f2（p），f3（p）和f4（p）可分別表示為：

f1（p）：p

┑p；f2（p）：p；

f3（p）：┑p；f4（p）：p

┑p。

當命題變項的數(shù)目為2時，設命題變項為p和q，那么p與q組成的所有不同的真值組合共有2×2=22種，即

pqf（p，q）真真真/假真假真/假假真真/假假假真/假

對于變項p和q的每一種真值組合，真值函項f（p，q）的取值又各有兩種真和假。因而當命題變項的數(shù)目為2時，所構成的不同的真值函項的數(shù)目有且只有2×2×2×2=24=16種。下面是這16種真值函項的真值表：

pqf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16真真真真真真真真真真假假假假假假假假真假真真真真假假假假真真真真假假假假假真真真假假真真假假真真假假真真假假假假真假真假真假真假真假真假真假真假

f1至f16的真值表達式分別為：f1：p

┑p；f2：p

q；f3：q

p；f4：p；f5：

p

q；f6：q；f7：p

q；f8：p

q；f9：┑（p

q）；f10：┑（p

q）；f11：┑q；f12：┑（p

q）；f13：┑p；f14：┑（q

p）；f15：┑（p

q）；f16：┑（p

┑p）。

在f1這個真值函項類中，不僅有p

┑p，還有q

┑q，┑p

p，┑q

q以及所有與p

┑p邏輯等值的公式都在p

┑p的真值函項類中。反過來說，在真值表是：

pqf

真真真真假真假真真假假真

的真值函項類中，有無窮多個真值形式，在這無窮多個真值形式中，我們可以任意選擇一個真值形式作為這一類真值函項的一個代表，比如選：p

┑p。當命題變項的數(shù)目為3時，設命題變項為p，q和r，則p，q，r所有不同的真值組合共有2×2×2=23=8種，即：

pqrf（p，q，r）真真真真/假真真假真/假真假真真/假真假假真/假假真真真/假假真假真/假假假真真/假假假假真/假

對于變項p，q和r的每一種組合，真值函項f（p，q，r）的取值又各有兩種：真和假。因而當命題變項的數(shù)目為3時，所構成的不同的真值函有且只有

2×2×2×2×2×2×2×2=28=256

種。限于篇幅，略去這256種真值函項的真值表和真值表達式。

一般地，當命題變項有n個時，其中每一個命題變項有且只有兩種取值。因此，n個命題變項的不同真

值組合共有：

2×2×2×…×2=2n

n個個。對于其中每一種命題變項的真值組合，真值函項的取值又各有兩種，因而不同的真值函項共有

2×2×2×…×2=2

2n

2n個

種?？傊?，當命題變項的數(shù)目確定之后，不同真值函項的種類是有限的，而真值形式的個數(shù)是無限的。一個真值函項可以用不同的真值形式來表示。（四）重言式及其判定方法

1.重言式盡管真值形式的數(shù)目是無限的，但是在變項的數(shù)目給定之后，真值

函項的種類是有限的。從真值表的角度來講，含有2個命題變項的真值形式，能并且只能做出16個不同的真值表。另外，從前面的討論中可以看出，不同的真值函項按所取真值的不同，可以分為下面三類：第一類：永真的，即不論真值函項中所含變項取什么值，真值函項的值總為真。例如，p

﹁p。

第二類：有真有假的，即不論真值函項中所含變項取什么值，真值函項的值有時為真有時為假。例如，p

q。第三類：永假的，即不論真值函項中所含變項取什么值，真值函項的值總為假。如：┑（p

┑p），它們的真值表為：pq┑pp

┑pp

q┑（p

┑p）真真假真真假真假假真假假假真真真假假假假真真假假

習慣上，我們把具有第一類特征的真值形式叫做重言式。它所對應的真值函項叫做重言的真值函項。把具有第二類特征的真值形式叫做可滿足式。把具有第三類特征的真值形式叫做不可滿足式，或永假式，或矛盾式。在命題邏輯中，重言式是人們最感興趣的，因為它所反映的是命題邏輯中的邏輯規(guī)律。從思維和形式結構上來說，可以將重言式分為以下三類：

第一類：有些重言式表示了命題邏輯的思維規(guī)律，如p

┑p是命題邏輯中的排中律，﹁（p

┑p）是命題邏輯中的不矛盾律。第二類：有些重言式還可以表示命題邏輯中正確的推理形式。如下面的推理：如果m2是偶數(shù)，則m是偶數(shù)；

m2

是偶數(shù)；所以，m是偶數(shù)。這是一個正確的假言推理。如果用合取號

將前提聯(lián)結為合取式（p

q）

p，

再用蘊涵號

將前提（p

q）

p和結論q聯(lián)結起來，構成蘊涵式（（p

q）

p）

q，則這一命題形式是重言式。推理的正確性是顯然的。第三類：還有一些重言式是以等值形式出現(xiàn)的，它們又叫重言等值式。這些等值式也表現(xiàn)了命題邏輯的規(guī)律，其中有一些對邏輯演算是很重要的。借助這些規(guī)律可以形成重要的邏輯方法，如求范式等。

除了以上三類之外，還有一些重言式是和我們的實際思維關系不大的，或者說在我們的思維中一般不會出現(xiàn)以這類重言式為形式的命題和推理，但這些重言式在邏輯中仍然有重要的作用。它們往往是借助邏輯演算得到的，或者它們是邏輯演算的出發(fā)點或者中間環(huán)節(jié)。例如，一些命題演算的公理、定理以及在求證定理的過程中得到的公式等等。另外，還有一些重言式從結構上看是無作用或無意義的。它們在思維和邏輯中都不會出現(xiàn)，是人們?yōu)榱艘欢ǖ哪康臉嫵?/p>

的，如┑┑（p

┑p），┑（p

p）等等。不可滿足式或永假式表示邏輯矛盾，它和重言式是相互對立的，所以下面的一些結論是顯然的：（1）一個真值形式是重言式當且僅當它的否定是不可滿足的。（2）一個真值形式是不可滿足的當且僅當它的否定是重言式。（3）一個真值形式不是重言式當且僅當至少在它所含命題變項的一種取值下，其值

為假。（4）一個真值形式是可滿足的當且僅當它不是不可滿足的。（5）重言式一定是可滿足的，反之不然。（6）不可滿足式一定不是重言式，反之不然。

2.重言式的作用（1）判定兩個真值形式是否等值

判定兩個真值形式是否等值，就是判定一個等值式是否為重言式。換句話說，不論其中的命題變項取什么值，這兩個真值形式的值總是同真或者同假。例如，我們已經(jīng)知道，不論p，q各取什么值，p

q與┑（p

┑p）的值同真或者同假。因此，

p

q

┑（p

┑p）是重言式。此時，我們也稱p

q與┑（p

┑p）是同一類的真值函項。而p

q┑

（p

┑p）為重言式等值。

又如：p

q

┑（┑p

┑q）是重言式等值式，因為p

q與┑（┑p

┑q）有相同的真值表：pq┑p┑q┑p

┑q┑（┑p

┑q）p

q

真真假假假真真真假假真假真真假真真假假真真假假真真真假假命題邏輯中常用的等值式有：（1）（p

q）

┑p

q

這個等值式刻畫了

的特征，即“p蘊涵q，等值于，p假或q真”。（2）（p

q）

┑（p

┑q）這個等值式也刻畫了

的特征，即“p蘊涵q，等值于，并非，p真并且q假”。（3）（p

q）

（p

q）

（q

p）這個等值式刻畫了

的特征，即“p當且僅當q，等值于，p蘊涵q并且q蘊涵p”。（4）p

q

q

p

這是析取交換律，即“p或q，等值于，q或p”。（5）p

q

q

p

這是合取交換律，即“p并且q，等值于，q并且p”。（6）（p

q）

r

p

（q

r）這是析取結合律，即“（p或q）或r

，等值于，p或（q或r

）”。（7）（p

q）

r

p

（q

r）這是合取結合律，即“（p并且q）并且r

，等值于，p并且（q并且r

）”。（8）p

（q

r）

（p

q）（p

r）這是合取對析取的分配律，即“（p并且（q或r），等值于，（p并且q）或者（p并且r

）”。（9）p

（q

r）

（p

q）

（p

r）這是析取對合取的分配律，即“（p或（q并且r），等值于，（p或q）并且（p或r

）”。（10）┑（p

q）

┑p

┑q

這是德?摩根律之一，即“并非（p或q），等值于，非p并且非q”。（11）┑（p

q）

┑p

┑q

這是德?摩根律之一，即“并非（p并且q），等值于，非p或非q”。（12）p

┑┑p

這是雙重否定原則，即“p，等值于，非非p”。（13）（p

q）（┑q

┑p）這是假言易位原則，即“p蘊涵q，等值于，非q蘊涵非p”。（2）判定一個推理形式是否正確判定一個推理形式是否正確，就是判定一個蘊涵式是否為重言式。一個推理由前提和結論兩部分組成。如果一個推理形式是正確的，那么由前提真必然能得出結論真。因此，前提與結論之間的關系是蘊涵關系。所以，我們可以用一個蘊涵式來表示推理形式，而這個蘊涵式的前件是各個前提的合取，后件是結論。如果推理形式是正確的，那么相應的蘊涵式就是一個重言式。因為正確的推理形式是不依賴于

前提和結論的具體內(nèi)容的，所以相應的蘊涵式必須對于所含命題變項的任何取值，取值總為真。觀察下面的兩個推理形式及相應的真值表：（1）如果p，那么q；所以，如果非q，那么非p。這是一個假言易位推理，和這個推理形式相應的蘊涵式為：（p

q）

（┑q

┑p）它的真值表為：pq┑p┑qp

q┑q

┑pα真真假假真真真真假假真假假真假真真假真真真假假真真真真真由于（p

q）（┑q

┑p）為重言式，所以，此推理形式是正確的。（2）如果p，那么q；非p；所以，非q。和這個推理形式相應的蘊涵式為：（（p

q）

┑p）

┑q它的真值表為：pq┑p┑qp

q（p

q）

┑pα

真真假假真假真真假假真假假真假真真假真真假假假真真真真真

由于（（p

q）

┑p）

┑q不是重言式，所以，此推理形式是不正確的。3.重言式的判定方法

(1)簡化真值表方法

一個真值形式不論多么復雜，我們都可以用真值表方法判斷它是不是一個重言式。但是，當它的構造比較復雜，或者所含命題變項的個數(shù)比較多時，構造它的真值表就是一件比較麻煩的事情。為此，這里給出一種比較簡便的判定方法：簡化

真值表方法，也叫賦值歸謬法。它是以真值表方法為基礎的。這種方法特別適合于蘊涵式。簡化真值表方法的主要思想是：不論該蘊涵式的命題變項各取什么值，都不能使它的前件為真后件為假。這種方法也就是反證法。具體做法是將所給蘊涵式的前件賦值真，后件賦值假。在這種賦值下，如果能導致矛盾的結果，從而就證明了該蘊涵式的前件真后件假是不可能的，因此要判定的蘊涵式就是一個重言式。如果不能導致矛盾的結果，那么所要判定的蘊涵

式就不是一個重言式。例9用簡化真值表方法判斷：（q

r）

（p

q

p

r）是否重言式。解：簡化真值表略！當（q

r）

（p

q

p

r）為假時，得出p亦真亦假，這是不可能的。故（q

r）

（p

q

p

r）是一個重言式。例10用簡化真值表方法判斷：p

q

q

p是否重言式。解：簡化真值表略！當p

q

q

p為假時，由q假，q真，矛盾。此式是一重言式。

例11用簡化真值表方法判斷：（（p

q）

┑p）

┑q是否重言式。

解：（（p

q）

┑p）

┑q┊①┊假┊（假設）②┊真┊假┊③真真┊真④假當p假q真時，（（p

q）

┑p）

┑q為假，故（（p

q）

┑p）

┑q不是重言式。

現(xiàn)在，做α：（（p

q）

┑p）

┑q的真值表：

pq┑p┑qp

q（p

q）

┑pα

真真假假真假真真假假真假假真假

真真假真真假

假假真真真真真

從上面的真值表也可以看出：當p假q真時，該公式的值為假。因此它不是重言式。這與用簡化真值表方法得出的結論是一致的。

簡化真值表方法還可以更簡單一些。如：（（p

q）

┑p）

┑q

假①

（（p

q）

┑p）

┑q

真假假②①②（（p

q）

┑p）

┑q

真真真假假③②③①②（（p

q）

┑p）

┑q

真真真真假假假真

③④②③④①②③(2)真值樹方法真值樹方法也是一種用來判定一個給定的公式（命題形式）是否為重言式的方法。在很多場合中它比真值表和簡化真值表方法更為有效。真值樹的形狀像一棵倒置的樹。這棵樹記做T。T的元素叫結點，每一結點上都放一個有窮的公式集。如圖1-1所示，每個結點屬于惟一的一層，層可以用自然數(shù)標明。如圖1-1所示的真值樹有3層，我們也可以說真值樹的深度為3。這里Фij（i,j=0，1，2，3）是任意有窮的公式集。Ф00叫做真值樹T的始點，Ф21叫做Ф11后繼，Ф31叫做樹T的一個終點。由Ф00，Ф11，Ф21和Ф31組成的這條道路叫真值樹的一個分枝。不同結點上的公式集既可以相同，也可以不同。一棵真值樹有幾個終點，就有幾個分枝。單個的Ф00也叫一棵真值樹（退化的），它既是始點又是終點，它的結點只有一個。所以，這棵真值樹只有一個分枝，就是它自身。T:Ф00

Ф11Ф12Ф13

Ф21Ф22Ф23

Ф31Ф32

真值樹T長出新枝的規(guī)則如下：┑┑規(guī)則：如果在T的一個終止于結點Ф的分枝的公式中有一個公式┑┑α,則附加一個新的結點｛α｝作為Ф的后繼，如下圖所示。

┑┑規(guī)則：┊

︱

┑┑α

┊

︱

α

規(guī)則：如果在T的一個終止于結點Ф的分枝的公式中有一個公式α

β，則附加兩個新的結點｛α｝和｛β｝作為Ф的后繼，如下圖所示。

規(guī)則：┊

︱

α

β

┊

αβ┑

規(guī)則：如果在T的一個終止于結點Ф的分枝的公式中有一個公式┑（α

β），則附加一個新的結點｛┑α，┑β｝作為Ф的后繼，如下圖所示。

┑

規(guī)則：

┊

︱┑（α

β）┊

︱

┑α,┑β

注意：（1）不一定只在各分枝的終點上才使用這些規(guī)則。（2）使用┑┑規(guī)則和┑

規(guī)則時，真值樹不分杈，使用

規(guī)則時真值樹分杈。（3）通常情況下，先使用不分杈的規(guī)則。例11構造┑（┑α

（┑β

α））的真值樹。解：

┑（┑α

（┑β

α））∣┑┑α┑

規(guī)則┑（┑β

α）∣┑┑規(guī)則α∣┑

規(guī)則┑┑β┑α∣┑┑規(guī)則β

這棵真值樹的深度為4，并且只有一個分枝。對公式┑（┑α

（┑β

α））或┑（┑β

α）等還可以再使用﹁

規(guī)則。但是繼續(xù)使用﹁

規(guī)則，產(chǎn)生不出新的公式。因此，在這種情況下，我們就不再繼續(xù)使用該公式來擴充此真值樹。但要在該公式旁畫√，表示該公式已經(jīng)使用過了。于是我們規(guī)定：在某一分枝上的某一公式α在該分枝中用過了，如果不是下列情況之一：①α是┑┑β，而β不是該分枝的公式；②α是（β

γ），而β和γ都不是該分枝的公式；③α是┑（β

γ），而┑β和┑γ二者不同為該分枝的公式。一棵真值樹的分枝是封閉的，如果有一個公式α，使得α和┑α都是該分枝的公式。公式α和┑α叫做用來封閉該分枝。對封閉的分枝，我們規(guī)定：在該分枝下方打叉，即×。

定理Ф的一棵真值樹被稱為Ф的一個反駁，如果它的所有分枝都是封閉的。反駁Ф就是構造Ф的一個反駁。特別地，如果┑α能被反駁，則α是一個重言式。例12用真值樹方法證明：

┑（┑q

r）

（┑（┑p

q）

（┑p

r））

是一個重言式。證明：現(xiàn)在構造

┑（（┑q

r）

（┑（┑p

q）

（┑p

r）））

的一個反駁。

┑（┑（┑q

r）

（┑（┑p

q）

（┑p

r）））√

︱┑┑（┑q

r）√┑（┑（┑p

q）

（┑p

r））√

︱┑q

r√︱┑┑（┑p

q）√┑（┑p

r）√

︱┑p

q√︱

┑┑p√┑r︱p∕＼┑pq×∕＼┑qr××

因為我們能夠構造┑（┑（┑q

r）

（┑（┑p

q）

（┑p

r）））的一個反駁，所以，┑（┑q

r）

（┑（┑p

q）

（┑p

r））是一個重言式。

由聯(lián)結詞

，

和

構成的公式，可以根據(jù)下面的等值式：（α

β）

┑（┑α

┑β）（α

β）

（┑α

β）（α

β）

（α

β）

（β

α）將它們轉換成只用聯(lián)結詞┑和

表示的公式，然后再來構造真值樹。另一方面也可以從┑┑規(guī)則，┑

規(guī)則和

規(guī)則中導出它們的規(guī)則，這些導出規(guī)則是：

規(guī)則：┑

規(guī)則：┊┊

︱︱α

β┑（α

β）┊┊

︱∕＼

α┑α┑ββ

規(guī)則：┑

規(guī)則：┊┊

︱︱α

β┑（α

β）┊︱∕＼α┑αβ┑β

規(guī)則：┑

規(guī)則：┊┊︱︱α

β┑（α

β）┊┊∕＼∕＼

α┑αα┑αβ┑β┑ββ例13用真值樹方法證明（q

r）

（p

q

p

r）是一個重言式。證明：

┑（（q

r）

（p

q

p

r））√

︱q

r√┑（p

q

p

r）√

︱p

q√┑（p

r）√

︱┑p┑r∕＼┑qr∕＼×pq××

因為我們能夠構造┑（（q

r）

（p

q

p

r））的一個反駁，所以（q

r）

（p

q

p

r）是一個重言式。例14用真值樹方法判定

p

（p

（p

q））是否重言式。證明：┑（p

（p

（p

q）））√

︱p┑（p

（p

q））√∕＼┑p