Chapter-1-命題邏輯初步

2024/5/141邏輯與代數

Logic&Algebra靳(jìn)勇飛

904693585discretemathe@163/IfIdoIcan@20132013.3本課程的主要內容命題邏輯初步謂詞邏輯初步集合與關系代數系統(tǒng)根底知識2024/5/14102關于數學--我的數學觀人們在認識世界的過程中，對世界(包括物質世界和認識物質世界產生的精神世界)的理解形成了一種共同的抽象，抽象到一定程度,這些抽象的字面含義不再與要認識的世界有直接的關系，這就形成了數學。認識數學要注意的的幾個特征由于是抽象，可以適用于多種場合由于是抽象，其必然受限于如何抽象，具體表現為不同時期的認識不同它是一種共同的抽象，因此具有再現性抽象至不再具有字面的意思，區(qū)別于其他科學抽象的結果作為一種精神存在，也可以作為進一步的認識對象數學的開展既有應用的推動，又有自身開展的需要邏輯的目的邏輯的目的不是告訴你什么是對的，而是告訴你怎么做可以在前提正確的情況下保證你的結論是對的2024/5/14106數理邏輯根底數理邏輯是用數學方法研究關于推理、證明等問題的一門學科。為之做出奠基性工作的有:

萊布尼茲(Leibniz,德國,1646-1716)

布爾(Boole,英國,1815-1864)

弗雷格(Frege,法國,1848-1925)

皮亞諾(Peano,意大利,1858-1932)

希爾伯特(Hilbert,德國,1862-1943)

羅素(Russel,英國,1872-1970)

哥德爾(G?del,德國,1906-1978)

圖靈(Turing,英國,1912-1954)等所有的數學內容都源自于一種對世界的夢想，你的夢想是什么？2024/5/141072000多年前：蘇格拉底、柏拉圖、亞里士多德新的知識是如何獲得的？歸納三段論所有的人都是要死的,蘇格拉底是人,所以蘇格拉底是要死的沒有一條魚是有理性的，所有的鯊魚都是魚，所以沒有一條鯊魚是有理性的人都是有理性的，有些動物是人，所以有些動物是有理性的沒有一個希臘人是黑色的，有些人是希臘人，所以有些人不是黑色的2024/5/14108大約350年前：萊布尼茲萊布尼茲的夢想我們需要一種普遍的文字，一個包含了人類全部思想領域的符號系統(tǒng)，有了這樣一個符號系統(tǒng)，我們就可以確定用這種語言寫成的哪些句子為真，以及他們之間存在著什么樣的邏輯關系萊布尼茲設計、制造了能做加、減、乘、除以及開方運

算的計算機,提出了“使所有推理過程實現機械

化”2024/5/14109萊布尼茲的邏輯演算〔草稿〕定義3A在L之內或者L包含A,等價于L可以與以A為其中一項的許多項相一致。BN=L表示B在L之內，B與N共同組成了L.更多的數目的項的情形也是一樣。公理1BN=NB公理2AA=A命題5如果A在L之內且A=B,那么B在L之內命題6如果A在B之內且B=C,那么A在C之內命題7A在A之內…命題20如果A在M之內，B在N之內，那么AB在MN之內2024/5/141010Leibniz的主要奉獻：

(1)創(chuàng)造微積分;創(chuàng)造了一套微積分的符號系統(tǒng).

(2)設計、制造了能做加、減、乘、除以及開方運

算的計算機,提出了“使所有推理過程實現機械

化”這一宏偉方案.

(3)創(chuàng)造了二進制系統(tǒng),并用它對中國古老的八卦方

圓圖給出了合理的解釋(將中國古老的易圖解釋

成0~64的二進制數表).

(4)提出了數理邏輯的根本思想和理論根底(手稿).2024/5/141011大約150年前：布爾…假設一個形容詞，比方說“好的”，被用作一個描述詞，那么讓我們用一個字母，比方說y來表示可以用“好的”來描述的所有事物，即“所有好的事物”或“好的事物”的類。再另xy這一組合表示同時適用于x和y所代表的名稱或描述詞的所有事物的類。于是，如果x表示“白的東西”，y表示“綿羊”，那么xy表示“白的綿羊”；類似的，如果z表示“有角的東西”…那么zxy表示“有腳的白綿羊”…2024/5/141012布爾的邏輯代數xx=x總是為真的，既是綿羊又是綿羊的東西是綿羊這個方程只有在0、1時才成立，如果只限于0和1兩個值，邏輯代數就是普通代數了！0可解釋成沒有任何東西屬于它的類，1可解釋成包含所有考慮對象的類x+y表示或者在x中或者在y中的所有事物的類，x-y表示在x中但不在y中的事物的類x+(1-x)=1表示在x中的事物或者不在x中的事物就是所有的事物

x(1-x)=0表示即在x中有不在x中的事物不存在：亞里士多德的排中律2024/5/141013用布爾代數進行三段論的推導所有的x都是y,所有的y都是z,所以所有的x都是z所有的x都是y，即沒有東西在x中但不在y中，x(1-y)=0,x=xy所有的y都是z，即沒有東西在y中但不在z中，y(1-z)=0,y=yzx=xy=x(yz)=(xy)z=xz,x(1-z)=0,沒有東西在x中但不在z中，所有的x都是z布爾的工作把邏輯演繹變成了一個數學分支2024/5/141014Boole的主要奉獻:(1)實現了邏輯的數學化(用符號進行邏輯演算),創(chuàng)造了邏輯的代數系統(tǒng).(2)出版了兩部重要的數理邏輯奠基性的著作:《邏輯的數學分析》(1847)《思維規(guī)律的研究作為邏輯與概率的數學理論的根底》(1854)在這兩部著作中,他給出了現今稱為“Boole代數”的理論的雛形.2024/5/141015.

