第五章-數(shù)理邏輯

第五章數(shù)理邏輯數(shù)理邏輯：用數(shù)學的方法來研究形式邏輯。所謂數(shù)學的方法，主要是指引進一套符號體系的方法。故又稱為符號邏輯?！?命題演算1.1命題1.2命題公式1.3重言式1.4命題演算基本公式1.5命題演算的基本蘊含重言式及推理規(guī)則1.6范式1.7命題連接詞的擴充與歸約1.1命題一、命題的基本概念定義1.命題：能分辨其真假的語句。一般用大寫字母（P,Q,R,…）表示。如1.三角形的內(nèi)角之和為180O。

2.中國在亞洲。一、命題的基本概念NOTE:(1)

命題分為真命題、假命題。（分別用T、F表示）如：①子路是孔子的學生（T）②張飛是孔子的學生（F）③3是素數(shù)（T）④3＋2>10（F）(2)只有陳述句才能是命題。

如：①請問到中關村怎么走？②請把門關上！均不是命題。一、命題的基本概念(3)悖論不是命題。如：①我正在撒謊。②村里有名理發(fā)師，他約定：“每個人只給不給自己刮胡子的人刮胡子?！雹垭u蛋悖論④柏拉圖與蘇格拉底悖論

柏拉圖：“蘇格拉底老師下面的話是假話。”

蘇格拉底：“柏拉圖上面的話是對的。”一、命題的基本概念(4)命題要么是真，要么是假。（具有模棱兩可含義的語句不能作為命題）如：100是個很大的數(shù)。(5)有些語句目前不能判斷其真假，但他是有真假的。這樣的語句也是命題。如：①木星上有生命。②任一足夠大偶數(shù)都能表示為兩素數(shù)之和（哥德巴赫猜想）

均是命題。一、命題的基本概念例1：判斷下列語句哪些是命題。

(1)《紅樓夢》的作者是曹雪芹。

(2)1＋1＝10

（是否正確與“數(shù)制”有關）

(3)我喜歡聽你唱歌。

(4)你喜歡“藍色的多瑙河”嗎？

(5)x+y>=3(x和y是任意數(shù))

解：(1)、(2)、(3)是命題。(4)、(5)不是。對于(5)，不能確定真假（∵x、y代入不同的值，會得不同的真假值，當x、y為復數(shù)時，比較關系根本不存在?。┮?、命題的基本概念定義2.

一個命題若不能再分成更簡單的命題，則稱為原子命題；否則稱為復合命題。例：

P:李明學習好。

Q:李明球踢得好。R：李明學習好，并且球踢得也很好。則R是一個復合命題二、命題聯(lián)接詞(1)合取聯(lián)接詞——“并且”。

P并且Q，記為P∧Q,稱為P與Q的合取式；

P、Q稱為合取項。PQP∧QTTFFTFTFTFFF∧真值表：

例2.

P:4是偶數(shù)Q:2是奇數(shù)

P∧Q：4是偶數(shù)且2是奇數(shù)。

P或者Q，記為P∨Q。稱為P與Q的析取式；P、Q稱為析取項。

例3.P:今晚我看電視

Q:今晚我看《離散數(shù)學》

P∨Q：今晚我看電視或看《離散數(shù)學》。(2)析取聯(lián)接詞——“或者”PQP∨QTTFFTFTFTTTF∨真值表：

P的否定命題，記為﹁P。

例4.P:

地球是圓的

﹁

P:地球不是圓的

其真值關系表為：P﹁PTFFT(3)否定聯(lián)接詞——“非”P蘊含Q，記為P→Q?？衫斫鉃椤叭绻鸓，則Q”。其中P稱為蘊含前件，Q稱為蘊含后件。

例5:P:下雨了Q:地濕了

P→Q：如果下雨了，則地濕了。其真值關系表為：PQP→QTTFFTFFTTFTT(4)蘊含聯(lián)結(jié)詞NOTE:

①注意理解真值表后兩行。②注意數(shù)理邏輯與日常用語的區(qū)別。

(5)等價聯(lián)接詞例6.P:2-3≤0Q:

3-2≥0

P等價Q:2-3<=0當且僅當3-2>=0例7.

P:

愛因斯坦是個偉大的科學家

Q:

李白是唐代著名的詩人愛因斯坦是個偉大的科學家當且僅當李白是唐代著名的詩人。

其真值關系為：PQTFTFFTTFFFTT

等價表達式：充分必要、只有……才能……NOTE:命題聯(lián)接詞是命題間的聯(lián)接詞，而不是名詞或形容詞之間的聯(lián)接詞。如：P:“王蘭和王英是姐妹”中的“和”不是命題聯(lián)接詞，故P也不是一個復合語句。(5)等價聯(lián)接詞例8.

