命題邏輯真值形式

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

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

3、李知道癌癥是遺傳的。其中，句(1)和句(2)是原子命題，因為其中不包合和自身不同的命題，而句(3)、句(4)和句(5)不是原子命題，因為這些命題中都包含了和自身不同的命題(劃橫線的部分)，這樣的命題稱為支命題。像句(3)、句(4)和句(5)這樣的命題，雖然都是包含支命題的非原子命題但它們之間存在重要的區(qū)別。句(3)和句(4)的真值是由其支命題的真值惟一地確定的，而句(5)則不是。如果“癌癥是遺傳的”是真的，則句(3)是假的；如果“癌癥是遺傳的”是假的，則句(3)是真的。如果“癌癥是遺傳的”是真的，并且“老李患癌癥是不可避免的”是假的，則句(4)是假的；在支命題的其他真假情況下，句(4) 都是真

4、的。句（5）的真值卻不是由其支題的真值性地確定的：如果“癌癥是遺傳的”是真的，則句(5)可以是真的，也可以是假的。像句(2)和句(4)這樣的命題，稱為復合命題。在命題邏聯(lián)中，復合命題指這樣的命題：第。它包含和自身不同的命題作為支命題；第二，它的真值由其支命題的真值惟一地確定。推薦精選復合命題的支命題可以是原子命題，也可以是復合命題。復合命題最終是出原子命題依據(jù)一定的邏輯關系構成，依據(jù)這種邏輯關系，原子命題的真值，惟一地確定由其構成的復合命題的真值。表達這種邏輯關系的語詞，稱為聯(lián)結詞。因此，復合命題的終極構成成分只有兩個，一個是原子命題，另一個是聯(lián)結詞。例如，上例句(3)中的聯(lián)結向是“并非”；句

5、(4)中的聯(lián)結詞是“如果，那么”。2真值聯(lián)結詞·真值形式·常用真值聯(lián)結詞真值聯(lián)結詞和真值形式日常語言所表達的聯(lián)結問，除了表達原子命題和復合真假關系之外，在特定的語境下，還會表達其他某些意思。例如：(1)小張和小李結了婚，并見有了孩子。如果交換句(1)中兩個支命題的位置，得到：(2)小張和小李有了孩子，并且結了婚。句(2)的含義顯然較之句(1)有了變化。這說明，這里聯(lián)結詞“并且”除了斷定兩個支命題都是真的以外，還表達了其他什么意思。如果只保留聯(lián)結詞中對于真假關系的斷定，我們就從聯(lián)結詞得到了真值聯(lián)結詞。因此，真值聯(lián)結詞是對聯(lián)結詞的一種抽象，它刻畫并且只刻畫原子命題和由其構成的復

6、合命題之間的真假關系。在命題邏輯中，真值聯(lián)結詞用專門的符號表示。由真值聯(lián)結詞構成的復合命題的形式結構，就是真值形式。例如，句(1)的真值形式是，其中，“”是真值聯(lián)結詞，讀作“合取”，表示“并且”；p和q稱作命題變項，表示原子命題。因此，真值形式也就是命題變項和真值聯(lián)結詞的合式構成。單個命題變項也是真值形式，真值聯(lián)結詞在其中零次出現(xiàn)。特殊地，如果命題變項和真值聯(lián)結詞都零次出現(xiàn)，這樣的真值形式稱為空式?？帐揭彩钦嬷敌问?。在某些場合，空式的概念不可缺少。另外，真值形式必須是有限構成的，即是有限長的符號串。，在以后的討論中，p，q，r表示命題變項，A，B，C表示任意的真值形式。常用真值聯(lián)結詞這里定義五

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

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

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

10、，因此，假命題可以蘊涵任何命題，而真命題可以被任何命題蘊涵。這樣，因為“廢話是財富”是個假命題，因此，它既可以蘊涵“夸夸其談者可以成為百萬富翁”，又可以蘊涵“夸夸其談者將一貧如洗”。事實上，我們可以接受“如果廢話是財富，那么夸夸其談者可以成為百萬富翁”為真命題，但不能接受“如果廢話是財富。那么夸夸其談者將一貧如洗”為真命題，特別是不能把這兩個內(nèi)容正好相悖的命題，同時接受為真命題。像“如果廢話是財富那么夸夸其談者將一貧如洗”這樣的在實質(zhì)蘊涵的意義上被確認為真，在事實上難以成立或顯然不能成立的條件命題。就稱為“蘊涵怪論”。推薦精選為了排除蘊涵怪論，邏輯學家定義了一種有別于實質(zhì)蘊涵的“嚴格蘊涵”，從

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

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

13、所定義的常用真值聯(lián)結詞，就可以在命題邏輯的層次上對自然語言進行符號化，也就是對自然語言所表達的復合命題和命題推理，抽象出它們的真值形式。把自然語言所表達的復合命題翻譯成相應的真值形式，其步驟是：第一，確定復合命題所包含的所有不同的原于命題；第二，用同一命題變項表示所有相同的原子命題，用不同的命題變項分別表示所有不同的原子命題(表示命題變項的符號是小寫英文字母p、q、r、s、t)；第三，確定復合命題所斷定的支命題之間的邏輯關系，并用相應的真值聯(lián)結詞加以表達；第四，依據(jù)確定的層次，寫出整個復合命題的真值形式。下面通過實例加以說明。例1 寫出下列各復合命題的真值形式：(1)要么總經(jīng)理辭職，要么董事長

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

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