的主要奉獻131年前：弗雷格1879年費雷格出版了一本不到100頁的小冊子《概念語言》，副標題是“一種模仿算術語言構造的純思維的形式語言”，被譽為“也許是自古以來最重要的一部邏輯學著作”。試圖找到一個能夠包含數學實踐中的全部演繹推理的邏輯系統(tǒng)。2024/5/141016弗雷格的形式語法弗雷格把連接命題的關系用于分析命題的結構他考慮了“如果…那么…”、“…且…”、“…或…”、“任何…”、“某個…”、“非…”等，并給出了相應的符號∧∨弗雷格的體系原那么上包括了通常使用的全部推理2024/5/141017弗雷格的形式語法的例子所有的馬都是哺乳動物。(

x)(x是一匹馬x是哺乳動物)有些馬是純種的。(

x)(x是一匹馬∧x是純種的)所有不及格的學生或者是糊涂的或者是懶惰的F(x)表示x是個不及格的學生，S(x)表示x是糊涂的，L(x)表示x是懶惰的，(

x)(F(x)

S(x)∨L(x))2024/5/141018Frege的主要奉獻:(1)總結性著作為《概念語言》一書(1879年出版).在其中創(chuàng)造了一種所謂的“純粹思想的語言”,即表意的語言,使我們可以完全精確地表達判斷的概念內涵.例如:他嚴格區(qū)別了命題的表達和判斷;明確提出了真值蘊含的思想,并指出了它與日常語言的區(qū)別;他還引進了內容同一的符號;引入了量詞的理論等等.(2)給出了歷史上第一個嚴格的現代邏輯系統(tǒng).這個系統(tǒng)實際上包含了作為現代數理邏輯根底的兩個演算系統(tǒng)------命題演算系統(tǒng)和一階謂詞演算系統(tǒng).2024/5/141019108年前：羅素康托爾對無窮集的研究：集合的基數，對角線方法羅素悖論：令A表示所有不包含自身的集合組成的集合，即A={B|BB}.現在的問題是AA是否成立？羅素悖論意味著集合這個概念有問題，而集合是所有數學，當然也包括弗雷格的邏輯，的根底2024/5/141020Russel的主要奉獻:(1)給出著名的Russel悖論,并提出了類型論以消除悖論.對數學根底產生了重大影響,并對數學根底的研究進一步做出了奉獻.(2)與合著《數學原理》一書(共三卷,1910~1913年間出版).從較簡單的邏輯系統(tǒng)出發(fā),再加上少量的非邏輯公理,推導出了很大一局部經典數學.

2024/5/141021Peano的主要奉獻:(1)是符號邏輯的先驅和公理化方法的身體力行的推行人.(2)對整數作了公理化處理,給出了著名的自然數公理.見他的名著《算術原理新方法》一書(1889年出版).(3)用公理化方法研究數學,寫出了5卷本巨著《數學公式匯編》(1895~1908年間出版)(4)為他的《數學公式》方案花了26年的時間進行研究,試圖從他的邏輯記號的假設干根本公理出發(fā)來建立整個的數學體系.對當代數學家以及后來著名的Bourbaki學派產生了很大的影響.2024/5/1410221900年：Hilbert的綱領皮亞諾的自然數公理，PA系統(tǒng)希爾伯特的《幾何根底》〔1899〕是公理化思想的代表作，書中把歐幾里得幾何學加以整理，成為建立在一組簡單公理根底上的純粹演繹系統(tǒng)，并開始探討公理之間的相互關系與研究整個演繹系統(tǒng)的邏輯結構建議從假設干形式公理出發(fā)將數學形式化為符號語言系統(tǒng)，并從不假定實無窮的有窮觀點出發(fā)，建立相應的邏輯系統(tǒng)。然后再研究這個形式語言系統(tǒng)的邏輯性質，從而創(chuàng)立了元數學和證明論。希爾伯特的目的是試圖對某一形式語言系統(tǒng)的無矛盾性給出絕對的證明，以便克服悖論所引起的危機，一勞永逸地消除對數學根底以及數學推理方法可靠性的疑心。2024/5/141023Hilbert的主要奉獻:(1)創(chuàng)立了現代公理方法.明確提出了公理系統(tǒng)的三大基本要求,即相容性、獨立性和完備性.(2)提出了著名的形式化方法.其方法的要點在對于整個數學的邏輯系統(tǒng)的相容性的研究，這就是著名的證明論或者“元數學”的研究,希望一勞永逸地解決數學根底中的問題。(3)數學形式主義綱領的代表著作(與W.Ackermann以及P.Bernays合作):《數理邏輯根底》(1928年出版)《數學根底》(1934年出版)2024/5/1410241930年：哥德爾1930年柯尼斯堡，PA系統(tǒng)是不完備的1931年，PM(懷特海和羅素的形式邏輯系統(tǒng))是不完備的PM不完備性:即使把初等數論形式化之后，在這個形式的演繹系統(tǒng)中也總可以找出一個合理的命題來，在該系統(tǒng)中既無法證明它為真，也無法證明它為假。(在系統(tǒng)外部是可以證明這個結論是真的。)2024/5/141025G?del的主要奉獻:(1)Hilbert的形式公理系統(tǒng)的邏輯根底是謂詞演算,當時已證明了謂詞演算的可靠性(即一致性),是G?del于1929年證明了謂詞演算也有完全性,這是對Hilbert的形式化方案的一個有力支持.(2)1934年他證明了形式算術系統(tǒng)的不完全性這一著名的定理,從而否認了Hilbert的形式化數學方案.2024/5/1410261935年左右：圖靈1930年，哥德爾證明了弗雷格的規(guī)那么是完備的希爾伯特判定問題：是否存在一個計算程序，只用所謂的一階邏輯的符號系統(tǒng)寫出的某些前提和結論，通過這個程序總是可以判定？圖靈對計算過程進行了分析，得出結論：判定問題的算法不存在。副產品：發(fā)現了通用計算器的數學模型！2024/5/141027Turing的主要奉獻:(1)對計算和算法給出了完全確定的定義,第一次把計算和自動機(現稱Turing機)聯系了起來.(2)解決了著名的Hilbert的判定問題以及半群的字的問題等數學難題.(3)于1945年最先提出了存貯程序控制計算機的設計;他還是人工智能的先驅,并參與了現代計算機的設計工作.2024/5/141028終于有了現代的計算機！2024/5/141029集合(set)

