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

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

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

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

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

6、符號表示。由真值聯結詞構成的復合命題的形式結構，就是真值形式。例如，句（1）的真值形式是p q，其中，“ ”是真值聯結詞，讀作“合取”，表示“并且”；p和q稱作命題變項，表示原子命題。因此，真值形式也就是 命題變項和真值聯結詞的合式構成。單個命題變項也是真值形式，真值聯結詞在其中零次出現。特殊地，如果命題變項和真值聯結詞都零次出現，這樣的真值形式稱為空式。空式也是真值形式。在某些場合，空式的概念不可缺少。另外，真值形式必須是有限構成的，即是有 限長的符號串。，在以后的討論中，p, q, r表示命題變項，A , B , C表示任意的真值形式。常用真值聯結詞這里定義五個常用真值聯結詞，即“入”、“

7、m”、“T ”、“”和“”及相關的五個基本真值形式。合取真值形式“ paq ”，讀作“ p合取q”，斷定：p和q都是真的。也就是說 p和q中， 只要有一個是假的，p q就是假的。“ p q ”可如下定義：pqp r111100010000上面這樣的表格，稱為真值表。其中， “1 ”表示真，“ o”表示假。真值表列出了在原子 命題的每一組真值組合下復合命題的真值。 因此，正如下面將要說明的，一個完整的真值表, 就定義了一個真值函數。不同的真值表，定義不同的真值函數。以上的真值表說明，關于 入的真值運算，下面的等式成立：1 1 = 1; 1 0 = 0 1 = 0 0= 0。在日常語言中，“p代q

8、”表述為“ P并且q”，“不但P,而且q”等等。合取式相當于 傳統邏輯中的聯言命題。析取真值形式“ p訂q ”讀作“ p析取q”斷定：P和q中至少有一個是真的。也就是說, 只有當p和q都是假的，p q才是假的。“ p q ”可如下定義：pqP “q111101011000以上的真值表說明，關于的真值運算，以下的等式成立：1 . 1 = 1 . 0 = 0 I" 1 = 1 ;0 I" 0 = 0。在日常語言中，“ p vq "表述為“ p或者q”析取式相當于傳統邏輯中的相容選言命 題。蘊涵真值形式“ pt q ”，讀作“ P蘊涵q”斷定：只有當p真和q假時，pT

9、q才是假 的；在其余情況下，p > q都是真的。“ p > q ”可如下定義：pqPT q111100011001如上定義的蘊涵.稱為“實質蘊涵”。以上的真值表說明，關于> 的真值運算，以下的等式成立：1一； 0= 0; 1一； 1=1 一； 0=0； 0=1。在日常語言中，“ PT q "表述為“如果 P,那么q” “只要P,就q”等等。蘊涵式 相當于傳統邏輯中的充分條件假言命題。“ pT q ”和“如果P,那么q”的含義是有區別的。“如果P,那么q”除了表示“不會P真而q假”這種p和q之間的真假關系以外，根據具體的語境，還可能表示P和q之間的其他聯系；而“ p

10、> q ”除了表示“不會 P真而q假”以外，不表示 P和q之 間的任何其他聯系。因此，如果“如果p,那么q”成立則“ p > q ”成立：但反過來，如果“ p > q ”成立，則“如果p,那么q”不一定成立。在后面的情況下就會出現所謂 的“蘊涵怪論”。根據“蘊涵”的定義，只有當一個真命題蘊涵一個假命題的時候，這個蘊涵式才是假 的，因此，假命題可以蘊涵任何命題，而真命題可以被任何命題蘊涵。這樣，因為“廢話是 財富”是個假命題，因此，它既可以蘊涵“夸夸其談者可以成為百萬富翁”，又可以蘊涵“夸 夸其談者將一貧如洗”。事實上，我們可以接受“如果廢話是財富，那么夸夸其談者可以成 為百萬

11、富翁”為真命題，但不能接受“如果廢話是財富。那么夸夸其談者將一貧如洗”為真 命題，特別是不能把這兩個內容正好相悖的命題，同時接受為真命題。像“如果廢話是財富.那么夸夸其談者將一貧如洗”這樣的在實質蘊涵的意義上被確認為真，在事實上難以成立或顯然不能成立的條件命題。就稱為“蘊涵怪論”。為了排除蘊涵怪論，邏輯學家定義了一種有別于實質蘊涵的“嚴格蘊涵”，從而產牛了一個重要的邏輯分支一一模態邏輯。基于實質蘊涵的一階邏輯不排除蘊涵怪論。這里的關鍵問題是，“p)q”不完全等同于“如果p，那么q”，而只是對后者的一種真值抽象。推理和蘊涵有著密切的聯系。我們說從前提A能推出結論B,意思就是說，如果A是真的，那么

