2023年國(guó)家公務(wù)員考試行測(cè)經(jīng)典邏輯推理題滿分備考技巧講義

經(jīng)典邏輯推理

掌握謂詞公式的概念及可滿足性的定義，弄清置換與

合一的概念，掌握求取最一般合一置換的方法

掌握歸結(jié)原理及歸結(jié)推理方法。掌握Skolem標(biāo)準(zhǔn)式

和子句集的求取方法，理解謂詞公式和子句集在不可

滿足意義下的一致性，弄懂Herbrand定理，掌握H域

、原子集、H域上的解釋求法，掌握命題邏輯和謂詞

邏輯中的歸結(jié)原理

掌握利用歸結(jié)原理進(jìn)行定理證明的方法

掌握應(yīng)用歸結(jié)原理進(jìn)行問(wèn)題求解的方法

掌握歸結(jié)過(guò)程中的控制策略

1

H基本概念

&自然演繹推理

￡歸結(jié)演繹推理

與/或形演繹推理

按某種策略由已知判斷推出另一判斷的思維過(guò)程

包括已掌握的與求解問(wèn)題有關(guān)的知識(shí)及關(guān)于問(wèn)題的已知事實(shí)

推理的結(jié)論2由已知判斷推出新判斷

推理由程序程序?qū)崿F(xiàn)，稱為推理機(jī)

推理的基本任務(wù)

一從二種判斷推出另二種判斷

推理過(guò)程

從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過(guò)程

大前提：已知的一般性知識(shí)或假設(shè)

小前提：關(guān)于所研究的具體情況或個(gè)別事實(shí)的判斷

結(jié)論：由大前提推出的適合于小前提所示情況的新判斷

-在任何情況下，由演繹推導(dǎo)出的結(jié)論都是蘊(yùn)涵在大前提的一般性知識(shí)中

-只要大前提和小前提是正確的，則由它們推出的結(jié)論必然是正確的

歸納推理

從足夠多的事例中歸納出一般性

結(jié)論的推理過(guò)程，是一種從個(gè)別到一

般的推理

完全歸納推理不完全歸納推理

在進(jìn)行歸納時(shí)考察

了相應(yīng)事物的全部只考察了相

對(duì)象，并根據(jù)這些應(yīng)事物的部

對(duì)象是否都具有某分對(duì)象就得

種屬性，從而推出

這個(gè)事物是否具有出了結(jié)論

這個(gè)屬性

類比推理：在兩個(gè)或兩類

事物有許多屬性都相同或

相似的基礎(chǔ)上，推出它們

在其他屬性上也相同或相

似的一種推理

默認(rèn)推理

又稱缺省推理，它是在知識(shí)不完全的情

況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理

擺脫了需要知道全部事實(shí)才能進(jìn)行推理的

需求，使得在知識(shí)不完全的情況下也能進(jìn)行推

理

確定性推理儺醐淵礴鞭瞰分不確定性推理

推理時(shí)所用的知推理時(shí)所用的知識(shí)

識(shí)都是精確的，推推理不都是精確的，推

出的結(jié)論也是確定出的結(jié)論也不完全

的，其真值或者為是肯定的，真值位

真，或?yàn)榧?，沒(méi)有于真與假之間，命

第三種情況出現(xiàn)題的外延模糊不清

單調(diào)推理蹲睡幅蹦蜘非單調(diào)推理

在推理過(guò)程中隨著推

在推理過(guò)程中由于新知

理的向前及新知識(shí)的

推理識(shí)的加入，不僅沒(méi)有

加入，推出的結(jié)論是

加強(qiáng)已推出的結(jié)論，

呈單調(diào)增加的趨勢(shì)，

反而要否定它，使得

并且越來(lái)越接近最終

推理退回到前面的某

目標(biāo)，在推理過(guò)程中

一步，重新開(kāi)始

不出現(xiàn)反復(fù)的情況

推理過(guò)程

二個(gè)思維過(guò)程，即求解問(wèn)題的過(guò)程

1.推理方向

正向推理

以已知事實(shí)作為出發(fā)點(diǎn)的一種推理，又

稱為數(shù)據(jù)驅(qū)動(dòng)推理、前向鏈推理、模式制

導(dǎo)推理及前件推理