集合的根本概念一般把假設干東西(元素)放在一起就構成一個集合.假設元素a屬于集合A,記作aA,假設元素a不屬于集合A,記作aA.集合中的元素不必是具體的事物,也可以是抽象的對象,甚至集合也可以作為集合的元素.例下面是集合的幾個例子:(1)S={1,2,3,4};(2)Z=所有整數(integer)組成的集合N=自然數集合={1,2,3,4,...}Q=所有有理數(rationalnumber)組成的集合R=所有實數(realnumber)組成的集合(3)T={x:x

R且x4-10x3+35x2-50x+24=0}(4)W={z|z

Z且存在x,y,u,v

Z使得x2+y2+u2+v2=z}集合的性質(i)集合元素確實定性:即對具體一個集合而言,一個元素或在此集合中,或不在此集合中,二者必居其一;(ii)集合元素的無重復性:即集合的元素彼此不同,沒有重復的元素在同一個集合中重復出現;{1,3,2}和{1,3,3,2}是同一個集合(iii)集合元素的無序性:例如我們認為{1,2}和{2,1}是同一個集合;定義沒有任何元素的集合稱為空集〔emptyset,nullset,orvoidset〕，用表示定義兩個集合A和B是相等(equal)的,當且僅當A和B有相同的元素,記作A=B;集合A與集合B不相等,記作AB;A=B表示：如果xA，那么必有xB,并且如果xB，那么必有xA.集合元素的個數(cardinalityofset)集合A中元素的個數，用|A|表示。定義如果一個集合中只有限多(自然數或〇)個元素,那么稱之為一個有限集(finiteset);如果有無窮多個元素那么稱之為一個無限集〔或無窮集,infiniteset〕.子集(subset)定義.設A、B是任意兩個集合,如果任取xA,都有xB,那么稱A是B的子集(subset),或A包含在B內,記作AB(或BA).如果有AB,但AB,也就是說,至少存在一個元素bB,使得bA,那么稱A是B的一個真子集(propersubset),記為AB(或BA).注意“”與“”的意義完全不同.空集是任何集合的子集；空集、集合A稱為集合A的平凡子集(trivalsubset)；集合A的其他的子集稱為A的非平凡子集。下面的圖表達了集合B與其子集合A之間的關系:

例如,A={1,2},B={1,2,3},

那么AB,且也有AB.ZQRAB“”的性質自反性AA;傳遞性AB且BC,那么AC;反對稱性如果AB且BA,那么A=B注：我們用了反自反性來定義兩個集合相等冪集(powerset)定義假設A是一個給定的集合,將集合A的每個子集看成一個元素,那么集合A的所有子集為元素所作成的新的集合稱為集合A的冪集,記為(A).

例求空集的冪集.解由于空集只有一個子集，也就是空集自己,從而它的冪集為

(

)={

}

.

(注)請注意將空集與{

}區(qū)別開來:中沒有任何元素,而{

}中恰好有一個元素.例

設A={1,2,3},試求它的冪集

(A).

解:集合A有8個子集,

它的冪集為

(A).

={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.定理如果A有n個元素,那么冪集(A)有2n個元素.

集合的運算集合的并unionAB={x|(xA)或(xB)}集合的交intersectionAB={x|(xA)且(xB)}.集合的差differenceAB={x|xA且xB}集合的補complementAC或者~A如果在考慮的問題中E表示全集(universalset)，那么AC=E－A差又稱為相對補(relativedifference)冪集的一些性質定理設A和B是兩個任意的集合,那么:(A)(B)的充要條件是AB.(A)=(B)的充要條件是A=B.(A)(B)(AB).(A-B)((A)-(B)){}.(A)(B)(AB).此外,(A)(B)=(AB)的充要條件是

AB或者BA.

多集合的并和交如果S表示一組集合

S={x|存在某個A

S使得x

A}

S={x|對所有的A

S都有x

A}.如果S={A1,A2,A3,...,An}如果S={A1,A2,A3,...}邏輯(logic)2024/5/141046命題(proposition)定義有確定的真(true)或者假(false)〔不是兩者皆有〕的陳述句稱為命題。真值：指命題的判斷結果,它不是“真”(T)就是“假”(F)一個句子是否為命題,先看它是否為陳述句,再看它的真值是否唯一.2024/5/141047例北京是中華人民共和國的首都。1+1=10.在太陽系以外的天體中是否存在與人類相似的有高度智慧的生物？請努力為實現你自己的人生理想而奮斗！在太陽系以外不存在像人類一樣的有高度智慧的生物.只要努力，任何人都有可能實現自己的人生理想。我正在說謊.2024/5/141048通常用大寫字母表示命題,稱為命題標識符.

例.A:2是素數

A表示命題“2是素數”。

例.P:1+1=3P表示命題“1+1=3”。2024/5/141049聯結詞(connective)2024/5/141050真值表(truthtable)設A是命題公式,對所有出現在A中的命題變元P1,P2,…,Pn指定一組真值,那么稱這組真值為A的一個解釋或真值指派,將公式A在其所有可能的解釋下所取真值匯列成表,稱為命題公式的真值表.2024/5/141051

否認〔negation)否認設P是一命題,P的否認是一個新的命題,記作P(非P).P的真值表(truthtable)如下所示：2024/5/141052PPTFFT例P:漢城和首爾是同一個城市;那么,P:漢城和首爾不是同一個城市.P:計算機根底是所有本科生的一門必修課;那么,P:計算機根底不是所有本科生的一門必修課.2024/5/141053合取(conjunction)設P和Q是命題，P和Q的合取是一個新命題，記作PQ,合取的定義為：當且僅當P和Q都為T時,P

