邏輯學導論（第5版）課件 第二章 命題邏輯

命題邏輯第二章

第一節(jié)

日常聯(lián)結(jié)詞和復合命題第二章：命題邏輯一、簡單命題和復合命題簡單命題就是只能分析為不同的詞項、不能分析為其他命題的命題，因此又叫作“原子命題”。例如：(1)香山楓葉正紅。(2)諸葛亮舌戰(zhàn)群儒。(3)擲骰子4點朝上的概率是1/6。都是簡單命題。第二章：命題邏輯復合命題則是包含其他命題的命題，它是用一定的聯(lián)結(jié)詞連接其他命題而形成的。例如：(4)北京是中國的政治中心，并且是文化中心。(5)勝者或因其強，或因其指揮無誤。(6)如果一個推理的前提真實，并且推理形式有效，則結(jié)論必真。組成復合命題的其他命題叫作該復合命題的支命題。第二章：命題邏輯二、聯(lián)言命題聯(lián)言命題是由“并且”這類聯(lián)結(jié)詞連接兩個或多個支命題形成的復合命題，它們是斷定幾種事物情況同時存在的命題。例如：(1)3是素數(shù)，并且117也是素數(shù)。(2)魯迅是思想家，并且魯迅是文學家。聯(lián)言命題中的支命題叫作“聯(lián)言支”。聯(lián)言支的主項或者謂項在很多時候相同，這時我們可以省略一個主項或謂項。例如，(1)和(2)可以分別變成：(1′)3和117都是素數(shù)。(2′)魯迅既是思想家，又是文學家。第二章：命題邏輯根據(jù)聯(lián)言命題的上述性質(zhì)，聯(lián)言推理有如下有效式：Ⅰ.合成式：如果分別肯定兩個聯(lián)言支，則可以肯定由這兩個聯(lián)言支組成的聯(lián)言命題。Ⅱ.分解式：如果肯定一個聯(lián)言命題，則可以分別肯定其中的每一個聯(lián)言支。Ⅲ.否定式：如果否定一個聯(lián)言支，則可以否定包含這個聯(lián)言支的聯(lián)言命題。第二章：命題邏輯三、選言命題選言命題分為相容選言命題和不相容選言命題兩類，其中的支命題都叫作“選言支”。相容選言命題是借助“或者”這類聯(lián)結(jié)詞連接兩個支命題形成的復合命題，它們斷定幾種事物情況至少有一種存在。例如：(1)病人或失業(yè)者可以停付保險費。(2)小強發(fā)燒或者是由于感冒，或者是由于肺炎。(3)根據(jù)我的經(jīng)驗，明天不是刮風就是下雨。(4)這份民調(diào)結(jié)果，要么是原始數(shù)據(jù)有錯誤，要么是計算過程有錯誤。第二章：命題邏輯根據(jù)相容選言命題的上述性質(zhì)，相容選言推理有如下有效式：Ⅰ.否定肯定式：如果肯定一個相容選言命題并且否定其中的一個選言支，則必須肯定其中的另一個選言支。Ⅱ.肯定肯定式：如果肯定一個選言支，則必須肯定包含這個選言支的任一選言命題。第二章：命題邏輯根據(jù)不相容選言命題的上述性質(zhì)，不相容選言推理有如下有效式：Ⅰ.否定肯定式：如果否定一個不相容選言命題的一個選言支，則必須肯定它的另一個選言支。Ⅱ.肯定否定式：如果肯定一個不相容選言命題的一個選言支，則必須否定它的另一個選言支。第二章：命題邏輯關(guān)于選言命題，應該注意以下兩點：首先，一個選言命題究竟是相容的還是不相容的，沒有專用的形式識別標記，只能看其中的各個選言支是否能夠同時為真：能夠同時為真的，是相容選言命題；不能同時為真的，是不相容選言命題。其次，如果一個選言命題窮盡了所有的選言支，則該選言命題必真；假若選言支不窮盡，則選言命題有可能為假。第二章：命題邏輯四、假言命題假言命題亦稱“條件命題”，其中表示條件的支命題叫作“前件”，表示結(jié)果的支命題叫作“后件”。假言命題斷定了前件和后件之間的某種條件關(guān)系。而條件關(guān)系一般來說分為三種：充分條件、必要條件和充分必要條件，相應地，假言命題也分為三種：充分條件假言命題、必要條件假言命題、充分必要條件假言命題。第二章：命題邏輯1.充分條件假言命題及其推理充分條件假言命題是由“如果，則”這類聯(lián)結(jié)詞連接兩個支命題而形成的命題，它在自然語言中有多種表述方式，例如：(1)如果物體摩擦，則物體生熱。(2)只要你勤奮耕耘，總會有所收獲。(3)假如這個玻璃杯從我手中滑落，則它會摔得粉碎。第二章：命題邏輯根據(jù)充分條件假言命題的上述性質(zhì)，充分條件假言推理有如下有效式：Ⅰ.肯定前件式：例如：“如果官員甲擁有不受監(jiān)控的權(quán)力，官員甲很容易導致腐?。还賳T甲確實擁有不受監(jiān)控的權(quán)力，所以，官員甲很容易導致腐敗?！雹?否定后件式：例如：“如果小王患肺炎的話，則他的體溫會不正常升高；但經(jīng)檢查，小王現(xiàn)在體溫正常，所以，小王目前沒有患肺炎。”第二章：命題邏輯2.必要條件假言命題及其推理必要條件假言命題是由“只有，才”這類聯(lián)結(jié)詞連接兩個支命題形成的復合命題，它在自然語言中的表述方式是多種多樣的。例如：(1)只有不畏勞苦，才能攀上科學高峰。(2)除非你把那本書還給我，我才會把這本書借給你。(3)不入虎穴，焉得虎子。第二章：命題邏輯根據(jù)必要條件假言命題的上述性質(zhì)，必要條件假言推理有如下有效式：Ⅰ.否定前件式：例如：“只有陳夢溪年滿18歲，他才有選舉權(quán)和被選舉權(quán)；陳夢溪年僅16歲，所以他沒有選舉權(quán)和被選舉權(quán)?！雹?肯定后件式：例如：“只有小張學習成績好，他才能當三好學生；小張已當選為三好學生，所以，他一定學習成績好?！钡诙拢好}邏輯3.充分必要條件假言命題及其推理充分必要條件假言命題，是由“當且僅當”這類聯(lián)結(jié)詞連接兩個支命題形成的命題。例如：(1)一個三角形的三邊相等，當且僅當，它的三內(nèi)角都是60°。(2)AB，當且僅當，對任意x，如果x∈A，則x∈B。(3)張猛是單身漢，當且僅當，他是未婚男子。第二章：命題邏輯“當且僅當”這一聯(lián)結(jié)詞通常只在數(shù)學、邏輯及其他精確科學中出現(xiàn)，在社會科學和人們的日常交談中很少使用。在日常語言中，人們要表述充分必要條件假言命題時，常常分成兩句話，一句話說前件是后件的充分條件，另一句說前件是后件的必要條件。例如：(4)人不犯我，我不犯人；人若犯我，我必犯人。(5)如果公民年滿18歲，則他有選舉權(quán)；并且，只有公民年滿18歲，他才有選舉權(quán)。顯然，當前件和后件同真或同假時，一個充分必要條件假言命題為真；在前后件不同真或者不同假的情況下，它都是假的。第二章：命題邏輯

