離散數(shù)學 通關寶典

目錄第1章命題與命題公式 4命題與命題聯(lián)結(jié)詞 4命題與命題的表示 4復合命題與聯(lián)結(jié)詞 6命題公式的等值演算 11命題公式 11等值演算與蘊涵式 17聯(lián)結(jié)詞完備集 20第2章命題邏輯的推理理論 232.1范式 23范式的概念 23小項與大項 25主范式 28主析取范式 28主合取范式 29自然推理系統(tǒng) 30第3章謂詞邏輯 35謂詞的概念與表示 35量詞與合式公式 36謂詞演算的等價式與蘊涵式 37前束范式 39謂詞演算的推理理論 39第4章集合 41集合的基本概念 41集合的概念 41集合的表示法 424.2集合的運算 44集合的基本運算 44集合運算的恒等式 45有序?qū)εc笛卡兒積 49有序?qū)?49笛卡兒積 50第5章關系與函數(shù) 53關系及關系的性質(zhì) 53關系的定義及表示 53關系的性質(zhì) 55關系的運算 57關系的常規(guī)運算 57復合關系 59關系矩陣的布爾運算 60關系的閉包 61等價關系與序關系 62等價關系 62序關系 645.4函數(shù) 66函數(shù)的概念 66復合函數(shù) 67第6章代數(shù)系統(tǒng)的一般概念 70代數(shù)系統(tǒng) 70群與半群 73半群和獨異點 736.2.2群 74環(huán)與域 76第7章格與布爾代數(shù) 80格的基本概念 80格的定義 80格的性質(zhì) 81分配格與有補格 83分配格 83有補格 84布爾代數(shù) 86第8章圖 88圖的基本概念 88圖的連通性 93圖的表示 96第9章圖的應用 99歐拉圖與哈密頓圖 99歐拉圖 99哈密頓圖 1029.2平面圖 103樹及其遍歷 106樹的基本概念 106二叉樹的基本概念 110二叉樹與樹的遍歷 111PAGEPAGE41命題與命題的表示由一個或幾個已知的前提，推導出一個未知結(jié)論的思維過程稱為推理。推理的基本要素就是表達這些前提的一些陳述句，每個陳述句或成立或不成立，一般來講，限定于某種情況下，一個陳述句不可能既成立又不成立。成立或不成立可以看作是這個陳述句的一個屬性，稱之為真值。當陳述句成立時，就說其真值為真，表示為T當陳述句不成立時，就說其真值為假，表示為F。例如，“地球是行星”是一個陳述句，并且是正確的，即它的真值為真。而陳述句“2是無理數(shù)”是錯誤的，其真值為假。具有唯一真值的陳述句稱作命題，也稱為語句。真值為真的命題稱為真命題；真值為假的命題稱為假命題。有些陳述句并不具有唯一的真值，也就是說，它有時為真，有時為假。這樣的陳述句不是命題。例如，陳述句“xy5”，它的真值要依變量x與y的值來確定。比如，當x5，y3時xy5為真；當x1，y2時，xy5為假。因此在不確定變量x、y的值的情況下，無法確定“xy5”的真值。像這種有時為真有時為假的陳述句不是命題。請記住，命題的真值一定是唯一的，或者為真，或者為假，不能既真又假。有些陳述句具有唯一的真值，但是依我們目前所掌握的知識及了解的情況，不能判斷它的真假。例如“宇宙中存在與地球類似的有生命體的星球”，限于人類目前的認知水平，還不知道這樣的星球是否存在。但這個句子的真值是唯一的，所以它是命題。此外，疑問句、感嘆句、祈使句等都不能構(gòu)成命題。例1.1判斷下列句子中哪些構(gòu)成命題。（1）8不是素數(shù)；）雪是黑的；）到2049年世界人口將超過90億；）每臺計算機都有唯一的IP地址；）喜馬拉雅山好高?。。┗玖Ｗ邮遣豢煞值?；）離散數(shù)學難學嗎？）請遵守交通規(guī)則?。?）x12。解：只有陳述句才可能是命題，其他的語句如疑問句、感嘆句、祈使句等都不能是命題。依據(jù)這個準則，很容易知道（5（7）和（8）（5）是感嘆（7）是一般疑問句，（8）是祈使句，這三個都不是陳述句，所以都不是命題。在剩余的6個語句中，除（9）外都是命題。其中（1）是正確的，故為真命題；是錯誤的，即為假命題（3所描述的情況我們目前不得而知，需要等到20A9年時才能知道是對還是錯，但不管怎樣，它有唯一的真值，所以（3也是命題（4）和（6）所描述的情況需要根據(jù)專業(yè)知識來判斷真假，我們知道有些計算機是具有多IP地址的，而現(xiàn)代物理學已經(jīng)告訴我們，基本粒子是可分的，所以這兩個都是假命題；對于（9）中所描述的情況，它的真假值取決于x的值，當x1時，它為真，當x1時，它為假。當x的值沒有指定時，它的真假值是不確定的，也就是不唯一的，所以它不是命題。當然，當x的值已經(jīng)確定，我們可以判斷x12是否成立時，這個語句就是命題了?？偠灾袛嗝}有兩個條件，一是語句本身是個陳述句，二是它有唯一的真值。實際上，還有一種特殊的陳述句也不是命題，那就是悖論。悖論是指在邏輯上可以推導出互相矛盾之結(jié)論的陳述。對于一個悖論A，如果認為它是真的，則可以推導出A為假；如果認為A是假的，則可以推導出A為真。例如，“我正在說謊”就是一個悖論。讀者可以自行驗證。悖論不是命題，本書也不討論悖論。在數(shù)理邏輯中，常常使用符號來表示一個命題，就好像我們在程序中用標識符表示變量一樣，用符號來表示命題的這個過程稱為命題的符號化。表示命題的符號既可以是大寫的英文字母，也可以是小寫的英文字母，如P或p有時還可以用字母加數(shù)字來表示，為了清楚起見，數(shù)字常表示為下標，如P1Q2。表示命題的符號稱為命題標識符。當命題標識符表示某個確定的命題時，稱為命題常量或命題常項，如果命題標識符只表示命題位置，稱為命題變元或命題變項。命題變元可以表示任意一個命題，即在確定它所代表的命題之前，命題變元不具有確定的真值。當用一個具體的命題去代替命題變元時，它的真值也就確定下來了，這稱為對命題變元的指派。命題為真時，其真值用“T1”來表示，為假時，其真值用“F”或“0”來表示。例1.2將下面命題符號化，并指出它們的真值。）是有理數(shù)；）所有的素數(shù)都是奇數(shù)；（3）6是一個合數(shù)。解：分別使用P、Q和R來表示上述三個命題：P是有理數(shù)。Q：所有的素數(shù)都是奇數(shù)。R6是一個合數(shù)。是無理數(shù)，所以P的真值為F。2是素數(shù)，也是偶數(shù)，除此之外，其他的素數(shù)都是奇數(shù)。Q的真值為F。因為2和3都是6的因子，所以6是合數(shù)，R的真值T。復合命題與聯(lián)結(jié)詞在例1.2所舉的命題示例中，都是不能再分解的命題，這樣的命題稱為原子命題或簡單命題。實際中，我們常常要表達更豐富的信息，例如“如果今年有假期，我將去歐洲旅游”，這個句子中表達了兩層含義，一是“今年有假期”，二是“我去歐洲旅游”，而且這兩個含義之間還是有關聯(lián)的，前一個是前提，后一個是結(jié)果。在自然語言中，我們常使用連詞來表示兩個句子之間的關系，例如本例中的“如果”。在命題符號化時，這樣的連詞將表示為聯(lián)結(jié)詞，聯(lián)結(jié)詞都具有特定的符號。由原子命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題，稱為復合命題。一般而言自然語言都具有二義性，即有些句子的含義多于一種。在數(shù)理邏輯中，為了能精確地進行推導，命題及聯(lián)結(jié)詞的含義必須是確定的。數(shù)理邏輯中常用的聯(lián)結(jié)詞共有五個，下面詳細介紹。）定義1.1設P為命題，P的否定是一個復合命題，記作P。符號稱作否定聯(lián)結(jié)詞。若PTP為FP為F，PT。命題P讀作“非P由定義可知，P是一個復合命題。復合命題的真值依命題中所含各原子命題的真值來確定，可用一張表來表示，這樣的表稱為真值表。聯(lián)結(jié)詞的定義如表1.1所示。1.1的定義PPTFFT例1.3給出命題P:“今天是星期五”的否定，并用自然語言表示出來。解：P：今天是星期五。P：今天不是星期五。2.合取定義1.2設P、Q為兩個命題，P和Q的合取是一個復合命題，記作PQ。符號稱為合取聯(lián)結(jié)詞。當且僅當P、Q同時為T時，PQT，其余情況PQ為F。P和Q的合取表示的是“P并且Q”的含義。聯(lián)結(jié)詞的定義如表1.2所示。PQPPQPQPAGEPAGE7TTTTFFFTFFFF自然語言中的“并且”可以對應于合取，其根本的含義是表示兩件事情同時成立。與此的“與”用在主語中，它連接的是兩個并列的主語，而不是兩個原子命題。所以這個命題并不是合取命題，實際上，它僅僅是一個原子命題。1.4將下面命題符號化。（1）2我今天不但聽了離散數(shù)學課，還聽了數(shù)據(jù)結(jié)構(gòu)課；今天的離散數(shù)學課停上，美元上漲。（設P:2Q：2故（1）PQ。設P:我今天聽了離散數(shù)學課，Q：我今天聽了數(shù)據(jù)結(jié)構(gòu)課。故（2）PQ。設P:今天的離散數(shù)學課停上，Q：今天美元上漲。故（3）PQ。復合命題PQ中的兩個原子命題可以互換位置，即PQ與QP的含義是相同的，它們的真值表也是一樣的。這表示合取具有對稱性。自然語言除了要符合語法外，還要有合理的語義，即表達的意思要合乎邏輯。但是復合命題所含的多個原子命題之間可以沒有邏輯關聯(lián)性。例如（3）中的兩個原子命題之間不存在任何關聯(lián)關系，上沒上離散數(shù)學課，不會影響美元的走勢。在命題邏輯中，我們僅關心它的表示，而忽略其語義。所以它的真值只與原子命題的真值有關，與語義無關。特別地，命題聯(lián)結(jié)詞“合取”可將兩個互為否定的命題聯(lián)結(jié)在一起。以P表示命題，PP的真值必是F。如表1.3所示。3.析取定義1.3設P、QP和Q的析取是一個復合命題，記作PVQ。符號V稱為析取聯(lián)結(jié)詞。當且僅當P、Q同時為FPQ的真值為F，其余情況PVQ的真值為T。P和Q的析取表示的是“P或者Q”的含義。聯(lián)結(jié)詞V的定義如表1.4所示。表1.3PP的真值PPPPTFFFTFPAGEPAGE81.4VPQPQTTTTFTFTTFFF從上述定義可以看出，聯(lián)結(jié)詞析取與自然語言中的“或”有些相似。1.5將下面命題符號化。100我今天或者去聽離散數(shù)學課，或者去聽數(shù)據(jù)結(jié)構(gòu)課。設PQ100故（1）可表示為PVQ。這個命題表達的是王小林或者是跳高冠軍，或者是短跑冠軍，也有可能是兩個項目的冠軍。（2）設PQ：我今天去聽數(shù)據(jù)結(jié)構(gòu)課。故（2）可表示為PVQ。這個命題表達的是我今天可能去聽離散數(shù)學或者數(shù)據(jù)結(jié)構(gòu)課，也可能兩門課都去聽。時成立。自然語言中有時會使用“或”來表示“相斥”的含義，即用“或”連接的兩者不能同時成立，這樣的語句不能表示為析取。1.6分析以下的復合命題。王小林今天或者去美國，或者去歐洲。王小林或者是坐火車去北京，或者是乘飛機去北京。（設PQ顯然，如果王小林今天去了美國，他就不可能去歐洲，反之也是一樣。王小林沒有分身術，他只能去一個地方。所以（1）PVQ。（2）設PQ：王小林乘飛機去北京。這個命題假設王小林只需乘坐一種交通工具即可到達北京。與（1）類似，王小林不能PVQ也不能精確地表達（2）中命題的含義。（1）和（2）所表述的這兩個例子有一個共同的特點，即復合命題中的兩個原子命題2）均可表示為(PQPQ。與合取命題類似，復合命題中PQ中的兩個原子命題也可以互換位置，即PQ與QP的含義是相同的，它們的真值表也是一樣的。這表示析取V具有對稱性。4.條件定義14設PQ為兩個命題，P和Q組成的條件命題是一個復合命題，記作PQ。符號稱為條件聯(lián)結(jié)詞。當且僅當P的真值為TQ的真值為F時，PQFPQ的真值為T。復合命題讀作PQ讀作“如果P那么Q”，亦可讀為“若P則Q”。其中P表1.5的定義PQPQTTTTFFFTTFFT稱為前件或前提，Q稱為后件或結(jié)論。條件聯(lián)結(jié)詞的定義如表1.5所示。條件命題表示的是，當前件發(fā)生時后件是否發(fā)生。而當前件沒有發(fā)生即P為F時，后件發(fā)生或不發(fā)生都沒有關系。與合取和析取均具有對稱性不同，條件命題中PQ的前件與后件不可以互換位置，即PQ與QP的含義是不同的。所以條件聯(lián)結(jié)詞不具有對稱性。例1.7將下面命題符號化。）如果今天不下雨，我就去公園鍛煉。）如果我考試通過，就能拿到合格證書。（1）設P:今天下雨，Q：我去公園鍛煉。故（1）可表示為PQ。僅當今天沒有下雨而我沒去公園鍛煉時，命題（1）為F（2）P:我考試通過，Q：我拿到合格證書。故（2）可表示為PQ。需要注意，條件命題的前件和后件之間可以在語義上不存在邏輯關系。這與我們?nèi)粘５谋硎鍪怯胁町惖?。?.8如果雪是黑的，則房間里有20張桌子。設P:雪是黑的；Q：房間里有20張桌子。本例符號化為PQ。雙條件定義15設P、Q為兩個命題，P和Q組成的雙條件命題是一個復合命題，記作PQ。符號稱為雙條件聯(lián)結(jié)詞。當P與Q的真值相同時，PQ的真值TPQ的真值為F。復合命題PQ讀作P當且僅當Q。聯(lián)結(jié)詞的定義如表1.6所示。PAGEPAGE10PQPQTTTTFFFTFFFT雙條件命題PQ表示P與Q的真值是否相同。當它們的真值相同時，也可以看作P與Q是等價的，即P與Q互為充分必要條件。數(shù)學上有時也將充分必要條件表示為“iffifdonlyif”即當且僅當?shù)囊馑肌２浑y看出(PQQP)與互為充要條件。