Q為T.真值表如下：

2024/5/141054PQP

QTTTTFFFTFFFF例P:他在吃飯,Q:他在說話.

PQ:他在吃飯，且他在說話.P:我今天晚上去柏林看世界杯冠軍爭奪賽,Q:我家里有12把椅子。

PQ:我今天晚上去柏林看世界杯冠軍爭奪賽，并且我家里有12把椅子。

合取聯結詞是自然語言中的“并且”“不但…,而且…”等詞的邏輯抽象，但它的使用與自然語言中相應的用法并不完全一致：在自然語言中通常兩個命題之間有某種自然的聯系，而在數理邏輯中那么不然。

2024/5/141055析取(disjunction)設P和Q是命題，P和Q的析取是一個新命題，記作PQ。它的定義是：當且僅當P和Q都為F時,P

Q為F.

真值表如下：

2024/5/141056PQP

QTTTTFTFTTFFF例注：析取聯結詞與自然語言中的“或”的意義不完全相同,在漢語中的“或”有時表示“可兼取的或”,有時表示“不兼取的或”。而數理邏輯中的析取只能是“可兼或”。他今天晚上在家吃飯或在學校食堂吃飯.T27次從北京開往拉薩的列車是9：30或21：30開。他是奧運會100米冠軍或是奧運會200米冠軍.前兩例中的“或”是“不可兼或”，而最后一例中“或”是“可兼或”〕2024/5/141057例大局部程序設計語言中定義的and、or和not與我們前面定義的合取、析取和非完全一樣。例如在C語言中如果P:x<10Q:x<4那么PQ和在C語言中表示為(x<10)&&!(x>4)的式子表示一個意思Baidu搜索引擎中可用&、|和-分表表示、和2024/5/141058條件(單條件，也可稱為蘊含,condition)設P和Q是命題,條件命題(conditionalproposition)是一個復合命題,記作PQ,其定義為：當且僅當P的真值為T,Q的真值為F時,PQ的真值才為F.真值表如下：

2024/5/141059PQP

QTTTTFFFTTFFTP稱為前提(或假設,hypothesisorantecedent),Q稱為結論(或結果,conclusionorconsequent)“如果我被選為總統(tǒng),我會鏟除腐敗”。

P:我被選為總統(tǒng),Q:我會鏟除腐敗,那么命題為:PQ;“如果太陽從西邊出,我就投降”必為真命題;“如果1+2=3,那么2+2=6”在十進制下是假命題。函數F(x)可導的必要條件是F(x)是連續(xù)函數。P:函數F(x)可導,Q:F(x)是連續(xù)函數,那么命題為:PQ;函數F(x)可導的充分條件是F(x)是連續(xù)函數。P:函數F(x)是連續(xù)函數,Q:F(x)可導,那么命題為:PQ;2024/5/141060注當條件命題前件為“假”時,無論后件是“真”還是“假”,條件命題的真值都為“真”,稱為truebydefault或者vacuouslytrue.條件命題的真值為True，并不是說條件命題中的結論局部真值為True2024/5/141061例〔x是實數〕如果x>4，那么x+2>4.P:x>4Q:x+2>4PQ如果5>4，那么5+2>4.如果3>4，那么3+2>4.如果1>4，那么1+2>4.2024/5/141062逆換式、反換式、逆反式稱QP是PQ的逆換式(converse);稱PQ是PQ的反換式(contrary);稱QP是PQ的逆反式(contrapositive);2024/5/1463雙條件(bicondition)設P和Q是命題,雙條件命題(biconditionalpropostion)是一個復合命題,記PQ,或者P

Q其定義為：當且僅當P與Q的真值相同時,PQ的真值為T.真值表如下：

2024/5/141064PQP

QTTTTFFFTFFFT注：雙條件聯結詞

是自然語言中“當且僅當”,“相當于”,“…與…一樣”等詞匯的邏輯抽象。例“兩個三角形相似當且僅當它們的三個角對應相等”是一個真命題。

“a為偶數的充要條件是a的平方被4除余1”是一個假命題。

2024/5/141065聯結詞的運算優(yōu)先級五個聯結詞“”，“”，“”，“”，“”可理解為命題的五個根本的邏輯運算。運算優(yōu)先級為：有括號時，優(yōu)先計算括號內的運算；沒有括號時，按照從高到低優(yōu)先順序依次為：

，，，，同一聯接詞的運算，在沒有括號時，按照從左到右的順序計算2024/5/141066合式公式(Well-FormedFormula)與翻譯命題演算的合式公式:

(1)單個命題變元是一個合式公式;

(2)如果A和B是合式公式,那么

A,(A

B),(A

B),(A

B)和(A

B)以及對它們合法添加括號所得公式都是合式公式;

