謂詞邏輯與歸結(jié)原理

謂詞邏輯與歸結(jié)原理第一頁，共五十二頁，2022年，8月28日1歸結(jié)推理命題邏輯謂詞邏輯Skolem標準形、子句集基本概念謂詞邏輯歸結(jié)原理合一和置換、控制策略數(shù)理邏輯命題邏輯歸結(jié)Herbrand定理第二頁，共五十二頁，2022年，8月28日2命題與聯(lián)結(jié)詞稱能判斷真假而不是可真可假的陳述句為命題

（proposition）。作為命題的陳述句所表達得的判斷結(jié)果稱為命題的真值。真值只取兩個：真與假。真值為真的命題稱為真命題。真值為假的命題稱為假命題。感嘆句、疑問句、祈使句都不能稱為命題。判斷結(jié)果不唯一確定的陳述句不是命題。陳述句中的悖論不是命題。說明第三頁，共五十二頁，2022年，8月28日34是素數(shù)。

x大于y。充分大的偶數(shù)等于兩個素數(shù)之和。今天是星期二。

請不要吸煙！這朵花真美麗??！我正在說假話。例1.1

判斷下列句子是否為命題。

是，假命題是，真命題不是，無確定的真值是，真值客觀存在是，真值根據(jù)具體情況而定。不是，疑問句不是，祈使句不是，感嘆句不是，悖論第四頁，共五十二頁，2022年，8月28日4命題和真值的符號化用小寫英文字母p,q,r…,pi,qi

,ri

…表示命題用“1”表示真，用“0”表示假

r：充分大的偶數(shù)等于兩個素數(shù)之和。s：今天是星期二。p：4是素數(shù)。q：不能被分解成更簡單的陳述句，稱這樣的命題為簡單命題或原子命題。由簡單陳述句通過聯(lián)結(jié)詞而成的陳述句，稱這樣的命題為復(fù)合命題。

第五頁，共五十二頁，2022年，8月28日5例將下面這段陳述中所出現(xiàn)的原子命題符號化，并指出它們的真值，然后再寫出這段陳述。

是有理數(shù)是不對的；2是偶素數(shù)；2或4是素數(shù)；如果2是素數(shù)，則3也是素數(shù)；2是素數(shù)當且僅當3也是素數(shù)。

p：是有理數(shù)q：2是素數(shù)；r：2是偶數(shù)s：3是素數(shù)；t：4是素數(shù)01110非p；q并且(與)r；q或t；如果q，則s；q當且僅當s。第六頁，共五十二頁，2022年，8月28日6半形式化形式數(shù)理邏輯研究方法的主要特征是將論述或推理中的各種要素都符號化。即構(gòu)造各種符號語言來代替自然語言。形式化語言：完全由符號所構(gòu)成的語言。將聯(lián)結(jié)詞（connective）符號化，消除其二義性，對其進行嚴格定義。例如： 他是100米或400米賽跑的冠軍。

魚香肉絲或鍋包肉，加一碗湯。第七頁，共五十二頁，2022年，8月28日7定義1.1 否定(negation)設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式,記作┐p，符號┐稱作否定聯(lián)結(jié)詞，并規(guī)定┐p為真當且僅當p為假。

例如：p： 哈爾濱是一個大城市。

┐p：哈爾濱是一個不大城市。

┐p：哈爾濱不是一個大城市。p┐p1001第八頁，共五十二頁，2022年，8月28日8定義1.2 合取(conjunction)設(shè)p,q為二命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞，并規(guī)定p∧q為真當且僅當p與q同時為真。使用合取聯(lián)結(jié)詞時要注意的兩點：描述合取式的靈活性與多樣性。

自然語言中的“既……又……”、“不但……而且……”、“雖然……但是……”、“一面……一面……”等聯(lián)結(jié)詞都可以符號化為∧。分清簡單命題與復(fù)合命題。

不要見到“與”或“和”就使用聯(lián)結(jié)詞∧。

pqp∧q1

