命題邏輯真值形式

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)如果癌癥是遺傳的，那么老李患癌癥是不可避免的。(5)老

3、李知道癌癥是遺傳的。其中，句(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)成成分只有兩個(gè)，一個(gè)是原子命題，另一個(gè)是聯(lián)結(jié)詞。例如，上例句(3)中的聯(lián)結(jié)向是“并非”；句

5、(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é)了婚，并見(jiàn)有了孩子。如果交換句(1)中兩個(gè)支命題的位置，得到：(2)小張和小李有了孩子，并且結(jié)了婚。句(2)的含義顯然較之句(1)有了變化。這說(shuō)明，這里聯(lián)結(jié)詞“并且”除了斷定兩個(gè)支命題都是真的以外，還表達(dá)了其他什么意思。如果只保留聯(lián)結(jié)詞中對(duì)于真假關(guān)系的斷定，我們就從聯(lián)結(jié)詞得到了真值聯(lián)結(jié)詞。因此，真值聯(lián)結(jié)詞是對(duì)聯(lián)結(jié)詞的一種抽象，它刻畫并且只刻畫原子命題和由其構(gòu)成的復(fù)

6、合命題之間的真假關(guān)系。在命題邏輯中，真值聯(lián)結(jié)詞用專門的符號(hào)表示。由真值聯(lián)結(jié)詞構(gòu)成的復(fù)合命題的形式結(jié)構(gòu)，就是真值形式。例如，句(1)的真值形式是，其中，“”是真值聯(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)合，空式的概念不可缺少。另外，真值形式必須是有限構(gòu)成的，即是有限長(zhǎng)的符號(hào)串。，在以后的討論中，p，q，r表示命題變項(xiàng)，A，B，C表示任意的真值形式。常用真值聯(lián)結(jié)詞這里定義五

7、個(gè)常用真值聯(lián)結(jié)詞，即“”、“”、“”、“”和“”及相關(guān)的五個(gè)基本真值形式。合取真值形式“”，讀作“p合取q”，斷定：p和q都是真的。也就是說(shuō)p和q中，只要有個(gè)是假的，就是假的?！啊笨扇缦露x：p q 1 11 1 00 0 10 0 00上面這樣的表格，稱為真值表。其中，“1”表示真，“o”表示假。真值表列出了在原子命題的每一組真值組合下復(fù)合命題的真值。因此，正如下面將要說(shuō)明的，一個(gè)完整的真值表，就定義了個(gè)真值函數(shù)。不同的真值表，定義不同的真值函數(shù)。以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，下面的等式成立：111；1001000。在日常語(yǔ)言中，“p q”表述為“P并且q”，“不但P，而且q”等等。合取

8、式相當(dāng)于傳統(tǒng)邏輯中的聯(lián)言命題。推薦精選析取真值形式“”，讀作“p析取q”，斷定：P和q中至少有一個(gè)是真的。也就是說(shuō)，只有當(dāng)p和q都是假的，才是假的?！啊笨扇缦露x：p q 1 11 1 01 0 11 0 00以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，以下的等式成立： 1110011；000。在日常語(yǔ)言中，“”表述為“p或者q”。析取式相當(dāng)于傳統(tǒng)邏輯中的相容選言命題。蘊(yùn)涵真值形式“”，讀作“P蘊(yùn)涵q”，斷定：只有當(dāng)p真和q假時(shí)，才是假的；在其余情況下，都是真的。“”可如下定義：p q 1 11 1 00 0 11 0 01如上定義的蘊(yùn)涵稱為“實(shí)質(zhì)蘊(yùn)涵”。以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，以下的等式成立

