命題邏輯真值形式

1、.第一章命題邏輯一、真值形式1命題及其真值、原子命題和復(fù)合命題前題及其真值我們已經(jīng)知道， 作為邏輯研究主要對(duì)象的推理， 是一個(gè)命題序列， 是從某個(gè)或某些命題得到某個(gè)命題的思維過(guò)程。那么，什么是命題呢？命題是表達(dá)判斷的語(yǔ)句。所謂判斷，就是人對(duì)思維對(duì)象有所斷定。一切能被人思考的客體都構(gòu)成思維對(duì)象， 簡(jiǎn)稱對(duì)象。 對(duì)象可以是有形的， 也可以是無(wú)形的；可以是物質(zhì)的， 也可以是精神的； 可以是存在的， 也可以是不存在的。 總之， 包羅萬(wàn)象。對(duì)象要能被思考， 必須具有一定的性質(zhì)， 處于定的關(guān)系之中。 對(duì)象的性質(zhì)和對(duì)象之間的關(guān)系統(tǒng)稱對(duì)象的屬性。沒(méi)有屬性的對(duì)象，是不存在的。判斷對(duì)對(duì)象有所斷定，就是斷定對(duì)象具有或

2、不具有某種屬性。判斷用語(yǔ)句的形式表達(dá)出來(lái)，就是命題。例如：(1) 所有不受外力作用的物體都作勻速直線運(yùn)動(dòng)。(2) 上帝是萬(wàn)能的追物主。(3) 如果上帝是萬(wàn)能的造物主，那么他既能又不能造出一塊他自己都無(wú)法舉起的石頭。這些都是命題。命題都有真假。沒(méi)有真假的語(yǔ)切不表達(dá)確定的判斷因而不是命題。命題的真或假，稱為命題的真值。也就是說(shuō)，命題的真值包括兩個(gè)值，一個(gè)值是“真”，另一個(gè)值是“假” 。真命題的真值是“真”，假命題的真值是“假”。原子命題和復(fù)合命題原子命題是不包含和自身不同的命題的命題。例如：(1) 癌癥是遺傳的。(2) 癌癥不是遺傳的。(3) 并非癌癥是遺傳的。(4) 如果癌癥是遺傳的，那么老患癌

3、癥是不可避免的。(5) 老知道癌癥是遺傳的。其中，句 (1) 和句 (2) 是原子命題， 因?yàn)槠渲胁话虾妥陨聿煌拿}，而句 (3) 、句 (4)和句 (5) 不是原子命題，因?yàn)檫@些命題中都包含了和自身不同的命題( 劃?rùn)M線的部分) ，這樣的命題稱為支命題。像句 (3) 、句 (4) 和句 (5) 這樣的命題，雖然都是包含支命題的非原子命題但它們之間存在重要的區(qū)別。 句 (3) 和句 (4) 的真值是由其支命題的真值惟一地確定的，而句 (5) 則不是。如果“癌癥是遺傳的”是真的，則句(3) 是假的；如果“癌癥是遺傳的”是假的，則句(3) 是真的。如果“癌癥是遺傳的”是真的，并且“老患癌癥是不可

4、避免的”是假的，則句(4) 是假的；在支命題的其他真假情況下，句(4)都是真的。句（ 5）的真值卻不是由其支題的真值性地確定的：如果“癌癥是遺傳的”是真的，則句 (5) 可以是真的，也可以是假的。像句 (2) 和句 (4) 這樣的命題，稱為復(fù)合命題。在命題邏聯(lián)中，復(fù)合命題指這樣的命題：第。它包含和自身不同的命題作為支命題；第二，它的真值由其支命題的真值惟一地確定。. .復(fù)合命題的支命題可以是原子命題，也可以是復(fù)合命題。復(fù)合命題最終是出原子命題依據(jù)一定的邏輯關(guān)系構(gòu)成，依據(jù)這種邏輯關(guān)系，原子命題的真值，惟一地確定由其構(gòu)成的復(fù)合命題的真值。表達(dá)這種邏輯關(guān)系的語(yǔ)詞，稱為聯(lián)結(jié)詞。因此，復(fù)合命題的終極構(gòu)成