11100010000第九頁，共五十二頁，2022年，8月28日9例將下列命題符號化吳穎既用功又聰明。吳穎不僅用功而且聰明。吳穎雖然聰明，但不用功。張輝與王麗都是三好學(xué)生。張輝與王麗是同學(xué)。

p:吳穎用功。q:吳穎聰明。r:張輝是三好學(xué)生。s:王麗是三好學(xué)生。t:張輝與王麗是同學(xué)。

(1)p∧q(2)p∧q(3)q∧┐p(4)r∧s(5)t第十頁，共五十二頁，2022年，8月28日10合取舉例p：我們?nèi)タ措娪啊?/p>

q：房間里有十張桌子。

p∧q：我們?nèi)タ措娪安⑶曳块g里有十張桌子。在數(shù)理邏輯中，關(guān)心的只是復(fù)合命題與構(gòu)成復(fù)合命題的各原子命題之間的真值關(guān)系，即抽象的邏輯關(guān)系，并不關(guān)心各語句的具體內(nèi)容。說明第十一頁，共五十二頁，2022年，8月28日11定義1.3 析取(disjunction)設(shè)p，q為二命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞，并規(guī)定p∨q為假當且僅當p與q同時為假。

自然語言中的“或”具有二義性，用它聯(lián)結(jié)的命題有時具有相容性，有時具有排斥性，對應(yīng)的聯(lián)結(jié)詞分別稱為相容或和排斥或(排異或)。

說明pqp∨q1

11101011000第十二頁，共五十二頁，2022年，8月28日12例將下列命題符號化

張曉靜愛唱歌或愛聽音樂。張曉靜只能挑選202或203房間。張曉靜是江西人或安徽人。他昨天做了二十或三十道習(xí)題。設(shè)p：張曉靜愛唱歌，q：張曉靜愛聽音樂。

相容或，符號化為

p∨q設(shè)t：張曉靜挑選202房間，

u：張曉靜挑選203房間。

排斥或，符號化為：(t∧┐u)∨(┐t∧u)設(shè)r：張曉靜是江西人，

s：張曉靜是安徽人。

排斥或，符號化為：r∨s。

(排斥或聯(lián)結(jié)的兩個命題事實上不可能同時為真)

或符號化為：(r∧┐s)∨(┐r∧s)原子命題，因為“或”只表示了習(xí)題的近似數(shù)目。第十三頁，共五十二頁，2022年，8月28日13定義1.4 蘊涵(implication)設(shè)p，q為二命題，復(fù)合命題“如果p，則q”稱作p與q的蘊涵式，記作p→q，并稱p是蘊涵式的前件，q為蘊涵式的后件，→稱作蘊涵聯(lián)結(jié)詞,并規(guī)定p→q為假當且僅當p為真q為假。

說明p→q的邏輯關(guān)系表示q是p的必要條件。

q是p的必要條件有許多不同的敘述方式

只要p，就q

因為p，所以qp僅當q只有q才p除非q才p除非q，否則非p

pqp→q1

11100011001第十四頁，共五十二頁，2022年，8月28日14例將下列命題符號化，并指出其真值

如果3+3＝6，則雪是白的。如果3+3≠6，則雪是白的。如果3+3＝6，則雪不是白的。如果3+3≠6，則雪不是白的。解：令p：3+3＝6，p的真值為1。

q：雪是白色的，q的真值也為1。

p→q┐p→q p→┐q ┐p→┐q 1101第十五頁，共五十二頁，2022年，8月28日15例將下列命題符號化，并指出其真值

以下命題中出現(xiàn)的a是一個給定的正整數(shù)：(5)只要a能被4整除，則a一定能被2整除。(6)a能被4整除，僅當a能被2整除。(7)除非a能被2整除，a才能被4整除。(8)除非a能被2整除，否則a不能被4整除。(9)

只有a能被2整除，a才能被4整除。(10)只有a能被4整除，a才能被2整除。解：令r：a能被4整除