五、負命題負命題是由否定一個命題而得到的命題，它是通過把“并非”這類否定詞置于一個命題之前或之后而形成的，其標準形式是“并非p”和“并不是p”。例如：(1)并非所有天鵝都是白色的。(2)并非一刮風就下雨。第二章：命題邏輯在自然語言中，負命題的表達形式是多種多樣的，例如為了表達“并非所有閃光的東西都是金子”，我們也可以說：(3)不是所有閃光的東西都是金子。(4)說“所有閃光的東西都是金子”是假的。(5)“所有閃光的東西都是金子”，這一說法不成立。(6)說“所有閃光的東西都是金子”不符合事實。第二章：命題邏輯負命題所否定的可以是一簡單命題，如例(1)；也可以是一復合命題，如例(2)。被否定的命題稱為原命題。值得注意的是，負命題所否定的是整個原命題，而不是原命題的一部分。因此，負命題的真值與原命題恰恰相反：若原命題為真，則負命題為假；若原命題為假，則負命題為真。這就是負命題的邏輯性質(zhì)。也正因為如此，“并非”是由一個命題形成一個新命題的聯(lián)結(jié)詞。第二章：命題邏輯第二節(jié)

真值聯(lián)結(jié)詞

真值形式

第二章：命題邏輯一、從日常聯(lián)結(jié)詞到真值聯(lián)結(jié)詞在命題邏輯中，簡單命題究竟是一個什么樣的命題，究竟是真是假，實際上是無關(guān)緊要的；真正重要的是復合命題的邏輯性質(zhì)，以及由這種性質(zhì)所決定的復合命題與其支命題之間以及復合命題相互之間的邏輯關(guān)系。而這是由命題聯(lián)結(jié)詞決定的。命題形式有兩種成分：代表具體內(nèi)容的位置，由命題變項表示；連接或組合這些位置的結(jié)構(gòu)成分，即命題聯(lián)結(jié)詞，亦稱“邏輯常項”。第二章：命題邏輯從邏輯角度看，這些日常語言聯(lián)結(jié)詞存在兩個主要問題：一是不精確，以“或者”和“要么”為例，它們既可以在相容意義上使用，也可以在不相容意義上使用。二是負載了許多非邏輯的內(nèi)容。以各種聯(lián)言命題為例，它們除表示各個支命題同時為真外，還表示并列關(guān)系、承接關(guān)系、遞進關(guān)系、轉(zhuǎn)折關(guān)系、對比關(guān)系等等。第二章：命題邏輯為了與日常聯(lián)結(jié)詞相區(qū)別，同時也為了書寫的方便，邏輯學家們特制了一些專門的符號去表示真值聯(lián)結(jié)詞：(1)∧：讀作“合取”(conjunction)，相當于日常語言中的“并且”。(2)∨：讀作“析取”(disjunction)，相當于日常語言中的“或者”。(3)→：讀作“蘊涵”(implication)，相當于日常語言中的“如果，則”。(4)：讀作“等值”(equivalence)，相當于日常語言中的“當且僅當”。(5)┑：讀作“否定”(negation)，相當于日常語言中的“并非”。第二章：命題邏輯完整地給出命題邏輯的語言：Ⅰ.初始符號(i)命題變項：p，q，r，s……(ii)命題聯(lián)結(jié)詞：┑，∧，∨，→，(iii)輔助性符號：左括號“(”，右括號“)”Ⅱ.形成規(guī)則(i)任意的p，q，r，s是公式；(ii)若A是公式，則┑A是公式；(iii)若A和B分別是公式，則(A∧B)、(A∨B)、(A→B)、(AB)是公式；(iv)只有按以上方式形成的符號串是公式。第二章：命題邏輯二、真值形式指派與賦值在上一小節(jié)所定義的“公式”中，作為其構(gòu)成成分出現(xiàn)且符合形成規(guī)則的部分，叫作該公式的“子公式”。在形成規(guī)則中，p、q、r、s、┑、∧、∨、→、是對象語言符號，而A、B、C是元語言符號，它們代表用對象語言表述的任一公式。例如，A可以是下面的任一公式：p，q，r，┑p，(q∧s)，(r∨s)，(p→q)，(qs)，((((┑p)∧q)→r)(s∨q))其中，┑p、(q∧s)、(r∨s)、(p→q)、(qs)是五種最基本的公式，分別叫作“否定式”、“合取式”、“析取式”、“蘊涵式”和“等值式”。第二章：命題邏輯為了避免結(jié)構(gòu)歧義，二元聯(lián)結(jié)詞為主聯(lián)結(jié)詞的公式外側(cè)總有括號。但層層疊疊的括號有時令人困擾，所以這里約定三條省略括號的規(guī)則。(1)公式最外層的括號總是可以省略。例如：(p∧q)可寫作p∧q，(┑((p∧q)(r∨s))∧p)可寫作┑((p∧q)(r∨s))∧p。(2)像算術(shù)中在沒有括號的情況下規(guī)定先乘除后加減一樣，我們現(xiàn)在也規(guī)定：聯(lián)結(jié)詞的結(jié)合力按下述秩序而遞減：┑，∧，∨，→，這就是說，在沒有括號的情況下，我們先看┑，再看∧，再看∨，再看→，最后看。據(jù)此可以省略一些括號。例如：┑((p∧q)(r∨s))∧p可寫作┑(p∧qr∨s)∧p。(3)形如(A∧B)∧C的公式可寫作A∧B∧C；形如(A∨B)∨C的公式可寫作A∨B∨C；形如A→(B→C)的公式可寫作A→B→C。其中的A、B、C表示任意的公式。例如：p→(q→(r→s))可寫作p→q→r→s。第二章：命題邏輯公式不是一個有具體內(nèi)容的命題，而是一個命題模式或命題框架，它們是沒有真值的。當我們在一個公式中，用具體命題替換其中的命題變項，則得到該公式的一個實例，或者說代入實例。例如，下面4個命題都是公式p→q的代入實例：(1)冬天來了→春天不會遙遠。(2)你熱愛生命→你別浪費時間。(3)2+2=4→2+2=4。(4)(x>y)∧(y>z)→(x>z)第二章：命題邏輯公式的真值取決于兩個要素：一是命題變項的真值，這來自真值指派；二是真值聯(lián)結(jié)詞的意義，這來自解釋。一組真值指派和一個解釋構(gòu)成一個真值賦值。如上所述，命題變項本身沒有真值，但它的代入實例有真值，其代入實例的真值無非是真或者假，據(jù)此可以把命題變項的所有代入實例分為兩類：{真命題}和{假命題}。在這個意義上，命題變項也獲得兩個派生的真值：真和假。顯然，這兩個真值不是來自于與現(xiàn)實的比較和對照，而是由我們直接給予或任意指定的，所以，叫作“真值指派”。第二章：命題邏輯三、否定真值形式┑p稱為“否定式”，讀作“非p”、“并非p”，其中命題變項p代表任一命題，對其可以指派兩個真值：真(以后用“1”表示)和假(以后用“0”表示)。否定詞的意義在于：如果原命題為真，則它的否定式為假；如果原命題為假，則它的否定式為真。第二章：命題邏輯四、合取真值形式p∧q稱為“合取式”，讀作“p合取q”或“p并且q”，p、q都是p∧q的合取支。其中合取詞∧的意義是：當合取式的各個合取支都真時，該合取式為真；只要有一個合取支為假，該合取式為假。課本（表2-2）真值表所刻畫的合取詞∧，只保留了各種聯(lián)言聯(lián)結(jié)詞所表示的聯(lián)言命題與其支命題之間的真假關(guān)系，而舍去了它們可能表示的并列、承接、遞進、轉(zhuǎn)折、對比等意義，以及由這種意義賦予各個支命題的某種順序關(guān)系，例如：“孫佳結(jié)了婚，并且生了孩子”，“吳為學問好，人緣也好”。由此造成下述兩個結(jié)果：(1)合取交換律成立，p∧q與q∧p總是取同樣的真值。一個合取命題成立與否，與其中合取支的順序無關(guān)。(2)只要兩個合取支都是真的，相應的合取命題總是真的，不管其合取支之間是否有內(nèi)容、意義上的關(guān)聯(lián)。例如，“2+2=4并且北大未名湖很美麗”就是一個真的合取命題。第二章：命題邏輯五、析取真值形式p∨q稱為“析取式”，讀作“p析取q”或“p或者q”，p、q都是p∨q的析取支。其中析取詞∨的意義在于：如果p和q中至少有一個為真，則p∨q為真；如果p和q全都為假，則p∨q為假。第二章：命題邏輯基本真值聯(lián)結(jié)詞中沒有不相容析取，至少有以下兩個原因：(1)可用┑、∧、∨去定義二元的不相容析取，后者權(quán)且用“⊙”表示，用公式表示，其定義如下：p⊙q=df(p∨q)∧┑(p∧q)(2)與相容析取詞∨相比，不相容析取詞⊙是更特殊的，它是通過在前者上施加一個限制得到的：不僅各個析取支不能同假，而且不能同真。第二章：命題邏輯六、蘊涵真值形式p→q稱為“蘊涵式”，讀作“p蘊涵q”、“如果p則q”，其中p、q分別是蘊涵式的前件和后件。蘊涵詞→的意義在于：p→q只有在p真q假的情況下才是假的，在p真q真、p假q真、p假q假的情況下，p→q都是真的。對于蘊涵詞的這樣一種解釋，被稱為“實質(zhì)蘊涵”，因為它能夠?qū)С鋈缦乱恍┏Ｕ娴恼嬷敌问蕉鴤涫芊亲h：(1)p→(q→p)(2)┑p→(p→q)(3)(p→q)∨(q→p)(4)(p→q)∨(p→┑q)第二章：命題邏輯下面我要為實質(zhì)蘊涵，實際上是更一般地為從真值角度研究復合命題的性質(zhì)及其推理關(guān)系的做法，做一些簡短的辯護：第一，實質(zhì)蘊涵抽象、概括出了自然語言中“如果，則”這類聯(lián)結(jié)詞的共性，在對“如果，則”的各種解釋中是最弱的，因而具有普適性和簡單性，而這種普適性和簡單性是邏輯的本質(zhì)要求。第二，實質(zhì)蘊涵也有關(guān)于“如果，則”的日常用法的經(jīng)驗根據(jù)或基礎。人們對“當p真q假時，p→q為假”一般不持異議，但對于承認“當p假或q真時，p→q為真”卻有很大保留。第三，從前后一致的角度看，如果承認┑(否定)、∨(析取)分別是“并非”和“或者”的合理抽象，那么也應該承認→(蘊涵)是“如果，則”的合理抽象。第二章：命題邏輯七、等值真值形式p?q稱為“等值式”，讀作“p等值(于)q”，或“p當且僅當q”，p、q分別是p?q的前件和后件。等值詞?的意義在于：只有當p和q同真或同假時，p?q才是真的；如果p和q不同真或不同假，則p?q是假的。第二章：命題邏輯八、自然語言中復合命題的符號化我們之所以說┑、∧、∨、→、這5個聯(lián)結(jié)詞是基本的，一是因為它們的對應者在自然語言中最常用；二是因為其他的(真值)聯(lián)結(jié)詞都可以由它們定義或構(gòu)造出來。因此，它們可以表示自然語言中的絕大多數(shù)復合命題。例如，自然語言中的必要條件假言命題“只有p才q”，如果只從真假關(guān)系的角度看，它等值于“如果q則p”，或“如果非p則非q”，因此就可以用真值聯(lián)結(jié)詞→和┑來表示，即“q→p”和“┑p→┑q”。第二章：命題邏輯例如，“只有保護環(huán)境，才能保持經(jīng)濟的持續(xù)健康發(fā)展”，這是一個典型的必要條件假言命題，如果用p表示“保護環(huán)境”，用q表示“保持經(jīng)濟的持續(xù)健康發(fā)展”，則可以用兩種方式將其符號化為“q→p”(如果要保持經(jīng)濟的持續(xù)健康發(fā)展，就要保護環(huán)境)，“┑p→┑q”(如果不保護環(huán)境，就不能保持經(jīng)濟的持續(xù)健康發(fā)展)。于是，我們有下述三個等值式：“只有p才q”等值于“如果q則p”?！爸挥衟才q”等值于“如果非p則非q”。“如果p則q”等值于“只有q才p”。這就是一般的說法：如果p是q的充分條件，則q是p的必要條件；如果p是q的必要條件，則q是p的充分條件。第二章：命題邏輯第三節(jié)