9、： 100；1 l=10=00=l。在日常語(yǔ)言中，“”表述為“如果P，那么q”，“只要P，就q”，等等。蘊(yùn)涵式相當(dāng)于傳統(tǒng)邏輯中的充分條件假言命題。 “”和“如果P，那么q”的含義是有區(qū)別的?！叭绻鸓，那么q”除了表示“不會(huì)P真而q假”這種p和q之間的真假關(guān)系以外，根據(jù)具體的語(yǔ)境，還可能表示P和q之間的其他聯(lián)系；而“”除了表示“不會(huì)P真而q假”以外，不表示P和q之間的任何其他聯(lián)系。因此，如果“如果p，那么q”成立則“”成立：但反過(guò)來(lái)，如果“”成立，則“如果p，那么q”不一定成立。在后面的情況下就會(huì)出現(xiàn)所謂的“蘊(yùn)涵怪論”。根據(jù)“蘊(yùn)涵”的定義，只有當(dāng)一個(gè)真命題蘊(yùn)涵一個(gè)假命題的時(shí)候，這個(gè)蘊(yùn)涵式才是假的

10、，因此，假命題可以蘊(yùn)涵任何命題，而真命題可以被任何命題蘊(yùn)涵。這樣，因?yàn)椤皬U話是財(cái)富”是個(gè)假命題，因此，它既可以蘊(yùn)涵“夸夸其談?wù)呖梢猿蔀榘偃f(wàn)富翁”，又可以蘊(yùn)涵“夸夸其談?wù)邔⒁回毴缦础薄Ｊ聦?shí)上，我們可以接受“如果廢話是財(cái)富，那么夸夸其談?wù)呖梢猿蔀榘偃f(wàn)富翁”為真命題，但不能接受“如果廢話是財(cái)富。那么夸夸其談?wù)邔⒁回毴缦础睘檎婷}，特別是不能把這兩個(gè)內(nèi)容正好相悖的命題，同時(shí)接受為真命題。像“如果廢話是財(cái)富那么夸夸其談?wù)邔⒁回毴缦础边@樣的在實(shí)質(zhì)蘊(yùn)涵的意義上被確認(rèn)為真，在事實(shí)上難以成立或顯然不能成立的條件命題。就稱為“蘊(yùn)涵怪論”。推薦精選為了排除蘊(yùn)涵怪論，邏輯學(xué)家定義了一種有別于實(shí)質(zhì)蘊(yùn)涵的“嚴(yán)格蘊(yùn)涵”，從

11、而產(chǎn)生了一個(gè)重要的邏輯分支模態(tài)邏輯?；趯?shí)質(zhì)蘊(yùn)涵的一階邏輯不排除蘊(yùn)涵怪論。這里的關(guān)鍵問(wèn)題是，“pq”不完全等同于“如果p，那么q”，而只是對(duì)后者的一種真值抽象。 推理和蘊(yùn)涵有著密切的聯(lián)系。我們說(shuō)從前提A能推出結(jié)論B，意思就是說(shuō)，如果A是真的，那么B就不會(huì)是假的，這正是A蘊(yùn)涵B的意思。因此，個(gè)推理的真值形式就是一個(gè)蘊(yùn)涵式。等值真值形式“q”，讀作“p當(dāng)且僅當(dāng)q”，也讀作“p和q等值”，斷定：p和q具有相同的真值。“pq”可如下定義： p qq 1 11 1 00 0 10 0 01以上的真值表說(shuō)明，關(guān)于的真值運(yùn)算，以下的等式成立： 1100=1；10=01=0。在日常語(yǔ)言中，“pq”表述為“如果

12、p，那么q ；并且只有p才q”。等值式相當(dāng)于傳統(tǒng)邏輯中的充分必要條件假言命題。定義所表達(dá)的定義項(xiàng)和被定義項(xiàng)之間的關(guān)系就是種常見(jiàn)的等價(jià)關(guān)系。換句話說(shuō)，如果兩個(gè)命題之間具有等值關(guān)系，它們是可以互相定義的。顯然，如果P蘊(yùn)涵q，并且q蘊(yùn)油p，則p和q 就是等值的。反之亦然。也就是說(shuō)“pq”可定義為“”。并非真值形式“”，讀作“并非p”，斷定和p具有不同的真值。“”可如下定義： P 1001關(guān)于的真值運(yùn)算，以下的等式成立10；01。例完成以下的真值運(yùn)算：解 = = =推薦精選 = =13命題邏輯層次上的自然語(yǔ)言符號(hào)化·復(fù)合命題的真值形式·命題推理及其真值形式復(fù)合命題的真值形式基于上面

