命題邏輯真值形式

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

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

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

4、一地確定的：如果“癌癥是遺傳的”是真的，則句(5)可以是真的，也可以是假的。像句 和句 這樣的命題，稱為復(fù)合命題。在命題邏聯(lián)中，復(fù)合命題指這樣的命題：第一。它包含和自身不同的命題作為支命題； 第二，它的真值由其支Word文檔命題的真值惟一地確定。復(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é)向是“并非”；句（4）中的聯(lián)結(jié)詞是“如果，那么”。

5、2真值聯(lián)結(jié)詞真值形式常用真值聯(lián)結(jié)詞真值聯(lián)結(jié)詞和真值形式日常語(yǔ)言所表達(dá)的聯(lián)結(jié)問，除了表達(dá)原子命題和復(fù)合真假關(guān)系之外，在特定的語(yǔ)境下， 還會(huì)表達(dá)其他某些意思。例如：（1）小和小結(jié)了婚，并見有了孩子。如果交換句（1）中兩個(gè)支命題的位置，得到:（2）小和小有了孩子，并且結(jié)了婚。句（2）的含義顯然較之句（1）有了變化。這說明，這里聯(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ù)合命題之間的真假關(guān)系。在命題邏輯中，真值聯(lián)結(jié)詞用專門的符號(hào)表

6、示。由真值聯(lián)結(jié)詞構(gòu)成的復(fù)合命題的形式結(jié)構(gòu)，就是真值形式。例如，句（1）的真值形式是p q，其中，“ ”是真值聯(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é)詞這里定義五個(gè)常用真值聯(lián)結(jié)詞，即個(gè)基本真值形式。合取真值形

7、式“p只要有一個(gè)是假的，q”，讀作“p合取q”，斷定：p和q都是真的。也就是說p和q中,p q就是假的。p q”可如下定義:pqp q111100010000上面這樣的表格，稱為真值表。其中， “1”表示真，“o”表示假。真值表列出了在原子 命題的每一組真值組合下復(fù)合命題的真值。 因此，正如下面將要說明的，一個(gè)完整的真值表, 就定義了一個(gè)真值函數(shù)。不同的真值表，定義不同的真值函數(shù)。以上的真值表說明，關(guān)于的真值運(yùn)算，下面的等式成立：1 1=1;1 0=0 1=0 0=0。在日常語(yǔ)言中，“pq”表述為“P并且q”，“不但P,而且q”等等。合取式相當(dāng)于和“”及相關(guān)的五Word文檔傳統(tǒng)邏輯中的聯(lián)言命題

8、。Word文檔析取真值形式“p q”讀作“p析取q”斷定：P和q中至少有一個(gè)是真的。也就是說,只有當(dāng)p和q都是假的，p“p q”可如下定義：pqp q111101011000以上的真值表說明，關(guān)于的真值運(yùn)算，以下的等式成立:p q表述為“p或者q”析取式相當(dāng)于傳統(tǒng)邏輯中的相容選言命題。q”讀作“P蘊(yùn)涵q”斷定：只有當(dāng)p真和q假時(shí)，p p q都是真的。p q”可如下定義:pqp q111100011001如上定義的蘊(yùn)涵.稱為“實(shí)質(zhì)蘊(yùn)涵”。以上的真值表說明，關(guān)于的真值運(yùn)算，以下的等式成立：1 0=0;1 1=1 0=0 0=1。在日常語(yǔ)言中，“p q表述為“如果P,那么q” “只要P,就q”等等。

9、蘊(yùn)涵式 相當(dāng)于傳統(tǒng)邏輯中的充分條件假言命題?！皃 q”和“如果P,那么q”的含義是有區(qū)別的?！叭绻鸓,那么q”除了表 示“不會(huì)P真而q假”這種p和q之間的真假關(guān)系以外，根據(jù)具體的語(yǔ)境，還可能表示P和q之間的其他聯(lián)系；而“pq”除了表示“不會(huì)P真而q假”以外，不表示P和q之間的任何其他聯(lián)系。因此，如果“如果p,那么q”成立則“p q”成立：但反過來，如果“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