12、B就不會是假的，這正是 A蘊涵B的意思。因此，一個推理的真值形式就是一 個蘊涵式。等值真值形式“ pq”，讀作“ p當且僅當q”，也讀作“ p和q等值”，斷定：p和q具有 相同的真值。“ p q"可如下定義：pqPq111100010001以上的真值表說明，關于 的真值運算，以下的等式成立：11 = 00=1 ；仆 0=0，1=0。在日常語言中，“pq”表述為“如果p，那么q ;并且只有p才q”。等值式相當于 傳統邏輯中的充分必要條件假言命題。定義所表達的定義項和被定義項之間的關系就是一種常見的等價關系。換句話說，如果兩個命題之間具有等值關系，它們是可以互相定義的。顯然，如果P蘊涵q

13、,并且q蘊油p,則p和q就是等值的。反之亦然。也就是說“pi q” 可定義為“ p_. qjq p ”。并非真值形式“”，讀作“并非p”，斷定p和p具有不同的真值。“ 一p ”可如下定義：Pp1001關于一的真值運算，以下的等式成立一1= 0； 0= 1。例完成以下的真值運算：-1 一00 尸 |：01解一 1 一0 r 0(0 1=一 11 一； 0 L 1=一 1 一； 0 1 11.1=13命題邏輯層次上的自然語言符號化復合命題的真值形式命題推理及其真值形式復合命題的真值形式基于上面所定義的常用真值聯結詞，就可以在命題邏輯的層次上對自然語言進行符號 化，也就是對自然語言所表達的復合命題和

14、命題推理，抽象出它們的真值形式。把自然語言所表達的復合命題翻譯成相應的真值形式，其步驟是：第一，確定復合命題所包含的所有不同的原于命題；第二，用同一命題變項表示所有相同的原子命題，用不同的命題變項分別表示所有不同的原子命題(表示命題變項的符號是小寫英文字母p、q、r、s、t)；第三，確定復合命題所斷定的支命題之間的邏輯關系，并用相應的真值聯結詞加以 表達；第四，依據確定的層次，寫出整個復合命題的真值形式。下面通過實例加以說明。例1寫出下列各復合命題的真值形式：(1)要么總經理辭職，要么董事長承擔全部責任。令P表示總經理辭職，q表示董事長承擔全部責任。 命題(1)斷定p和q兩個命題有且只有一個為

15、真，因此，其真值形式是：p qp q。p q表示傳統邏輯中的相容選言命題；在傳統邏輯中，表示不相容選言命題的聯結詞 是“要么，要么”。本例說明，不相容選言命題“P,要么q”的真值形式是p q p q。(2)只有確保產品質量，企業才能具備起碼的競爭力。令P表示(企業)確保產品質量，q表示企業具備起碼的競爭力。命題(2)斷定p是q的必要條件，即無p則無q。因此，其真值形式是：p q。q和pi q分別表示傳統邏輯中的充分條件和充分必要條件假言命題；在傳統邏輯 中，表示必要條件假言命題的聯結詞是“只有才”。本例說明,必要條件假言命題“只有P,才有q”的真值形式是 p、-q。命題(3)的真值3除非制定的

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

17、q i 1(一p r)。事實上，以后將會看到，這兩個形式真值是等值的。(2) 如果大張在孩子落水的現場但沒有參加營救，那么，或者他看到了孩子落水但卻裝 著看不見，或者他確實不會游泳。令P表示大張在孩子落水的現場，q表示大張參加了營救，r表示大張看到了孩子落水，s表示大張裝著看不見孩子落水，t表示大張會游泳。命題的真值形式是：p-q ii：r s-t。大張看到了孩子落水，和大張裝著看不見孩子落水，是兩個沒有真值關系的原子命題， 必須用不同的命題變項表示。r表示大張看到了孩子落水，-r表示大張沒看到孩子落水，而不表示大張裝著看不見孩子落水。(3) 如果光強調固結，不強調斗爭，或者光強調斗爭，不強調

18、固結，就不能達到既弄清 思想又團結同志的目的。令P表示強調團結，q表示強調斗爭，r表示喬清思想，s表示團結同志(這里都省略了 主語)。命題的真值形式是：p -q q p - r s。命題推理及其真值形式命題邏輯的中心課題，是研究命題推理的形式結構及其有效性的判定。那么，什么是命題推理呢 ？看下面兩個推理：(1) 如果大張是作案者，那么他一定有作案動機大張沒有作案動機所以，大張不是作案者(2) 所有的作案者都有作案動機大張沒有作案動機所以，大張不是作案者這兩個推理都是有效的，并且有著相同的內容。但是。它們之間有著實質性的區別：推理(1)的有效性的根據是命題之間的關系，而推理(2)的有效性的根據是

19、原子命題內部的構成要素之間的關系。像推理(1)這樣的推理，稱為命題推理。任命題推理中，事實上在整個命題邏輯中，原 子命題作為最基本的單位，它的內部結構不再分析。求命題推理的真值形式的步驟是：第一，分別號出各個前提和結論的真值形式；第二， 用合取號把各個前提的真值形式聯結起來，所得的合取式，即是前提的真值形式；第三，用蘊涵號把前面提和結論的真值形式聯結起來，所得的蘊涵式，即是整個命題推理的真值形式。例3寫出以下命題推理的真值形式：如果上帝不能創造出一塊他自己都不能搬動的石頭，則他不是萬能的；如果上帝能創造出一塊他自己都不能搬動的石頭，則他同樣不是萬能的。 上帝或者能創造出一塊他自己都不能搬動的石

20、頭，或者不能，二者必居其一。因此，上帝不是萬能的。令P表示上帝能創造出一塊他自己都不能搬動的石頭，q表示上帝是萬能的。 則該推理的格式是：一卩一 qPT飛 P 一P _ q它的真值形式是：i) p；q p；qp 一p 丁一；q。4真值聯結詞的一般性質真值函數n元真值函數的總數真值聯結詞的可定義性、完全性和獨立性真值函數所謂函數，是指在兩個集合的元素之間建立對應關系的一種運算。設A和B是兩個集合，若對 A中的元素，或元素元組，依據某種運算，能惟一地確定 B中的某個元素與之對應，這就定義了一個從 A到B的(單值)函數。A稱為該函數的定義域， B稱為該函數的值域；定義域上的元素稱為自變量，值域上的元