13、所定義的常用真值聯(lián)結(jié)詞，就可以在命題邏輯的層次上對(duì)自然語(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)

14、承擔(dān)全部責(zé)任。令P表示總經(jīng)理辭職，q表示董事長(zhǎng)承擔(dān)全部責(zé)任。命題(1)斷定p和q兩個(gè)命題有且只有一個(gè)為真，因此，其真值形式是：。pq表示傳統(tǒng)邏輯中的相容選言命題；在傳統(tǒng)邏輯中，表示不相容選言命題的聯(lián)結(jié)詞是“要么，要么”。本例說(shuō)明，不相容選言命題“要么P，要么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和pq分別表示傳統(tǒng)邏輯中的充分條件和充分必要條件假言命題；在傳統(tǒng)邏輯中，表示必要條件假言命題的聯(lián)結(jié)詞是“只有才”。本例說(shuō)明，必要條件假言命題“

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

16、式是：。也可以寫作。事實(shí)上，以后將會(huì)看到，這兩個(gè)形式真值是等值的。(2)如果大張?jiān)诤⒆勇渌默F(xiàn)場(chǎng)但沒(méi)有參加營(yíng)救，那么，或者他看到了孩子落水但卻裝著看不見(jiàn)，或者他確實(shí)不會(huì)游泳。推薦精選令P表示大張?jiān)诤⒆勇渌默F(xiàn)場(chǎng)，q表示大張參加了營(yíng)救，r表示大張看到了孩子落水，s表示大張裝著看不見(jiàn)孩子落水，t表示大張會(huì)游泳。命題(2)的真值形式是：。大張看到了孩子落水，和大張裝著看不見(jiàn)孩子落水，是兩個(gè)沒(méi)有真值關(guān)系的原子命題，必須用不同的命題變項(xiàng)表示。r表示大張看到了孩子落水，r表示大張沒(méi)看到孩子落水，而不表示大張裝著看不見(jiàn)孩子落水。(3)如果光強(qiáng)調(diào)固結(jié)，不強(qiáng)調(diào)斗爭(zhēng)，或者光強(qiáng)調(diào)斗爭(zhēng)，不強(qiáng)調(diào)固結(jié)，就不能達(dá)到既弄清思

17、想又團(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)的真值形式是：。命題推理及其真值形式命題邏輯的中心課題，是研究命題推理的形式結(jié)構(gòu)及其有效性的判定。那么，什么是命題推理呢?看下面兩個(gè)推理：(1)如果大張是作案者，那么他一定有作案動(dòng)機(jī) 大張沒(méi)有作案動(dòng)機(jī) 所以，大張不是作案者(2)所有的作案者都有作案動(dòng)機(jī) 大張沒(méi)有作案動(dòng)機(jī) 所以，大張不是作案者這兩個(gè)推理都是有效的，并且有著相同的內(nèi)容。但是。它們之間有著實(shí)質(zhì)性的區(qū)別：推理(1)的有效性的根據(jù)是命題之間的關(guān)系，而推理(2)的有效性的根據(jù)是原子命題內(nèi)部的構(gòu)成要素之間的關(guān)系。像推理(1)這

18、樣的推理，稱為命題推理。任命題推理中，事實(shí)上在整個(gè)命題邏輯中，原子命題作為最基本的單位，它的內(nèi)部結(jié)構(gòu)不再分析。求命題推理的真值形式的步驟是：第一，分別號(hào)出各個(gè)前提和結(jié)論的真值形式；第二，用合取號(hào)把各個(gè)前提的真值形式聯(lián)結(jié)起來(lái)，所得的合取式，即是前提的真值形式；第三，用蘊(yùn)涵號(hào)把前面提和結(jié)論的真值形式聯(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)能的。令

