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

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

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

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

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

柏拉圖：“蘇格拉底老師下面的話是假話?！?/p>

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

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

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

(2)1＋1＝10

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

(3)我喜歡聽(tīng)你唱歌。

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

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

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

一個(gè)命題若不能再分成更簡(jiǎn)單的命題，則稱為原子命題；否則稱為復(fù)合命題。例：

P:李明學(xué)習(xí)好。

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

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

P、Q稱為合取項(xiàng)。PQP∧QTTFFTFTFTFFF∧真值表：

例2.

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

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

P或者Q，記為P∨Q。稱為P與Q的析取式；P、Q稱為析取項(xiàng)。

例3.P:今晚我看電視

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

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

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

例4.P:

地球是圓的

﹁

P:地球不是圓的

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

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

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

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

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

3-2≥0

P等價(jià)Q:2-3<=0當(dāng)且僅當(dāng)3-2>=0例7.

P:

愛(ài)因斯坦是個(gè)偉大的科學(xué)家

Q:

李白是唐代著名的詩(shī)人愛(ài)因斯坦是個(gè)偉大的科學(xué)家當(dāng)且僅當(dāng)李白是唐代著名的詩(shī)人。

其真值關(guān)系為：PQTFTFFTTFFFTT

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

求下列命題的真值。

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

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

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

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

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

R為：“我去學(xué)校”。則：①明天不是雨夾雪，則我去學(xué)校?？蓪?xiě)成

﹁(P∧Q)→R

②明天不下雨，且不下雪，則我去學(xué)校。

﹁P∧﹁Q→R

③明天下雨或下雪，我不去學(xué)校。

P∨Q→﹁R

④只有當(dāng)明天不下雨且不下雪，我才去學(xué)校。⑤明天我一定去學(xué)校，風(fēng)雨無(wú)阻。(P∧Q∧R)∨(P∧﹁Q∧R)∨(﹁P∧

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

﹁

QR

三、復(fù)合命題例10.

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

給我叫車R:

我出去則上述語(yǔ)句可用如下復(fù)合命題來(lái)表達(dá)：﹁(P∨Q)

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

一個(gè)任意的未指定真值的命題，稱為命題變?cè)＃ㄒ话阋埠?jiǎn)稱為命題）定義4.

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

1.命題變?cè)敲}公式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.命題變?cè)唤M確定的值稱為公式的一個(gè)指派。所有的指派構(gòu)成的公式的真值組合稱為公式真值表。問(wèn)題：一個(gè)由n個(gè)命題變?cè)獦?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命題演算的基本蘊(yùn)含重言式及推理規(guī)則1.6范式1.7命題連接詞的擴(kuò)充與歸約1.3重言式考慮的真值表PQP→Q﹁(P→Q)TTFFTFTFTFTTFTFFTTTT定義1.命題公式若對(duì)其所有指派的真值均為T(mén)，稱為永真式或重言式。相反，命題公式若對(duì)其所有指派的真值均為F，稱為永假式或矛盾。

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

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

命題演算基本等式P178-1791.4

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

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

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

命題演算基本等式例2.化簡(jiǎn)下面語(yǔ)句：

情況并非如此：如果他不來(lái)，那么我也不去。

即：我去了但他沒(méi)來(lái)。解：

P:他來(lái)，Q：我去1.4

命題演算基本等式例3.

試證語(yǔ)句“不會(huì)休息的人不會(huì)工作，沒(méi)有豐富知識(shí)的人也不會(huì)工作”“工作好的人一定會(huì)休息，并且具有豐富的知識(shí)”。解：P:

某人會(huì)休息Q：某人有豐富的知識(shí)

R:

某人工作的好則語(yǔ)句為1.4

命題演算基本等式例4.

化簡(jiǎn)程序：如有下面一段PASCAL程序：

IFA

THENIFB

THENX

ELSEY

ELSEIFB

THENX

ELSEY;1.4

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

THENIFB

THENX

ELSEY

ELSEIFB

THENX

ELSEY;1.4

命題演算基本等式解：原程序用公式可表示為：令I(lǐng)FA

THENIFB

THENX

ELSEY

ELSEIFB

THENX

ELSEY;故原程序可化簡(jiǎn)為：

IFB

THENX

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

相當(dāng)于1.5

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

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

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

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

P:甲是兇手

Q:乙是兇手

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

析取范式定義1.

一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式，其中Ai為由若干個(gè)命題變?cè)蛎}變?cè)姆穸ńM成的合取式。③利用分配律最后化成?；獠襟E：①用(36式)

(37式)

把公式的“→”和“”去掉。②用狄摩根定律將公式的否定符號(hào)深入至命題變?cè)?，并利用減少否定符號(hào)。1.6.1

析取范式例1.

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

公式為矛盾析取范式中每個(gè)析取項(xiàng)均為矛盾

析取項(xiàng)中必同時(shí)包含一個(gè)命題變?cè)捌浞穸ā?/p>

如:

即為矛盾。1.6.2

特異析取范式定義2.如果一個(gè)析取范式中，每個(gè)析取項(xiàng)均包含了所有命題變?cè)?，它以命題變?cè)蛎}變?cè)穸ㄐ问匠霈F(xiàn)且僅出現(xiàn)一次，這樣的析取范式稱為特異析取范式。

化解步驟：①化成析取范式；②出去永假項(xiàng)（即P∧┓P）③用P∧P=P化簡(jiǎn)某變?cè)霈F(xiàn)多次某變?cè)闯霈F(xiàn)④若某變?cè)猀未出現(xiàn)，則用下式補(bǔ)充：1.6.2