s：a能被2整除(5)至(9)五個命題均敘述的是a能被2整除是a能被4整除的必要條件，因而都符號化為r→s。其真值為1在(10)中，將a能被4整除看成了a能被2整除的必要條件，因而應(yīng)符號化為s→r。a值不定時，真值未知。第十六頁，共五十二頁，2022年，8月28日16關(guān)于蘊含的進一步說明作為一種規(guī)定，當p為假時，無論q是真是假，p→q均為真。也就是說，只有p為真q為假這一種情況使得復(fù)合命題p→q為假。稱為實質(zhì)蘊含。例：如果x>5，則x>2。

(1)x=6 如果6>5，則6>2。

(2)

x=3

如果3>5，則3>2。

(3)x=1 如果1>5，則1>2。

例：如果我有車，那么我去接你常出現(xiàn)的錯誤，沒有分清充分條件與必要條件。第十七頁，共五十二頁，2022年，8月28日17定義1.5 等價(two-way-implication)設(shè)p，q為二命題，復(fù)合命題“p當且僅當q”稱作p與q的等價式，記作pq，稱作等價聯(lián)結(jié)詞，并規(guī)定pq為真當且僅當p與q同時為真或同時為假。說明“當且僅當”（ifandonlyif）pq的邏輯關(guān)系為p與q互為充分必要條件。

(p→q)∧(q→p)與pq的邏輯關(guān)系完全一致。pqpq1

11100010001第十八頁，共五十二頁，2022年，8月28日18關(guān)于基本聯(lián)結(jié)詞的說明{┐,∧,∨,→,}，稱為一個聯(lián)結(jié)詞集。由聯(lián)結(jié)詞集{┐,∧,∨,→,}中的一個聯(lián)結(jié)詞聯(lián)結(jié)一個或兩個原子命題組成的復(fù)合命題是最簡單的復(fù)合命題，可以稱它們?yōu)榛镜膹?fù)合命題?；緩?fù)合命題的真值見下表：第十九頁，共五十二頁，2022年，8月28日19關(guān)于基本聯(lián)結(jié)詞的說明多次使用聯(lián)結(jié)詞集中的聯(lián)結(jié)詞，可以組成更為復(fù)雜的復(fù)合命題。求復(fù)雜復(fù)合命題的真值時，除依據(jù)上表外，還要規(guī)定聯(lián)結(jié)詞的優(yōu)先順序，將括號也算在內(nèi)。本書規(guī)定的聯(lián)結(jié)詞優(yōu)先順序為：()，┐，∧，∨，→，，對于同一優(yōu)先級的聯(lián)結(jié)詞，先出現(xiàn)者先運算。第二十頁，共五十二頁，2022年，8月28日20例令 p：北京比天津人口多。

q：2+2＝4.

r：烏鴉是白色的。求下列復(fù)合命題的真值：

(1)((┐p∧q)∨(p∧┐q))→r

(2)(q∨r)→(p→┐r)

(3)(┐p∨r)(p∧┐r)解：p、q、r的真值分別為

1、1、0

(1)1

(2)1

(3)0我們關(guān)心的是復(fù)合命題中命題之間的真值關(guān)系，而不關(guān)心命題的內(nèi)容。說明第二十一頁，共五十二頁，2022年，8月28日21關(guān)于合式公式(┐A)、(A∧B)等公式單獨出現(xiàn)時，外層括號可以省去，寫成┐A、A∧B等。公式中不影響運算次序的括號可以省去，

如公式(p∨q)∨(┐r)可以寫成p∨q∨┐r。合式公式的例子：

(p→q)∧(qr)

(p∧q)∧┐r

p∧(q∧┐r)不是合式公式的例子

pq→r