逆向推理

以某個(gè)假設(shè)目標(biāo)為出發(fā)點(diǎn)的一種推理,

又稱為目標(biāo)驅(qū)動(dòng)推理、逆向鏈推理、目標(biāo)

制導(dǎo)推理及后件推理

混合推理

?已知的事實(shí)不充分。通過(guò)正向推理先把

其運(yùn)用條件不能完全匹配的知識(shí)都找出來(lái),

并把這些知識(shí)可導(dǎo)出的結(jié)論作為假設(shè)，然

后分別對(duì)這些假設(shè)進(jìn)行逆向推理

?由正向推理推出的結(jié)論可信度不高

?希望得到更多的結(jié)論

通過(guò)正向推理，即從已知事實(shí)演繹出部分結(jié)果，然后再用

逆向推理證實(shí)該目標(biāo)或提高其可信度

先假設(shè)一個(gè)目標(biāo)進(jìn)行逆向推理，然后再利用逆向推理中

先逆向再正向

得到的信息進(jìn)行正向推理，以推出更多的結(jié)論

雙向推理

?雙向推理是指正向推理與逆向推理同時(shí)

進(jìn)行，且在推理過(guò)程中的某一步驟上“碰

頭”的一種推理。

?正向推理所得的中間結(jié)論恰好是逆向推

理此時(shí)要求的證據(jù)

2.求解策略

推理是只求一個(gè)解還是求所有解以及最優(yōu)解等

3.限制策略

/-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------X

對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)行限制

4.沖突消解策略

己知事實(shí)不能與知識(shí)庫(kù)中的任何知識(shí)匹配

成功

在推理過(guò)已知事實(shí)恰好只與知識(shí)庫(kù)中的一個(gè)知識(shí)匹

程中，匹配成功

配會(huì)出現(xiàn)

三種情況

已知事實(shí)可與知識(shí)庫(kù)中的多個(gè)知識(shí)匹配成功；或者

有多個(gè)（組）已知事實(shí)都可與知識(shí)庫(kù)中某一知識(shí)匹

配成功；或者有多個(gè)（組）已知事實(shí)可與知識(shí)庫(kù)中

的多個(gè)知識(shí)匹配成功

出現(xiàn)沖突的情況

正向推理：逆向推理：

如果有多條產(chǎn)生式規(guī)如果有多條產(chǎn)生

則的前件都和已知的式的后件都和同

事實(shí)匹配成功；或者一假設(shè)匹配成功,

有多組不同的已知事

或者有多條產(chǎn)生

實(shí)都與同一條產(chǎn)生式

式后件可與多個(gè)

規(guī)則的前件匹配成功;

或者兩種情況同時(shí)出假設(shè)匹配成功

現(xiàn)

1.按就近原則

排序一,該策略把最近被使用過(guò)的規(guī)則賦予較高的優(yōu)先級(jí)

2.按已知事實(shí)

的新鮮性排序后生成的事實(shí)比先生成的事實(shí)具有較大的優(yōu)先性

3?按匹配度

排序,根據(jù)匹配程度來(lái)決定哪一個(gè)產(chǎn)生式規(guī)則優(yōu)先被應(yīng)用

?按領(lǐng)域問(wèn)、

題特點(diǎn)排序’按照求解問(wèn)題領(lǐng)域的特點(diǎn)將知識(shí)排成固定的次序

J

5^3^根據(jù)當(dāng)前數(shù)據(jù)庫(kù)的已知事實(shí)與上下文的匹配情況確定

6.按條件

個(gè)數(shù)排序?qū)l件少的規(guī)則賦予較高的優(yōu)先級(jí)，優(yōu)先被啟用

7.按規(guī)則的

次序排序,以知識(shí)庫(kù)中預(yù)先存入規(guī)則的排列順序作為知識(shí)排序的依據(jù)

模式匹配

指對(duì)兩個(gè)知識(shí)模式的比較與耦合，即

檢查這兩個(gè)知識(shí)是否完全一致或近似一致

確定性匹配：兩個(gè)知識(shí)模式完全一致

,或者經(jīng)過(guò)變量代換后變得完全一致

不確定性匹配：兩個(gè)知識(shí)模式不完全