(3)有限次地應用(1)和(2)所得到的任何符號串是合式公式。換句話說，正確的使用運算符得到的公式稱為合式公式

例如,(P

Q),

(P

Q),(P(P

Q)),((P

Q)(Q

R)

(S

T)),都是合式公式.

而(P

Q)(Q),(P

Q,(P

Q)

Q)都不是合式公式.2024/5/141067

例符號化以下命題:(1)中國人既勤勞又勇敢;(2)不在改革中前進，就在落后中滅亡;(3)除非天下大雨,否那么我將外出散步.解:(1)設P:中國人勤勞,Q:中國人勇敢,那么命題可表為:PQ;(2)設P:在改革中前進,Q:在落后中滅亡,那么命題可表為:(PQ)(PQ);(3)原命題的意義為:如果天不下大雨,那么我將外出散步;

設P:天下大雨,Q:我將外出散步,那么命題可表為:PQ;

2024/5/141068如果你學習努力，你一定能通過離散數學考試；如果你迷戀網絡游戲，或者熱衷于看武俠小說，那么你就不會努力學習；你沒通過離散數學考試，你也沒有熱衷于看武俠小說；所以你一定迷戀網絡游戲！2024/5/141069A:你學習努力B:你通過離散數學考試C:你迷戀網絡游戲D:你熱衷于看武俠小說(A

B)

(C

D

A)

(

B

D)

C2024/5/141070例構造

P

Q和PQ的真值表;

解:2024/5/141071PQ

P

P

QPQTTFTTTFFFFFTTTTFFTTT例構造(P

Q)

P的真值表；

解:

2024/5/141072PQ

PP

Q(P

Q)

PTTFTFTFFFFFTTFFFFTFF注:象(P

Q)

P這樣恒取真值F的命題稱為永假式或矛盾式。

例構造(P

Q)(P

Q)和PQ的真值表；

解:

2024/5/141073PQ

P

QP

Q

P

Q(P

Q)(P

Q)PQTTFFTFTTTFFTFFFFFTTFFFFFFFTTFTTT注:象(P

Q)(P

Q)和PQ這樣有可能取到真值T且又不恒取真值T的命題稱為可滿足式。例給出

(P

Q)(P

Q)的真值表;

解:

2024/5/141074PQ

P

QP

Q

P

Q

(P

Q)

(P

Q)(P

Q)TTFFTFFTTFFTFTTTFTTFFTTTFFTTFTTT注:象

(P

Q)(P

Q)這樣恒取真值T的命題稱為永真式或重言式。如果一個命題公式A對于它所包含的命題變元的任意一組真值指派,其真值恒為真,那么稱公式A為永真式或重言式,記為T;如果對于它所包含的命題變元的任意一組真值指派,其真值恒為假,那么稱公式A為永假式或矛盾式,記為F;如果至少有一組真值指派使得公式A的真值為真,那么稱公式A為可滿足式。2024/5/141075例用數字0與1構造(PQ)(QS)的真值表;

解：

2024/5/141076PQSPQQS(PQ)(QS)111111110111101010100000011010010010001111000100等價(邏輯等價logicallyequivalent)設A和B是命題公式,P1,P2,…,Pn為A和B中的所有原子變元,如果對P1,P2,…,Pn任何一組真值指派,A和B的真值都相同,那么稱A和B是等價的或邏輯相等的,記作AB.兩個命題的等價性可用它們的真值表加以證明。由前例可知

P

Q和PQ是等價的,即(P

Q)

(PQ).(P

Q)(P

Q)和PQ是等價的,即(P

Q)(P

Q)

(PQ).

2024/5/141077命題公式之間的等價性具有如下重要性質:

(1)自反性:對任意的公式A,必有:AA;

(2)對稱性:對任意的公式A,B,假設有:AB,

那么必有:BA;

(3)傳遞性:對任意的公式A,B,C,假設有:AB,BC,那么必有:AC。

2024/5/141078例求證:PQ(PQ)(QP);

證明:列出真值表

可知(PQ)(QP)與PQ的真值表完全相同,故有

PQ(PQ)(QP)2024/5/141079PQPQQPPQ(PQ)(QP)TTTTTTTFFTFFFTTFFFFFTTTT例P與Q的不可兼或(PQ)(PQ)和(PQ)的真值表如下：

注：由此可見，P與Q的不可兼或也可以用(PQ)來表示。2024/5/141080PQPQ(PQ)(PQ)(PQ)TTTFFTFFTTFTFTTFFTFF常用的演算公式對合律(雙重否認律):PP；冪等律:PPP,PPP；結合律:(PQ)RP(QR)；

(PQ)RP(QR)；交換律:PQQP,PQqp；分配律:P(QR)(PQ)(PR)；

P(QR)(PQ)(PR)；

2024/5/141081吸收律:P(PQ)P,

P(PQ)P；De.Morgan律:(PQ)PQ,

(PQ)PQ；同一律:PFP,PTP；零律:PTT,PFF；否認律(補律):PPT,PPF；條件律:PQPQQP，

PQ(PQ)(QP)PQ；

2024/5/141082例驗證吸收律:P(PQ)P,P(PQ)P.解:由它們的真值表

立即可以看出這兩個等價性是成立的。2024/5/141083PQP

QP

QP(PQ)P(PQ)TTTTTTTFFTTTFTFTFFFFFFFF子公式和代換如果X是合式公式A的一局部,且X本身也是一個合式公式,那么稱X是公式A的子公式。