(p→(r→q)第二十二頁，共五十二頁，2022年，8月28日22賦值舉例在公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，

000(p1＝0，p2＝0，p3＝0)，

110(p1＝1，p2＝1，p3＝0)都是成真賦值，

001(p1＝0，p2＝0，p3＝1)，

011(p1＝0，p2＝1，p3＝1)都是成假賦值。在(p∧┐q)→r中，

011(p1＝0，p2＝1，p3＝1)為成真賦值，

100(p1＝1，p2＝0，p3＝0)為成假賦值。重要結(jié)論：

含n(n≥1)個命題變項的公式共有2n個不同的賦值。

第二十三頁，共五十二頁，2022年，8月28日23真值表求下列公式的真值表，并求成真賦值和成假賦值。(1)(┐p∧q)→┐r(2)(p∧┐p)(q∧┐q)(3)┐(p→q)∧q∧r

第二十四頁，共五十二頁，2022年，8月28日24定義1.10重言式、永真式、可滿足式設(shè)A為任一命題公式(1)若A在它的各種賦值下取值均為真,則稱A是重言式(tautology)或永真式。(2)若A在它的各種賦值下取值均為假,則稱A是矛盾式(contradiction)或永假式。(3)若A不是矛盾式,則稱A是可滿足式（satisfactableformula）。第二十五頁，共五十二頁，2022年，8月28日25例題下列各公式均含兩個命題變項p與q，它們中哪些具有相同的真值表?

(1)p→q (4)(p→q)∧(q→p)

(2)pq (5)┐q∨p

(3)┐(p∧┐q)第二十六頁，共五十二頁，2022年，8月28日26啞元設(shè)公式A,B中共含有命題變項p1,p2,…,pn，，而A或B不全含有這些命題變項，比如A中不含pi,pi+1,…,pn,稱這些命題變項為A的啞元，A的取值與啞元的變化無關(guān)，因而在討論A與B是否有相等的真值表時，將A,B都看成p1,p2,…,pn的命題公式。第二十七頁，共五十二頁，2022年，8月28日27例題

例1.10

下列公式中,哪些具有相同的真值表?

(1)p→q

(2)┐q∨r

(3)(┐p∨q)∧((p∧r)→p)

(4)(q→r)∧(p→p)第二十八頁，共五十二頁，2022年，8月28日28自動推理第二十九頁，共五十二頁，2022年，8月28日29Resolution歸結(jié)方法是一種機械化的,可在計算機上加以實現(xiàn)的推理方法可認為是一種反向推理形式提供了一種自動定理證明的方法第三十頁，共五十二頁，2022年，8月28日30ResolutionRefutations（1）定理證明的任務(wù):由前提A1A2...An推出結(jié)論B即證明:A1A2...AnB永真轉(zhuǎn)化為證明:A1A2...An~B為永假式歸結(jié)推理就是:從A1A2...An~B出發(fā),使用歸結(jié)推理規(guī)則來找出矛盾,最后證明定理A1A2...AnB的成立第三十一頁，共五十二頁，2022年，8月28日31ResolutionRefutations（2）定理證明的任務(wù):由前提A1A2...An推出結(jié)論B即證明:A1A2...AnB永真轉(zhuǎn)化為證明:A1A2...An~B為永假式歸結(jié)推理就是:從A1A2...An~B出發(fā),使用歸結(jié)推理規(guī)則來找出矛盾,最后證明定理A1A2...AnB的成立第三十二頁，共五十二頁，2022年，8月28日32ResolutionRefutations（3）一般過程:建立子句集S從子句集S出發(fā),僅對S的子句間使用歸結(jié)推理規(guī)則如果得出空子句,則結(jié)束;否則轉(zhuǎn)下一步將所得歸結(jié)式仍放入S中對新的子句集使用歸結(jié)推理規(guī)則轉(zhuǎn)(3)空子句不含有文字,它不能被任何解釋滿足,所以空子句是永假的,不可滿足的歸結(jié)過程出現(xiàn)空子句,說明出現(xiàn)互補子句對,說明S中有矛盾,因此S是不可滿足的.第三十三頁，共五十二頁，2022年，8月28日33SoundnessandCompleteness歸結(jié)原理是合理的歸結(jié)原理是完備的第三十四頁，共五十二頁，2022年，8月28日34歸結(jié)原理概述歸結(jié)原理由由1965年提出。與演繹法(deductiveinference)完全不同，新的邏輯演算(inductiveinference)算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。而歸結(jié)方法是自動推理、自動推導(dǎo)證明用的。（“數(shù)學(xué)定理機器證明”）本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題。

第三十五頁，共五十二頁，2022年，8月28日35命題邏輯的歸結(jié)法命題邏輯基礎(chǔ)：定義：合取式：p與q，記做pΛ

q析取式：

p或q，記做p∨

q蘊含式：如果p則q，記做p→

q等價式：p當且僅當q，記做p<=>

q

。。。。。。第三十六頁，共五十二頁，2022年，8月28日36命題邏輯基礎(chǔ)定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。第三十七頁，共五十二頁，2022年，8月28日37命題邏輯基礎(chǔ)基本等值式24個(1)交換率：p∨q<=>q

∨p

；

pΛq<=>qΛp

結(jié)合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

第三十八頁，共五十二頁，2022年，8月28日38命題邏輯基礎(chǔ)基本等值式（1）摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蘊含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

第三十九頁，共五十二頁，2022年，8月28日39命題表示公式例如：1．

“如果我進城我就去看你，除非我很累?！? 設(shè)：p，我進城，q，去看你，r，我很累。 則有命題公式：～r→(p→q)。2．“應(yīng)屆高中生，得過數(shù)學(xué)或物理競賽的一等獎， 保送上北京大學(xué)?！?設(shè)：p，應(yīng)屆高中生，q，保送上北京大學(xué)上學(xué)，

r，是得過數(shù)學(xué)一等獎。t，是得過物理一等獎。 則有命題公式公式：p

∧(r∨t)→

q。

第四十頁，共五十二頁，2022年，8月28日40命題邏輯的歸結(jié)法基本單元：簡單命題（陳述句）例：命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

第四十一頁，共五十二頁，2022年，8月28日41命題邏輯的歸結(jié)法建立子句集合取范式：命題、命題和的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

第四十二頁，共五十二頁，2022年，8月28日42命題邏輯的歸結(jié)法歸結(jié)過程

將命題寫成合取范式求出子句集對子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。第四十三頁，共五十二頁，2022年，8月28日43命題邏輯歸結(jié)例題（1）例題，證明公式：(P→Q)→(～Q→～P)證明：（1）根據(jù)歸結(jié)原理，將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：

(P→Q)∧～(～Q→～P)（2）分別將公式前項化為合取范式：

P→Q＝～P∨Q

結(jié)論求～后的后項化為合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P

兩項合并后化為合取范式： （～P∨Q）∧～Q∧P

（3）則子句集為：

{～P∨Q，～Q，P}第四十四頁，共五十二頁，2022年，8月28日44命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}（4）對子句集中的子句進行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結(jié)）5.