一致，但從整體上看，它們的相似程

度落在規(guī)定的范圍內(nèi)

定義1

代換是形如

{/1/X1，，2/尤2，…/〃//}

的有限集合。其中，,1冉，…心是項(xiàng),

是變宛盧2,…袤示用替換/巧，

不允許i與七相同，也不允許變

元循環(huán)出現(xiàn)在殍r個(gè)中

%

定義2

反夕=…，'〃/%}

義={〃1/%，〃2/乃，…〃〃/"}

是兩個(gè)代換，則此兩個(gè)代換的復(fù)合也是

一個(gè)代換，它是從

U

〃//片,12HX］，…3入風(fēng)必/M,〃2/%，…n/yn

中刪去如下兩種元素：

先刪除：％/y當(dāng)y日占戶2,

后刪除：，//xi當(dāng).丸=七

設(shè)有公式集產(chǎn)=｛片，…，凡｝,若存在

一個(gè)代換2

使得L°廠「廠°

FYA,—F2A,=???—FnA>

則稱X為公式集F的一個(gè)合一，且稱

Fi，F(xiàn)z，…，F(xiàn)〃是可合一的。

一個(gè)公式集的合一一般來(lái)說(shuō)是不唯一的。

設(shè)b是公式集F的一個(gè)合一，如果

對(duì)任一合一0都存在一個(gè)代換；I，

使得

e=bo2

則稱CT是一個(gè)最一般的合一

般合一是唯一的。

令k=0?Fk=尸,b&=s

最T若■.只含有一個(gè)表達(dá)式，則算法停止

般T找出招的差異集2

合——尸

丁若，中存在元素與和憶其中4是變?cè)?

算是項(xiàng)R且不在〃中出現(xiàn)，則做（5）,

法否則不可合一

bk+\=bko{tk/Xk}

石Z+i=Fk{丁左/Xk}

k=k+1

3.2自然演繹推理

自然演繹推理

從一組已知的事實(shí)出發(fā)，直接運(yùn)用命題邏

輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過(guò)程

推理規(guī)則/

避免產(chǎn)生兩類錯(cuò)誤:

肯定后件(Q)否定前件(P)

的錯(cuò)誤：的錯(cuò)誤：

希望通過(guò)肯希望通過(guò)

定后件Q推出否定前件P

前件P為真推出后件Q

為假

例

設(shè)已知事實(shí)

(1)只要不怕困難的人，就會(huì)獲

得勝利。

(2)運(yùn)動(dòng)員都是不怕困難的人。

(3)王力是運(yùn)動(dòng)員。

求證：王力會(huì)獲得勝利。

自然演繹推理的

優(yōu)點(diǎn)優(yōu)缺點(diǎn)

缺點(diǎn)

?定理證明過(guò)程自然,

容易理解

容易產(chǎn)生組合爆

?擁有豐富的推理規(guī)

則，推理過(guò)程靈活，炸，推理過(guò)程中

得到的中間結(jié)論

?便于在它的推理規(guī)

一般呈指數(shù)形式

則中嵌入領(lǐng)域啟發(fā)式

遞增

知識(shí)/

人

3.3歸結(jié)演繹推理

原子謂詞公式及其否定統(tǒng)稱為文字

任何文字的析取式稱為子句

空子句不包含任何文字的子句稱為空子句

_______________________________________________>

空子句中不包含任何文字，不能被任何解

件滿足，所以空子句是永假的，不可滿足的

謂詞公式化為子句集道

步驟

t消去存在量詞

利用等價(jià)

謂詞關(guān)系

消去謂詞存在量詞不出現(xiàn)在全稱

量詞的轄域內(nèi)，此時(shí)只

公式中的

“‘，，要用一個(gè)新的個(gè)體常量

利用等價(jià)關(guān)替換該存在量詞的約束

2，，

系把S”變?cè)上ゴ嬖诹吭~

移到緊靠謂存在量詞位于一個(gè)或多

詞個(gè)全稱量詞的轄域內(nèi)

謂詞公式化為子句集

步驟

把全

63稱量詞

消去移到公

合取式左邊

對(duì)

詞

變?cè)ト玫葍r(jià)關(guān)系

更名稱量詞把公式化大、

Skolem標(biāo)準(zhǔn)形