設A是命題公式,P1,P2,…Pn是其中的命題變元,假設用某些公式代換A中的某些命題變元，且假設用公式Qi代換Pi,那么必須用Qi代換A中的所有Pi,由此得到的新公式B稱為公式A的一個代換(置換).

2024/5/141084定理設X是公式A的子公式,XY,如果將A中的X用Y來置換得到公式B,那么公式B與公式A等價,即,AB。

2024/5/141085例求證:Q(P(PQ))QP;

證明:設公式A:QP,因為,P(PQ)P,(吸收律)

A中的P用P(PQ)置換得到

公式B:Q(P(PQ)),

所以:AB,

即,QPQ(P(PQ))#

當然Q(P(PQ))QP也可用真值表來驗證。

2024/5/141086例求證:(PQ)(PQ)P;

證明:(PQ)(PQ)P(QQ)PTP

分配律否認律零律

2024/5/141087例求證:P(QR)Q(PR)R(QP);

證明:P(QR)P(QR)(條件律)

Q(PR)(結合律,交換律)

Q(PR)(條件律)

又,P(QR)P(QR)

R(QP)R(QP)#2024/5/141088例求證:((PQ)(P(QR))(PQ)(PR)

T;證明:((PQ)(P(QR))(PQ)(PR)

((PQ)(P(QR))(PQ)(PR)(D.M)

((PQ)(P(QR))(PQ)(PR)(D.M)

((PQ)((PQ)(PR)))((PQ)(PR))(D.M,分配律)

((PQ)(PR))((PQ)(PR))(冪等)

T(否認)#2024/5/141089定理

任何兩個重言式的合取或析取,仍然是一個重言式.

2024/5/141090定理一個公式A是一個重言式,對其含的同一分量都用任何合式公式置換得到公式B,那么B仍是一個重言式.

例.求證((PS)R)((PS)R)為重言式.

證明:因為AAT,以((PS)R)代換A,即得,(PS)R)((PS)R)T#2024/5/141091

定理

設A和B是命題公式,A

B當且僅當A

B是一個重言式.

2024/5/141092例求證:(PQ)(PQ);

證明:在前例中已得:(PQ)(PQ)是重言式,所以:(PQ)(PQ)#求證：(PQ)(QP)問：PQ與QP是等價的嗎？

2024/5/141093邏輯蘊含當且僅當PQ是重言式時,稱“P邏輯蘊含Q”,記作:PQ;

請注意將“蘊含”與“邏輯蘊含”區(qū)別開來。2024/5/141094蘊含式公式公式名稱PQP化簡律simplificationPPQ增廣律additionP(PQ)Q析取三段論disjunctivesyllogismP(PQ)Q肯定前件假言推理modusponens

Q(PQ)P否定后件假言推理modustollens(PQ)(QR)PR假言三段論hypotheticalsyllogism

公式名稱PPQ否定前件律

QPQ肯定后件律(PQ)(PR)(QR)R兩難推理

(PQ)P(PQ)Q(PQ)(RS)(PR)(QS)(PQ)(QR)(PR)例求證：(PQ)(QR)PR證明：只需證(PQ)(QR)(PR)是重言式。(PQ)(QR)(PR)?((PQ)(QR))(PR)?((?PQ)(?QR))(?PR)?(?PQ)?(?QR))(?PR)(P?Q)(Q?R))(?PR)(P?Q)?P)(Q?R)R)(?Q?P)(QR)?QQ?PR

T2024/5/141097

定理

設P和Q為任意兩個命題公式,PQ的充分必要條件是:PQ且QP;

2024/5/141098蘊含式的性質(1)設A、B、C為命題公式,假設AB,且A是重言式,

那么B必是重言式;

證明:由AB,知AB的真值恒為T,所以,A為T

時,B也必為T#

(2)假設AB,BC,那么AC;

證明:由AB,BC,得:AB和BC為重言式,

由定理4.2知:(AB)(BC)也是重言式,

又由假言三段論知:(AB)(BC)AC,

由性質(1)知:AC為重言式,即AC#2024/5/141099(3)假設AB,AC,那么A(BC);

證明:因為AB,AC皆為重言式,

1)假設A為T,那么B和C皆為T,故BC為T,

因此,A(BC)為T,

2)假設A為F,那么無論BC為何真值,

都有,A(BC)為T,

故A(BC)為重言式,即A(BC)#

2024/5/1410100(4)假設AB,CB,那么ACB;

證明:設AB,CB,那么AB為T,且CB為T,從而,(AB)(CB)也為T,而由分配律得

(AB)(CB)

=(AC)B=(AC)B=ACB

從而有ACB為T,故ACB#2024/5/1410101推理理論定義設A和C是兩個命題公式,如果AC為重言式,即AC,稱C為A的有效結論,或稱C可由A邏輯地推出。

一般地,假設H1,H2,…,Hn以及C都是命題公式,如果有H1H2…HnC,那么稱C是一組前提H1,H2,…,Hn的有效結論。

邏輯推理的方法

邏輯推理的方法主要有真值表法、直接證法和間接證法。2024/5/1410103真值表法

設P1,P2,…,Pm是H1,H2,…,Hn和C中的所有原子命題變元,如果對P1,P2,…,Pm作了全部真值指派,并求出H1,H2,…,Hn和C對應的真值,就可判斷H1H2…HnC是否成立。例用真值表證明邏輯蘊含式:(PQ)(RQ)PR.解:令A=(PQ)(RQ),B=PR,那么有右邊真值表。

由此表可以看出,所要證明的邏輯蘊含式是成立的.#PQR

P

QR

QAB=P

RA

BTTTTFFFTTTFFTFTTTFTFTFFTTFFFTFTTFTTTFFTTFTFTTTTTFFTTTTTTFFFTTTTT直接證法直接證法就是由一組前提,根據的等價式和蘊含式以及一些公認的推理規(guī)那么,推出有效的結論。