10、話是 財(cái)富”是個(gè)假命題，因此，它既可以蘊(yùn)涵“夸夸其談?wù)呖梢猿蔀榘偃f(wàn)富翁”，又可以蘊(yùn)涵“夸 夸其談?wù)邔⒁回毴缦础薄Ｊ聦?shí)上，我們可以接受“如果廢話是財(cái)富，那么夸夸其談?wù)呖梢猿?為百萬(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)邏輯。q才是假的。1 1=10=0 1=

11、1；0 0=0。在日常語(yǔ)言中,蘊(yùn)涵真值形式“p的；在其余情況下，q才是假Word文檔基于實(shí)質(zhì)蘊(yùn)涵的一階邏輯不排除蘊(yùn)涵怪論。這里的關(guān)鍵問題是，“p q”不完全等同于“如果p，那么q”，而只是對(duì)后者的一種真值抽象。推理和蘊(yùn)涵有著密切的聯(lián)系。我們說從前提A能推出結(jié)論B,意思就是說，如果A是真的，那么B就不會(huì)是假的，這正是A蘊(yùn)涵B的意思。因此，一個(gè)推理的真值形式就是一 個(gè)蘊(yùn)涵式。等值真值形式“pq”，讀作“p當(dāng)且僅當(dāng)q”，也讀作“p和q等值”，斷定：p和q具有相同的真值?！皃 q”可如下定義：pqpq111100010001以上的真值表說明，關(guān)于的真值運(yùn)算，以下的等式成立：1 1=0 0=1;1 0=

12、0 1=0。在日常語(yǔ)言中，“pq”表述為“如果p，那么q;并且只有p才q”。等值式相當(dāng)于傳統(tǒng)邏輯中的充分必要條件假言命題。定義所表達(dá)的定義項(xiàng)和被定義項(xiàng)之間的關(guān)系就是一種常見的等價(jià)關(guān)系。換句話說，如果兩個(gè)命題之間具有等值關(guān)系，它們是可以互相定義的。顯然， 如果P蘊(yùn)涵q,并且q蘊(yùn)油p,則p和q就是等值的。 反之亦然。 也就是說“p q” 可定義為“p q q p”。并非真值形式“p”，讀作“并非p”，斷定p和p具有不同的真值?！皃”可如下定義：Pp1001關(guān)于 的真值運(yùn)算，以下的等式成立1=0;0=1。例完成以下的真值運(yùn)算：1 0 0 0 1解1000 1=110 1=10 1Word文檔=13命

13、題邏輯層次上的自然語(yǔ)言符號(hào)化復(fù)合命題的真值形式命題推理及其真值形式復(fù)合命題的真值形式基于上面所定義的常用真值聯(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ù)合命題的真值

14、形式。下面通過實(shí)例加以說明。例1寫出下列各復(fù)合命題的真值形式：(1)要么總經(jīng)理辭職，要么董事長(zhǎng)承擔(dān)全部責(zé)任。令P表示總經(jīng)理辭職，q表示董事長(zhǎng)承擔(dān)全部責(zé)任。 命題(1)斷定p和q兩個(gè)命題有且只有一個(gè)為真，因此，其真值形式是：p q p q。p q表示傳統(tǒng)邏輯中的相容選言命題；在傳統(tǒng)邏輯中，表示不相容選言命題的聯(lián)結(jié)詞 是“要么，要么”。本例說明，不相容選言命題“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的必要條件，即無p則無q。因此，其真值形式是：p q。p q和p q分別表示傳統(tǒng)邏輯中的

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