重言式及其判定方法

第二章：命題邏輯一、重言式真值形式雖然在數(shù)量上是無限的，但可以分為三種類型：重言式、矛盾式和偶真式。嚴格定義如下：D1一真值形式A是重言式，當且僅當，對于任一真值賦值(真值指派+真值計算)，A恒取值為真。D2一真值形式A是矛盾式，當且僅當，對于任一真值賦值，A恒取值為假。D3一真值形式A是偶真式，當且僅當，對于某些真值賦值A取值為真，對于另一些真值賦值A取值為假。第二章：命題邏輯關(guān)于重言式、矛盾式和偶真式，下面的一些結(jié)論是顯然的：(1)一個真值形式是重言式，當且僅當，它的否定式是矛盾式。(2)一個真值形式不是重言式，當且僅當，在其中命題變項的至少一組真值指派下，它取值為假。(3)一個真值形式不是矛盾式，當且僅當，在其中命題變項的至少一組真值指派下，它取值為真。(4)一個真值形式是偶真式，當且僅當，它既不是重言式也不是矛盾式。

第二章：命題邏輯判定程序要滿足以下三個要求：(i)程序的每一步都是由一套事先給定的規(guī)則明確規(guī)定好了的，該規(guī)則規(guī)定了第一步如何做，以及在某一步完成之后下一步又如何做；(ii)該程序能夠在有窮步內(nèi)結(jié)束；(iii)對于所判定的對象是否具有某性質(zhì)，該程序給出了唯一確定的結(jié)果。