5、成分只有兩個(gè)，一個(gè)是原子命題，另一個(gè)是聯(lián)結(jié)詞。例如，上例句(3) 中的聯(lián)結(jié)向是“并非” ；句 (4)中的聯(lián)結(jié)詞是“如果，那么”。2真值聯(lián)結(jié)詞·真值形式·常用真值聯(lián)結(jié)詞真值聯(lián)結(jié)詞和真值形式日常語(yǔ)言所表達(dá)的聯(lián)結(jié)問(wèn)，除了表達(dá)原子命題和復(fù)合真假關(guān)系之外，在特定的語(yǔ)境下，還會(huì)表達(dá)其他某些意思。例如：(1) 小和小結(jié)了婚，并見有了孩子。如果交換句 (1) 中兩個(gè)支命題的位置，得到：(2) 小和小有了孩子，并且結(jié)了婚。句 (2) 的含義顯然較之句(1) 有了變化。這說(shuō)明，這里聯(lián)結(jié)詞“并且”除了斷定兩個(gè)支命題都是真的以外，還表達(dá)了其他什么意思。如果只保留聯(lián)結(jié)詞中對(duì)于真假關(guān)系的斷定，我們就從

6、聯(lián)結(jié)詞得到了真值聯(lián)結(jié)詞。因此，真值聯(lián)結(jié)詞是對(duì)聯(lián)結(jié)詞的一種抽象，它刻畫并且只刻畫原子命題和由其構(gòu)成的復(fù)合命題之間的真假關(guān)系。 在命題邏輯中， 真值聯(lián)結(jié)詞用專門的符號(hào)表示。由真值聯(lián)結(jié)詞構(gòu)成的復(fù)合命題的形式結(jié)構(gòu)， 就是真值形式。 例如，句 (1) 的真值形式是pq ，其中，“”是真值聯(lián)結(jié)詞，讀作“合取” ，表示“并且” ； p 和 q 稱作命題變項(xiàng)，表示原子命題。因此，真值形式也就是命題變項(xiàng)和真值聯(lián)結(jié)詞的合式構(gòu)成。單個(gè)命題變項(xiàng)也是真值形式，真值聯(lián)結(jié)詞在其中零次出現(xiàn)。特殊地，如果命題變項(xiàng)和真值聯(lián)結(jié)詞都零次出現(xiàn)，這樣的真值形式稱為空式?？帐揭彩钦嬷敌问健Ｔ谀承﹫?chǎng)合，空式的概念不可缺少。另外，真值形式必須

7、是有限構(gòu)成的，即是有限長(zhǎng)的符號(hào)串。 ，在以后的討論中，p， q，r 表示命題變項(xiàng)，A， B， C表示任意的真值形式。常用真值聯(lián)結(jié)詞這里定義五個(gè)常用真值聯(lián)結(jié)詞，即“ ”、“ ”、“ ”、“ ”和“ ”及相關(guān)的五個(gè)基本真值形式。合取真值形式“ pq”，讀作“ p 合取 q”，斷定： p 和 q 都是真的。也就是說(shuō)p 和 q 中，只要有個(gè)是假的，pq 就是假的?！?p q ”可如下定義：pqp q111100010000上面這樣的表格，稱為真值表。其中，“ 1”表示真，“ o”表示假。真值表列出了在原子命題的每一組真值組合下復(fù)合命題的真值。因此，正如下面將要說(shuō)明的，一個(gè)完整的真值表，就定義了個(gè)真值函

8、數(shù)。不同的真值表，定義不同的真值函數(shù)。以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，下面的等式成立：111；1001000。在日常語(yǔ)言中， “pq ”表述為“ P 并且 q”，“不但P，而且q”等等。合取式相當(dāng)于傳統(tǒng)邏輯中的聯(lián)言命題。. .析取真值形式“ p q ”，讀作“ p 析取 q”，斷定： P 和 q 中至少有一個(gè)是真的。也就是說(shuō)，只有當(dāng) p 和 q 都是假的， pq 才是假的?！?p q ”可如下定義：pqp q111101011000以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，以下的等式成立：11 10 011；000。在日常語(yǔ)言中， “ pq ”表述為“ p 或者 q”。析取式相當(dāng)于傳統(tǒng)邏輯中的相容選