求下列命題的真值。

(1)如果1＋2＝3，則雪是黑的

(2)如果太陽從西邊出來，那么地球自轉(zhuǎn)

(3)如果太陽從東邊出來，那么地球自轉(zhuǎn)停止。三、復合命題運算優(yōu)先級問題：優(yōu)先級：“﹁”

→“∧”→“∨”→“→”→“”復合命題：經(jīng)過命題連接詞連接而成的命題。三、復合命題例9.

命題P為：“明天下雨”。Q為：“明天下雪”。

R為：“我去學?！?。則：①明天不是雨夾雪，則我去學校?？蓪懗?/p>

﹁(P∧Q)→R

②明天不下雨，且不下雪，則我去學校。

﹁P∧﹁Q→R

③明天下雨或下雪，我不去學校。

P∨Q→﹁R

④只有當明天不下雨且不下雪，我才去學校。⑤明天我一定去學校，風雨無阻。(P∧Q∧R)∨(P∧﹁Q∧R)∨(﹁P∧

Q∧R)∨(﹁P∧﹁Q∧R)﹁P∧

﹁

QR

三、復合命題例10.

除非你陪我或給我叫車，否則我不出去?？衫斫鉃?“我出去的充要條件是你陪我或給我叫車”。令P:你陪我Q:

給我叫車R:

我出去則上述語句可用如下復合命題來表達：﹁(P∨Q)

﹁R或P∨QR§1命題演算1.1命題1.2命題公式1.3重言式1.4命題演算基本公式1.5命題演算的基本蘊含重言式及推理規(guī)則1.6范式1.7命題連接詞的擴充與歸約1.2命題公式定義3.

一個任意的未指定真值的命題，稱為命題變元。（一般也簡稱為命題）定義4.

經(jīng)有限步使用，下面法則所得到的公式稱為命題公式。

1.命題變元是命題公式2.若P和Q是命題公式，則﹁P、P∧Q、P∨Q、P→Q、PQ是命題公式。1.2命題公式例11.

已知P、Q、R是命題，則

是命題公式

P、Q

是命題P、Q

是命題公式P∧Q是命題公式R是命題公式是命題公式P、Q

是命題P、Q

是命題公式P∨Q是命題公式是命題公式1.2命題公式例12.

P→∧Q不是公式。定義5.命題變元一組確定的值稱為公式的一個指派。所有的指派構(gòu)成的公式的真值組合稱為公式真值表。問題：一個由n個命題變元構(gòu)成的公式共有種多少指派？答案：2n1.2命題公式例13.

構(gòu)造下列命題的真值表解：PQTTFFTFTFFTFFFTTTTTFFFTFTFFFTTTFFP∧Q﹁(P∧Q)﹁P﹁Q﹁P∧

﹁Q§1命題演算1.1命題1.2命題公式1.3重言式1.4命題演算基本公式1.5命題演算的基本蘊含重言式及推理規(guī)則1.6范式1.7命題連接詞的擴充與歸約1.3重言式考慮的真值表PQP→Q﹁(P→Q)TTFFTFTFTFTTFTFFTTTT定義1.命題公式若對其所有指派的真值均為T，稱為永真式或重言式。相反，命題公式若對其所有指派的真值均為F，稱為永假式或矛盾。

定義2.一個命題公式如果至少存在一個指派，使其取值為F，則稱為非永真式。如果至少存在一個指派，使其取值為T，則稱為可滿足的。1.3重言式例1.

（1）P∨﹁P是永真式（2）P∧﹁P是永假式（3）是永真式，為矛盾（4）不是永真式，也不是永假式，是可滿足的。1.3重言式關于重言式和矛盾，有些顯而易見的特性：（1）重言式的否定是矛盾，矛盾的否定是重言式。（2）兩個重言式的合取、析取、蘊含、等價均為重言式。（3）兩個矛盾的合取、析取必為矛盾；兩個矛盾的蘊含、等價必為重言式。（4）兩個公式P、Q，若PQ為重言式，則P、Q對任何指派必為同真假。1.3重言式定義3.P、Q為兩個公式，若為重言式，則稱其為等價重言式，也可稱為P、Q相等。記為。定義4.P、Q為兩個公式，若P→Q為重言式，則稱為蘊含重言式，記為?！?命題演算1.1命題1.2命題公式1.3重言式1.4命題演算基本公式1.5命題演算的基本蘊含重言式及推理規(guī)則1.6范式1.7命題連接詞的擴充與歸約1.4