第二章：命題邏輯二、真值表方法用真值表法判定一個公式的步驟是：(1)找出該公式中所有不同的命題變項，并豎行列出它們之間所有可能的真值組合。(2)按照該公式的生成次序，由簡單到復雜橫行列出該公式的所有子公式，直至該公式本身。(3)按照上面給定的真值聯(lián)結(jié)詞的真值表，由命題變項的真值逐步計算出各個子公式的真值，直至該公式本身的真值。第二章：命題邏輯命題邏輯中的代入要滿足三個條件：(1)只有命題變項才能被代入，其他復合公式，例如┑p、q∨s等，不能被代入；不過，用來代入的公式卻是任意的。(2)必須處處代入：在被代入變項出現(xiàn)的每一個位置上，用同一個公式去代入該變項。(3)必須同時代入：當對一個公式中n個變項做代入時，不能先對某個變項做代入，再對該次代入的結(jié)果做新的代入，而要用相同的公式對這n個變項中的每一個同時做代入。

第二章：命題邏輯三、歸謬賦值法歸謬賦值法就是真值表方法的一種簡化，其基本思路是：如果公式A是一個重言式，那么，無論給A中的變項指派什么樣的真值，根據(jù)A的形式結(jié)構(gòu)以及其中聯(lián)結(jié)詞所表示的真值運算，A必定且只能取值為真。因此，若假設A不是重言式，即可以為假，然后按照聯(lián)結(jié)詞的真值表，逐步逆推出其中各個子公式應該取的真值，直至逆推出其中所含的命題變項的真值，看能否在子公式或命題變項上導致矛盾的賦值，即必須對同一個子公式或命題變項既指派真又指派假。根據(jù)歸謬法，從一個假設導致矛盾，而矛盾肯定不成立，因此原假設不成立，該公式不可能為假，恒為真，是重言式。第二章：命題邏輯歸謬賦值法的具體做法是：(1)寫出所要判定的公式A。(2)在A的主聯(lián)結(jié)詞下寫0。(3)按照聯(lián)結(jié)詞的真值表，由主聯(lián)結(jié)詞的真值逐步逆推出其中子公式的真值，在相應子公式下寫1或者0，并按此辦法依次進行下去。在一子公式下寫1或者0，也就是在它的主聯(lián)結(jié)詞下寫1或者0；如果這個公式是命題變項，則在該變項下寫1或者0。(4)檢查賦值中是否出現(xiàn)矛盾。盡管賦值過程尚未最后完成，但已經(jīng)出現(xiàn)矛盾，則就此打住。否則，賦值過程一直進行下去，直至給出命題變項的真值。若出現(xiàn)矛盾，為醒目起見，在互相矛盾的賦值下面置一短橫線。這表明該公式不可能為假，必定是重言式。若未出現(xiàn)矛盾，則表明該公式可以為假，不是重言式。第二章：命題邏輯四、樹形圖方法在畫樹形圖時，再強調(diào)以下兩點：(1)在遇到分叉的規(guī)則(即┑∧規(guī)則、∨規(guī)則、→規(guī)則、規(guī)則和┑規(guī)則)與不分叉規(guī)則(即┑┑規(guī)則、∧規(guī)則、┑∨規(guī)則和┑→規(guī)則)時，先使用不分叉的規(guī)則，讓各個枝共有的東西長在樹干上，使樹形圖簡潔明了。否則，樹形圖過早分叉，有些公式屬于每一個枝，將導致各個枝上有很多重復的東西，樹形圖很累贅，且容易出錯。第二章：命題邏輯(2)一個公式是重言式，當且僅當，帶否定號公式的樹形圖的每一個枝都是閉枝。因此，如果在畫圖過程中，有一個枝已經(jīng)終結(jié)，但該枝上沒有出現(xiàn)一個公式和它的否定公式，這說明該枝沒有封閉，帶否定號的公式不是邏輯矛盾，可以為真，只要把該枝上取1的命題變項和取0的命題的值按該公式的結(jié)構(gòu)組合起來，進行計算，該公式就為真。此時，盡管其他的枝還未終結(jié)，整個樹形圖尚未畫完，也可以不必繼續(xù)畫了，直接做出結(jié)論：待判定公式(即不帶否定號的公式)不是重言式。第二章：命題邏輯第四節(jié)

