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

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

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

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

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

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

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

,ri

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

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

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

是有理數(shù)是不對(duì)的；2是偶素?cái)?shù)；2或4是素?cái)?shù)；如果2是素?cái)?shù)，則3也是素?cái)?shù)；2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)。

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

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

例如：p： 哈爾濱是一個(gè)大城市。

┐p：哈爾濱是一個(gè)不大城市。

┐p：哈爾濱不是一個(gè)大城市。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為真當(dāng)且僅當(dāng)p與q同時(shí)為真。使用合取聯(lián)結(jié)詞時(shí)要注意的兩點(diǎn)：描述合取式的靈活性與多樣性。

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

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

pqp∧q1

11100010000第九頁，共五十二頁，2022年，8月28日9例將下列命題符號(hào)化吳穎既用功又聰明。吳穎不僅用功而且聰明。吳穎雖然聰明，但不用功。張輝與王麗都是三好學(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為假當(dāng)且僅當(dāng)p與q同時(shí)為假。

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

說明pqp∨q1

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

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

相容或，符號(hào)化為

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

u：張曉靜挑選203房間。

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

s：張曉靜是安徽人。

排斥或，符號(hào)化為：r∨s。

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

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

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

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

只要p，就q

因?yàn)閜，所以qp僅當(dāng)q只有q才p除非q才p除非q，否則非p

pqp→q1

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

如果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例將下列命題符號(hào)化，并指出其真值

以下命題中出現(xiàn)的a是一個(gè)給定的正整數(shù)：(5)只要a能被4整除，則a一定能被2整除。(6)a能被4整除，僅當(dāng)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)五個(gè)命題均敘述的是a能被2整除是a能被4整除的必要條件，因而都符號(hào)化為r→s。其真值為1在(10)中，將a能被4整除看成了a能被2整除的必要條件，因而應(yīng)符號(hào)化為s→r。a值不定時(shí)，真值未知。第十六頁，共五十二頁，2022年，8月28日16關(guān)于蘊(yùn)含的進(jìn)一步說明作為一種規(guī)定，當(dāng)p為假時(shí)，無論q是真是假，p→q均為真。也就是說，只有p為真q為假這一種情況使得復(fù)合命題p→q為假。稱為實(shí)質(zhì)蘊(yùn)含。例：如果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)的錯(cuò)誤，沒有分清充分條件與必要條件。第十七頁，共五十二頁，2022年，8月28日17定義1.5 等價(jià)(two-way-implication)設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq，稱作等價(jià)聯(lián)結(jié)詞，并規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假。說明“當(dāng)且僅當(dāng)”（ifandonlyif）pq的邏輯關(guān)系為p與q互為充分必要條件。

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

11100010001第十八頁，共五十二頁，2022年，8月28日18關(guān)于基本聯(lián)結(jié)詞的說明{┐,∧,∨,→,}，稱為一個(gè)聯(lián)結(jié)詞集。由聯(lián)結(jié)詞集{┐,∧,∨,→,}中的一個(gè)聯(lián)結(jié)詞聯(lián)結(jié)一個(gè)或兩個(gè)原子命題組成的復(fù)合命題是最簡(jiǎn)單的復(fù)合命題，可以稱它們?yōu)榛镜膹?fù)合命題?；緩?fù)合命題的真值見下表：第十九頁，共五十二頁，2022年，8月28日19關(guān)于基本聯(lián)結(jié)詞的說明多次使用聯(lián)結(jié)詞集中的聯(lián)結(jié)詞，可以組成更為復(fù)雜的復(fù)合命題。求復(fù)雜復(fù)合命題的真值時(shí)，除依據(jù)上表外，還要規(guī)定聯(lián)結(jié)詞的優(yōu)先順序，將括號(hào)也算在內(nèi)。本書規(guī)定的聯(lián)結(jié)詞優(yōu)先順序?yàn)椋?)，┐，∧，∨，→，，對(duì)于同一優(yōu)先級(jí)的聯(lián)結(jié)詞，先出現(xiàn)者先運(yù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)等公式單獨(dú)出現(xiàn)時(shí)，外層括號(hào)可以省去，寫成┐A、A∧B等。公式中不影響運(yùn)算次序的括號(hào)可以省去，

如公式(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)個(gè)命題變項(xiàng)的公式共有2n個(gè)不同的賦值。

第二十三頁，共五十二頁，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例題下列各公式均含兩個(gè)命題變項(xiàng)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中共含有命題變項(xiàng)p1,p2,…,pn，，而A或B不全含有這些命題變項(xiàng)，比如A中不含pi,pi+1,…,pn,稱這些命題變項(xiàng)為A的啞元，A的取值與啞元的變化無關(guān)，因而在討論A與B是否有相等的真值表時(shí)，將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自動(dòng)推理第二十九頁，共五十二頁，2022年，8月28日29Resolution歸結(jié)方法是一種機(jī)械化的,可在計(jì)算機(jī)上加以實(shí)現(xiàn)的推理方法可認(rèn)為是一種反向推理形式提供了一種自動(dòng)定理證明的方法第三十頁，共五十二頁，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ā),僅對(duì)S的子句間使用歸結(jié)推理規(guī)則如果得出空子句,則結(jié)束;否則轉(zhuǎn)下一步將所得歸結(jié)式仍放入S中對(duì)新的子句集使用歸結(jié)推理規(guī)則轉(zhuǎn)(3)空子句不含有文字,它不能被任何解釋滿足,所以空子句是永假的,不可滿足的歸結(jié)過程出現(xiàn)空子句,說明出現(xiàn)互補(bǔ)子句對(duì),說明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òng)推理、自動(dòng)推導(dǎo)證明用的。（“數(shù)學(xué)定理機(jī)器證明”）本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題。

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

q析取式：

p或q，記做p∨

q蘊(yùn)含式：如果p則q，記做p→

q等價(jià)式：p當(dāng)且僅當(dāng)q，記做p<=>

q

。。。。。。第三十六頁，共五十二頁，2022年，8月28日36命題邏輯基礎(chǔ)定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個(gè)成真賦值，則稱A為可滿足的；析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式。合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式。第三十七頁，共五十二頁，2022年，8月28日37命題邏輯基礎(chǔ)基本等值式24個(gè)(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

蘊(yùn)含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

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

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

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

∧(r∨t)→

q。

第四十頁，共五十二頁，2022年，8月28日40命題邏輯的歸結(jié)法基本單元：簡(jiǎn)單命題（陳述句）例：命題：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é)過程

將命題寫成合取范式求出子句集對(duì)子句集使用歸結(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）分別將公式前項(xiàng)化為合取范式：

P→Q＝～P∨Q

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

兩項(xiàng)合并后化為合取范式： （～P∨Q）∧～Q∧P

（3）則子句集為：

{～P∨Q，～Q，P}第四十四頁，共五十二頁，2022年，8月28日44命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}（4）對(duì)子句集中的子句進(jìn)行歸結(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命題邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用

邏輯難題

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

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