命題演算基本等式P178-1791.4

命題演算基本等式定義5.

（對偶公式）設有公式A，若它僅用聯(lián)接詞﹁、∨、∧，把A種的∨、∧、T、F分別換成∧、∨、F、T，得到公式A*，稱為A的對偶公式。又如：吸收律：如狄摩根定律：定理1.

設有等式A=B,則必有A*=B*。(此處A、B僅有聯(lián)接詞﹁、∨和∧)1.4

命題演算基本等式例2.化簡下面語句：

情況并非如此：如果他不來，那么我也不去。

即：我去了但他沒來。解：

P:他來，Q：我去1.4

命題演算基本等式例3.

試證語句“不會休息的人不會工作，沒有豐富知識的人也不會工作”“工作好的人一定會休息，并且具有豐富的知識”。解：P:

某人會休息Q：某人有豐富的知識

R:

某人工作的好則語句為1.4

命題演算基本等式例4.

化簡程序：如有下面一段PASCAL程序：

IFA

THENIFB

THENX

ELSEY

ELSEIFB

THENX

ELSEY;1.4

命題演算基本等式解：原程序用公式可表示為：令則上式可寫為：IFA

THENIFB

THENX

ELSEY

ELSEIFB

THENX

ELSEY;1.4

命題演算基本等式解：原程序用公式可表示為：令IFA

THENIFB

THENX

ELSEY

ELSEIFB

THENX

ELSEY;故原程序可化簡為：

IFB

THENX

ELSEY.§1命題演算1.1命題1.2命題公式1.3重言式1.4命題演算基本公式1.5命題演算的基本蘊含重言式及推理規(guī)則1.6范式1.7命題連接詞的擴充與歸約1.5命題演算的基本蘊含重言式及推理規(guī)則首先，1.4節(jié)中的所有基本等式都可以作為兩個蘊含重言式即：P=Q

相當于1.5

命題演算的基本蘊含重言式及推理規(guī)則除此之外，還有一些基本蘊含式，其正確性可由真值表給出。P┣QP,Q┣R┣R(67)(析取三段論)┓P,P∨Q┣Q(68)(假言推論)P,P→Q┣Q(69)(拒取式)┓Q,P→Q┣┓P1.5

命題演算的基本蘊含重言式及推理規(guī)則例.

某女子深夜下班在路上被殺害，經(jīng)初步查證兇手為某甲或某乙，后進一步查實，某乙當晚在廠值夜班未外出，從而最后斷定兇手必為甲。

∴(69)(拒取式)(67)(析取三段論)Q→R，┓R┣┓Q┓Q,P∨Q┣P解：

P:甲是兇手

Q:乙是兇手

R:乙當晚外出前提為：P∨Q，﹁R，隱含前提：兇手必當晚外出。即：Q→R§1命題演算1.1命題1.2命題公式1.3重言式1.4命題演算基本公式1.5命題演算的基本蘊含重言式及推理規(guī)則1.6范式1.7命題連接詞的擴充與歸約1.6.1

析取范式定義1.

一個命題公式稱為析取范式，當且僅當它具有形式，其中Ai為由若干個命題變元或命題變元的否定組成的合取式。③利用分配律最后化成?；獠襟E：①用(36式)

(37式)

把公式的“→”和“”去掉。②用狄摩根定律將公式的否定符號深入至命題變元，并利用減少否定符號。1.6.1

析取范式例1.

求公式的析取范式。①去掉“”原式＝②上式＝③＝析取范式的特性:

公式為矛盾析取范式中每個析取項均為矛盾

析取項中必同時包含一個命題變元及其否定。

如:

即為矛盾。1.6.2

特異析取范式定義2.如果一個析取范式中，每個析取項均包含了所有命題變元，它以命題變元或命題變元之否定形式出現(xiàn)且僅出現(xiàn)一次，這樣的析取范式稱為特異析取范式。

化解步驟：①化成析取范式；②出去永假項（即P∧┓P）③用P∧P=P化簡某變元出現(xiàn)多次某變元未出現(xiàn)④若某變元Q未出現(xiàn)，則用下式補充：1.6.2

特異析取范式例2.

求命題公式

的特異析取范式。1.6.2

特異析取范式定義3.特異析取范式中的析取項稱為最小項。n個命題變元可組成2n個最小項。使最小項為T的指派最小項如3個命題變元P、Q、R：1.6.2

特異析取范式每個最小項只存在唯一的指派使其為T。（規(guī)則：若以P形式出現(xiàn)，則令其為T；若以﹁P形式出現(xiàn)，則其為F），如上表。