重言蘊涵式重言等值式

第二章：命題邏輯一、推理的形式結(jié)構(gòu)重言蘊涵式一個推理由前提和結(jié)論兩部分組成。如果一個推理形式是有效的，那么由真前提必定得到真結(jié)論。因此，前提和結(jié)論之間是蘊涵關(guān)系。我們可以用一個蘊涵式來表示推理形式，蘊涵式的前件是推理的各個前提的合取，后件是推理的結(jié)論。如果一個推理形式只與聯(lián)結(jié)詞和復合命題相關(guān)，而不涉及各種非命題成分，如主詞、謂詞、系詞、量詞，或個體詞、謂詞等，那么，該推理形式是有效的當且僅當相應的蘊涵式是重言式。這是因為，有效的推理形式是不依賴前提和結(jié)論的具體內(nèi)容的，所以，相應的蘊涵式必定對于所含命題變項的任意一組真值指派都真，所以必定是重言式。第二章：命題邏輯［例12］如果某甲是罪犯，則他有作案時間；他沒有作案時間，所以他不是罪犯。解析：與例12相應的蘊涵式是：(p→q)∧┑q→┑p用歸謬賦值法來檢驗它的有效性：(p→q)∧┑q→┑p110110001出現(xiàn)矛盾的賦值，所以該蘊涵式是一個重言式，從而該推理是一個有效的推理。第二章：命題邏輯［例13］或者邏輯學難學，或者沒有多少學生喜歡它。如果數(shù)學容易學，那么邏輯學不難學。因此，如果許多學生喜歡邏輯學，那么，數(shù)學并不容易學。解析：與例13相應的蘊涵式是：(p∨q)∧(r→┑p)→(┑q→┑r)用歸謬賦值法來驗證它的有效性：(p∨q)∧(r→┑p)→(┑q→┑r)01011110010001矛盾，所以該蘊涵式是一個有效式，該推理是一個有效的推理。第二章：命題邏輯二、重言等值式置換規(guī)則證明下述關(guān)于重言等值式的定理：等值置換定理令CA表示A是C的子公式，CB是用B置換A在C中的一處或多處出現(xiàn)的結(jié)果，則：(Ⅰ)(A?B)→(CA?CB)是重言式；(Ⅱ)如果(A?B)是重言式，則(CA?CB)是重言式。第二章：命題邏輯我們先說明置換與代入的不同：(1)代入的對象是命題變項，置換的對象可以是命題變項，也可以是比變項更復雜的公式。(2)當用一個公式代入某一特定公式中的命題變項時，要求用該公式對該變項的每一處出現(xiàn)做代入，簡稱處處代入。置換則不同，以某一公式B置換C中的子公式A時，不必把A的每一處出現(xiàn)都換成B，可以只在需要的地方置換。(3)之所以如此，是因為代入公式與被代入公式不是等值的；而用來置換的公式與被置換公式是等值的，即(A?B)是重言式。第二章：命題邏輯第五節(jié)