9、言命題。蘊(yùn)涵真值形式“ pq ”，讀作“ P 蘊(yùn)涵 q”，斷定：只有當(dāng)p 真和 q 假時(shí)， pq 才是假的；在其余情況下，pq 都是真的。“ pq ”可如下定義：pqp q111100011001如上定義的蘊(yùn)涵稱為“實(shí)質(zhì)蘊(yùn)涵”。以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，以下的等式成立：10 0；1l=10=00=l 。在日常語(yǔ)言中， “ pq ”表述為“如果P，那么 q”，“只要 P，就 q”，等等。蘊(yùn)涵式相當(dāng)于傳統(tǒng)邏輯中的充分條件假言命題?！?pq ”和“如果 P，那么 q”的含義是有區(qū)別的。 “如果 P，那么 q”除了表示“不會(huì) P 真而 q 假”這種 p 和 q 之間的真假關(guān)系以外，根據(jù)具體的語(yǔ)

10、境，還可能表示P 和 q之間的其他聯(lián)系；而“pq ”除了表示“不會(huì)P 真而 q 假”以外，不表示P 和 q 之間的任何其他聯(lián)系。因此，如果“如果p，那么 q”成立則“pq ”成立：但反過(guò)來(lái)，如果“ p q ”成立， 則“如果 p，那么 q”不一定成立。 在后面的情況下 就會(huì)出現(xiàn)所謂的 “蘊(yùn)涵怪論”。根據(jù)“蘊(yùn)涵”的定義，只有當(dāng)一個(gè)真命題蘊(yùn)涵一個(gè)假命題的時(shí)候，這個(gè)蘊(yùn)涵式才是假的，因此，假命題可以蘊(yùn)涵任何命題，而真命題可以被任何命題蘊(yùn)涵。這樣，因?yàn)椤皬U話是財(cái)富” 是個(gè)假命題， 因此， 它既可以蘊(yùn)涵 “夸夸其談?wù)呖梢猿蔀榘偃f(wàn)富翁” ，又可以蘊(yùn)涵 “夸夸其談?wù)邔⒁回毴缦础?。事實(shí)上，我們可以接受“如果廢

11、話是財(cái)富，那么夸夸其談?wù)呖梢猿蔀榘偃f(wàn)富翁”為真命題，但不能接受“如果廢話是財(cái)富。那么夸夸其談?wù)邔⒁回毴缦础睘檎婷}，特別是不能把這兩個(gè)容正好相悖的命題，同時(shí)接受為真命題。 像“如果廢話是財(cái)富 那么夸夸其談?wù)邔⒁回毴缦础?這樣的在實(shí)質(zhì)蘊(yùn)涵的意義上被確認(rèn)為真，在事實(shí)上難以成立或顯然不能成立的條件命題。就稱為“蘊(yùn)涵怪論”。為了排除蘊(yùn)涵怪論，邏輯學(xué)家定義了一種有別于實(shí)質(zhì)蘊(yùn)涵的“嚴(yán)格蘊(yùn)涵”，從而產(chǎn)生了. .一個(gè)重要的邏輯分支模態(tài)邏輯?；趯?shí)質(zhì)蘊(yùn)涵的一階邏輯不排除蘊(yùn)涵怪論。這里的關(guān)鍵問(wèn)題是， “ pq”不完全等同于“如果 p，那么 q”，而只是對(duì)后者的一種真值抽象。推理和蘊(yùn)涵有著密切的聯(lián)系。我們說(shuō)從前提