21、素稱為函數值。顯然，真值聯結詞也是一種函數，稱為真值函數。它的定義域和值域都是由“真”“假”兩個真值構成的集合。真值函數的自變量和函數值都是真值。對任一真值形式，如果其中命題變項的真值確定了，那么真值形式的真值也就惟一地確定了。也就是說，真值形式的值，是真值函數的函數值。因此，真值形式也稱為真值函項。在以上定義的五種常用真值聯結詞中，“-”由一個命題變項定義，是一元真值函數；其余的都有兩個命題變項定義，是二元真值函數。一般地，如果由n個命題變項定義的真值函數，稱為n元真值函數，即 n元真值聯結詞。n元真值函數的總數上述五個常用真值聯結詞是從人們的日常思維中概括出來的。現在的問題是，它們是否窮盡

22、了所有的一元、二元真值聯結詞？也就是說，包括-在內的一元真值聯結詞共有多少個?包括 、一;和I在內的二元真值聯結詞共有多少個 ？一般地，n元真值聯結詞.即 n元真值函數共有多少個？前面已經提到，一個完整的真值表，定義了一個確定的真值函數；不同的真值表，定義 了不同的真值函數。 因此n元真值函數共有多少個，也就是問，具有n個命題變項的不同的真值表共有多少個？一個完整的真值表，有兩個構成要素：第一，要列出命題變項所有不同的真假情況， 即要列出所定義的真值函數自變量的所有取值；第二，對命題變項所有不同的真假情況，真值函數都有確定的真值作為函數值。例如，設f(p,q)為一二元真值函數,函數并非都有確定

23、的真值作為函數值。因此，要回答具有 n個命題變項的不同的真值表共有多少個，無非是要回答這樣兩個 問題：第一，n個命題變項所有不同的真假情況共是多少？第二，對應于n個命題變項所有不同的真假情況，作為函數值共有多少種不同的真值排列？由于每個每個命題變項都可以取真或假，因此，一個命題變項所有不同的真假情況是2個，兩個命題變項所有不同的真假情況是4個，三個命題變項所有不同的真假情況是8個，一般地，n個命題變項所有不同的真假情況共是，個。而對應于命題變項的 ，種的每一種，函數值可以取真或假，因此，對應于命題變項的2“種不同的取值，真值函數共有2 2叮 ，:2 （連乘 2“次）種不同的取值。 也就是說，n

24、元真值函數， 共有2 2'： : 2n ,n A（連乘2次）=2個。這樣，一元真值聯接詞，共有4個，二元真值聯接詞，共有 16個。以下分別是所有一元和二元真值聯接詞的一覽表。其中，表示f一元真值聯接詞，g表示二元真值聯接詞。表1 一元真值聯接詞一覽表pf1f2f3f41110001010表2二元真值聯接詞一覽表pqg1g2g3g4g5g6g7g8g9g10g11g12g13g14g15g16111111111100000000101111000011110000011100110011001100001010101010101010真值聯接詞的可定義性在表i和表2中，f 3即是一，g是