命題邏輯的自然推理

第二章：命題邏輯在命題邏輯中，形式推演是從給定的前提(可以沒有)利用給定的推理規(guī)則，得出給定結(jié)論的過程。嚴格定義如下：D1命題邏輯中的形式推演是一個有窮長的公式序列，序列中的每一項或者是給定的前提，或者是從序列中前面的公式根據(jù)給定的規(guī)則得到的公式，序列的末尾是該推演的結(jié)論。如果序列末尾的公式是從空前提得到的，則稱該公式是命題邏輯的定理，此推演是關(guān)于該定理的一個證明。第二章：命題邏輯一、PN推演規(guī)則1.合取消去規(guī)則∧-：從A∧B可推出A；從A∧B可推出B。也可以寫成：A∧B├A；A∧B├B。2.合取引入規(guī)則∧+：從A，B可推出A∧B。也可以寫成：A，B├A∧B。3.析取消去規(guī)則∨-：從A∨B，A→C，B→C，可以推出C。也可以寫成：A∨B，A→C，B→C├C。4.析取引入規(guī)則∨+：從A可推出A∨B；從B可推出A∨B。也可以寫成：A├A∨B；B├A∨B。第二章：命題邏輯5.蘊涵消去規(guī)則→-：從公式A→B和A可以推出B。也可以寫成：A→B，A├B。6.蘊涵引入規(guī)則→+：如果在公式集Γ下引入假設A可以推出B，則在Γ本身之下可以推出A→B。7.等值消去規(guī)則-：從AB可推出A→B；從AB可推出B→A。也可以寫成：AB├A→B；AB├B→A。8.等值引入規(guī)則+：從A→B和B→A可推出AB。也可以寫成：A→B，B→A├AB。第二章：命題邏輯9.否定消去規(guī)則┑-：如果在公式集Γ下引入假設┑A可推出B和┑B，則在Γ下可推出A。10.否定引入規(guī)則┑+：如果在公式集Γ下引入假設A可推出B和┑B，則在Γ下可推出┑A。11.自推規(guī)則∈：從一組前提或假設A1，A2，A3，…，An出發(fā)，可推出該組中的任一公式Ai，記作A1，A2，A3，…，An├Ai(1≤i≤n)。第二章：命題邏輯以上11個規(guī)則可以分為兩組：∧+、∧-、∨+、∨-、→-、+、-和∈為一組，它們都是在原有前提之下進行的推演；→+、┑+、┑-為另一組，它們先在原有前提下引入某個假設，最后推出了不依賴于該假設、只依賴于原有前提的結(jié)論。所以，后三個規(guī)則既是引入假設的規(guī)則，也是最后解除假設的規(guī)則。第二章：命題邏輯二、PN定理及其證明為了正確地給出一個PN推演，并便于檢驗它的有效性，我們引入下面的書寫約定：(1)一開始就分行列出所有給定的前提，并在每個前提公式的右邊標明它們是前提。(2)如果要引入假設，最好一開始就引入所有假設，并在每個假設的右邊標明它們是假設。(3)每列出一個假設，就把它向上一個公式的右邊推移一個空格。第二章：命題邏輯(4)以后每列出一個公式，就在該公式右邊注明它是從上面哪個或哪些公式使用什么推理規(guī)則得到的(5)在一假設下根據(jù)∧+、∧-、∨+、∨-、→-、+、-和∈得到的公式，都與該假設對齊，表示它們?nèi)家蕾囉谠摷僭O和它前面的假設。(6)如果一個公式是通過使用→+、┑+、┑-得到的，則讓它“進位”，即與它上面的倒數(shù)第二個假設對齊，表示它不依賴于它上面的倒數(shù)第一個假設，該假設及其下面的公式都被解除了；但它仍依賴于倒數(shù)第二個假設及以前的假設。(7)我們在一推演的右邊畫一垂直線，表示該推演的起訖；如果右邊的公式是假設，則在該垂直線的頂端置一小圓圈。第二章：命題邏輯三、PN有前提推演PN的定理是無前提的推演，即前提或假設公式集Γ是空集。在日常思維中，我們常常是從一些前提出發(fā)，推出了某個或某些結(jié)論，而我們想知道從這樣的前提是否能邏輯地推出該結(jié)論，或者說已經(jīng)進行的某個推理是不是正確而有效的。我們當然有很多辦法做這件事情，例如先把該推理表示為符號公式，再用前面所講的判定方法去判定它是不是重言式。我們也可以用推理的方法，看一看使用PN規(guī)則，能不能從那些前提推出該結(jié)論。在做這樣的推演時，所有命題邏輯的定理在原則上都可以使用，因為我們是在利用命題邏輯去處理日常思維中的具體推理問題。更明確地說，我們是在應用邏輯，而不是在構(gòu)造邏輯本身。第二章：命題邏輯第六節(jié)