12、A 能推出結(jié)論 B，意思就是說(shuō)，如果 A 是真的， 那么 B 就不會(huì)是假的，這正是 A 蘊(yùn)涵 B 的意思。因此， 個(gè)推理的真值形式就是一個(gè)蘊(yùn)涵式。等值真值形式“ pq”，讀作“ p 當(dāng)且僅當(dāng) q”，也讀作“ p 和 q 等值”，斷定： p 和 q 具有相同的真值。“ p q”可如下定義：pqp q111100010001以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，以下的等式成立：11 00=1；10=01=0。在日常語(yǔ)言中， “ p q”表述為“如果 p，那么 q ；并且只有 p 才 q”。等值式相當(dāng)于傳統(tǒng)邏輯中的充分必要條件假言命題。定義所表達(dá)的定義項(xiàng)和被定義項(xiàng)之間的關(guān)系就是種常見的等價(jià)關(guān)系。換句話說(shuō)

13、， 如果兩個(gè)命題之間具有等值關(guān)系，它們是可以互相定義的。顯然，如果 P 蘊(yùn)涵 q，并且 q 蘊(yùn)油 p，則 p 和 q 就是等值的。 反之亦然。也就是說(shuō)“ pq”可定義為“pqqp ”。并非真值形式“p ”，讀作“并非p”，斷定p 和 p 具有不同的真值。“ p ”可如下定義：Pp1001關(guān)于的真值運(yùn)算，以下的等式成立1 0；0 1。 例 完成以下的真值運(yùn)算：10001 解 10001=1101=101=01. .= 1 1=13命題邏輯層次上的自然語(yǔ)言符號(hào)化·復(fù)合命題的真值形式·命題推理及其真值形式復(fù)合命題的真值形式基于上面所定義的常用真值聯(lián)結(jié)詞，就可以在命題邏輯的層次上對(duì)

14、自然語(yǔ)言進(jìn)行符號(hào)化，也就是對(duì)自然語(yǔ)言所表達(dá)的復(fù)合命題和命題推理，抽象出它們的真值形式。把自然語(yǔ)言所表達(dá)的復(fù)合命題翻譯成相應(yīng)的真值形式，其步驟是： 第一， 確定復(fù)合命題所包含的所有不同的原于命題；第二，用同一命題變項(xiàng)表示所有相同的原子命題，用不同的命題變項(xiàng)分別表示所有不同的原子命題( 表示命題變項(xiàng)的符號(hào)是小寫英文字母p、 q、 r 、 s、t ) ；第三，確定復(fù)合命題所斷定的支命題之間的邏輯關(guān)系，并用相應(yīng)的真值聯(lián)結(jié)詞加以表達(dá)；第四，依據(jù)確定的層次，寫出整個(gè)復(fù)合命題的真值形式。下面通過(guò)實(shí)例加以說(shuō)明。 例 1寫出下列各復(fù)合命題的真值形式：(1) 要么總經(jīng)理辭職，要么董事長(zhǎng)承擔(dān)全部責(zé)任。令 P 表示總

15、經(jīng)理辭職，q 表示董事長(zhǎng)承擔(dān)全部責(zé)任。命題(1) 斷定 p 和 q 兩個(gè)命題有且只有一個(gè)為真，因此，其真值形式是：pqpq 。p q 表示傳統(tǒng)邏輯中的相容選言命題；在傳統(tǒng)邏輯中，表示不相容選言命題的聯(lián)結(jié)詞是“要么，要么”。本例說(shuō)明，不相容選言命題“要么P，要么q”的真值形式是pqp q 。(2) 只有確保產(chǎn)品質(zhì)量，企業(yè)才能具備起碼的競(jìng)爭(zhēng)力。令 P 表示 ( 企業(yè) ) 確保產(chǎn)品質(zhì)量， q 表示企業(yè)具備起碼的競(jìng)爭(zhēng)力。命題(2) 斷定 p 是 q 的必要條件，即無(wú)p 則無(wú) q。因此，其真值形式是：pq 。p q 和 p q 分別表示傳統(tǒng)邏輯中的充分條件和充分必要條件假言命題；在傳統(tǒng)邏輯中，表示必要條