特異析取范式例2.

求命題公式

的特異析取范式。1.6.2

特異析取范式定義3.特異析取范式中的析取項(xiàng)稱為最小項(xiàng)。n個(gè)命題變?cè)山M成2n個(gè)最小項(xiàng)。使最小項(xiàng)為T(mén)的指派最小項(xiàng)如3個(gè)命題變?cè)狿、Q、R：1.6.2

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

如此，最小項(xiàng)與指派間建立了一一對(duì)應(yīng)關(guān)系。定理：在公式的真值表中，以使公式真值為T(mén)的指派所對(duì)應(yīng)的最小項(xiàng)為析取項(xiàng)所構(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

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

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

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

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

在不考慮命題變?cè)拇涡蚯疤嵯?，一個(gè)命題公式的特異析取范式是唯一的。1.6.2

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

（1）n個(gè)命題變?cè)荒芙M成22n個(gè)不能的公式。

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

合取范式和特異合取范式與析取式對(duì)應(yīng)，合取范式有如下形式：其中P1為由若干個(gè)命題變?cè)蚱浞穸ㄐ问綐?gòu)成的析取式。

合取范式的特性：

公式為永真式合取范式中每個(gè)合取項(xiàng)均為永真式合取范式中每個(gè)合取項(xiàng)同時(shí)包含一個(gè)命題變?cè)捌浞穸ā?/p>

可以類似地把一個(gè)公式化為合取范式和特異合取范式。特異合取范式中的合取項(xiàng)稱為最大項(xiàng)。1.6.3

合取范式和特異合取范式n個(gè)命題變?cè)山M成2n個(gè)最大項(xiàng)，每一個(gè)最大項(xiàng)只存在一個(gè)指派使其為假。

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

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

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

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

（2）與非↑

（3）或非↓

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

P:小王考試全班第一

Q:小王考試全班第二

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

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

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

∧，∨，﹁

又∵

∴只需2個(gè)即可。（∧，﹁）或（∨，﹁）

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

↑或↓。

∵

或

§2

謂詞演算2.1謂詞與個(gè)體

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變?cè)图s束變?cè)?/p>

2.6謂詞演算的永真公式

§2

謂詞演算2.1

謂詞與個(gè)體

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

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

凡人必死

蘇格拉底是人

所以，蘇格拉底必死PQ

∴R

？2.1

謂詞與個(gè)體故應(yīng)如此符號(hào)化：

所有A是B

C是A

∴C是B

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

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

（2）這本書(shū)很有趣多元謂詞一元謂詞2.1

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

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

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

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

謂詞與個(gè)體例4.

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

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

a：這個(gè)則：F(a)

∧G(a)

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

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

謂詞與個(gè)體2.1

謂詞與個(gè)體例5.

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

F3(x,y)：x看y

F4(x)：x是紅皮的

a：這個(gè)b：那個(gè)則：2.1

謂詞與個(gè)體例6.

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

F3(x)：x是學(xué)生

a：我b：甲c：乙則：2.1謂詞與個(gè)體

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變?cè)图s束變?cè)?/p>

2.6謂詞演算的永真公式

2.2

量詞例1.

所有的書(shū)都有價(jià)值。例2.

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

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

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

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

量詞在存在量詞的謂詞演算中必須表明個(gè)體域。此時(shí)用特性謂詞來(lái)刻劃個(gè)體變?cè)淖兓秶?。如：M(x)：x是書(shū)；R(x)：x是實(shí)數(shù)。然后按下面規(guī)則，將特性謂詞加入到已有的命題中。

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

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

例1應(yīng)寫(xiě)為：例2應(yīng)寫(xiě)為：例1.

所有的書(shū)都有價(jià)值。例2.

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

量詞例3.

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

（1）有些自然數(shù)是素?cái)?shù)。

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

F(x)：x是素?cái)?shù)

∴

（2）沒(méi)有不犯錯(cuò)誤的人。

M(x)：x是人

F(x)：x犯錯(cuò)誤

則：2.2

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

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

F(x,y)：x>y

G(x,y)：x=y

H(x,y)：x<y

則：2.2

量詞例4.

每個(gè)人都有一些缺點(diǎn)。例5.

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

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

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

量詞例6.

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

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

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

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變?cè)图s束變?cè)?/p>

2.6謂詞演算的永真公式

2.3

函數(shù)引出：

G(x,y)：x=y

如何表示x+y=1?

G(x+y,1)

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

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

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

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

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

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

例：個(gè)體域?yàn)槿说募希琭(x)表示x的父親，則

f(f(x))表示x的祖父。例：個(gè)體域?yàn)閷?shí)數(shù)域，g(x,y)表示x+y，則g(8,9)是17。例：肖陽(yáng)的爸爸去北京了。

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

a：肖陽(yáng)b：北京

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

2.2量詞

2.3函數(shù)

2.4謂詞演算公式

2.5自由變?cè)图s束變?cè)?/p>

2.6謂詞演算的永真公式

2.4

謂詞演算公式謂詞演算要使用的符號(hào)：

（1）個(gè)體常量符：a,b,c,…

（2）個(gè)體變量符：x,y,z,…

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

（4）量詞：

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

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

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

謂詞演算公式定義：項(xiàng)

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

（1）個(gè)體常量是項(xiàng)

（2）個(gè)體變量是項(xiàng)

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

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