謂詞邏輯與歸結原理1第1頁，課件共52頁，創(chuàng)作于2023年2月歸結推理命題邏輯謂詞邏輯Skolem標準形、子句集基本概念謂詞邏輯歸結原理合一和置換、控制策略數理邏輯命題邏輯歸結Herbrand定理2第2頁，課件共52頁，創(chuàng)作于2023年2月命題與聯結詞稱能判斷真假而不是可真可假的陳述句為命題

（proposition）。作為命題的陳述句所表達得的判斷結果稱為命題的真值。真值只取兩個：真與假。真值為真的命題稱為真命題。真值為假的命題稱為假命題。感嘆句、疑問句、祈使句都不能稱為命題。判斷結果不唯一確定的陳述句不是命題。陳述句中的悖論不是命題。說明3第3頁，課件共52頁，創(chuàng)作于2023年2月4是素數。

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

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

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

是，假命題是，真命題不是，無確定的真值是，真值客觀存在是，真值根據具體情況而定。不是，疑問句不是，祈使句不是，感嘆句不是，悖論4第4頁，課件共52頁，創(chuàng)作于2023年2月命題和真值的符號化用小寫英文字母p,q,r…,pi,qi

,ri

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

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

5第5頁，課件共52頁，創(chuàng)作于2023年2月例將下面這段陳述中所出現的原子命題符號化，并指出它們的真值，然后再寫出這段陳述。

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

p：是有理數q：2是素數；r：2是偶數s：3是素數；t：4是素數01110非p；q并且(與)r；q或t；如果q，則s；q當且僅當s。6第6頁，課件共52頁，創(chuàng)作于2023年2月半形式化形式數理邏輯研究方法的主要特征是將論述或推理中的各種要素都符號化。即構造各種符號語言來代替自然語言。形式化語言：完全由符號所構成的語言。將聯結詞（connective）符號化，消除其二義性，對其進行嚴格定義。例如： 他是100米或400米賽跑的冠軍。

魚香肉絲或鍋包肉，加一碗湯。7第7頁，課件共52頁，創(chuàng)作于2023年2月定義1.1 否定(negation)設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式,記作┐p，符號┐稱作否定聯結詞，并規(guī)定┐p為真當且僅當p為假。

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

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

┐p：哈爾濱不是一個大城市。p┐p10018第8頁，課件共52頁，創(chuàng)作于2023年2月定義1.2 合取(conjunction)設p,q為二命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯結詞，并規(guī)定p∧q為真當且僅當p與q同時為真。使用合取聯結詞時要注意的兩點：描述合取式的靈活性與多樣性。

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

不要見到“與”或“和”就使用聯結詞∧。

pqp∧q1

111000100009第9頁，課件共52頁，創(chuàng)作于2023年2月例將下列命題符號化吳穎既用功又聰明。吳穎不僅用功而且聰明。吳穎雖然聰明，但不用功。張輝與王麗都是三好學生。張輝與王麗是同學。

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

(1)p∧q(2)p∧q(3)q∧┐p(4)r∧s(5)t10第10頁，課件共52頁，創(chuàng)作于2023年2月合取舉例p：我們去看電影。

q：房間里有十張桌子。

p∧q：我們去看電影并且房間里有十張桌子。

在數理邏輯中，關心的只是復合命題與構成復合命題的各原子命題之間的真值關系，即抽象的邏輯關系，并不關心各語句的具體內容。說明11第11頁，課件共52頁，創(chuàng)作于2023年2月定義1.3 析取(disjunction)設p，q為二命題，復合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯結詞，并規(guī)定p∨q為假當且僅當p與q同時為假。

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

說明pqp∨q1

1110101100012第12頁，課件共52頁，創(chuàng)作于2023年2月例將下列命題符號化

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

相容或，符號化為

p∨q設t：張曉靜挑選202房間，

u：張曉靜挑選203房間。

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

s：張曉靜是安徽人。

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

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

或符號化為：(r∧┐s)∨(┐r∧s)原子命題，因為“或”只表示了習題的近似數目。13第13頁，課件共52頁，創(chuàng)作于2023年2月定義1.4 蘊涵(implication)設p，q為二命題，復合命題“如果p，則q”稱作p與q的蘊涵式，記作p→q，并稱p是蘊涵式的前件，q為蘊涵式的后件，→稱作蘊涵聯結詞,并規(guī)定p→q為假當且僅當p為真q為假。

說明p→q的邏輯關系表示q是p的必要條件。

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

只要p，就q

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

pqp→q1

1110001100114第14頁，課件共52頁，創(chuàng)作于2023年2月例將下列命題符號化，并指出其真值

如果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 110115第15頁，課件共52頁，創(chuàng)作于2023年2月例將下列命題符號化，并指出其真值