16、件假言命題的聯(lián)結(jié)詞是“只有才”。本例說(shuō)明 ，必要條件假言命題“只有 P，才有 q”的真值形式是pq 。 3除非制定的法律都能得到有力的實(shí)施，否則，依法治國(guó)就是一句空話。令 P 表示制定的法律都能得到有力的實(shí)施，q 表示依法治國(guó)是一句空話。命題(3) 的真值形式是：pq 。(4) 明天將舉行全校運(yùn)動(dòng)合，除非天下雨。令 P 表示明天將舉行全校運(yùn)動(dòng)會(huì)，q 表示 ( 明 ) 天下雨。題 (4) 的真值形式是：pq 。 例 2寫出下列各復(fù)合命題的真值形式：(1) 如果恐怖分子的要求能在規(guī)定期限滿足，則全體人質(zhì)就能獲釋；否則，恐怖分子就要?dú)⒑θ速|(zhì)，除非特種部隊(duì)能實(shí)施有效的營(yíng)救。令 p 表示恐怖分子的要求能

17、在規(guī)定期限滿足，q 表示全體人質(zhì)就能獲釋，r 表示恐怖分子 就 要 殺 害 人 質(zhì) ， s表 示 特 種 部 隊(duì) 能 實(shí) 施 有 效 的 營(yíng) 救 。 命 題 (1) 的 真 值 形 式 是 ：pqpsr。也可以寫作pq(psr ) 。事實(shí)上，以后將會(huì)看到，這兩個(gè)形式真值是等值的。. .(2) 如果大在孩子落水的現(xiàn)場(chǎng)但沒(méi)有參加營(yíng)救，那么，或者他看到了孩子落水但卻裝著看不見，或者他確實(shí)不會(huì)游泳。令 P 表示大在孩子落水的現(xiàn)場(chǎng)，q 表示大參加了營(yíng)救，r 表示大看到了孩子落水，s 表示 大 裝 著 看 不 見 孩 子 落 水 ， t表 示 大 會(huì) 游 泳 。 命 題 (2)的 真 值 形 式 是 ：p

18、qrst 。大看到了孩子落水，和大裝著看不見孩子落水，是兩個(gè)沒(méi)有真值關(guān)系的原子命題，必須用不同的命題變項(xiàng)表示。r 表示大看到了孩子落水，r 表示大沒(méi)看到孩子落水，而不表示大裝著看不見孩子落水。(3) 如果光強(qiáng)調(diào)固結(jié)，不強(qiáng)調(diào)斗爭(zhēng)，或者光強(qiáng)調(diào)斗爭(zhēng)，不強(qiáng)調(diào)固結(jié)，就不能達(dá)到既弄清思想又團(tuán)結(jié)同志的目的。令 P 表示強(qiáng)調(diào)團(tuán)結(jié)， q 表示強(qiáng)調(diào)斗爭(zhēng)， r 表示喬清思想， s 表示團(tuán)結(jié)同志 ( 這里都省略了主語(yǔ) ) 。命題 (3) 的真值形式是：pqqprs 。命題推理及其真值形式命題邏輯的中心課題，是研究命題推理的形式結(jié)構(gòu)及其有效性的判定。那么，什么是命題推理呢?看下面兩個(gè)推理：(1) 如果大是作案者，那么他

19、一定有作案動(dòng)機(jī)大沒(méi)有作案動(dòng)機(jī)所以，大不是作案者(2) 所有的作案者都有作案動(dòng)機(jī)大沒(méi)有作案動(dòng)機(jī)所以，大不是作案者這兩個(gè)推理都是有效的，并且有著相同的容。但是。它們之間有著實(shí)質(zhì)性的區(qū)別：推理(1) 的有效性的根據(jù)是命題之間的關(guān)系，而推理 (2) 的有效性的根據(jù)是原子命題部的構(gòu)成要素之間的關(guān)系。像推理 (1) 這樣的推理，稱為命題推理。任命題推理中，事實(shí)上在整個(gè)命題邏輯中，原子命題作為最基本的單位，它的部結(jié)構(gòu)不再分析。求命題推理的真值形式的步驟是：第一，分別號(hào)出各個(gè)前提和結(jié)論的真值形式；第二，用合取號(hào)把各個(gè)前提的真值形式聯(lián)結(jié)起來(lái)，所得的合取式，即是前提的真值形式；第三，用蘊(yùn)涵號(hào)把前面提和結(jié)論的真值形