如此，最小項與指派間建立了一一對應關系。定理：在公式的真值表中，以使公式真值為T的指派所對應的最小項為析取項所構(gòu)成的公式為原公式的特異析取范式。1.6.2

特異析取范式P、Q、R﹁PR∨P﹁P→R∨PTTTTTFTFTTFFFTTFTFFFFFTTTTTTTFTTTTTFTTFFFFT√T√FFFFFFTFFFTTTFTFTTT√F例3.

例2中公式的真值表為：1.6.2

特異析取范式由公式的真值表可知，公式S的特異析取范式為：（與例2結(jié)果相同）1.6.2

特異析取范式如何理解該定理：

設原式為S，按定理規(guī)則所構(gòu)成的公式為S’，只須證S與S’同真假。為此需考慮公式S的所有指派（分以下2類）

（1）對于使S為真的指派，由于它所對應的最小項出現(xiàn)在S’中，故該指派也必使S’為真。

（2）對于使S為假的指派，由于它所對應的最小項不出現(xiàn)在S’中，故該指派也必使S’的每一項為假，從而使S’為假。

在不考慮命題變元的次序前提下，一個命題公式的特異析取范式是唯一的。1.6.2

特異析取范式關于特異析取范式，有以下結(jié)論：

（1）n個命題變元只能組成22n個不能的公式。

（2）一公式為永真式其特異析取范式包含所有的最小項（3）一公式為矛盾其特異析取范式不包含任何最小項，即為“空”。（4）兩公式相等兩公式的特異析取范式一樣。1.6.3

合取范式和特異合取范式與析取式對應，合取范式有如下形式：其中P1為由若干個命題變元或其否定形式構(gòu)成的析取式。

合取范式的特性：

公式為永真式合取范式中每個合取項均為永真式合取范式中每個合取項同時包含一個命題變元及其否定。

可以類似地把一個公式化為合取范式和特異合取范式。特異合取范式中的合取項稱為最大項。1.6.3

合取范式和特異合取范式n個命題變元可組成2n個最大項，每一個最大項只存在一個指派使其為假。

特異合取范式的性質(zhì)：

（1）一公式為矛盾其特異合取范式包含所有的最大項。

（2）一公式為重言式其特異合取范式為空。

（3）兩公式相等其特異合取范式一致。1.7.1命題聯(lián)結(jié)詞的擴充（1）異或⊕

（2）與非↑

（3）或非↓

（4）蘊含否定→例.小王考試全班第一或全班第二。

P:小王考試全班第一

Q:小王考試全班第二

則上句可表示為：此即為不可兼或，與以前的或（可兼或）不同。1.7.1命題聯(lián)結(jié)詞的擴充又如：我明天上北京，或去上海。（不可兼）

我喜歡唱歌或跳舞。（可兼）

明天下雨或下雪。（可兼）PQP⊕QP↑QP↓QP→QTTTFFTFTTFTTFFFFTFFFFTTF可以證明，以上講的9個聯(lián)結(jié)詞能包含所有的情況。1.7.2命題聯(lián)結(jié)詞的歸納（1）由范式的討論可知，只需3個，即

∧，∨，﹁

又∵

∴只需2個即可。（∧，﹁）或（∨，﹁）

（2）后來，謝佛和魏汩分別發(fā)現(xiàn)只需一個即可：

↑或↓。

∵

或

§2

謂詞演算2.1謂詞與個體

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變元和約束變元

2.6謂詞演算的永真公式

§2

謂詞演算2.1

謂詞與個體

命題演算中，原子命題是一個基本的不可分割的單位。

但有些論證只靠命題演算是不夠的，如“蘇格拉底論題”：

凡人必死

蘇格拉底是人

所以，蘇格拉底必死PQ

∴R

？2.1

謂詞與個體故應如此符號化：

所有A是B

C是A

∴C是B

從語法上看，每個被視為命題的語句是由主語和謂語兩部分組成。

例1.（1）蘇格拉底是人

（2）這本書很有趣多元謂詞一元謂詞2.1

謂詞與個體個體——客觀存在的人或事物，可具體、抽象，用a，b，c表示。

謂詞——描述個體的性質(zhì)或幾個個體之間的關系，用F，G，H表示。每個個體有一定的變化范圍，稱為個體域。不考慮具體的個體而只考慮以個體域為變域的變元稱為個體變元。一般用x，y，z表示。由謂詞與與之相關的若干個體構(gòu)成命題，此命題可寫為：如：陳化和陳華是兄妹。定義：例2.

令F(x,y)表示x和y是兄妹。a:陳化b：陳華則命題可表示為F(a,b)。例3.蘇格拉底是人。解：A(x)表示“x是人”