16、獲釋，r表示恐怖分子就要?dú)⒑θ速|(zhì)，s表示特種部隊(duì)能實(shí)施有效的營(yíng)救。命題(1)的真值形式是：p q p s r。也可以寫作p q ( p s r)。事實(shí)上，以后將會(huì)看到，這兩個(gè)形式真值是等值的。命題(3)的真值令P表示明天將舉行全校運(yùn)動(dòng)會(huì),Word文檔(2)如果大在孩子落水的現(xiàn)場(chǎng)但沒有參加營(yíng)救，那么，或者他看到了孩子落水但卻裝著 看不見，或者他確實(shí)不會(huì)游泳。令P表示大在孩子落水的現(xiàn)場(chǎng)，q表示大參加了營(yíng)救，r表示大看到了孩子落水，s表示 大裝著看不見孩子落水，t表示大會(huì)游泳。命題的真值形式是：p q r s t。(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ǔ))。命題的真值形式是：p q q pr s。命題推理及其真值形式命題邏輯的中心課題，是研究命題推理的形式結(jié)構(gòu)及其有效性的判定。那么，什么是命題推理呢？看下面兩個(gè)推理：(1)如果大是作案者，那么他一定有作案動(dòng)機(jī)大沒有作案動(dòng)機(jī)所以，大不是作案者(2)所有的作案者都有作案動(dòng)機(jī)大沒有作案動(dòng)機(jī)所以，大不是作案者這兩個(gè)推理都是有效的，并且有著相同的容。 但是。它們之間有著實(shí)質(zhì)性的區(qū)別：推理(1)的有效性的根據(jù)是命題之間的關(guān)系，而推理(2)的有效性的根據(jù)是原子命題部的構(gòu)成要素之間的關(guān)系。像推理(1)這樣的推理，

18、稱為命題推理。任命題推理中，事實(shí)上在整個(gè)命題邏輯中，原 子命題作為最基本的單位，它的部結(jié)構(gòu)不再分析。求命題推理的真值形式的步驟是：第一，分別號(hào)出各個(gè)前提和結(jié)論的真值形式；第二， 用合取號(hào)把各個(gè)前提的真值形式聯(lián)結(jié)起來，所得的合取式，即是前提的真值形式；第三，用蘊(yùn)涵號(hào)把前面提和結(jié)論的真值形式聯(lián)結(jié)起來，所得的蘊(yùn)涵式，即是整個(gè)命題推理的真值形式。例3寫出以下命題推理的真值形式：如果上帝不能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭，則他不是萬(wàn)能的；如果上帝能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭，則他同樣不是萬(wàn)能的。 上帝或者能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭，或者不能，二者必居其一。因此，上帝不是萬(wàn)能的。令P表示上

19、帝能創(chuàng)造出一塊他自己都不能搬動(dòng)的石頭，q表示上帝是萬(wàn)能的。 則該推理的格式是：p q大看到了孩子落水, 用不同的命題變項(xiàng)表示。 大裝著看不見孩子落水。和大裝著看不見孩子落水,r表示大看到了孩子落水,是兩個(gè)沒有真值關(guān)系的原子命題，必須r表示大沒看到孩子落水，而不表示W(wǎng)ord文檔p q p p q它的真值形式是：p q p q p p q。全性和獨(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ù)的值域；定義域

20、上的元素稱為自變量，值域上的元素稱為函數(shù)值。顯然，真值聯(lián)結(jié)詞也是一種函數(shù)，稱為真值函數(shù)。它的定義域和值域都是由“真”“假”兩個(gè)真值構(gòu)成的集合。真值函數(shù)的自變量和函數(shù)值都是真值。對(duì)任一真值形式，如果其中命題變項(xiàng)的真值確定了，那么真值形式的真值也就惟一地確定了。也就是說，真值形式的值，是真值函數(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é)詞是從人們的日常思維中概括出來的