20、式聯(lián)結(jié)起來(lái)，所得的蘊(yùn)涵式， 即是整個(gè)命題推理的真值形式。 例 3寫出以下命題推理的真值形式：如果上帝不能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭， 則他不是萬(wàn)能的； 如果上帝能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭， 則他同樣不是萬(wàn)能的。 上帝或者能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭，或者不能，二者必居其一。因此，上帝不是萬(wàn)能的。令 P 表示上帝能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭，q 表示上帝是萬(wàn)能的。則該推理的格式是：pqp q p p q它的真值形式是：pqpqppq 。. .4真值聯(lián)結(jié)詞的一般性質(zhì)·真值函數(shù)·n 元真值函數(shù)的總數(shù)·真值聯(lián)結(jié)詞的可定義性、完全性和獨(dú)立性真值函數(shù)

21、所謂函數(shù)，是指在兩個(gè)集合的元素之間建立對(duì)應(yīng)關(guān)系的一種運(yùn)算。設(shè) A 和 B 是兩個(gè)集合，若對(duì)A 中的元素，或元素元組，依據(jù)某種運(yùn)算，能惟一地確定B中的某個(gè)元素與之對(duì)應(yīng)，這就定義了一個(gè)從A 到 B 的 ( 單值 ) 函數(shù)。 A 稱為該函數(shù)的定義域，B 稱為該函數(shù)的值域；定義域上的元素稱為自變量，值域上的元素稱為函數(shù)值。顯然，真值聯(lián)結(jié)詞也是一種函數(shù)，稱為真值函數(shù)。它的定義域和值域都是由“真”“假”兩個(gè)真值構(gòu)成的集合。真值函數(shù)的自變量和函數(shù)值都是真值。對(duì)任真值形式，如果其中命題變項(xiàng)的真值確定了，那么真值形式的真值也就惟一地確定了。也就是說(shuō)，真值形式的值，是真值函數(shù)的函數(shù)值。因此，真值形式也稱為真值函項(xiàng)

22、。在以上定義的五種常用真值聯(lián)結(jié)詞中，“”由一個(gè)命題變項(xiàng)定義，是一元真值函數(shù)；其余的都有兩個(gè)命題變項(xiàng)定義，是二元真值函數(shù)。一般地， 如果由 n 個(gè)命題變項(xiàng)定義的真值函數(shù)，稱為n 元真值函數(shù)，即n 元真值聯(lián)結(jié)詞。n 元真值函數(shù)的總數(shù)上述五個(gè)常用真值聯(lián)結(jié)詞是從人們的日常思維中概括出來(lái)的。現(xiàn)在的問(wèn)題是， 它們是否窮盡了所有的一元、二元真值聯(lián)結(jié)詞？也就是說(shuō)，包括在的一元真值聯(lián)結(jié)詞共有多少個(gè)?包括、和在的二元真值聯(lián)結(jié)詞共有多少個(gè)?一般地， n 元真值聯(lián)結(jié)詞即n 元真值函數(shù)共有多少個(gè)？前面已經(jīng)提到，一個(gè)完整的真值表，定義了一個(gè)確定的真值函數(shù)；不同的真值表， 定義了不同的真值函數(shù)。因此 n 元真值函數(shù)共有多少