19、P表示上帝能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭，q表示上帝是萬(wàn)能的。則該推理的格式是： 它的真值形式是：。4真值聯(lián)結(jié)詞的一般性質(zhì)·真值函數(shù)·n元真值函數(shù)的總數(shù)·真值聯(lián)結(jié)詞的可定義性、完全性和獨(dú)立性推薦精選 真值函數(shù) 所謂函數(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ù)。它的定義域和值域都是由

20、“真”“假”兩個(gè)真值構(gòu)成的集合。真值函數(shù)的自變量和函數(shù)值都是真值。 對(duì)任真值形式，如果其中命題變項(xiàng)的真值確定了，那么真值形式的真值也就惟一地確定了。也就是說(shuō)，真值形式的值，是真值函數(shù)的函數(shù)值。因此，真值形式也稱為真值函項(xiàng)。 在以上定義的五種常用真值聯(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)的?，F(xiàn)在的問(wèn)題是，它們是否窮盡了所有的一元、二元真值聯(lián)結(jié)詞？也就是說(shuō)，包括在內(nèi)的一元真值聯(lián)結(jié)詞共有多少個(gè)?包

21、括、和在內(nèi)的二元真值聯(lián)結(jié)詞共有多少個(gè)?一般地，n元真值聯(lián)結(jié)詞即n元真值函數(shù)共有多少個(gè)？ 前面已經(jīng)提到，一個(gè)完整的真值表，定義了一個(gè)確定的真值函數(shù)；不同的真值表，定義了不同的真值函數(shù)。因此n元真值函數(shù)共有多少個(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ù)， p qf(p,q) 1 11 1 00 0 10以上的表格就不是一個(gè)完整的真值表，因?yàn)樗鼪](méi)有窮盡命題變項(xiàng)所有的真

22、假情況。事實(shí)上，它遺漏了p和q都取假值的情況。再如： p qf(p,q) 1 11 1 00 0 1？001以上的表格也不是一個(gè)完整的真值表，因?yàn)閷?duì)命題變項(xiàng)所有的不同的真假情況，真值函數(shù)并非都有確定的真值作為函數(shù)值。因此，要回答具有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)所有不同的真假情況是8個(gè)，推薦精選一般地，n個(gè)命

23、題變項(xiàng)所有不同的真假情況共是個(gè) 。而對(duì)應(yīng)于命題變項(xiàng)的種的每一種，函數(shù)值可以取真或假，因此，對(duì)應(yīng)于命題變項(xiàng)的種不同的取值，真值函數(shù)共有（連乘次）種不同的取值。也就是說(shuō)，n元真值函數(shù)，共有（連乘次）=個(gè)。這樣，一元真值聯(lián)接詞，共有4個(gè)，二元真值聯(lián)接詞，共有16個(gè)。以下分別是所有一元和二元真值聯(lián)接詞的一覽表。其中，表示f一元真值聯(lián)接詞，g表示二元真值聯(lián)接詞。表1 一元真值聯(lián)接詞一覽表 1 11000 101 0表2 二元真值聯(lián)接詞一覽表111111111100000000101111000011110000011100110011001100001010101010101010真值聯(lián)接詞的可定義性在

24、表1和表2中，即是，是，是，是，是。因?yàn)閮蓚€(gè)等值的真值形式是可以互相定義的，因此，可定義為pp。可定義為pp。可定義為p。表示“只有p，才q”，可定義為。表示“要么p，要么q”，可定義為。推薦精選pq111101010001我們可以用構(gòu)造真值表的方法來(lái)驗(yàn)證，定義右邊的真值形式的真值表，和所要定義的真值函數(shù)的真值表是相同的。這說(shuō)明二者是等值的，是可以互相定義的。例如，以下的真值表說(shuō)明，和具有相同的真值表，兩者是可以互相定義的： 真值聯(lián)結(jié)詞的完全性現(xiàn)在的問(wèn)題是，常用真值聯(lián)結(jié)詞是否能定義所有的一元和二元真值聯(lián)結(jié)詞?或者更一般地，常用真值聯(lián)結(jié)詞是否能定義所有的n元真值聯(lián)結(jié)詞，回答是肯定的。定義41 一