21、。現(xiàn)在的問題是，它們是否窮盡了所有的一元、二元真值聯(lián)結(jié)詞？也就是說，包括在的一元真值聯(lián)結(jié)詞共有多少個(gè)?包括 、 和 在的二元真值聯(lián)結(jié)詞共有多少個(gè)？一般地，n元真值聯(lián)結(jié)詞.即n元 真值函數(shù)共有多少個(gè)？前面已經(jīng)提到，一個(gè)完整的真值表，定義了一個(gè)確定的真值函數(shù)；不同的真值表，定義 了不同的真值函數(shù)。 因此n元真值函數(shù)共有多少個(gè)， 也就是問，具有n個(gè)命題變項(xiàng)的不同的 真值表共有多少個(gè)？一個(gè)完整的真值表，有兩個(gè)構(gòu)成要素：第一，要列出命題變項(xiàng)所有不同的真假情況， 即要列出所定義的真值函數(shù)自變量的所有取值；第二，對(duì)命題變項(xiàng)所有不同的真假情況，真值函數(shù)都有確定的真值作為函數(shù)值。例如，設(shè)f(p,q)為一二元真值

22、函數(shù),函數(shù)并非都有確定的真值作為函數(shù)值。因此，要回答具有n個(gè)命題變項(xiàng)的不同的真值表共有多少個(gè)，無非是要回答這樣兩個(gè) 問題：第一，n個(gè)命題變項(xiàng)所有不同的真假情況共是多少？第二，對(duì)應(yīng)于n個(gè)命題變項(xiàng)所有不同的真假情況，作為函數(shù)值共有多少種不同的真值排列？4.真值聯(lián)結(jié)詞的一般性質(zhì)真值函數(shù)n元真值函數(shù)的總數(shù)真值聯(lián)結(jié)詞的可定義性、完Word文檔由于每個(gè)每個(gè)命題變項(xiàng)都可以取真或假，因此，一個(gè)命題變項(xiàng)所有不同的真假情況是2個(gè)，兩個(gè)命題變項(xiàng)所有不同的真假情況是4個(gè)，三個(gè)命題變項(xiàng)所有不同的真假情況是8個(gè)，一般地，n個(gè)命題變項(xiàng)所有不同的真假情況共是2個(gè)。而對(duì)應(yīng)于命題變項(xiàng)的2種的每一種，函數(shù)值可以取真或假，因此，對(duì)應(yīng)

23、于命題變項(xiàng)的2種不同的取值，真值函數(shù)共有2 22（連乘2次）種不同的取值。 也就是說，n元真值函數(shù)，共有2 22n ,nA（連乘2次）=2個(gè)。這樣，一元真值聯(lián)接詞，共有4個(gè)，二元真值聯(lián)接詞，共有16個(gè)。以下分別是所有一元和二元真值聯(lián)接詞的一覽表。其中，表示f一元真值聯(lián)接詞，g表示二元真值聯(lián)接詞。表1一元真值聯(lián)接詞一覽表pf1f2f3f41110001010表2二元真值聯(lián)接詞一覽表pqg1g2g3g4g5g6g7g8g9g10g g1：；g1：gg1g1611111111110000000010111100001111000001110011001100110000101010101010101

24、0真值聯(lián)接詞的可定義性在表1和表2中，f 即是 ，g?是 ，g是 ，是 ，g?是 因?yàn)閮蓚€(gè)等值的真值形式是可以互相定義的，因此，fi可定義為pp。f4可定義為PP。f2可定義為P。g3表示“只有p，才q”可定義為p q。gi0表示“要么P,要么q”可定義為p q p q。Word文檔我們可以用構(gòu)造真值表的方法來驗(yàn)證，定義右邊的真值形式的真值表， 和所要定義的真 值函數(shù)的真值表是相同的。 這說明二者是等值的， 是可以互 相定義的。例如，以下的真值表說明，pq和g3具有相同的真值表，兩者是可以互相定義的：真值聯(lián)結(jié)詞的完全性現(xiàn)在的問題是，常用真值聯(lián)結(jié)詞是否能定義所有的一元和二元真值聯(lián)結(jié)詞？或者更一般