以下命題中出現的a是一個給定的正整數：(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整除的必要條件，因而應符號化為s→r。a值不定時，真值未知。16第16頁，課件共52頁，創(chuàng)作于2023年2月關于蘊含的進一步說明作為一種規(guī)定，當p為假時，無論q是真是假，p→q均為真。也就是說，只有p為真q為假這一種情況使得復合命題p→q為假。稱為實質蘊含。例：如果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。

例：如果我有車，那么我去接你常出現的錯誤，沒有分清充分條件與必要條件。17第17頁，課件共52頁，創(chuàng)作于2023年2月定義1.5 等價(two-way-implication)設p，q為二命題，復合命題“p當且僅當q”稱作p與q的等價式，記作pq，稱作等價聯結詞，并規(guī)定pq為真當且僅當p與q同時為真或同時為假。說明“當且僅當”（ifandonlyif）pq的邏輯關系為p與q互為充分必要條件。

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

1110001000118第18頁，課件共52頁，創(chuàng)作于2023年2月關于基本聯結詞的說明{┐,∧,∨,→,}，稱為一個聯結詞集。由聯結詞集{┐,∧,∨,→,}中的一個聯結詞聯結一個或兩個原子命題組成的復合命題是最簡單的復合命題，可以稱它們?yōu)榛镜膹秃厦}?；緩秃厦}的真值見下表：19第19頁，課件共52頁，創(chuàng)作于2023年2月關于基本聯結詞的說明多次使用聯結詞集中的聯結詞，可以組成更為復雜的復合命題。求復雜復合命題的真值時，除依據上表外，還要規(guī)定聯結詞的優(yōu)先順序，將括號也算在內。本書規(guī)定的聯結詞優(yōu)先順序為：()，┐，∧，∨，→，，對于同一優(yōu)先級的聯結詞，先出現者先運算。20第20頁，課件共52頁，創(chuàng)作于2023年2月例令 p：北京比天津人口多。

q：2+2＝4.

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

(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我們關心的是復合命題中命題之間的真值關系，而不關心命題的內容。說明21第21頁，課件共52頁，創(chuàng)作于2023年2月關于合式公式(┐A)、(A∧B)等公式單獨出現時，外層括號可以省去，寫成┐A、A∧B等。公式中不影響運算次序的括號可以省去，

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

(p→q)∧(qr)

(p∧q)∧┐r

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

pq→r

(p→(r→q)22第22頁，課件共52頁，創(chuàng)作于2023年2月賦值舉例在公式(┐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)為成假賦值。重要結論：

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

23第23頁，課件共52頁，創(chuàng)作于2023年2月真值表求下列公式的真值表，并求成真賦值和成假賦值。(1)(┐p∧q)→┐r(2)(p∧┐p)(q∧┐q)(3)┐(p→q)∧q∧r

24第24頁，課件共52頁，創(chuàng)作于2023年2月定義1.10重言式、永真式、可滿足式設A為任一命題公式(1)若A在它的各種賦值下取值均為真,則稱A是重言式(tautology)或永真式。(2)若A在它的各種賦值下取值均為假,則稱A是矛盾式(contradiction)或永假式。(3)若A不是矛盾式,則稱A是可滿足式（satisfactableformula）。25第25頁，課件共52頁，創(chuàng)作于2023年2月例題下列各公式均含兩個命題變項p與q，它們中哪些具有相同的真值表?

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

(2)pq (5)┐q∨p

(3)┐(p∧┐q)26第26頁，課件共52頁，創(chuàng)作于2023年2月啞元設公式A,B中共含有命題變項p1,p2,…,pn，，而A或B不全含有這些命題變項，比如A中不含pi,pi+1,…,pn,稱這些命題變項為A的啞元，A的取值與啞元的變化無關，因而在討論A與B是否有相等的真值表時，將A,B都看成p1,p2,…,pn的命題公式。27第27頁，課件共52頁，創(chuàng)作于2023年2月例題

例1.10

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

(1)p→q

(2)┐q∨r

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

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

35第35頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯的歸結法命題邏輯基礎：定義：合取式：p與q，記做pΛ

q析取式：

p或q，記做p∨

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

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

q

。。。。。。36第36頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯基礎定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。37第37頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯基礎基本等值式24個(1)交換率：p∨q<=>q

∨p

；

pΛq<=>qΛp

結合率：(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)

38第38頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯基礎基本等值式（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

39第39頁，課件共52頁，創(chuàng)作于2023年2月命題表示公式例如：1．

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

r，是得過數學一等獎。t，是得過物理一等獎。 則有命題公式公式：p

∧(r∨t)→

q。

40第40頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯的歸結法基本單元：簡單命題（陳述句）例：命題：A1、A2、A3

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

41第41頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯的歸結法建立子句集合取范式：命題、命題和的與，如：

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

42第42頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯的歸結法歸結過程

將命題寫成合取范式求出子句集對子句集使用歸結推理規(guī)則歸結式作為新子句參加歸結歸結式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結：除了有量詞和函數以外，其余和命題歸結過程一樣。43第43頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯歸結例題（1）例題，證明公式：(P→Q)→(～Q→～P)證明：（1）根據歸結原理，將待證明公式轉化成待歸結命題公式：

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

P→Q＝～P∨Q

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

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

（3）則子句集為：

{～P∨Q，～Q，P}44第44頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯歸結例題（2）子句集為： {～P∨Q，～Q，P}（4）對子句集中的子句進行歸結可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結）5.

， （2，4歸結）

由上可得原公式成立。45第45頁，課件共52頁，創(chuàng)作于2023年2月證明：化成子句集

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

例：設已知前提集為

P……………

…(1)(P∧Q)→R………(2)(S∨T)→Q………(3)T…………(4)求證R。46第46頁，課件共52頁，創(chuàng)作于2023年2月命題邏輯在計算機科學中的應用

邏輯難題

可以用邏輯推理解決的難題稱為邏輯難題。求解邏輯難題是實踐邏輯規(guī)則的一種好方法 涉及用于執(zhí)行邏輯推理的計算機程序通常也使用著名的邏輯難題來演示它們的能力47第47頁，課件共52頁，創(chuàng)作于2023年2月1.7命題邏輯在計算機科學中的應用

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