25、組真值聯(lián)結(jié)詞是完全的，當(dāng)且僅當(dāng)由它能定義任一n元真值聯(lián)結(jié)詞。定理42 是完全的。在給出正式的證明以前先分析一個(gè)實(shí)例。不妨討論如何用，和來(lái)定義表2中的二元真值聯(lián)結(jié)詞。的真值表顯示， (p，q)為真，當(dāng)且僅當(dāng)：p真且q真或者p真且q假。因此，它顯然可定義為：。事實(shí)上，用這種方式，可以，和來(lái)定義任一n元真值聯(lián)結(jié)詞。證明 設(shè)是任一n元真值聯(lián)結(jié)詞。顯然，它可以用一個(gè)行的真值表來(lái)定義。現(xiàn)在考慮在該真值表中函數(shù)值為真的那些行。設(shè)第i行(1i）的函數(shù)值為真，構(gòu)造合取式每一(j1，n)是命題變項(xiàng)或其否定：如果在第i行的值是真，則就是；如果在第i行的值是假，則就是。顯然，當(dāng)取第i行的值時(shí)，的值是真，與在第i行的值

26、相同。令D是所有這樣構(gòu)造的合取式的析取。如果的值為常真，即在真值表的每一行都真，則D就有個(gè)析取支；如果的值為真的行數(shù)是k，則D就有k個(gè)析取支；如果的值為常假，即在真值表的每一行都假，這時(shí)令D為。對(duì)于這樣構(gòu)造的真值形式D，如果它是真的，則由的定義，可知存在某個(gè)(1i)為真，又由的構(gòu)造定義，可知為真；如果為真，則存在某個(gè)i(1i)，在第i行的值為真，同樣由的構(gòu)造定義可知為真，則D為真。因此，和D等值。因?yàn)镈中只出現(xiàn)，又因?yàn)橥扑]精選具有任意性，因此，是完全的。證畢。自然，也是完全的。例1 用和定義以下三元真值函數(shù)： 11111100101010010111010100100000 上述真值函數(shù)可定義

27、為：。定理43 是完全的。證明 可通過(guò)構(gòu)造真值表驗(yàn)證：可定義為；pq可定義為。這說(shuō)明運(yùn)用和可定義和，又因?yàn)槭峭耆?，所以，是完全的。證畢。定理44 是完全的。證明 pq可定義為。這說(shuō)明運(yùn)用和可定義。又因?yàn)槭峭耆?，所以，是完全的。證畢。定理45 是完全的。證明 pq可定義為。與定理44的證明同理， 是完全的。證畢。定理46 不完全的。這里僅敘述證明的思路，嚴(yán)格的證明可運(yùn)用數(shù)學(xué)歸納法完成。考慮一個(gè)僅包含和兩個(gè)不同的命題變項(xiàng)的真值形式。因?yàn)橹话瑑蓚€(gè)命題變項(xiàng)，所以它的真值表是四行；又因?yàn)閮H包含，所以它在這四行中的真值，有且只有三種不同的情況：第一，都是真；第二都是假；第三，兩行為真，兩行為假。而推薦精選的真值表的四行中，有三行為真，一行為假。這說(shuō)明，不可能由和定義。因此，是不完全的。定理47 是不完全的。證明 不能由，和定義。如果能，則存在公式A，A中只出現(xiàn)p和和。因?yàn)?，所以，?dāng)命題變項(xiàng)P的值為1時(shí)，A的值為l，而P的值為0。這說(shuō)明，不能由，和定義。證畢。因此，包含是某組常用真值聯(lián)結(jié)詞滿足