25、地，常用真值聯(lián)結(jié)詞是否能定義所有的n元真值聯(lián)結(jié)詞，回答是肯定的。定義4.1一組真值聯(lián)結(jié)詞是完全的，當(dāng)且僅當(dāng)由它能定義任一n元真值聯(lián)結(jié)詞。在給出正式的證明以前先分析一個(gè)實(shí)例。不妨討論如何用 的二元真值聯(lián)結(jié)詞g4。g4的真值表顯示，g4(p,q)為真，當(dāng)且僅當(dāng)：p真且q真.或者p真且q假。因此，它顯然可定義為：p q p q。事實(shí)上，用這種方式，可以和來定義任一n元真值聯(lián)結(jié)詞。證明設(shè)f P!,6是任一n元真值聯(lián)結(jié)詞。顯然，它可以用一個(gè)2n行的真值表來定義?，F(xiàn)在考慮在該真值表中函數(shù)值為真的那些行。設(shè)第i行(1viv2n)的函數(shù)值為真，構(gòu)造合取式Ci: p；p；pn，每一pj(j=1，n)是命題變項(xiàng)P

26、j或其否定Pj：如果在第i行pj的值是真，則p；就是Pj；如果在第i行Pj的值是假，則pj就是Pj。 顯然，當(dāng)p；, , pn取第i行的值時(shí)，Ci的值是真，與f pi, , pn在第i行的值相同。令D是所有這樣構(gòu)造的合取式Ci的析取。如果f P；, ,Pn的值為常真，即在真值表的每一行都真，則D就有2n個(gè)析取支；如果f p；, , Pn的值為真的行數(shù)是k,則D就有k個(gè)析 取支；如果f P；, , Pn的值為常假，即在真值表的每一行都假，這時(shí)令D為P P。對(duì) 于這樣構(gòu)造的真值形式D，如果它是真的，則由 的定義，可知存在某個(gè)Ci(iwi2n)為真，又由Ci的構(gòu)造定義，可知f P；, , Pn為真；

27、如果f P；, , Pn為真，則存在某個(gè)i(1Wiw2n),f p；, , Pn在第i行的值為真， 同樣由Ci的構(gòu)造定義.可知C為真， 貝yD為 真。 因此，f p；, , Pn和D等值。 因?yàn)镈中只出現(xiàn)， ， ，又因?yàn)閒 P；, , Pn具有Pqg3Pq； ； ； ；o；0；0；o0；00o；00；定理4.2是完全的。和來定義表2中Word文檔任意性，因此，是完全的。證畢。自然，也是完全的。例1用，和 定義以下三元真值函數(shù)f p,q,rpqrf p, q, r11111100101010010111010100100000上述真值函數(shù)可定義為：pqr p q r pqr p q r。定理4.

28、3,是完全的。這說明運(yùn)用 _和_可定義_和_,又因?yàn)?是完全的，所以，,是完全的。證畢。定理4.4,是完全的。證明p_q可定義為p q。這說明運(yùn)用和 可定義 。又因?yàn)橥耆模?，是完全的。證畢。定理4.5,是完全的。證明p q可定義為p q。與定理4.4的證明同理，是完全的。證 畢。定理4.6,不完全的。這里僅敘述證明的思路，嚴(yán)格的證明可運(yùn)用數(shù)學(xué)歸納法完成?？紤]一個(gè)僅包含，和兩個(gè)不同的命題變項(xiàng)的真值形式。因?yàn)橹话瑑蓚€(gè)命題變項(xiàng)，所以它的真值表是四行；又因?yàn)閮H包含，所以它在這四行中的真值，有且只有三種不證明可通過構(gòu)造真值表驗(yàn)證:p q可定義為pq;_q可定義為pWord文檔同的情況：第一，都是真；第二.都是假；第三，兩行為真，兩行為假。而p q的真值Word文檔表的四行中，有二行為真，一行為假。這說明，不可能由和定義。因此，是不完全