命題邏輯的擴充系統(tǒng)——廣義模態(tài)邏輯

第二章：命題邏輯一、模態(tài)詞的種類“模態(tài)”源于拉丁詞modalis，含“形態(tài)”“樣式”等意思，就是反映事物或人的認識存在、發(fā)展的樣式、情狀、趨勢等等的詞語。根據(jù)不同的標準，模態(tài)詞可以分為不同的種類。1.邏輯模態(tài)和非邏輯模態(tài)邏輯模態(tài)指邏輯上的必然性和可能性，邏輯、數(shù)學的一切規(guī)律和規(guī)則都被認為是必然的，凡不與這些規(guī)律和規(guī)則相矛盾的一切東西都被認為是可能的。例如，“一個推理，若前提真，推理形式正確，則結(jié)論必真”，“一個人不可能既比另一個人高又不比他高”，“太陽有可能明天從西方升起”，這些命題所表達的都是邏輯模態(tài)。第二章：命題邏輯非邏輯模態(tài)有時又稱“物理模態(tài)”，人們把所有自然科學的規(guī)律看作物理上必然的，凡不與這些規(guī)律相矛盾的一切都是物理上可能的。例如，“一個人不可能揪著自己的頭發(fā)上天”，“生物體必然要進行新陳代謝”，“人類的某些體育技能如田徑可能存在極限”，所有這些命題都表達著物理模態(tài)。邏輯模態(tài)和非邏輯模態(tài)的相互關(guān)系是：邏輯上不可能的東西一定是物理上不可能的，物理上可能的東西一定是邏輯上可能的。但是，物理上必然的不一定是邏輯上必然的，物理上不可能的不一定是邏輯上不可能的。牛頓力學的三大定律、巴甫洛夫的條件反射定律都不是邏輯上必然的；而太陽圍繞地球轉(zhuǎn)、孫悟空七十二變之類的事情都是邏輯上可能的。第二章：命題邏輯2.從言模態(tài)和從物模態(tài)在邏輯史上，歐洲中世紀邏輯學家把模態(tài)分為dedicto與dere，這一區(qū)分涉及模態(tài)詞的轄域。dedicto是指“關(guān)于語句的”，即模態(tài)詞所修飾的是意義完整的句子或命題。例如，“‘蘇格拉底有死’是必然的”，“‘明天發(fā)生海戰(zhàn)’是可能的”。這類模態(tài)命題的一般結(jié)構(gòu)是：p是必然的，p是可能的，指命題p為真具有必然性或可能性。dere是指“關(guān)于事物的”，“從屬于事物的”，即把模態(tài)詞插入句子中間，置于句子的系詞或動詞之前。第二章：命題邏輯3.狹義模態(tài)和廣義模態(tài)狹義模態(tài)是指事物或人的認識的必然性或可能性，在現(xiàn)代邏輯文獻中常把它們叫作“alethic模態(tài)”，這類模態(tài)涉及一命題真還是不真，更確切地說，涉及一命題的真假強度(必然真抑或可能真)，于是人們常將其譯做“真勢模態(tài)”，分別用符號□、

表示“必然”和“可能”。與狹義模態(tài)與廣義模態(tài)的區(qū)分相關(guān)聯(lián)，模態(tài)邏輯分為狹義模態(tài)邏輯和廣義模態(tài)邏輯。狹義模態(tài)邏輯就是指真勢模態(tài)邏輯，即關(guān)于含模態(tài)詞“必然”“可能”的命題的邏輯特性及其推理關(guān)系的邏輯，包括兩部分：模態(tài)命題邏輯和模態(tài)謂詞邏輯。第二章：命題邏輯二、模態(tài)命題的真值條件狹義模態(tài)是指事物或人的認識的必然性或可能性，在現(xiàn)代邏輯文獻中常把它們叫作“alethic模態(tài)”，這類模態(tài)涉及一命題真還是不真，更確切地說，涉及一命題的真假強度(必然真抑或可能真)，于是人們常將其譯做“真勢模態(tài)”，分別用符號□、