23、個(gè)，也就是問(wèn)， 具有 n 個(gè)命題變項(xiàng)的不同的真值表共有多少個(gè)?一個(gè)完整的真值表，有兩個(gè)構(gòu)成要素：第一，要列出命題變項(xiàng)所有不同的真假情況，即要列出所定義的真值函數(shù)自變量的所有取值；第二，對(duì)命題變項(xiàng)所有不同的真假情況，真值函數(shù)都有確定的真值作為函數(shù)值。例如，設(shè)f(p,q)為一二元真值函數(shù)，pqf(p,q)111100010以上的表格就不是一個(gè)完整的真值表，因?yàn)樗鼪](méi)有窮盡命題變項(xiàng)所有的真假情況。事實(shí)上，它遺漏了 p 和 q 都取假值的情況。再如：pqf(p,q)11110001？001以上的表格也不是一個(gè)完整的真值表，因?yàn)閷?duì)命題變項(xiàng)所有的不同的真假情況，真值函數(shù)并非都有確定的真值作為函數(shù)值。因此，要

24、回答具有n 個(gè)命題變項(xiàng)的不同的真值表共有多少個(gè)，無(wú)非是要回答這樣兩個(gè)問(wèn)題：第一， n 個(gè)命題變項(xiàng)所有不同的真假情況共是多少？第二，對(duì)應(yīng)于 n 個(gè)命題變項(xiàng)所有不同的真假情況，作為函數(shù)值共有多少種不同的真值排列？由于每個(gè)每個(gè)命題變項(xiàng)都可以取真或假，因此，一個(gè)命題變項(xiàng)所有不同的真假情況是2. .個(gè)，兩個(gè)命題變項(xiàng)所有不同的真假情況是4 個(gè)，三個(gè)命題變項(xiàng)所有不同的真假情況是8nn個(gè)， 一般地， n 個(gè)命題變項(xiàng)所有不同的真假情況共是2個(gè) 。而對(duì)應(yīng)于命題變項(xiàng)的2種n的每一種，函數(shù)值可以取真或假，因此，對(duì)應(yīng)于命題變項(xiàng)的2種不同的取值，真值函數(shù)共2222n222有（連乘次）種不同的取值。 也就是說(shuō)， n元真值函

25、數(shù)， 共有nn（連乘2次） =2個(gè)。這樣，一元真值聯(lián)接詞，共有4 個(gè)，二元真值聯(lián)接詞，共有16 個(gè)。以下分別是所有一元和二元真值聯(lián)接詞的一覽表。其中，表示f 一元真值聯(lián)接詞， g 表示二元真值聯(lián)接詞。 表 1一元真值聯(lián)接詞一覽表pf 1f 2f 3f 41110001010表 2二元真值聯(lián)接詞一覽表p q g1g2 g3 g4 g5g6g7 g8g9 g10 g11 g12 g13 g14 g15 g16111111111100000000101111000011110000011100110011001100001010101010101010真值聯(lián)接詞的可定義性在表 1 和表 2 中， f

26、 3 即是 ， g2 是 ， g8 是 ， g5 是 ， g7 是。因?yàn)閮蓚€(gè)等值的真值形式是可以互相定義的，因此，f 1 可定義為 pp。f 4 可定義為 pp。f 2 可定義為 p。g3 表示“只有p，才 q”，可定義為pq 。g10 表示“要么p，要么 q”，可定義為pqpq 。. .我們可以用構(gòu)造真值表的方法來(lái)驗(yàn)證，定義右邊的真值形式的真值表，和所要定義的真值函數(shù)的真值表是相同的。這說(shuō)明二者是等值的，是可以互p qpq相定義的。g3例如，以下的真值表說(shuō)明，pq 和 g3111具有相同的真值表，兩者是可以互相定義的：1010100011 1 110 10 1 00 0 1真值聯(lián)結(jié)詞的完全性

27、現(xiàn)在的問(wèn)題是，常用真值聯(lián)結(jié)詞是否能定義所有的一元和二元真值聯(lián)結(jié)詞?或者更一般地，常用真值聯(lián)結(jié)詞是否能定義所有的n 元真值聯(lián)結(jié)詞，回答是肯定的。定義 4 1一組真值聯(lián)結(jié)詞是完全的，當(dāng)且僅當(dāng)由它能定義任一n 元真值聯(lián)結(jié)詞。定理 4 2, ,是完全的。在給出正式的證明以前先分析一個(gè)實(shí)例。不妨討論如何用，和來(lái)定義表2中的二元真值聯(lián)結(jié)詞g4 。 g4 的真值表顯示，g4 (p ， q) 為真，當(dāng)且僅當(dāng)：p 真且 q 真或者p真且 q 假。因此，它顯然可定義為：pqpq 。事實(shí)上，用這種方式，可以，和 來(lái)定義任一 n 元真值聯(lián)結(jié)詞。 證明 設(shè) fp1 , pn 是任一 n 元真值聯(lián)結(jié)詞。顯然，它可以用一個(gè)