Skolem標(biāo)準(zhǔn)形的一般形式

(VXJ(VX2)???(VZ)M,其中M為合取式

定理：設(shè)有謂詞公式F,其標(biāo)準(zhǔn)形的子句集為S,

則F不可滿足的充要條件是S不可滿足。

H域

設(shè)S為子句集，則按下述方法構(gòu)造的域稱

為海明倫域，簡(jiǎn)稱為H域

令是S中所有個(gè)體常量的集合，若S

中不包含個(gè)體常量，則令勺={々},其

中a為任意指定的一個(gè)個(gè)體常量

方令心=旦U{S中所有九元函掰…/〃}

勺。=1,2,…是H,中的元素

^■8?I下列集合稱為子句集s的原子集：

A=｛所有形如尸。"2,…"〃）的元素｝

其中，尸（KG…乩）是出現(xiàn)在S中的任一

謂詞符號(hào)，而…Jn是S在H域上的

任意元素。一

子句集S在H域上的解釋就是對(duì)S中出現(xiàn)的常量、

函數(shù)及謂詞取值，一次取值就是一個(gè)解釋。

H域上的解釋

子句集S在H域上的一個(gè)解釋I滿足下列條件:

在解釋下，常量映射到自身

2S中的任一個(gè)n元函數(shù)是H的映射

S中的任一個(gè)n元謂詞是｛T,岫映射。

謂詞的真值可以指派為T,也可以指派為F

可證明，對(duì)給定域D上的任何一個(gè)解稔，總能在H城上

構(gòu)造一個(gè)斛將與它對(duì)應(yīng)，如果D域上的斛希能滿足子句集S,

則在H域上相應(yīng)斛將也能滿足S。

子句集S不可滿足的充要條件是S對(duì)H域上的一切

解釋都為假。

O子句集不可滿足的充要條件是在一個(gè)有限的

Q不可滿足的基子句集S'

魯賓遜

歸結(jié)原

理基本

檢查子句集S中是否包含空子句，若包含，

則s不可滿足；若不包含，就在子句集中選擇

合適的子句進(jìn)行歸結(jié)，一旦通過(guò)歸結(jié)能推出空

子句集，就說(shuō)明子句集S是不可滿足的。

互補(bǔ)文字

若P是原子謂詞公式，則稱尸與「尸為

互補(bǔ)文字

1、命題邏輯中的歸結(jié)原理

歸結(jié)

設(shè)G與。2是子句集中的任意兩個(gè)子句，

如果G中的文字上與中的文字乙2互補(bǔ)，

那么從和G中分別消去和乙，不移

二個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新

子句，/1稱這一過(guò)程為歸結(jié)，稱為G2

和c的峭吉式，稱和G為。2的第本

子句

定理歸結(jié)式。是親本子句怎蹴輯結(jié)論。

推論1

設(shè)隼得子句集s中的兩個(gè)子句，是它們的歸結(jié)式,

若用代替2和彳影噴仔句集，則由S1的不可滯

足性可推出原子句集S的不可滿足性,即

S1的不可滿足性ns的不可'滿足性

推論22設(shè)隼是子句集s中的兩個(gè)子句，是它們的歸

結(jié)式，若把加AS中，得到新子句集，則S與

在不用茜足的意義上是等價(jià)的，即

§2的不可滿足性=S的不可滿足性

y

1、謂詞邏輯中的歸結(jié)

定義

4殳G與G是兩個(gè)沒(méi)有相同變?cè)淖泳?，心和?/p>

分別是和G中的文字，若b是乙和「乙2的最一般

合一，則稱

Q2=(G0-{/)U(Go-{3})

為G和02的二元式，七和G稱為歸結(jié)式上的文字

定義

子句G和。2的歸結(jié)式是下列二元?dú)w結(jié)式之一：

1.G與c2的二元?dú)w結(jié)式

2.G與G的因子G%的二元?dú)w結(jié)式

3.G的因子Gb1與G的二元?dú)w結(jié)式

4.Q的因子G。1與G的因子c2b2的二元?dú)w

結(jié)式

舊結(jié)策略

刪除策略限制策略

通過(guò)對(duì)參加歸結(jié)的子

通過(guò)刪除某