a:蘇格拉底則A(a)：蘇格拉底是人。2.1

謂詞與個體例4.

這棟大樓建成了。解：F(x)：x建成了

G(x)：x是樓H(x)：x是大的

a：這個則：F(a)

∧G(a)

∧H(a)謂詞：通用名詞，形容詞，動詞

個體：專有名詞，人稱代詞，指示代詞結(jié)論：2.1

謂詞與個體2.1

謂詞與個體例5.

這個人正在看那本紅皮書。解：F1(x)：x是人F2(x)：x是書

F3(x,y)：x看y

F4(x)：x是紅皮的

a：這個b：那個則：2.1

謂詞與個體例6.

我一面講課，一面注意學生甲、乙的反應。解：F1(x)：x講課F2(x,y)：x注意y的反應

F3(x)：x是學生

a：我b：甲c：乙則：2.1謂詞與個體

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變元和約束變元

2.6謂詞演算的永真公式

2.2

量詞例1.

所有的書都有價值。例2.

存在實數(shù)x使x+3=2。例1中，令F(x)：x有價值；

例2中，令G(x)：x+3=2；x：表示所有的書則可表示為：x：存在x則可表示為：定義：

x稱為全稱量詞。x稱為存在量詞。

緊跟在量詞后面的最小的子公式稱為量詞的轄域。2.2

量詞在存在量詞的謂詞演算中必須表明個體域。此時用特性謂詞來刻劃個體變元的變化范圍。如：M(x)：x是書；R(x)：x是實數(shù)。然后按下面規(guī)則，將特性謂詞加入到已有的命題中。

(1)對于全稱量詞，特性謂詞作為蘊含式的前件加入。

(2)對于存在量詞，特性謂詞作為合取式的合取項加入。

例1應寫為：例2應寫為：例1.

所有的書都有價值。例2.

存在實數(shù)x使x+3=2。2.2

量詞例3.

將下列語句形式化為謂詞邏輯的命題。

（1）有些自然數(shù)是素數(shù)。

M(x)：x是自然數(shù)

F(x)：x是素數(shù)

∴

（2）沒有不犯錯誤的人。

M(x)：x是人

F(x)：x犯錯誤

則：2.2

量詞（3）凡是實數(shù)不是大于零就是等于或小于零。

R(x)：x是實數(shù)

F(x,y)：x>y

G(x,y)：x=y

H(x,y)：x<y

則：2.2

量詞例4.

每個人都有一些缺點。例5.

有些女孩子比所有的男孩子都聰明。解：F(x,y)：x有y

特性謂詞：M1(x)：x是人M2(x)：x是缺點則：解：P(x)：x是女孩子Q(x)：x是男孩子

G(x,y)：x比y聰明則：2.2

量詞例6.

沒有最大的自然數(shù)。解：該語句等價于“對于任意自然數(shù)x存在比x更大的自然數(shù)y”。

N(x)：x是自然數(shù)

G(x,y)：x比y大則：2.1謂詞與個體

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變元和約束變元

2.6謂詞演算的永真公式

2.3

函數(shù)引出：

G(x,y)：x=y

如何表示x+y=1?

G(x+y,1)

但為了完全符號化，需f(x,y)：x+y

G(f(x,y),1)2.3

函數(shù)函數(shù)——謂詞演算中個體與個體之間的關系。

即函數(shù)是個體→個體的映射。

f(x)：x是個體，f(x)仍是個體。

f(x,y)：x,y是個體，f(x,y)仍是個體。

例：個體域為人的集合，f(x)表示x的父親，則

f(f(x))表示x的祖父。例：個體域為實數(shù)域，g(x,y)表示x+y，則g(8,9)是17。例：肖陽的爸爸去北京了。

f(x)：x的爸爸F(x,y):x去y地方

a：肖陽b：北京

則：F(f(a),b)2.1謂詞與個體

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變元和約束變元

2.6謂詞演算的永真公式

2.4

謂詞演算公式謂詞演算要使用的符號：

（1）個體常量符：a,b,c,…

（2）個體變量符：x,y,z,…

（3）謂詞：F,G,H,…

（4）量詞：

（5）函數(shù)：f,g,h,…

（6）聯(lián)結(jié)詞：

（7）括號、逗號：“(”,“)”,“,”2.4

謂詞演算公式定義：項

——經(jīng)過下面3步迭代有限次：

（1）個體常量是項

（2）個體變量是項

（3）f是n元函數(shù)符，t1,t2,…,tn為項，則

f(t1,t2,…,tn)為項。定義：原子公式——設P是n元謂詞符，x1,x2,…,xn是項，則P(x