表示“必然”和“可能”。與狹義模態(tài)與廣義模態(tài)的區(qū)分相關(guān)聯(lián)，模態(tài)邏輯分為狹義模態(tài)邏輯和廣義模態(tài)邏輯。狹義模態(tài)邏輯就是指真勢模態(tài)邏輯，即關(guān)于含模態(tài)詞“必然”“可能”的命題的邏輯特性及其推理關(guān)系的邏輯，包括兩部分：模態(tài)命題邏輯和模態(tài)謂詞邏輯。第二章：命題邏輯20世紀50—60年代，鑒于模態(tài)邏輯發(fā)展的迫切需要，一批邏輯學家如克里普克(SaulKripke)等人從萊布尼茨的上述思想出發(fā)，發(fā)展了一種模態(tài)語義理論即可能世界語義學。相對于經(jīng)典語義學和萊布尼茨的思想而言，它有幾個重大的改進，具體來說：第一，它使命題的真假相對化，即相對于各種不同的可能世界而言。由于有多個可能世界，它們之間有某些差異，一個體可以在一可能世界中存在，但并不在另一可能世界中存在；一事件可以在一可能世界中發(fā)生，但不在另一可能世界中發(fā)生。于是，描述或反映該個體或事件的命題就有可能在一可能世界中真，但在另一可能世界中假。第二章：命題邏輯第二，它使必然性、可能性概念相對化。由于必然性、可能性概念是與命題的真假密切相關(guān)的，甚至是用后者定義的，既然后者是相對于特定的可能世界而言的，前者因此也就是相對于特定的可能世界而言的。第三，它使可能世界之間具有一定的關(guān)系。命題p在一可能世界中是必然的，不再要求它無限制地在所有的可能世界中真，而只要求它在與該世界有關(guān)的所有可能世界中真。第二章：命題邏輯三、模態(tài)邏輯系統(tǒng)TN模態(tài)邏輯系統(tǒng)TN是在如前所述的命題邏輯PN的11個推理規(guī)則的基礎上，加進與模態(tài)詞“必然”相關(guān)的推理規(guī)則所構(gòu)成的。新加入的規(guī)則有：1.必然消去規(guī)則(記為□-1)：在推演的任何步驟上，都可以從□A直接推出A，即：□A├A。2.必然引入子證明進入規(guī)則(記為□-2)：如果一個公式處于□的轄域內(nèi)，則該公式可以進入必然引入子證明，不過在進入之前，要去掉它前面的□；由于命題邏輯重言式都是必然的，所以在必然引入子證明的任何步驟上，都可以引入一個重言式。第二章：命題邏輯3.必然引入子證明退出規(guī)則(記為□+)：在退出一個必然引入子證明時，該子證明中的任何公式都可以加上□，特別是結(jié)尾公式。4.可能性引入規(guī)則(記為

+)：在推演的任何步驟上，都可以從A直接推出

A，即：A├

A。5.可能性消去規(guī)則(記為

-)：在推演的任何步驟上，都可以從□(A→B)和

A直接推出

B，即：□(A→B)，

A├

B。第二章：命題邏輯第七節(jié)

命題邏輯知識的綜合應用

第二章：命題邏輯

在國內(nèi)外各種能力性考試的邏輯部分中，有時會單獨用到關(guān)于某一種復合命題的知識，更多的時候是要綜合運用關(guān)于各種復合命題及其推理的知識。還有許多智力測驗和思考題，也有可能要綜合運用命題邏輯的知識，下面舉幾個比較復雜的例子，并詳細說明解題思路和方法，相信讀者能觸類旁通，舉一反三。第二章：命題邏輯［例22］北大百年校慶時，昔日學友甲、乙、丙會聚燕園。時光荏苒，他們也都功成名就，分別為作家、教授、省長。還知道：Ⅰ.他們分別畢業(yè)于哲學系、經(jīng)濟系和中文系。Ⅱ.作家稱贊中文系畢業(yè)者身體健康。Ⅲ.經(jīng)濟系畢業(yè)者請教授寫了一個條幅。Ⅳ.作家和經(jīng)濟系畢業(yè)者在一個省工作。Ⅴ.乙向哲學系畢業(yè)者請教過哲學。Ⅵ.過去念書時，經(jīng)濟系畢業(yè)者、乙都追求過丙。第二章：命題邏輯根據(jù)上述題干，下列陳述哪一個是真的?A.丙是作家，甲是省長。B.乙畢業(yè)于哲學系。C.甲畢業(yè)于中文系。D.中文系畢業(yè)的是作家。E.經(jīng)濟系畢業(yè)的是教授。第二章：命題邏輯解析：從題干知道，兩個不相容選言命題“或者畢業(yè)于哲學系，或者畢業(yè)于經(jīng)濟系，或者畢業(yè)于中文系”和“或者是作家，或者是教授，或者是省長”，對于甲、乙、丙都成立。由Ⅵ知道，甲畢業(yè)于經(jīng)濟系；由Ⅳ知道，甲不是作家；由Ⅲ知道，甲不是教授；所以，甲是省長。由Ⅴ知道，乙不是畢業(yè)于哲學系，乙當然也不是畢業(yè)于經(jīng)濟系，故他畢業(yè)于中文系；由Ⅱ知道，乙不是作家，所以乙是教授。由此可知，丙畢業(yè)于哲學系，是作家。因此，正確選項是A。第二章：命題邏輯［例24］紅星中學的四位老師在高考前對某理科畢業(yè)班學生的前景進行推測，他們特別關(guān)注班里的兩個尖子生。張老師說：“如果余涌能考上清華，那么方寧也能考上清華?！崩罾蠋熣f：“依我看這個班