PQ的邏輯關系完全一樣，都表示雙條件命題PQ中的兩個原子命題互為條件，所以它們也是可交換的，即

PQ與

QP的含義是完全相同的。所以雙條件聯(lián)結(jié)詞具有對稱性。例1.9將下面命題符號化，并指出其真值。）當且僅當實數(shù)R可以表示為分數(shù)時，R是有理數(shù)；3） 是無理數(shù)當且僅當加拿大位于亞洲。3解（1）設P：實數(shù)R可以表示為分數(shù)，Q：實數(shù)R是有理數(shù)。則（1）可表示為PQ。由數(shù)學知識可知，（1）所表述的即是有理數(shù)的定義，所以它的真值為T。3（2）設P： 是無理數(shù)，Q：加拿大位于亞洲。3則（2）可表示為PQ。由數(shù)學知識知，PT，而由地理知識知，Q為F，所以（2）的真值為F。例1.10將下列命題符號化。）如果今天不下雨而且不刮風，我會去爬山；）若今天是星期一，則明天是星期二；）只有今天是星期一，明天才是星期二。解：（1）設P：今天下雨，Q：今天刮風，R：我去爬山。則（1）可表示為(PQR）P：今天是星期一，Q：明天是星期二。則（2）可表示為PQ。本例還隱含著另一層意思，即如果今天不是星期一（前件為假時，則明天可能是星期二，也可能不是星期二，不得而知?；蛘叻催^來說，如果明天是星期二，則不表明今天一定是星期一。要注意，命題的含義一定要和我們?nèi)粘５母拍罘珠_。）P:今天是星期一，Q：明天是星期二。則（3）可表示為QP。命題pq表示“q是p的必要條件”。自然語言中表示“q是p的必要條件”PAGEPAGE11有許多不同的敘述方式，例如，“只要p，就q”，“因為p，所以qp僅當q只有q才p”，等等。本例中表述的另一層含義是“明天是星期二”的話，“今天一定是星期一”。例1.11設P:今天下雨，Q：今天刮風，R：我去爬山。將下面命題用自然語言表述。（1）(PQ)R；（2）R(PQ)；（3）PQ；（4）PQ；（5）QP。（1）(PQ)R表示：今天要是下雨或者刮風，我就不去爬山了；）R(PQ)表示：如果我去爬山了，則今天既沒下雨也沒刮風;）PQ表示：今天下雨了，但沒有刮風；）PQ表示：如果今天下雨，就不會刮風；）QP表示：如果今天刮風，就會下雨。2命題公式的等值演算121命題公式命題符號化的過程中，可以用一個符號表示一個命題。當符號P代表一個具體的命題時，符號P稱為命題常項，此時P的真值是確定的，所以稱為“常”項。這類似于數(shù)學表達式中的一個常數(shù)。而當符號P僅僅表示是一個命題，但并沒有指明是哪個命題時，P為命題變元。命題變元P可以代表任一個命題，正如數(shù)學表達式中的一個變量一樣。如果給P代入一個真值為T的命題，P的真值為T;如果代入一個真值為F的命題，P的真值為F。在代入之前，P元。一般地，命題變元不是命題。在表示數(shù)學操作時，我們可以用操作符將操作數(shù)連接起來，得到一個數(shù)學表達式，比如a+3。同時可以使用圓括號改變操作符的運算次序，比如2*（x3。在命題邏輯中也是一樣，可以使用聯(lián)結(jié)詞將命題連接起來，得到一個更復雜的命題，即復合命題。這里，命題類似于表達式中的操作數(shù)，聯(lián)結(jié)詞類似于表達式中的操作符。聯(lián)結(jié)詞連接的命題符號既可以是命題常項，也可以是命題變元。同樣，也可以在這樣的式子中添加圓括號。將命題用聯(lián)結(jié)詞和圓括號按一定的邏輯關系聯(lián)結(jié)起來的符號串稱為合式公式。1.6命題演算的合式公式定義如下：）單個命題變元和命題常項是合式公式，并稱為原子命題公式；）若A是合式公式，則（A)是合式公式；）若A、B是合式公式，則（AB（AB（AB（AB）是合式公式；）有限次地應用（1）?（3）形成的符號串是合式公式。合式公式也稱為命題公式或命題形式，簡稱為公式。在合式公式中，當其中含有命題變元時，合式公式?jīng)]有確定的真值。僅當一個公式中所有的命題變元都被指派了具體的命題時，公式才有確定的真值。這與數(shù)學表達式是類似的，如果一個表達式中含有變量，且不知道變量的值，則表達式的值也是不知道的。只有給所有變量均賦予確定的值后，表達式的值才確定下來。與數(shù)學表達式必須要遵循語法規(guī)則一樣，合式公式也必須遵循定義1.6中所規(guī)定的規(guī)則，這樣形成的符號串才能稱為公式。定義1.6是一個遞歸定義，由最基礎的原子命題逐步形成最終的公式。例112設P、Q、R分別代表命題變元或命題常項，給定以下字符串，判斷哪些是合式公式。（1）(PQ)（2）（3）（4）