16、式是：。也可以寫作。事實上，以后將會看到，這兩個形式真值是等值的。(2)如果大張在孩子落水的現(xiàn)場但沒有參加營救，那么，或者他看到了孩子落水但卻裝著看不見，或者他確實不會游泳。推薦精選令P表示大張在孩子落水的現(xiàn)場，q表示大張參加了營救，r表示大張看到了孩子落水，s表示大張裝著看不見孩子落水，t表示大張會游泳。命題(2)的真值形式是：。大張看到了孩子落水，和大張裝著看不見孩子落水，是兩個沒有真值關系的原子命題，必須用不同的命題變項表示。r表示大張看到了孩子落水，r表示大張沒看到孩子落水，而不表示大張裝著看不見孩子落水。(3)如果光強調(diào)固結，不強調(diào)斗爭，或者光強調(diào)斗爭，不強調(diào)固結，就不能達到既弄清思

17、想又團結同志的目的。令P表示強調(diào)團結，q表示強調(diào)斗爭，r表示喬清思想，s表示團結同志(這里都省略了主語)。命題(3)的真值形式是：。命題推理及其真值形式命題邏輯的中心課題，是研究命題推理的形式結構及其有效性的判定。那么，什么是命題推理呢?看下面兩個推理：(1)如果大張是作案者，那么他一定有作案動機 大張沒有作案動機 所以，大張不是作案者(2)所有的作案者都有作案動機 大張沒有作案動機 所以，大張不是作案者這兩個推理都是有效的，并且有著相同的內(nèi)容。但是。它們之間有著實質(zhì)性的區(qū)別：推理(1)的有效性的根據(jù)是命題之間的關系，而推理(2)的有效性的根據(jù)是原子命題內(nèi)部的構成要素之間的關系。像推理(1)這

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

19、P表示上帝能創(chuàng)造出一塊他自己都不能搬動的石頭，q表示上帝是萬能的。則該推理的格式是： 它的真值形式是：。4真值聯(lián)結詞的一般性質(zhì)·真值函數(shù)·n元真值函數(shù)的總數(shù)·真值聯(lián)結詞的可定義性、完全性和獨立性推薦精選 真值函數(shù) 所謂函數(shù)，是指在兩個集合的元素之間建立對應關系的一種運算。 設A和B是兩個集合，若對A中的元素，或元素元組，依據(jù)某種運算，能惟一地確定B中的某個元素與之對應，這就定義了一個從A到B的(單值)函數(shù)。A稱為該函數(shù)的定義域，B稱為該函數(shù)的值域；定義域上的元素稱為自變量，值域上的元素稱為函數(shù)值。 顯然，真值聯(lián)結詞也是一種函數(shù)，稱為真值函數(shù)。它的定義域和值域都是由

20、“真”“假”兩個真值構成的集合。真值函數(shù)的自變量和函數(shù)值都是真值。 對任真值形式，如果其中命題變項的真值確定了，那么真值形式的真值也就惟一地確定了。也就是說，真值形式的值，是真值函數(shù)的函數(shù)值。因此，真值形式也稱為真值函項。 在以上定義的五種常用真值聯(lián)結詞中，“”由一個命題變項定義，是一元真值函數(shù)；其余的都有兩個命題變項定義，是二元真值函數(shù)。一般地，如果由n個命題變項定義的真值函數(shù)，稱為n元真值函數(shù)，即n元真值聯(lián)結詞。 n元真值函數(shù)的總數(shù) 上述五個常用真值聯(lián)結詞是從人們的日常思維中概括出來的?，F(xiàn)在的問題是，它們是否窮盡了所有的一元、二元真值聯(lián)結詞？也就是說，包括在內(nèi)的一元真值聯(lián)結詞共有多少個?包

21、括、和在內(nèi)的二元真值聯(lián)結詞共有多少個?一般地，n元真值聯(lián)結詞即n元真值函數(shù)共有多少個？ 前面已經(jīng)提到，一個完整的真值表，定義了一個確定的真值函數(shù)；不同的真值表，定義了不同的真值函數(shù)。因此n元真值函數(shù)共有多少個，也就是問，具有n個命題變項的不同的真值表共有多少個?一個完整的真值表，有兩個構成要素：第一，要列出命題變項所有不同的真假情況，即要列出所定義的真值函數(shù)自變量的所有取值；第二，對命題變項所有不同的真假情況，真值函數(shù)都有確定的真值作為函數(shù)值。例如，設f(p,q)為一二元真值函數(shù)， p qf(p,q) 1 11 1 00 0 10以上的表格就不是一個完整的真值表，因為它沒有窮盡命題變項所有的真

22、假情況。事實上，它遺漏了p和q都取假值的情況。再如： p qf(p,q) 1 11 1 00 0 1？001以上的表格也不是一個完整的真值表，因為對命題變項所有的不同的真假情況，真值函數(shù)并非都有確定的真值作為函數(shù)值。因此，要回答具有n個命題變項的不同的真值表共有多少個，無非是要回答這樣兩個問題：第一，n個命題變項所有不同的真假情況共是多少？第二，對應于n個命題變項所有不同的真假情況，作為函數(shù)值共有多少種不同的真值排列？由于每個每個命題變項都可以取真或假，因此，一個命題變項所有不同的真假情況是2個，兩個命題變項所有不同的真假情況是4個，三個命題變項所有不同的真假情況是8個，推薦精選一般地，n個命

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

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

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

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

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