28、2n 行的真值表來(lái)定義。 現(xiàn)在考慮在該真值表中函數(shù)值為真的那些行。設(shè)第 i 行 (1 i 2 n ）的函數(shù)值為真，構(gòu)造合取式 Ci: p1ip2ipni , 每一 p ij (j 1， n) 是命題變項(xiàng) p j 或其否定p j ：如果在第 i 行p j 的值是真，則 p ij 就是 p j ；如果在第 i行 p j的值是假，則pij 就是p j 。顯然，當(dāng) p1 , pn 取第 i行的值時(shí)， Ci 的值是真，與f p1 , pn 在第 i行的值相同。令 D 是所有這樣構(gòu)造的合取式C i 的析取。如果fp1 , pn 的值為常真，即在真值表的每一行都真，則D就有 2 n 個(gè)析取支；如果 f p1

29、, pn 的值為真的行數(shù)是 k，則 D 就有 k 個(gè)析取支；如果f p1 , pn的值為常假，即在真值表的每一行都假，這時(shí)令D 為 pp 。對(duì)于這樣構(gòu)造的真值形式D，如果它是真的，則由的定義，可知存在某個(gè)C i (1 i 2 n )為真，又由 C i 的構(gòu)造定義，可知 fp1, , pn為真；如果 fp1 , , pn 為真，則存在某個(gè)i(1 i 2 n ) ， fp1 , pn 在第 i行的值為真，同樣由Ci 的構(gòu)造定義可知Ci 為真，則 D為真。因此，f p1 , pn和 D等值。因?yàn)?D 中只出現(xiàn), , ，又因?yàn)?f p1 , , pn具有. .任意性，因此，, ,是完全的。證畢。自然，

30、,也是完全的。例1 用,和定義以下三元真值函數(shù)fp, q, r：pqrfp, q, r11111100101010010111010100100000上述真值函數(shù)可定義為：p q rpqrp q rp qr 。定理 43,是完全的。證明可 通 過(guò) 構(gòu) 造 真 值 表 驗(yàn) 證 ： pq 可 定 義 為 pq ； p q可定義為pq 。這說(shuō)明運(yùn)用和 可定義和，又因?yàn)? ,是完全的，所以，,是完全的。證畢。定理 44,是完全的。證明pq 可定義為pq。這說(shuō)明運(yùn)用和 可定義。又因?yàn)? ,是完全的，所以，,是完全的。證畢。定理 45,是完全的。證明pq 可定義為pq。與定理 4 4的證明同理，,是完全的。證畢。定理 46,不完全的。這里僅敘述證明的思路，嚴(yán)格的證明可運(yùn)用數(shù)學(xué)歸納法完成?？紤]一個(gè)僅包含,和兩個(gè)不同的命題變項(xiàng)的真值形式。因?yàn)橹话瑑蓚€(gè)命題變項(xiàng)，所以它的真值表是四行；又因?yàn)閮H包含,，所以它在這四行中的真值，有且只有三種不同的情況：第一，都是真；第二都是假；第三，兩行為真，兩行為假。而pq 的真值. .表的四行中， 有三行為真， 一行為假。 這說(shuō)明，不可能由和定義。因此，,是不完全的。定理 47, ,是不完全的。證明不能由， ，和定義。如果能，則存在公式A，pA，A 中只出現(xiàn) p 和 , ,和。因?yàn)?11 11 11 1 11, ，所以，當(dāng)命題變項(xiàng)P的值為 1 時(shí)，