P規(guī)那么---前提在推導過程中的任何時候都可以引入使用;

T規(guī)那么---在證明的任何步驟上得到的結論都可以在其后的證明中引用。例用直接證法證明邏輯蘊含式

(

P

Q)

(R

Q)

P

R.證法一:設左方為真，來證右方也為真。證畢。

(1)

P

Q=TP(2)若

P=T,則已有P

R=T

(分情況討論)(3)若Q=T,P=TT(1)(2)(分情況討論)(4)R

Q=TP(5)

R=TT(3)(4)(6)P

R=TT(3)(5)(

P

Q)

(R

Q)

P

R證法二:設右方為假，要證左方也為假.證畢。(1)

(P

R)P(2)PRT(1)(3)PT(2)(4)RT(2)(5)(P

(R

Q))T(3)(6)

(Q

(

R

Q))T(4)(7)

(Q

(R

Q))T(6)(8)

((

P

Q)

(R

Q))

T(5)(7)間接證法(反證法)定義假設公式H1,H2,…,Hm中的原子命題變元為P1,P2,…,Pn,如果存在P1,P2,…,Pn的一組真值指派,能使H1H2…Hm的真值為T,那么稱公式H1,H2,…,Hm是相容的。如果對于P1,P2,…,Pn的任一組真值指派,H1H2…Hm的真值均為F,那么稱公式H1,H2,…,Hm是不相容的。要證明:H1H2…HmC,(即由H1,…,Hm推出C)

即證:H1H2…HmC為重言式,

即證:C(H1H2…Hm)為重言式,

即證:C(H1H2…Hm)為重言式,

即證:C(H1H2…Hm)為矛盾式,

即證:H1,H2,…,Hm與C是不相容的。例用間接證法證明

(

P

Q)

(R

Q)

P

R.證明:證畢.(1)

(P

R)P(2)PRT(1)(3)PT(2)(4)RT(2)(5)

P

QP(6)QT(3)(5)(7)R

QP(8)

Q

T(4)(7)(9)Q

QT(6)(8)用CP規(guī)那么證明H1H2…Hn(RC)記S=H1H2...Hm,問題轉化為證明:S(RC).即證S(RC)為永真，即證S(RC)為永真，因為,S(RC)S(RC)

(SR)C)(SR)C

(SR)C,故只要證(SR)C為永真，即證(SR)C。所以,要證S(RC),只需證(SR)C即可。這種證明方法稱為CP規(guī)那么，稱R為附加前提。

例用CP規(guī)那么證明

(PQ)(RQ)PR.證明:證畢。(1)PP(附加前提)(2)

P

QP(3)QT(2)(4)R

QP(5)

RT(3)(4)其他聯結詞2024/5/1410113不可兼析取設P和Q是兩個命題公式,復合命題稱作P和Q的不可兼析取.的真值當且僅當P與Q的真值不相同時為T;否那么的真值為F.

定理連接詞有以下性質:

(1)交換律(2)結合律

(3)分配律:

(4)(同一律)

(5)(常元律)2024/5/14114條件否認、與非、或非(條件否認)設P和Q是兩個命題公式,復合命題PQ稱作P和Q的條件否認.PQ的真值為T,當且僅當P→Q的真值為F(即P=T,Q=F).(即PQ(P→Q)))(與非↑)設P和Q是兩個命題公式,復合命題P↑Q稱作P和Q的“與非”.P↑Q的真值為T,當且僅當PQ的真值為F.(即P↑Q(PQ))(或非↓)設P和Q是兩個命題公式,復合命題P↓Q稱作P和Q的“或非”.P↓Q的真值為T,當且僅當PQ的真值為F.

(即P↓Q(PQ))2024/5/1410115最小聯結詞組定義

如果一組連接詞可以表達出所有聯結詞,但去掉其中的任何一個,就不能表達出所有的聯結詞，稱該聯結詞組為最小聯結詞組.{,}、{,

}、{,→}、{↑}、{↓}等都是最小聯結詞組。2024/5/1410116對命題公式的進一步分析2024/5/1410117對偶式定義設A是命題公式,將A中的聯結詞換成,將換成,假設有特殊變元T和F,那么相互替換,所得的公式A*稱為公式A的對偶式。

顯然,假設A*是A的對偶式,那么A也是A*的對偶式,即有:(A*)*=A;

例

(PQ)R的對偶式是(PQ)R

((PQ)(PQ))((PQ)(PQ))的對偶式是((PQ)(PQ))((PQ)(PQ)).2024/5/14119例ABC的對偶式不是ABC而是A(BC)

(AB)(AC)2024/5/1410120假設P、Q均為命題公式，那么(PQ)*(P*Q*)(PQ)*P*Q*PQP*Q*(P↑Q)*=P*↓Q*(P↓Q)*=P*↑Q*(PQ)*P*Q*2024/5/1410121定理設A和A*是對偶式,P1,P2,…,Pn是出現在A和A*中的原子變元,那么有:

(1)(A*)*=A

(2)A(P1,P2,…,Pn)A*(P1,P2,…,Pn),

(3)A(P1,P2,…,Pn)A*(P1,P2,…,Pn);