(PQ)(PQ)PQ(PQ)PQ（1（2（3）都是合式公式。實際上，合式公式最外層的括號是可以省略的，所以（1）還可以表示為：PQ（2）本身已去掉了最外層的括號（4）不是合式公式。有意思的是（3）與（2）相比，它去掉了第一對括號。數(shù)理邏輯中規(guī)定，不影響運算次序的括號也可以省去。與數(shù)學表達式一樣，合式公式中的括號可以改變運算次序（2（3相差的只是第一對括號，去掉它會不會改變運算次序呢？這要看各聯(lián)結(jié)詞的優(yōu)先級了。命題邏輯中規(guī)定，聯(lián)結(jié)詞優(yōu)先次序依次為：，，，，。的優(yōu)先級高于的優(yōu)先級，有沒有括號，都要先計算運算。因（2）與（3）是一樣的。綜上所述，在定義1.6之外，合式公式還有以下的約定。）合式公式的最外層括號可以省略；）不影響運算次序的括號也可以省略；）聯(lián)結(jié)詞的優(yōu)先次序為：，，，，。定義1.7設Ai是公式A的一部分，且Ai是一個合式公式，稱Ai是A的子公式，或公式分量。例1.13指出以下所給合式公式中的子公式有哪些。A：(PQ)(R(PQ))解：已知公式A：(PQ)(R(PQ，它的子公式有以下一些：A1：PA3：RA4：PA5：PQA6：PQA7：R(PQ)在命題公式中，由于有命題變元的出現(xiàn)，因而真值是不確定的。用命題常項替換公式中的命題變元稱作指派。當將公式中出現(xiàn)的全部命題變元都指派成具體的命題常項之后，公式就成了真值確定的命題。nn定義1.8設A為一命題公式，P1P2P為出現(xiàn)在A中的所有命題變元，對P1，P2，…，P各指定一個真值稱為對A的一種指派或賦值。若指定的一種指派使A的值為真，則稱這組值為A的成真指派；若指定的一種指派使A的值為假，則稱這組值為A的成假指派。nn若命題公式A中共有命題變元心1，P2，…，n，給定一組指派i（i,,...,n，iF或iT。根據(jù)組合理論可知，含n個命題變元的命題公式，共有2n組指派。將命題公式A在所有指派下的取值情況列成表，稱為A的真值表。在真值表中，真值T、F也可分別用1、0表示。構(gòu)造真值表的具體步驟如下：）找出公式中所含的全體命題變元，設為PP2P，列出2n個賦值。1 n賦值從FF…F開始，然后按二進制加法依次寫出每個賦值，直到TT…T為止，或者從TTT開始，直到FF…F為止；）按從簡到繁的順序?qū)懗龉降母鱾€子公式；）對應各個賦值計算出各子公式的真值，直到最后計算出公式的真值。例1.14分別構(gòu)造下列合式公式的真值表，并分別指出其成假賦值。（1）PQR)（2）(PQ)R（3）(PQ)R。表1.7P(QR的真值表PQRQRP(QR)FFFTTFFTTTFTFFTFTTTTTFFTTTFTTTTTFFFTTTTTP(QR的成假賦值有1個：TTF）(PQ)R的真值表如表1.8所示。表1.8P(QR的真值表PQRPQ(PQ)RFFFTFFFTTTFTFTFFTTTTTFFFTTFTFTTTFTFTTTTT(PQ)R的成假賦值有三個，分別是：FFF、FTF和TTF。）(PQ)R的真值表如表1.9所示。表1.9(PQ)R的真值表PQRPQ(PQ)RFFFFTFFTFTFTFFTFTTFTTFFFTTFTFTTTFTFTTTTT(PQ)R的成假賦值有1個：TTF。從例1.14可以看出，有的命題公式在命題變元的不同指派下，其對應的真值與另一命題公式完全相同，如表1.7中的P(QR與表1.9中的(PQ)R。這表明了合式公式的另一個重要特性。定義1.9 給定兩個命題公式A和B,設

P1，P2，…，

Pn為所有出現(xiàn)于A和B中的原子變元，若給P1，P2，…，Pn任一組真值指派，A和B的真值都相同，稱A和B是等值的或等價的，記為AB。若至少存在—組真值指派，使得A與B的真值不相同，稱A和B不等值或不等價，記為AB。定義中的符號和是否等值的一種記法。

AB都不是聯(lián)結(jié)詞，它只是用來說明A與B由等價的定義可知,PQPQ,(PQPQ)PQ。定義1.10設A為一命題公式，若A在它的各種指派情況下，其取值均為真，則稱公式A為重言式或永真式。定義1.11設A為一命題公式，若A在它的各種指派情況下，其取值均為假，則稱公式A為矛盾式或永假式。定義1.12設A為一命題公式，若A在它的各種指派情況下至少存在一組成真指派，則稱A是可滿足式。若可滿足式A至少存在一個成假賦值，則稱A為非重言式的可滿足式。從定義1.10~定義1.12可知以下的結(jié)論：）合式公式P是可滿足式，等價于P至少存在一個成真賦值；）重言式一定是可滿足式，但可滿足式不一定是重言式；（3）若兩個命題公式P和Q等價，則PQ是重言式。例1.15給定下列合式公式，哪個是重言式，哪個是矛盾式，對于可滿足式，指出它的成真賦值。（1）(PQ)(PQ)；（2）(PQ)Q；（3）(PQQR。（1）(PQ)(PQ)的真值表如表1.10所示。由表1.10（1）是重言式。表1.10(PQ)(PQ的真值表PQPQ(PQ)PQPQ(PQ)(PQ)TTTFFFFTTFFTFTTTFTFTTFTTFFFTTTTT（2）(PQQ的真值表如表1.11所示表1.11(PQQ的真值表PQPQ(PQ)(PQ)QTTTFFTFFTFFTTFFFFTFF由表1.11（2）是矛盾式。）(PQQR的真值表如表1.12所示。表1.12(PQQR的真值表PQRP(PQ)(PQ)Q(PQ)QRTTTTFFTTTFTFFFTFTFTFTTFFFTFFFTTTFFTFTFTFFFFFTTFFTFFFTFFF由表1.12可知（3是可滿足的，其成真賦值分別是：TTTTFT、FTT和FFT。重言式常記為T，矛盾式常記為F。我們已經(jīng)知道，含n個命題變元的命題公式共有2n組指派，另一方面，含n個命題變元的命題公式會有無窮多個。因此，這無窮多個命題公式中，存在兩個公式P與Q，它們的真值表是相同的，即P與Q是等值的。實際上，對任一個公式P，都存在無窮多個公式與P等價。在命題邏輯中，常用的命題定律列在表1.13中。表1.13常用的命題定律雙重否定律AA冪等律AAA,AAA結(jié)合律(AB)CA(BC)(AB)CA(BC)交換律ABBAABBA分配律ABC)ABAC（對的分配律）ABC)ABAC（對的分配律）吸收律A(AB)A，A(AB)A德摩根律(AB)AB，(AB)AB同一律AFA，ATA零律ATT,AFF排中律AAT否定律AAFPAGEPAGE17蘊涵等值式ABAB等價等值式AB(AB)(BA)假言易位ABBA等價否定等值式ABAB歸謬論(AB)(AB)A1.2.2等值演算與蘊涵式研究兩個公式是否等值有兩種方法，一是基于真值表，看看兩個公式的真值表是否完全相同。二是基于表1.13中列出的常用命題定律。對于比較復雜的公式，第二種方法更方便，也更簡捷。由已知的等值式推演出另外一些等值式的過程稱為等值演算或等價變換，這是布爾代數(shù)或邏輯代數(shù)的重要組成部分。等值演算基于下列置換規(guī)則定理。定理1.1設（A）是含子公式A的命題公式，使用子公式B置換（A）中A的所有出現(xiàn)，得到命題公式（B，若則（A）（B。證明：因為若BA，那么在任意的真值賦值下B和A的真值都相同，把它們代入（x）得到的結(jié)果當然也相同，從而（A）（B。 例1.16用等值演算法驗證等值式：P(PQ)(PQ)(PQ(PQ)P(QQ)PT

P左 (同一律） 證畢例1.17(PQ)RP(QR)證明：在例1.14中，通過構(gòu)造(PQ)R與P(QR的真值表（表1.8和表1.7)，我們已經(jīng)看到這兩個公式是不等值的，現(xiàn)在再采用等值演算法證明這個結(jié)論。(PQ)R(PQ)R(PQ)R(PQ)RP(QR)P(QR)P(QR)(PQ)R

(蘊涵等值式）(蘊涵等值式）（德摩根律）（蘊涵等值式）（蘊涵等值式）（結(jié)合律）(PQ)R與(PQ)R是不相同的，當R取F時，兩個式子的真值分別PQ和PQPFPQF，而PQ為T。由FXF(X表示不論Q取何值）使得(PQRF，但使(PQ)RT,即FXF是(PQ)R的成假賦值，但是P(QR)的成真賦值。故(PQ)RP(QR)。 證畢例1.18(PQ)R(PR(QR)證明：方法一自左向右證明。PAGEPAGE18左=(PQ)R(PQ)R(PQ)R(PR)(QR)

（蘊涵等值式）（德摩根律）（分配律）(PR)(QR)右 （蘊涵等值式）方法二 自右向左證明。右=(PR)(QR)(PR)(QR)(PQ)R(PQ)R

（蘊涵等值式）（分配律）（德摩根律）(PQ)R左 （蘊涵等值式）故(PQ)R(PR)(QR) 證畢由命題定律證明等值式時，既可以從左向右證明（如例118中方法一所示），也可以從右向左證明（如例118中方法二所示），還可以左、右同時演算，讓它們都等于一個中間結(jié)果，從而證明左、右等值。在證明兩個命題公式是等值的時候，除了上述所說的真值表法及使用命題定律法之外，還可以應用下述定理進行推演。定理12設A、B為兩個命題公式，AB當且僅當AB為一個重言式。證明：若AB則A、B有相同真值，AB永為TAB為重言式，則AB永為T，故A、B的真值相同，即AB。 證畢定義113當且僅當PQ是一個重言式時，我們稱“P蘊涵Q”，并記作PQ。PQ稱P蘊涵Q或蘊涵式，亦稱作永真條件式。蘊涵式有下列性質(zhì)：（1）對任意公式AAA;對任意公式A、B和CAB，BC則AC;對任意公式A、B和C，若AB，AC則A(BC)對任意公式A、B和CAC，BC，有ABC。（1）顯然。下面證明（2。設AB,BC，則AB和BC均為重言式。分以下情況討論：如果A的真值為T，由AB是重言式，則B的真值為T，由BC為重言式，得C的真值為T，即AC為T。②如果A的真值為FAC必為T。綜上，因為AC是重言式，所以AC。下面證明（3。設AB，ACAB和AC均為重言式。分以下情況討論：①如果A的真值為TAB和AC是重言式，則B和C的真值均為T，得到BC的真值為T，即A(BC為T。②如果A的真值為F，則A(BC)必為T。綜上，因為A(BC)是重言式，所以A(BC)。下面證明（4。設AC，BC，則AC和BC均為重言式。分以下情況討論：①如果A的真值為T，B的真值為TAB為TAC是重言式，則C的真值為T，即ABC為T。②如果A的真值為TB的真值為F，則AB為T。由AC是重言式，則C的真值為TABC為T。③如果A的真值為F，B的真值為T,則AB為T。由BC是重言式，則C的真值為TABC為T。④如果AFBF，則ABF，則ABC為T。綜上，因為ABC是重言式，所以ABC。證畢定理1.3設A、B為任意兩個命題公式，AB的充分必要條件是AB且BA。證明：必要性若AB由定理1.2可知，AB為重言式。由等價等值式有ABABBA)，故ABBA都為T，ABBA。充分性若AB且BA，則必有AB和BA均為重言式。因此AB為重言式，AB成立。 證畢根據(jù)定理1.3PQPQ且QP即可。但如何證明蘊涵式PQ呢？除了利用真值表法證明PQ是重言式外，還有另外兩種方法：對于PQP的真值取T、Q的真值取FPQ真值都為T。故要證PQ，只需對PQ的前件P指定真值為T，若由此推出Q的真值亦為T，則

PQ是重言式，即

PQ成立。由于(PQ)(QP,所以要證PQQP是重言式，亦即證明假定后件Q的真值取FQ為真P的真值為FP，即推證了QPPQ成立。例1.19推證QPQ)P。證明：方法一Q(PQ為T，則Q為TPQ為T，進而得知Q為F。若P為TPQ為T，知Q必為T。矛盾。PF，即P為T。方法二假定PFP為T。若QFPQFQPQF。若Q為T，則Q為FQPQ為F。所以QPQP成立。證畢有一些重要的重言蘊涵式，稱為推理定律，如表1.14所示。1.14PQP化簡律PQQ化簡律P(PQ)附加律PPQ變形附加律QPQ變形附加律(PQ)P變形簡化律(PQ)Q變形簡化律P(PQ)Q假言推理(PQ)QP拒取式(PQ)QP析取三段論(PQ)(QR)(PR)條件三段論(PQ)(QR)(PR)等價三段論(PQ)(RS)(PR)QS合取構(gòu)造二難(PQ)(RS)(PR)QS析取構(gòu)造二難PQ(PR)(QR)前后件附加PQ(PR)(QR)前后件附加13聯(lián)結(jié)詞完備集1.1和，并且規(guī)定了它命題P和Q，它們所能構(gòu)成的不同真值結(jié)果共有16種，可以證明，這五個聯(lián)結(jié)詞已足夠用來構(gòu)成想要的任一復合命題。定義1.14設Sn(n1)元真值函數(shù)都可以由僅含S中的S是聯(lián)結(jié)詞完備集。根據(jù)定義可知，聯(lián)結(jié)詞集,,是完備集。由命題等值演算中可知，有些聯(lián)結(jié)詞可以轉(zhuǎn)換為其他的聯(lián)結(jié)詞，對同一個命題公式可通過等值公式的轉(zhuǎn)換，以不同的形式表示出來。例如，由等價等值式PQ(PQ)(QP的公式等價變換”的公式。這樣，由聯(lián)結(jié)詞集,,組合而成的所有命題公式，就可由聯(lián)結(jié)詞集,,來表示。由此得到，聯(lián)結(jié)詞集,,也是完備集，而且是比,,,,元素個數(shù)更少的集合。我們還可以進一步減少這個集合中的元素個數(shù)。由蘊涵等值式PQPQ說明包含“”和“V”的公式。由此，我們又可以簡化聯(lián)結(jié)詞集，得到,,。則聯(lián)結(jié)詞集,,也是完備集。最后，由德摩根律(AB)AB和(AB)AB，可將“與“V”相互轉(zhuǎn)換。聯(lián)結(jié)詞集,或,都是完備集。,及,稱作命題公式的最小聯(lián)結(jié)詞完備集。由上面的討論可知，聯(lián)結(jié)詞完備集可有以下幾種：（3）S3,（4）S4,（5）S5,而、、、,或等都不是命題公式的聯(lián)結(jié)詞完備集。、、。在計算機硬件設計中，出現(xiàn)了“與非門”或“或非門”這樣的結(jié)構(gòu)，對應于此，定義了以下兩個新的聯(lián)結(jié)詞。定義1.15設P、QP與Q的否定式是一個復合命題，稱作P與Q的PQPQ(PQ符號稱為與非聯(lián)結(jié)詞。定義1.16設P、QP或Q的否定式是一個復合命題，稱作P與Q的或非式，記作PQPQ(PQ。符號稱為或非聯(lián)結(jié)詞。和都是聯(lián)結(jié)詞完備集。練習題下列語句中哪個是真命題？（）A我正在說謊。B嚴禁吸煙。C如果1+2=3，那么雪是黑的。D如果1+2=5，那么雪是黑的。下面聯(lián)結(jié)詞中不具有對稱性的是（）A含n個命題變元的任一命題公式的指派個數(shù)是（）A2n2nn222n答案1.D2.B3.B2章命題邏輯的推理理論范式范式的概念定義2.1僅由有限個文字構(gòu)成的合取式稱作簡單合取式。例如，P，Q，PP、PQ、PQRPQR都是簡單析取式。P、Q、

PP、

PQ、PQR、和

PQR都是簡單合取式。實際上，簡單析取式中不包含除析取聯(lián)結(jié)詞之外的其他聯(lián)結(jié)詞，類似地，簡單合取式中不包含除合取聯(lián)結(jié)詞之外的其他聯(lián)結(jié)詞。2.1簡單析取式和簡單合取式有以下性質(zhì)。一個簡單析取式是重言式，當且僅當它同時含某個命題變元及它的否定式?！獋€簡單合取式是矛盾式，當且僅當它同時含某個命題變元及它的否定式。設A是含nApj否定式

pj，由交換律、排中律和零律可知，A為重言式。反之，若A為重言式，則它必同時含某個命題變元及它的否定式。否則，A中的不帶否定符的命題變元都取F值，帶否定符的命題變元都取T值，此賦值是A的成假賦值，這A是重言式相矛盾。（2）設A是含n個文字的簡單合取式，若A中既含某個命題變元pj，又含它的否定式pj，則由交換律、否定律和零律可知，A為矛盾式。反之，若A為矛盾式，則A中必同時含某個命題變元及它的否定式。否則，A中的不帶否定符的命題變元都取T值，帶否定符的命題變元都取F值，此賦值是A的成真賦值，A是矛盾式相矛盾。證畢例如，PPQRTQRTPPQRFQRF。.212...（n1，A1A2An都是簡單析取式。例如，(PR)(PQ)(RQ)是一個合取范式，它由三個簡單析取式的合取組成。合取范式是由簡單析取式的合取構(gòu)成的，根據(jù)合取聯(lián)結(jié)詞的定義可知，當且僅當每個簡單析取式都是重言式時，合取范式是重言式。定義.12...（n1，其中A1，A2，…，An都是簡單合取式。例如，(PR)(PQR(QR是一個析取范式，它由三個簡單合取式的析取組成。析取范式是由簡單合取式的析取構(gòu)成的，根據(jù)析取聯(lián)結(jié)詞的定義可知，當且僅當每個簡單合取式都是矛盾式時，析取范式是矛盾式。實際上，有些命題公式既可以看成是析取范式也可以看成是合取范式。例如PQR既可以看成是由一個簡單合取式構(gòu)成的析取范式，也可以看成是由三個簡單析取式構(gòu)成的合取范式；類似地，PQR既可以看成是由三個簡單合取式構(gòu)成的析取范式，也可以看成是由一個簡單析取式構(gòu)成的合取范式。范式的步驟如下。①任何公式都可變換為僅含聯(lián)結(jié)詞完備集,,中的聯(lián)結(jié)詞的公式。利用等價等值式ABABBA與蘊涵等值式ABAB的聯(lián)結(jié)詞和；②利用雙重否定律

和德摩根律

AB)AB、AB)AB進行等值變換，保證在范式中不出現(xiàn)形如A、AB)、(AB)出現(xiàn)在命題變元的前面，而不是括號的前面；③利用分配律ABC)ABAC、ABC)ABAC)進行等值變換，保證在析取范式中不出現(xiàn)形如A(BC)的子公式，在合取范式中不出現(xiàn)ABC的子公式。例2.1求(P(QR))S的析取范式和合取范式。解：先求析取范式。(P(QR))S(P(QR))S(P(QR))SP(QR)S再求合取范式。(P(QR))S(P(QR))S(P(QR))SP(QR)S(PS)(QR)(PQS)(PRS)一般來講，一個命題公式的合取范式或析取范式并不是唯一的，例如P(QR)是一個析取范式，它亦可寫成：P(QR)(PQ)(PR)(PP)(PR)(PQ)(QR)為了能夠唯一表示合式公式，我們進一步規(guī)范合式公式的形式。為此，先介紹小項與大項的概念。小項與大項定義2.4n個命題變元的簡單合取式，稱作布爾合取或極小項，簡稱為小項，其中每個式，或以變元的否定形式。兩個命題變元P和Q的小項共有4PQPQPQ和PQ。類似地，三個命題變元P、Q、R的小項共有8個，分別是：PQR、PQR、PQRPQR、PQR、PQR、PQR和PQR。按慣例，小項中代表命題變元的各字母按英文字母表的次序排列。比如，PQ通常不會寫為QP，小項PQRRPQ。n個命題變元P，P2，…，P2n個小項。為了表示的更直觀，我們1 n以字母m加上由編碼構(gòu)成的下標來表示每個小項，其中下標是一個n位的二進制數(shù)。在任一個小項中，若出現(xiàn)的是命題變元Pi，則對應該小項編碼的第i位為1，若出現(xiàn)的是命題變元ii（PQR1011。n位二進制對應的十進制數(shù)i來表示小項的編碼，如

m011也可表示為

m3。設P、Q、R為三個命題變元，真值T和F分別用“1”和“0”來表示，含三個2.12.1PQRPQRm000/m0PQRm001/m1PQRm010/m2PQRm011/m300010000010100010001001100011000000101000011000001110000PQRPQRm100/m4PQRm101/m5PQRm110/m6PQRm111/m7000000000100000100000011000010010001010100110001011100012.1每個小項具有一個相應編碼，且只在一種情況下真值為T，即按照其編碼值進行指派時，其真值為T,其他情況下，真值都為F。故每個小項有一個成真賦值，有2n1種成假賦值。每個小項的成真賦值均不相同。例如，小項（PQRm101P真值為T，Q真值為F，R真值為T時，小項（PQR）的真值為T2n1種指派情況，該小項真值都F。任意兩個不同小項的合取式為矛盾式。證明：每個小項均只有一個成真賦值，對任意兩個不同的小項mi和mj，它們的成真賦值是不同的。對任一種指派，不能使mi和mj同時為T，則mimj為F。根據(jù)零律，所有小項的合取式為矛盾式。證畢例如，m001m100(PQR)(PQR)PPQRRF全體小項的析取式為重言式。2n1i01...2n1Ti0一種指派1n1碼1n1kk為kk的真值為T為重言式。證畢定義2.5n個命題變元的簡單析取式，稱作布爾析取或極大項，簡稱為大項，其中每式，或以變元的否定形式。與小項情況類似，對每個大項也可以進行編碼。以字母M加上由編碼構(gòu)成的下標來表示每個大項，其中下標是一個n位的二進制數(shù)。在任一個大項中，若出現(xiàn)的是命題變元Pi，則對應該大項編碼的第i位為0，若出現(xiàn)的是命題變元Pi的否定，則對應的第i位為1。例如，由兩個命題變元P和Q構(gòu)成的大項共有4個，分別是：PQ、PQ、PQ和PQM00M01M10M11Mi（i0,1,2,3。三個命題變元P、Q、R構(gòu)成的大項共有8個，分別是：PQR、PQR、PQRPQR、PQR、PQR、PQR和PQR，對應的編碼依次是：M000、M001、M010、M011、M100、M101、M110和M111，或記為Mi（i0,1,2,3,4,5,6,7。各大項的成假賦值及對應的編碼如表2.2所示。2.2大項成假賦值編碼PQR000M0PQR001M1PQR010M2PQR011M3PQR100M4PQR101M5PQR110M6PQR111M7與小項的性質(zhì)類似，大項有如下性質(zhì)：每個大項具有一個相應編碼，且只在一種情況下真值為F，即按照其編碼值進行指派時，其真值為F，其他情況下，真值都為T。故每個大項有一個成假賦值，有2n1種成真賦值。每個大項的成假賦值均不相同。例如，大項（PQR）M010PFQ真值為TR真值F時，大項（PQR）F2n1種指派情況，該大項真值都為T。任意兩個不同大項的析取式為重言式。這個性質(zhì)的證明類似于小項性質(zhì)（2）的證明。證明略。M001M100(PQRPQR)PPQRRT全體大項的合取式為矛盾式。2n1MiM0M1...M2n1Fi0這個性質(zhì)的證明類似于小項性質(zhì)（3）的證明。證明略。n個命題變元P1P2PnmiMi，根據(jù)小miMiMimi。例如，m001PQRM001PQRm001M001，M001m001。主范式包括主析取范式和主合取范式。主析取范式定義2.6對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等價式稱為原式的主析取范式。定理2.2在公式的真值表中，所有真值為T的指派所對應的小項的析取，即構(gòu)成該公式的主析取范式。證明：設給定公式為A，其真值為Tmi1mi2mik，這些小項的析取式記為BBmi1mi2mikFmj1，mj2mjtt2nk。首先對使A為T的某一指派，必存在某個小項的真值為T，而該小項必定含在B中，miu(1ukmiu在此指派下真值為TB的真值為T。其次，對使A為F的某一指派，其對應的小項必定不包含在Bmi1，mi2mikFBmi1mi2mikF。A與B在相應指派下具有相同的真值，綜上，AB。求任一合式公式的主析取范式有多種方法，定理2.2是其中的一種方法。對于所給的任一合式公式，先求出其真值表，然后列出所有真值為T的小項，并求它們的析取，即得該合式公式的主析取范式。定理2.3任何命題公式都存在與之等值的主析取范式，并且是唯一的。證明：存在性可由定理2.2保證。下面采用反證法來證明唯一性。n個命題變元的可滿足命題公式A，若A有兩個不同的主析取范式A1和A2，因主析取范式是與原式等價的合式公式，則必有A1A2。由于A1和A2是兩個不同的主析取范式，它們所含的小項不完全相同，必存在某個小項只存在于A1和A2兩者之一中，不失一mi只在A1中，但不在A2中。設mi在A1SS指派下，主析取范式A1為真。由于A2不包含mimi為T的指派均是其他小項的成假指派，故該指派下A2F。這與A1A2除了采用真值表法可求合式公式的主析取范式外，還可采用等值演算方法求解。步驟如下。①采用2.1取式。②若某簡單合取式中沒有包含所有的變元，則需要根據(jù)排中律PiPiT、同一律ATAAi中缺少變元Pi可使簡單合取式AiPi或Pi。③去掉重復出現(xiàn)的小項。例2.2A：(PQ)QR的主析取范式。A2.32.3APQRPQ(PQ)QR(PQ)QR0001011000110100010100100111000010001111101011001101001011110000從表2.3可知，真值為1的小項只有m100，即(PQR。故A的主析取范式為(PQR,可以表示為(4)。除了使用真值表法求合式公式的主析取范式外，也可以用等值演算法求主析取范式。方法二(PQ)QR(PQ)QR(PQ)QRPQR主合取范式定義2.7對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則該等價式稱為原式的主合取范式。2.22.3,我們有以下定理。定理2.4在公式的真值表中，所有真值為F的指派所對應的大項的合取，即為此公式的主合取范式。2.2定理2.5任意含有n個命題變元的公式A，都存在與之等值的主合取范式，并且是唯一的。2.3求命題公式A的主合取范式與求主析取范式的步驟非常相似，仍然可以用兩種方法。方法一是采用真值表法，求出所有真值為F的大項，并求它們的合取即可。方法二是采用等值演算方法。利用蘊涵等值式與等價等值式去掉公式中出現(xiàn)的聯(lián)結(jié)詞和，并且保證公式中不出現(xiàn)A、AB)、AB)等形式的子公式，即采用雙重否定律和德摩根律，將A變換為A，將AB)變換為AB，將AB)變換為AB等。另外，如果出現(xiàn)A(BC))的形式，則利用分配律進行變換。此時會得到簡單析取式的合重復出現(xiàn)的大項。從A的主析取范式求其主合取范式步驟為：①求出A的主析取范式中未包含小項的下標；②把①中求出的“下標”寫成對應大項；③將②中得到的大項進行合取，即為A的主合取范式。例2.5求公式A(PQR))(PQR)的主合取范式。解：公式A的主析取范式為(0,1,2,7)，所以A(3,4,5,6)。對于含n個命題變元的公式A，根據(jù)主范式（主析取范式、主合取范式）的定義和定理，有以下結(jié)論：若A可化為與其等價的含2n個小項的主析取范式，則A為重言式。若A可化為與其等價的含2n個大項的主合取范式，則A為矛盾式。若A的主析取范式中至少含有一個小項，或A的主合取范式中最多含有2n－1A邏輯思維的特征是推理和演繹，推理是數(shù)理邏輯中主要的研究內(nèi)容之一。所謂推理是示這個過程。這里，前提被表示成命題，推理所遵從的規(guī)則表示為命題等值公式。如何表示推理是正確的呢？我們給出下列定義。定義2.8設H1，H2，…，Hn和C都是命題公式，若對于H1，H2Hn和C中出現(xiàn)的命題變元的任意一組賦值，或者H1H2Hn

H1H2Hn為真時C也為真，則稱由前提H1,H2,...,Hn推出結(jié)論C的推理是有C簡單地說，從前提出發(fā)，根據(jù)推理規(guī)則得出的結(jié)論就是有效的結(jié)論，而這個結(jié)論是否是真實的并不在我們討論的范圍之內(nèi)。也就是說，我們只關心這個結(jié)論是否是從前提推導出來的，推導的過程是否遵從推理規(guī)則，而不關心得到的結(jié)論的含義是什么。下面給出這個定義的符號化表示。定義2.9H1H2Hn，CH1H2HnC，稱C是一組前提H1H2Hn的有效結(jié)論，記為H1H2HnC。由交換律可知，對H1,H2,...,Hn的任一種排列次序Hi1，Hi2，...，Hin，存在以下的H1H2HnHi1Hi2Hin，這表明，前提的排列次序?qū)ν评磉^程沒有影響。由蘊涵定義可知，PQ的充分必要條件是PQ是一個重言式，而對于條件聯(lián)結(jié)詞4P為T而Q為F時，PQ為F，即不是重言式。其他3種情況下PQ的值均為T，即為重言式。所以，只要推導中不出現(xiàn)H1H2Hn為T且C為F時，推理就是有效的。由此我們得到定理2.6。定理2.6推理

H1H2...Hn

├C是有效推理的充分必要條件是H1H2HnC為重言式。證明：必要性設H1H2Hn推出C的推理正確，即H1H2HnC為有效推理，則對于H1H2,...,Hn和C中所含命題變元的任何一組賦值，不會出現(xiàn)H1H2Hn真而C為假的情況，即在任何賦值下，H1H2HnC均為真，H1H2HnC是重言式。充分性若H1H2HnC為重言式，表明對任何的賦值，該式均為真，這表明或者H1H2Hn為真且C亦為真，或者H1H2Hn為假。故可由H1H2Hn推出CH1H2HnC是有效推理。證畢判別有效結(jié)論的過程就是論證過程，可采用真值表法、主范式方法和推理法。2.8。2.7等值公式表E1AAE2ABBAE3ABBAE4(AB)CA(BC)E5(AB)CA(BC)E6A(BC)(AB)(AC)E7A(BC)(AB)(AC)E8(AB)ABE9(AB)ABE10AAAE11AAAE12A(BB)AE13A(BB)AE14A(BB)TE15A(BB)FPAGEPAGE32E16ABABE17(AB)ABE18ABBAE19A(BC)(AB)CE20AB(AB)(BA)E21AB(AB)(AB)E22(AB)AB2.8推理定律表I1ABAI2ABBI3AABI4BABI5AABI6BABI7(AB)AI8(AB)BI9A,BABI10A,ABBI11A,ABBI12B,ABAI13AB,BCACI14AB,AC,BCCI15AB(AC)(BC)I16AB(AC)(BC)在推理過程中，如果命題變元較多，用真值表法、等值演算法及主范式法等進行推理證明都不很方便，因而現(xiàn)在引入構(gòu)造論證的方法。首先假定已知的前提為真，然后使用推理公式可得到一系列的命題公式，這些命題公式或者是已知的前提，或者是由某些前提應用推理規(guī)則得到的結(jié)論。當?shù)玫揭笞C的結(jié)論時，推理過程結(jié)束。如果得到與待求證的結(jié)論相反的結(jié)果，則說明原推理是無效的。常用的推理規(guī)則有：前提引入規(guī)則：在證明的任何步驟上，都可以引入前提，簡稱P規(guī)則。結(jié)論引入規(guī)則：在證明的任何步驟上，所證明的結(jié)論都可作為后續(xù)證明的前提，稱為T規(guī)則。轉(zhuǎn)換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以用與之等PAGEPAGE33值的命題公式置換，如用PQ置換PQ，為此表2.7及表2.8的等值及推理公式都可應用。它亦記為T規(guī)則。例2.9(PQQRRP）QRQRRQ（5）(PQ)PQP

P規(guī)則P規(guī)則T(2)(3)I12P規(guī)則T(5)E8T(4)(6)I10證畢推導過程中，每一步都標注出了使用的規(guī)則，規(guī)則的含義舉例如下。T（1）E16：在得到的（1）步基礎上引用T規(guī)則應用E16公式。②T（）I12（3步基礎上引用TI12公式。③P規(guī)則：引入前提。定理2.7若H1H2HnC為矛盾式，則H1H2HnC成立。SH1H2HnSC為矛盾式，SC為矛盾式(SCFSC為TSC為TSC即SC成立。定理2.7的含義是，結(jié)論的否定可以作為附加前提在推理的過程中被引用。如果能推導出F，則表明原來的結(jié)論為有效結(jié)論。這種將結(jié)論的否定式作為附加前提引入并推出矛盾式的證進而說明對結(jié)論的否定是不正確的，即結(jié)論成立。2.10前pq)rrss，p結(jié)q明）q P則否）rssr（5）(pq)r（6）(pq)（7）pq

P規(guī)則P規(guī)則T(2)(3)I10P規(guī)則T(4)(5)I12T(6)E8p P規(guī)則qqq

T(7)(8)I10T(1)(9)I9F由此得到pq)rrsspqF，所以推理正確。證畢如果結(jié)論是一個條件式，則可采用下列定理確定的規(guī)則進行證明。定理2.8若H1H2HnRCH1H2HnRC。證明略。定理2.8H1，H2，...，Hn，RCH1，H2，...，HnRC。本規(guī)則也稱為CP規(guī)則。例2.11用CP規(guī)則證明下面有效推理。pqrspqsr明）s P則附前）spp

P規(guī)則T(1)(2)I10q P規(guī)則pq（6）(pq)r（7）r

T(3)(4)I9P規(guī)則T(5)(6)I11由此得到推理是正確的。 證畢練習題命題公式PQR的主析取范式中含極小項的個數(shù)是（）A8B3C5D0命題公式PQ的主析取范式是（）PQPQCPQDPQ命題公式PQ的主合取范式是（）答案1.C。2.B。3.B。3分析句子“x大于3一是句子的主語x，這是一個變暈，稱為個體詞；二是謂語部分“大于3”，它表示主語的某一個性質(zhì)，稱為謂詞?？梢杂肞(x)來表xPx字母a，b，c，…等來表示；當它表示抽象或泛指的個體時稱為個體變項，也稱個體變元或個體變量，多用小寫的英文字母x，y，z，…等來表示。個體變項的取值范圍為個體域，例如謂詞A表示“是大學生”，w表示“王強”，則“王強是大學生”可表示為A(w。再比如，設Bxc,y表示“c位于x和y之間”，jn，bj和sh分別表示“濟南”、“北京”和“上海”，則S(bj，jn，Sh)表示語句“濟南位于北京和上海之間”。謂詞用來指明個體的性質(zhì)或個體之間的關系等，常用大寫的英文字母P，Q，R，…來表示。表示具體性質(zhì)或關系的謂詞稱為謂詞常項，表示抽象的或泛指的性質(zhì)或關系的謂詞稱為謂詞變項。例如A(w)和B(bj，jn，sh)等都是謂詞常項，因為它們表示的都是具體的事情。定義3.1由一個謂詞、一些個體變量組成的表達式稱為謂詞變項或命題函數(shù)。例如對于命題函數(shù)P(x)，當x的值不確定時，P(x)的值也不能確定，所以它不是命題，而僅僅是命題函數(shù)。當變量x的值確定下來后，P(x)的真假也能確定下來。例如，P(2)為假，而P(20)為真?？梢詫(x)理解成謂詞P在x的值。單獨的個體詞和謂詞不能構(gòu)成命題，將個體詞和謂詞分開不是命題。謂詞中的個體變元個數(shù)可多可少，例如A(x)表示“xx是論域中的Lx,yxyx和y元的數(shù)目稱為謂詞變項的元數(shù)。如A(x)為一元謂詞，Lx,y為二元謂詞。一般地，P1,x2,...,xn1為nn1a，此時P(a,x1,x2,...,xn1)為n1元謂詞。通常把不帶個體變項的謂詞稱為0元謂詞，例如F(aP（a，b，...，d0在命題函數(shù)中，當其中出現(xiàn)的所有變量均被賦值后，得到的命題的真值也確定下來。有些命題函數(shù)中，使得命題為真或為假的變量值并不是唯一的，即變量取不同的值時，得到的命題真值是相同的。個體常項與變項之間的數(shù)量關系，即對命題函數(shù)進行量化。量詞分為兩種，一是全稱量詞，二是存在量詞。域即是論域，這樣的語句用全稱量詞表示。定義3.2P(x)P(x)對xxP(x)表P(x的全稱量化，其中稱為全稱量詞。xP(x也可表示為“對所有x，P(x)”或是“對每個x，P(x)”。日常語言中的“一切”、“任意的”、“所有”及“凡是”等詞，都可對應全稱量詞。與之相對的，有時需要表示某一性質(zhì)對變量在論域內(nèi)的若干值為真，對其他的值為假，這樣的語句用存在量詞表示。定義3.3P(x的存在量化是命題“論域中存在一個元素x使P(x為真”。符號xP(x)表示P(x的存在量化，其中稱為存在量詞。P(x)個x使得P(x)一個x使得P(x)語言中的“存在著”、“有一個”、“至少有一個”等詞，都可對應存在量詞。假定在變量x的論域中有n個對象，要確定xP(x)是否為真，可以對x的n個值依次查看P(x)是否總是真。如果遇到論域中的某一個值使P(x)為假，則xP(x)為假，否則xP(x為真。要確定xP(x)是否為真，則要依次查看x的n個值，查找使P(x為真的x的值。若找到一個，則xP(x)為真，若總也找不到這樣的x，則如xP(x)為假。P(x)為真時，xP(x)P(x)為真時，xP(x)即為真。反過來，有一個值使得P(x)xP(x)即為假；而所有的值P(x為假，則xP(x為假。在全稱量詞中，特性謂詞是條件式的前件，在存在量詞中特性謂詞后跟一個合取項。一般約定：如果事先沒有明確提出個體域，則認為個體域是全總個體域。例3.4使用自然語言描述命題：xyz((Fx,yF(x,z)(yz))F(y,z))，F(xiàn)aba和b是朋友”，論域是本校所有學生組成的集合。解：本命題表示：有一名學生x對本校所有學生y和z，若y和z都是x的朋友，且y和z不是同一個人，則y和z就不是朋友。換句話說，有一名學生，他的朋友之間都不是朋友。本例中，論域是本校所有學生，所以可以免去特性謂詞。3.52解：用Ex表示“xGx表示“x2x(ExGx。量詞出現(xiàn)的次序不同，得到的謂詞公式的邏輯含義也可能是不同的。合謂詞公式。定義3.4由一個或幾個原子謂詞公式以及邏輯聯(lián)結(jié)詞組合而成的表達式稱為復合謂詞公式。復合謂詞公式中使用的邏輯聯(lián)結(jié)詞包括：、、、和，這5個聯(lián)結(jié)詞的意義與命題演算中的解釋相似。3.5原子謂詞公式是合式公式。若A是合式公式，則A也是合式公式。若AB都是合式公式，則（AB（AB)和AB也是合式公式。若A是合式公式，x是A中出現(xiàn)的任何個體變元，則(xA和(xA也是合式公式。只有經(jīng)過有限次應用規(guī)則（1）~（4）所得到的符號串才是合式公式。（A)可以寫成A，(AB)可以寫成AB等。但需注意，量詞后面若有括號則這個括號不能省略。例如，xA(x)B(x))不能寫成xA(x)B(x)。合式公式A記為WffA，合式公式簡稱為公式。定義3.6給定謂詞合式公式AxB(x)或xB(x)、后面的x為指導變元，也稱為作用變元。稱B(x)為相應量詞的轄域（或作用域。在轄域中，x的一切出現(xiàn)稱為約束出現(xiàn)。在B(x)中除去約束出現(xiàn)的其他變元的出現(xiàn)稱為自由出現(xiàn)。在某個轄域內(nèi)，某個變量的出現(xiàn)或是約束出現(xiàn)，或是自由出現(xiàn)。但在整個公式中，一個變量可能會表現(xiàn)為既是約束出現(xiàn)也是自由出現(xiàn)的情況。在謂詞合式公式中，一個個體變元既可以是約束出現(xiàn)，又可以是自由出現(xiàn)，這很容易引起混淆。為了避免這些不必要的混淆，采用下面兩個規(guī)則改變命題公式的寫法：約束變元改名規(guī)則：將量詞轄域中，量詞的指導變元及其轄域中該變元的所有約束出現(xiàn)均改為本轄域中未曾出現(xiàn)過的個體變元，其余不變。自由變元代入規(guī)則：把公式中的某一自由變元，用該公式中沒有出現(xiàn)的個體變元符號替代，且要替換該自由變元在公式中的所有出現(xiàn)處。這兩個規(guī)則的使用目的，是為了保證個體變元在合式公式中或以約束形式出現(xiàn)，或以自由形式出現(xiàn)，不再有混合出現(xiàn)的情況，從而避免了混淆。有些命題可以有不同的符號化表示，甚至可以使用不同的量詞形式。比如，用Ax表“xBxx（1）x(A(x)B(x))（2）x(A(x)B(x))xP(x)與xP(x)都是一個特定的命題，例如論域是a,bc，則xS(x)即是S(a)S(b)S(c)xS(x)即S(aS(bS(ca1a2an，則下列關系式成立。xA(x)A(a1)A(a2)...A(an)xA(x)A(a1)A(a2)...A(an)在謂詞公式中常包含命題變元和個體變元，當個體變元用確定的個體取代，命題變元用確定的命題所取代時，就稱作對謂詞公式賦值（或解釋。定義3.7給定任何兩個謂詞公式WffA和WffB，設它們有共同的論域E，若對A和B的任一組個體變元進行賦值，所得命題的真值相同，則稱謂詞公式A和B在