， （2，4歸結(jié)）

由上可得原公式成立。第四十五頁，共五十二頁，2022年，8月28日45證明：化成子句集

S={P,┐P∨┐Q∨R，┐S∨Q，┐T∨Q，T，┐R}歸結(jié)可用圖的演繹樹表示，由于根部出現(xiàn)空子句，因此命題R得證。

例：設(shè)已知前提集為

P……………

…(1)(P∧Q)→R………(2)(S∨T)→Q………(3)T…………(4)求證R。第四十六頁，共五十二頁，2022年，8月28日46命題邏輯在計算機科學(xué)中的應(yīng)用

邏輯難題

可以用邏輯推理解決的難題稱為邏輯難題。求解邏輯難題是實踐邏輯規(guī)則的一種好方法 涉及用于執(zhí)行邏輯推理的計算機程序通常也使用著名的邏輯難題來演示它們的能力第四十七頁，共五十二頁，2022年，8月28日471.7命題邏輯在計算機科學(xué)中的應(yīng)用

愛因斯坦的一道題。一個土耳其商人，想找一個十分聰明的助手協(xié)助他經(jīng)商，有兩個人前來應(yīng)聘。這個商人為了試一試哪一個聰明些，就把兩個人帶進一間漆黑的屋子里，他打開電燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的?，F(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€人每人摸一頂帽子戴在頭上，在我開燈后，請你們盡快地說出自己頭上戴的帽子是什么顏色的?！闭f完之后，商人將電燈關(guān)掉，然后三人都