句進(jìn)行種種限制，

些無(wú)用的子盡可能地減小歸結(jié)

句來(lái)縮小歸巳的盲目性，使其盡

結(jié)的范圍4:L:快地歸結(jié)出空子句。

宣言丸則除法

把純文字所在的從子句集中

子句從子句集中刪除重言式

刪去

限制策略

設(shè)F為已知前提的公式集，G為目標(biāo)公式（結(jié)

論），用歸結(jié)反演證明Q為真的步驟是：

3

1L2

反復(fù)歸結(jié)子

把一＞。

否定G,句集s中的

并入到把公式集

得到「G子句，若出

公式集（F,P-

為子句集目現(xiàn)了空子句,

F中，則停止歸結(jié),

得至U此時(shí)就證明

任，f了G永真

例

某公司招聘工作人員，A、B、C三人

應(yīng)試，經(jīng)面試后公司表示如下想法：

(1)三人中至少錄取一人

(2)如果錄取A而不錄取B,則一定錄取C

(3)如果錄取B,則一定錄取C

求證：公司一定錄取C

知以下的事實(shí)：①M(fèi)arcus是人。②

Marcus是羅馬人。③Caser是一位統(tǒng)治者。

④所有羅馬人或忠于Caser或仇恨他。⑤

每個(gè)人都忠于某個(gè)人。⑥人們只想暗殺他

們不忠于的統(tǒng)治者。⑦M(jìn)arcus試圖暗殺

Casero

求證：Marcus仇恨Caser。

例

設(shè)A、B、C三人中有人從不說(shuō)真話，

也有人從不說(shuō)假話，某人向這三個(gè)人分別

提出同一個(gè)問(wèn)題：誰(shuí)是說(shuō)謊者？A答：“B

和C都是說(shuō)謊者"；B答“A和C都是說(shuō)謊

者”；C答：“A和B中至少有一個(gè)是說(shuō)謊

者?！鼻笳l(shuí)是老實(shí)人，誰(shuí)是說(shuō)謊者？

把已知

前提

用把待求解

把此析取

謂對(duì)S

若得到

詞公的問(wèn)題用

式化為子

式謂詞公式應(yīng)

表用歸結(jié)式

示句集，并

出表示，把歸

來(lái)結(jié)ANSW

且把該子

并，它否定并原

句集并入理

且化ER,貝IJ

與謂詞

為應(yīng)到子句集進(jìn)行

相答案在

ANSWE

的句S中，得歸結(jié)

ANS

子R構(gòu)成析

集到子句集

取式

WER中

S

S，

5

4

3

2

1

用歸結(jié)原理求解問(wèn)題

3.4與/或形演繹推理

血3

與/或形正向演繹推理

從已知事實(shí)出發(fā)，正向地使用蘊(yùn)

含式（F規(guī)則）進(jìn)行演繹推理，直至得到

某個(gè)目標(biāo)公式的一個(gè)終止條件為止。

事實(shí)表達(dá)式的與/或變換

45

消

去公

把

重

新

「

的

中引入消去全稱量

式

命

名

”

'“

元

變Skolem詞，且使各

一

到

緊

移

”函數(shù)消主要合取式

;田

詞

」

罪去存在中的變?cè)?/p>

1H詈

、

出"量詞同名

上

?在與/或樹(shù)中，每個(gè)節(jié)點(diǎn)表示相應(yīng)事實(shí)表達(dá)式的一個(gè)子

表達(dá)式，葉節(jié)點(diǎn)為謂詞公式中的文生

!?對(duì)于用析取符號(hào)V”連接而成的表達(dá)式，用一個(gè)連

:接將把它們連接起來(lái)。

?對(duì)于合取符號(hào)“八”連接而成的表達(dá)式，無(wú)須用連

1接符連接

《）F規(guī)則的表示形式

要求F規(guī)則具有如下形式：L-^W

其中L為單文字，W為與/或形

把領(lǐng)域知識(shí)的表示形式變成規(guī)定形式的步驟

消去公把J”引入

去

復(fù)

消

式中的移到緊Skolem恢

稱

蘊(yùn)

全

“t”靠謂詞函數(shù)消為

量

詞

式

的位置去存在含

推理過(guò)程

%