25、，g是，g是一；，g是。因為兩個等值的真值形式是可以互相定義的，因此，fi可定義為p p。f4可定義為P 一卩。f2可定義為P。g3表示“只有p，才q”可定義為pTq。gio表示“要么p,要么q”可定義為（pqWLp/q ）。我們可以用構造真值表的方法來驗證，定義右邊的真值形式的真值表， 和所要定義的真Pqg3Ptq111Ft1=1101Ft0=1010-<0t F = 0001Ot0 = 1值函數的真值表是相同的。 這說明二者是等值的， 是可以互 相定義的。例如，以下的真值表說明，p q和g3具有相同的真值表，兩者是可以互相定義的：真值聯結詞的完全性現在的問題是，常用真值聯結詞是否能定

26、義所有的一元和二元真值聯結詞？或者更一般地，常用真值聯結詞是否能定義所有的n元真值聯結詞，回答是肯定的。定義4. 1 一組真值聯結詞是完全的，當且僅當由它能定義任一n元真值聯結詞。定理4. 2 L, , 是完全的。在給出正式的證明以前先分析一個實例。不妨討論如何用一， 和 來定義表2中 的二元真值聯結詞 g4。g4的真值表顯示，g4 (p, q)為真，當且僅當：p真且q真.或者p真且q假。因此，它顯然可定義為：p q p -q。事實上，用這種方式，可以 一，和來定義任一 n元真值聯結詞。證明設f P!，心是任一 n元真值聯結詞。顯然，它可以用一個 2n行的真值表來定義。現在考慮在該真值表中函數

27、值為真的那些行。設第i行(1 v iv 2n )的函數值為真，構造合取式Ci : p； p； pn，每一 pj (j = 1，n)是命題變項Pj或其否定Pj ： 如果在第i行pj的值是真，則pj就是pj ；如果在第i行Pj的值是假，則pj就是一 Pj。 顯然，當p；,，Pn取第i行的值時，G的值是真，與f p；,，Pn在第i行的值相同。令 D是所有這樣構造的合取式 G的析取。如果f P；,，Pn的值為常真，即在真值表的每一 行都真，則D就有2n個析取支；如果f p；，,Pn的值為真的行數是k,則D就有k個析 取支；如果f 口，pn的值為常假，即在真值表的每一行都假，這時令 D為P _P。對 于

28、這樣構造的真值形式D，如果它是真的，則由的定義，可知存在某個 G(1w i< 2n)為真，又由G的構造定義，可知f P1/ , Pn為真；如果f P1,Pn為真，則存在某個i(1W i w 2n), f(p1,，Pn )在第i行的值為真，同樣由 C的構造定義.可知 C為真，貝y D為真。因此，f P1,，Pn和D等值。因為D中只出現，又因為f P1 / , Pn具有 任意性，因此，;、，是完全的。證畢。自然, ,一；尸，一 1也是完全的。例1用一，和 定義以下三元真值函數f p,q,r :pqrf (P,q,r)11111100101010010111010100100000上述真值函數

29、可定義為：p q r p _q _r_p q r _p q _r。定理4. 3 r ,一堤完全的。證明可通過構造真值表驗證：p q可定義為p q;_q可定義為一 p、q。這說明運用 > 和二可定義 _和_，又因為1一,是完全的，所以，匚廠.堤完全的。證畢。定理4. 4【-,是完全的。證明可定義為（pe"1硏。這說明運用一1和a可定義M。又因為匕“是 完全的，所以，是完全的。證畢。定理4. 5 L,是完全的。證明|paq可定義為。與定理4. 4的證明同理，匕門 是完全的。證 畢。定理4. 6 ：一,1 ；不完全的。這里僅敘述證明的思路，嚴格的證明可運用數學歸納法完成。考慮一個僅包含和兩個不同的命題變項的真值形式。因為只包含兩個命題變項，所以它的真值表是四行；又因為僅包含一,，所以它在這四行中的真值，有且只有三種不同的情況：第一，都是真；第二.都是假；第三，兩行為真，兩行為假。而p > q的真值 表的四行中，有三行為真，一行為假。這說明，、不可能由和定義。因此是 不完全的。定理4. 7:, ，”是不完全的。證明一不能由 ，一.和.r定義。如果能，則存在公式 A , - p.r A , A中 只出現p和，一；和I。因為1 1=1 1 = 1; 1 =