(4)A(P1,P2,…,Pn)B(P1,P2,…,Pn)的充要條件是A*(P1,P2,…,Pn)B*(P1,P2,…,Pn).前述定理說明，在等價的意義下，命題公式的對偶式是唯一的。我們將和命題公式A等價的命題公式的對偶式都稱之為A的對偶式。例寫出以下公式的對偶式.(1)(PQ)R(2)(PQ)(PQ)(3)(P↑Q)↓R.2024/5/1410124解:(1)(PQ)R(PQ)R,故它的對偶式為(PQ)R.(2)(PQ)(PQ)(PQ)(PQ)((PQ)(PQ))((PQ)(PQ))((PQ)(PQ))((PQ)(PQ)),故而它的對偶式為((PQ)(PQ))((PQ)(PQ)).

(3)(P↑Q)↓R((PQ))↓R(((PQ))R),故而它的對偶式為

(((PQ))R).

(注)經過化簡可以得到

(((PQ))R)

(((PQ))↑R

(P↓Q)↑R.范式和主范式2024/5/14127析取范式定義一個命題公式稱為析取范式,當且僅當它具有形式:A1A2…An(n1),其中A1,A2,…,An都是由原子命題變元或其否認所組成的合取式。

定義和一個命題公式等價的析取范式，稱為這個命題公式的一個析取范式例：析取范式

P(

P

Q)(PQR),PQ,

P

Q

R都是析取范式。問：PQR是不是析取范式？2024/5/1410129例：析取范式并不唯一顯然P

(Q

R)是一個析取范式;然而

P

(Q

R)(PP)P

(Q

R)這顯然也是它的一個形式不完全相同的析取范式.2024/5/1410130定理

每個命題公式都有與之等價的析取范式存在.例判斷以下各命題公式是否是析取范式:(1)P

Q

R

S

U(2)(P

Q)

(Q

R)解:(1)是的，因為它即如下形式

(P

Q

R)

S

U

(2)不是范式,但可通過等價找到它的一個析取范式:(P

Q)

(Q

R)

(P

Q)

(Q

R)

(

P

Q)

(Q

R)

(

P

Q)

Q

R.例將下述命題公式化為析取范式:

(P

Q)

(P

Q).解:原式

(P

Q)

(P

Q)((P

Q)

(Q

P))

(P

Q)((

P

Q)

(

Q

P))

(P

Q)((P

Q)

(Q

P))

(

P

Q).這就是原公式的一個析取范式.將命題公式化為析取范式的一般方法(1)將公式中所有的聯結詞化為,,這三種聯結詞;(2)利用德摩根律將否認聯結詞移到各個原子命題變量的前面;(3)再利用分配律和結合律等等價的命題公式將原命題公式化為析取范式.小項定義

形如P1*

P2*

…Pn*的命題公式稱為是由命題變元P1,P2,…,Pn產生的小項(也稱布爾小項、極小項、最小項、布爾合取式),其中Pi*為Pi或為

Pi。兩個命題變元P和Q的全部小項共有如下4個:

P

Q,P

Q,

P

Q,

P

Q;

三個命題變元P,Q,R的全部小項共有如下8個:

P

Q

R,P

Q

R,P

Q

R,P

Q

R,

P

Q

R,

P

Q

R,

P

Q

R,

P

Q

R一般來說,n個命題變元共有2n個小項。2024/5/1410136兩個命題變元P和Q的小項的真值表為:PQP

QP

Q

P

Q

P

QTTTFFFTFFTFFFTFFTFFFFFFT

三個命題變元P、Q、R的小項的真值表如下所示

2024/5/14138PQRPQRPQRPQRPQR

PQR

PQR

PQR

PQRTTTTFFFFFFFTTFFTFFFFFFTFTFFTFFFFFTFFFFFTFFFFFTTFFFFTFFFFTFFFFFFTFFFFTFFFFFFTFFFFFFFFFFFT小項性質(1)沒有兩個小項是等價的；

(2)任意兩個不同小項的合取是矛盾式；

例如(PQR)(PQR)

PPQRF#

(3)全體小項的析取必為T小項的編碼規(guī)那么三個命題變量P,Q,R的小項的編碼規(guī)那么:

m000=PQR,m001=PQR,m010=PQR,m011=PQR,m100=PQR,m101=PQR,m110=PQR,m111=PQR編碼的下標即使得小項取值為T的變量值的分配主析取范式定義如果命題公式A的一個析取范式僅由小項的析取所組成,那么此析取范式稱為公式A的主析取范式。矛盾式的主析取范式為空范式，用0表示。定理每個的命題公式都有主析取范式存在.

定理

對命題公式A而言，它的真值表中所有使得A的真值為T的指派所對應的小項的析取,即為公式A的主析取范式。

例分別求PQ,PQ,(PQ)的主析取范式。解:列出三公式的真值表:

PQPQPQ(PQ)

由真值表及前面的定理可知

PQ

m00m01m11=(PQ)(PQ)(PQ)

PQ即m11，它就是自己的主析取范式

(PQ)

m00m01m10=(PQ)(PQ)(PQ)PQPQPQ(PQ)11110100010110100101例設一公式A的真值表如右:故A的主析取范式為:

Am111m010m000

=(PQR)(PQR)(PQR)PQRA11111100101010000110010100100001例求以下公式的主析取范式:

(1)Q(P(QP))

(2)(P(QR))(P(QR))解:(1)公式Q(P(QP))的真值表如下:

故而Q(P(QP))m11m10m00=(PQ)(P┐Q)(┐P┐Q)2024/5/14146PQQPP(QP)Q(P(QP))11111101110100000111(2)(P(QR))(P(QR))

(P(QR))(P(QR))

(PP)((P(QR))

((QR)P)((QR)(QR))

F(PQR)(PQR)F

(PQR)(PQR)

=

m000m111求主析取范式的一般步驟(1)化為析取范式;(2)除去析取式中所有為永假的析取項;(3)將析取項中重復出現的合取項和相同的變元