離散數(shù)學第二章

離散數(shù)學第二章第一頁，共一百一十七頁，編輯于2023年，星期一用命題邏輯處理蘇格拉底三段論：謂詞邏輯又例:張華是大學生,李明也是大學生。所有的自然數(shù)都等于1.(F);存在著自然數(shù)等于1.(T)PQR人總是要死的,蘇格拉底是人,蘇格拉底是要死的。若論證有效則有:PQR,即PQR永真.第二頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯對簡單命題作進一步分析,分離出個體和謂詞,并考慮到泛指和特指(全稱和存在),在此基礎上,研究命題的邏輯結構及命題間的推理關系。PredicateLogic第二章第三頁，共一百一十七頁，編輯于2023年，星期一２-1謂詞的概念與表示２-2量詞２-3謂詞公式２-5等價式與重言式２-7

謂詞演算的推理理論2－6前束范式謂詞邏輯２-4謂詞公式的解釋第四頁，共一百一十七頁，編輯于2023年，星期一命題是具有確定真值的陳述句。2-1謂詞的概念和表示如

“電子計算機是科學技術的工具?！眰€體:思維的對象,可以是具體的事物或抽象的概念謂詞:刻畫個體性質或個體之間關系的詞。1.

個體和謂詞

陳述句由主語和謂語兩部分構成，主語謂語個體謂詞一元謂詞:與一個個體相關聯(lián)的謂詞.(描述個體性質)N元謂詞:與N個個體相關聯(lián)的謂詞.(描述個體間的關系)謂詞邏輯>謂詞的概念和表示第五頁，共一百一十七頁，編輯于2023年，星期一(a).他是三好學生。(b).7是質數(shù)。(c).每天作廣播操是好習慣。(d).5大于3.(e).地球繞著太陽轉。一元謂詞。謂詞刻畫個體性質(f).張明和張亮是兄弟。(e).上海位于南京和杭州之間。謂詞刻畫個體間關系。在謂詞邏輯中,命題是由一個謂詞和若干有序個體組成的。謂詞邏輯>謂詞的概念和表示二元謂詞二元謂詞二元謂詞三元謂詞第六頁，共一百一十七頁，編輯于2023年，星期一2.個體和謂詞的表示

命題由一個謂詞和若干個體組成謂詞邏輯>謂詞的概念和表示用大寫字母A,B,C,D,...代表謂詞。用小寫字母代表個體：用小寫字母

a,b,c...表示特定個體:個體常元用小寫字母x,y,z...表示任意個體：個體變元.一個n元謂詞記作:A(x1,x2,…xn)其中x1,x2,…,xn為個體變元.當A(x1,…xn)中個體變元用個體常元:a1,…an代入后,A(a1…an)就成為一個命題。則A(a)表示命題:張華是大學生,A(b)表示命題:李明是大學生。例:令A(x):x是大學生;a:張華,b:李明第七頁，共一百一十七頁，編輯于2023年，星期一命題由一個謂詞和若干個體組成，但并非任意個體都和任意謂詞都能構成命題。如2是偶數(shù),(T)個體域:個體的取值范圍,用D表示如謂詞“...是偶數(shù)”的個體域D:全體整數(shù)?！?..是要死的”D:全體生物或D:人類全總個體域:所有個體的集合稱之。謂詞邏輯>謂詞的概念和表示3是偶數(shù),(F)x是偶數(shù)(不是命題)當謂詞確定后,其允許的個體取值范圍稱為個體域。則A(a)表示命題:張華是大學生,A(b)表示命題:李明是大學生。例:令A(x):x是大學生;D:人類a:張華,b:李明第八頁，共一百一十七頁，編輯于2023年，星期一又例:上海位于南京和杭州之間。

令L(x,y,z):x位于y和z之間,D:城市則命題符號化為:L(a,b,c)謂詞邏輯>謂詞的概念和表示則L(2,3)表示命題:2<3.(真)又例:設L(x,y):x小于y,D:實數(shù)集合則L(5,1):表示命題:5<1.(假)a:上海b:南京c:杭州當謂詞及其個體域確定后，命題的真值與個體的取值有關，因此一個謂詞可看作是一個以個體為自變量,函數(shù)值取真值的函數(shù)。第九頁，共一百一十七頁，編輯于2023年，星期一由簡單命題及連接詞可構成復合命題。與命題邏輯同張華和李明都是大學生。例1P(x):x是大學生,D:人,a:張華,b:李明命題符號化:P(a)P(b)如果張三比李四高,李四比王五高,則張三比王五高。命題符號化:P(a,b)P(b,c)P(a,c)例3p:(x,y)x比y高,D:人;a:張三,b:李四,c:王五2既是偶數(shù)又是素數(shù)。例2P(x):x是偶數(shù),Q(x):x是素數(shù),D:整數(shù),a:2,命題符號化:P(a)Q(a)謂詞邏輯>謂詞的概念和表示3.復合命題第十頁，共一百一十七頁，編輯于2023年，星期一例如:張華的母親愛張華.設P(x,y):x愛y;D:人;f(x):x的母親;a:張華命題符號化:P(f(a),a)例如:2與3之和小于2與3之積.設P(x,y):x小于y;D:整數(shù);f(x,y):x與y之和g(x,y):x與y之積;a:2;b:3命題符號化:P(f(a,b),g(a,b))或P(2+3,2·3)自變量和函數(shù)值均為個體域中的個體.用小寫字母f,g...表示.謂詞邏輯>量詞4.個體函數(shù)例如:張華的母親愛張華.第十一頁，共一百一十七頁，編輯于2023年，星期一２-1謂詞的概念與表示２-2量詞２-3謂詞公式２-5等價式與蘊含式２-7

謂詞演算的推理理論2－6前束范式謂詞邏輯２-4謂詞公式的解釋第十二頁，共一百一十七頁，編輯于2023年，星期一例如:任何人都是要死的.(T)有些人是聰明的.(T)所有的自然數(shù)都等于1.(F)存在著自然數(shù)等于1.(T)對個體域中的所有個體成立對個體域中的某些個體成立當命題的主語是泛指時,命題的真值還取決于謂詞與個體域中個體的數(shù)量關系.謂詞邏輯>量詞2-2

量詞1.全稱量詞與存在量詞第十三頁，共一百一十七頁，編輯于2023年，星期一兩種量詞:命題中表示個體數(shù)量的詞。全稱量詞(UniversalQuantifier):表示個體域中全體個體的詞，記作

相當于“任意”,“凡是”,“所有”...若個體域中所有個體x,均使A(x)為真,記作(x)A(x)存在量詞(ExistentialQuantifier):表示個體域中部分個體的詞，記作

相當于“存在”,“至少有一個”,“有些”...若個體域中存在某些個體x,使A(x)為真,記作(x)A(x)謂詞邏輯>量詞第十四頁，共一百一十七頁，編輯于2023年，星期一設H(x):x是要死的,任何人都是要死的。例如:則命題表示為:(x)H(x)個體域D:人類又例如:有些人是聰明的.設A(x):x是聰明的,個體域D:人類則命題表示為:(x)A(x)謂詞邏輯>量詞第十五頁，共一百一十七頁，編輯于2023年，星期一當在全總個體域中討論命題時,需在命題表示中增加一個特性謂詞,以給出個體變元的個體域。2.特性謂詞(1)帶全稱量詞的命題,特性謂詞作為加入.任何人都是要死的例如:M(x):x是人則命題表示為：(x)(M(x)H(x))改為:謂詞邏輯>量詞設H(x):x是要死的個體域D:全人類則命題表示為：(x)H(x)。H(x):x是要死的條件式的前件第十六頁，共一百一十七頁，編輯于2023年，星期一例如:有些人是聰明的.個體域

D：人設A(x)：x是聰明的,則命題表示為:(x)A(x)改為:A(x)：x是聰明的,則命題表示為:(x)(M(x)A(x))(2)帶存在量詞的命題,特性謂詞作為合取項加入。為何特性謂詞以前件加在全稱量詞后,而以合取項加在存在量詞后?能否改為:(x)(H(x)M(x))和(x)(M(x)A(x))?謂詞邏輯>量詞M(x):x是人第十七頁，共一百一十七頁，編輯于2023年，星期一3.命題符號化謂詞邏輯>量詞日常用語翻譯第十八頁，共一百一十七頁，編輯于2023年，星期一用謂詞邏輯處理蘇格拉底三段論：人總是要死的,蘇格拉底是人,所以,蘇格拉底是要死的。a:蘇格拉底

M(x):x是人,(x)(M(x)P(x)),M(a),P(a).令謂詞邏輯>量詞例題P(x):x是要死的,推理形式為:(x)(M(x)P(x)),M(a)P(a).1.判斷是否復合命題(看有幾個主謂結構或連接詞).2.對復合命題找出每個原子命題.3.對每個原子命題分出主語和謂語,主語若是泛指需加量詞和特性謂詞.并用符號表示.4.分析各原子命題的關系,確定連接詞.第十九頁，共一百一十七頁，編輯于2023年，星期一存在著最小的自然數(shù).謂詞邏輯>量詞P61例題補例兔子比烏龜跑的快例題3盡管有人聰明,但未必一切人都聰明.例題1并非每個實數(shù)都是有理數(shù).每個人都有自己喜歡的職業(yè).R(x):x是實數(shù)設Q(x):x是有理數(shù),故符號化為:(x)(R(x)Q(x))

M(x):x是人設P(x):x是聰明的,(x)(P(x)M(x))(x)(M(x)P(x))第二十頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞作業(yè)2-1，2-2（1）（e）,（f）,（g）,（h）2-3（3）本節(jié)重點掌握的概念:個體，謂詞,量詞,個體域。本節(jié)重點掌握的方法:命題符號化。特別注意特性謂詞的兩種使用方法。第二十一頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>謂詞公式1.個體和謂詞2..謂詞的表示:P(x1,x2,...xn)每個命題有一個謂詞和若干個體組成.當謂詞確定后,命題的真值依賴個體,因此采用函數(shù)的記法表示謂詞,自變量的取值范圍稱為個體域D3.量詞:當句子的主語是泛指的時候,必須引入量詞符號4.特性謂詞:

若在全總個體域討論問題,還需在命題表達中增加特性謂詞,以說明命題中個體的取值范圍.5.命題符號化

“每個計算機系的學生都學離散數(shù)學““存在著偶素數(shù)”第二十二頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>謂詞公式北京是中國的首都甲是乙的父親3介于2與4之間3大于2僅當3大于4。張三和李四是同班同學天下烏鴉一般黑火車都比汽車跑得快有的火車比所有汽車快。

課堂練習在謂詞邏輯中符號化：第二十三頁，共一百一十七頁，編輯于2023年，星期一２-1謂詞的概念與表示２-2量詞２-3謂詞公式２-5等價式與蘊含式２-7

謂詞演算的推理理論2－6前束范式謂詞邏輯２-4謂詞公式的解釋第二十四頁，共一百一十七頁，編輯于2023年，星期一2-3

謂詞公式如P,P(x),P(x,y),P(f(x),y),P(a,y)均原子公式。1.

謂詞公式

補充定義(項)1).個體常元和個體變元是項.2).若f是n元個體函數(shù),t1,...,tn是項,則f(t1,...tn)是項.3).只有有限次運用1),2)規(guī)則得到的符號串是項.如x,a,f(x),g(x,y),g(f(x),a).謂詞邏輯>謂詞公式項代表公式中以各種形式出現(xiàn)的個體.原子公式:把A(t1,t2,…tn)稱為謂詞演算的原子公式,其中,t1,t2,…tn是項.不含個體變元的原子公式是原子命題.第二十五頁，共一百一十七頁，編輯于2023年，星期一定義2-3.1

謂詞演算的合式公式wff,由下述各條組成：(1)原子謂詞公式是合式公式。(2)若A是合式公式,則A是合式公式。(3)若A和B都是合式公式,則(AB),(AB),(AB)和(AB)是合式公式。(4)如果A是合式公式,x是A中出現(xiàn)的任何變元,則(x)A和(x)A都是合式公式。(5)只有經(jīng)過有限次的應用規(guī)則(1),(2),(3),(4)所得到的公式是合式公式。簡稱謂詞公式如

xyP(x,y),xP(f(x),y),謂詞邏輯>謂詞公式P(a,y)

Q

第二十六頁，共一百一十七頁，編輯于2023年，星期一2.變元的約束

若給定為一謂詞公式,它可帶有如下子公式:(x)A(x)或(x)A(x)指導變元轄域約束變元其中,、后的x

稱為該量詞的指導變元;

A(x)稱為量詞的作用域或轄域(scope);在轄域中x的一切出現(xiàn)稱為x在中的約束出現(xiàn),x稱為約束變元;在中除約束變元以外所出現(xiàn)的變元稱為自由變元。P63例題1如x(M(x)R(x)),yP(x,y)R(y)謂詞邏輯>謂詞公式第二十七頁，共一百一十七頁，編輯于2023年，星期一閉式:不含自由變元的公式.開式:含有自由變元的公式.

其中,含有k個自由變元x1,x2,...xk的公式稱為

k元謂詞,記作A(x1,x2,...xk),0元謂詞為閉式.例如

(x)P(x,y,z)

x是小于100的質數(shù):L(x,100)又如任意的實數(shù)x,都存在著實數(shù)y,使得x<y.（不存在最大實數(shù)）令P(x,y):x<y

,

R(x):x是實數(shù)xy(R(x)R(y)P(x,y))謂詞邏輯>謂詞公式

閉式(T)

二元謂詞一元謂詞由命題符號化得到的公式是閉式.第二十八頁，共一百一十七頁，編輯于2023年，星期一２-1謂詞的概念與表示２-2量詞２-3謂詞公式２-4謂詞公式的解釋２-5等價式與蘊含式２-7

謂詞演算的推理理論2－6前束范式謂詞邏輯第二十九頁，共一百一十七頁，編輯于2023年，星期一謂詞公式的真值與那些因素有關?謂詞公式的真值能否像命題邏輯那樣總可由真值表給出?例xy(P(x)Q(f(x,a),y,z)R)

的真值給出個體域指定謂詞2-4.謂詞公式的解釋指定個體函數(shù)和個體指定自由變元謂詞邏輯>謂詞公式的解釋令P(x,y):x<y

,

D:自然數(shù)xyP(x,y)(閉命題)

(F)

例(T);令P(x,y):x+y=0,D:自然數(shù)Q(x,y)P(x,y)(開命題)例令D:自然數(shù);P(x,y):x<y;

Q(x,y):x+y=0,

令x=2,y=1,(T);令x=1,y=2,(F)第三十頁，共一百一十七頁，編輯于2023年，星期一為公式中的每個自由變元指定個體域DI中的一個個體.謂詞公式的一個解釋I(Interpretation)解釋I下的一個賦值1).指定一個個體域DI.2).為每個個體常元符號指定DI中的一個個體.3).為每個n元個體函數(shù)符號指定DI上的n元個體函數(shù).4).為每個n元謂詞符號指定一個DI上的n元謂詞閉式在一解釋下有一確定真值.開式在一組解釋I及I下一個賦值下,有一確定真值.補例謂詞邏輯>謂詞公式的解釋第三十一頁，共一百一十七頁，編輯于2023年，星期一給定解釋I和I中的賦值如下:DI:自然數(shù)集,L(x,y):x<y,E(x,y):x=y,h(x,y):x·y,v1:x=0,v2:x=1求公式在解釋I下的真值.(1)

y(E(x,y)

L(x,y))(2)

yzE(h(y,z),x)解在解釋I下

E(x,y)為x=y;

L(x,y)為x<y當賦值為v1時,命題解釋為:對任意自然數(shù)y,均有0y(T)

當賦值為v2時,命題解釋為:對任意自然數(shù)y,均有1y(F)解在解釋I下,E(h(y,z),x)為y·z=x當賦值為v1時,命題為:對任意自然數(shù)y,存在z使得y·z=0(T)當賦值為v2時,命題為:對任意自然數(shù)y,存在z使得y·z=1(F)

謂詞邏輯>謂詞公式的解釋補例第三十二頁，共一百一十七頁，編輯于2023年，星期一補例設解釋I的個體域為{a1,a2,…,an},則在解釋I下,

xA(x)A(a1)A(a1)...A(an)xA(x)A(a1)A(a1)...A(an)當個體域DI中的元素個數(shù)有限時,可將變元的所有可能取值一一列舉出來,此時量詞可消除.謂詞邏輯>謂詞公式的解釋第三十三頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>謂詞公式的解釋求下列閉式在解釋I下的真值給定解釋I如下:D={2,3},f(2)=3,f(3)=2,P(2)=TP(3)=F,Q(2,2)=T,Q(3,3)=T,Q(2,3)=F,Q(3,2)=F.

解1)x(Q(f(x),x)P(x))

2)x(y)Q(x,y)

1).原式=(Q(f(2),2)P(2))

(Q(f(3),3)P(3))

=(Q(3,2)P(2))(Q(2,3)P(3))

=(FT)(FF)=T

2).原式=x(Q(x,2)

Q(x,3))=(Q(2,2)

Q(2,3))(Q(3,2)

Q(3,3))=

(TF)

(F

T)=TyxQ(x,y)的真值?補例第三十四頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>謂詞公式的解釋求(x)(y)(P(x)Q(x,y))

在解釋I的真值

DI={1,2},P(1)=F,P(2)=T,Q(1,1)=T,Q(2,2)=T;Q(1,2)=F,Q(2,1)=F.原式=

(x)((P(x)Q(x,1))(P(x)Q(x,2)))

=

((P(1)Q(1,1))(P(1)Q(1,2)))

((P(2)Q(2,1))(P(2)Q(2,2)))=((FT)(FT))((FF)(TT))=F補例第三十五頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>謂詞公式的解釋課堂練習1.“并非一切推理都能用計算機完成”符號化為()2.設R(x):x是實數(shù),P(x,y):x=y,則命題“對任意的實數(shù)

x,y,有x+y=y+x”符號化為()

3.不含有自由變元的謂詞公式是命題.()4.

yE(x,y)L(x,y,z))是二元謂詞()5.使一階邏輯公式y(tǒng)

xF(y,x)為真的解釋是()A.個體域為自然數(shù)集合，F(xiàn)(x,y)為xyB.個體域為自然數(shù)集合，F(xiàn)(x,y)為y<xC.個體域為自然數(shù)集合，F(xiàn)(x,y)為x=yD.均不屬于A、B、C6.在解釋I:DI={a,b},P(a,a)=p(b,b)=0P(a,b)=p(b,a)=1下,公式x

yP(x,y)的真值為_____

第三十六頁，共一百一十七頁，編輯于2023年，星期一作業(yè)2-4（2）（b）,（c）（3）(4)

2-5（1）（b）（2）(a),(d)謂詞邏輯>謂詞公式的解釋本節(jié)重點掌握的概念:謂詞公式,自由變元,約束變元,開式,閉式。本節(jié)重點掌握的方法:求謂詞公式的真值第三十七頁，共一百一十七頁，編輯于2023年，星期一要點回顧謂詞邏輯>等價與蘊含式1.個體和謂詞2.謂詞的表示:P(x1,x2,...xn)3.量詞4.特性謂詞5.謂詞公式6.謂詞公式的賦值:對謂詞公式一個賦值稱為一個解釋。閉式在一組解釋下會求得一個真值；開式還需在此基礎上對自由變元賦值，才能求出一個真值。例:對任意的自然數(shù)x存在著自然數(shù)y,使得p(x,y)成立.解釋1：p(x,y):x<=y,(T)解釋2：p(x,y):x+y=0,(F)第三十八頁，共一百一十七頁，編輯于2023年，星期一２-1謂詞的概念與表示２-2量詞２-3謂詞公式２-7

謂詞演算的推理理論2－6前束范式謂詞邏輯２-4謂詞公式的解釋２-5等價式與蘊含式第三十九頁，共一百一十七頁，編輯于2023年，星期一定義2-5.2,2-5.3如果公式A在任何解釋下均為真,稱A為永真式;如果

A在某個解釋I和I的一個賦值下為真,稱A可滿足;如果公式在任何解釋下均為假,稱A為永假式.2-5等價與蘊含1.永真式當個體域有限時,原則上可用真值表法判定一公式永真永假或可滿足；但當個體域無限時,真值表法失效.代入定理、等價演算

永真(永假)式的判定：謂詞邏輯>等價與蘊含式第四十頁，共一百一十七頁，編輯于2023年，星期一命題邏輯永真式（永假式）的代換實例是謂詞邏輯的永真式（永假式）。設A是包含命題變元P1,P2,...Pn的命題公式,B1,B2,...Bn是謂詞公式,用B1,B2,...Bn分別代替P1,P2,...Pn

在A中的所有出現(xiàn),得到的謂詞公式B稱A的代換實例,命題邏輯永真式的代換實例稱為重言式.謂詞邏輯>等價與蘊含式命題邏輯的代入定理:一個重言式,對同一分量都用任何合式公式置換,結果仍重言.第四十一頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>等價與蘊含式上式可看作命題公式PP的代入實例1)(x)P(x)(x)P(x)

2)(xP(x)(xQ(x)xP(x)))

上式可看作命題公式(P(QP))的代入實例而(P(QP))(P(QP))F所以,(xP(x)(xQ(x)xP(x)))為永假式而PPT,所以,(x)P(x)(x)P(x)為重言式判定公式的類型重言式是永真式,但永真未必重言.

例如xP(x)xP(x)是永真式，但不是重言式.補例第四十二頁，共一百一十七頁，編輯于2023年，星期一2.等價與蘊含定義

2-5.1

設A,B是公式,若AB是永真式,則稱A,B等價.記作AB.等價式的判定等價演算:利用基本公式、等價的性質和置換

定理，推演出其他等價式.定義

2-5.2

設A,B是公式,若AB是永真式,則稱A蘊含B.記作AB.謂詞邏輯>等價與蘊含式AB當且僅當AB且BA第四十三頁，共一百一十七頁，編輯于2023年，星期一(1)命題公式的推廣例如PQPQ

用

xP(x)代替P;

(x)P(x)(x)Q(x)(x)P(x)(x)Q(x)xQ(x)代替Q得到:(x)(P(x)Q(x))(x)R(x)(x(P(x)Q(x))

(x)R(x)同理

P(x)Q(x)P(x)Q(x)利用代入定理,將命題邏輯的所有等價式推廣到謂詞邏輯.謂詞邏輯>等價與蘊含式第四十四頁，共一百一十七頁，編輯于2023年，星期一(2)量詞與聯(lián)結詞的關系例

設

P(x):x今天來校上課,D:學生則P(x)表示:x今天沒來校上課“并非所有人今天來校上課”(x)P(x)

等價“有人今天沒來校上課”(x)P(x)

(x)P(x)(x)P(x)

“沒有人今天來校上課”

(x)

P(x)

等價“所有人今天都沒來校上課”(x)P(x)(x)

P(x)(x)P(x)謂詞邏輯>等價與蘊含式第四十五頁，共一百一十七頁，編輯于2023年，星期一(3)量詞作用域的擴張與收縮(x)(A(x)B)(x)A(x)BB(x)A(x)(x)(A(x)B)(x)A(x)BB(x)A(x)(x)A(x)B

(x)(A(x)

B)(x)A(x)B

(x)A((x)

B)B(x)A(x)

(B(x)A((x))B(x)A(x)

(B(x)A((x))由上式可推出謂詞邏輯>等價與蘊含式第四十六頁，共一百一十七頁，編輯于2023年，星期一(4)量詞與聯(lián)結詞之間的一些等價式例第一式中用A代A,用B代B：(x)(A(x)

B(x))(x)A(x)

(x)B(x)(x)(A(x)B(x))(x)A(x)(x)B(x)與“聯(lián)歡會上所有人唱歌且所有人跳舞”意義相同(x)(A(x)B(x))(x)A(x)(x)B(x)(x)(A(x)B(x))((x)A(x)(x)B(x)(x)(A(x)B(x))((x)A(x)(x)B(x)對滿足分配律對滿足分配律“聯(lián)歡會上所有人即唱歌又跳舞.”謂詞邏輯>等價與蘊含式(x)(A(x)B(x))((x)A(x)(x)B(x)第四十七頁，共一百一十七頁，編輯于2023年，星期一(x)(A(x)B(x))(x)A(x)(x)B(x)?(x)(A(x)B(x))((x)A(x)(x)B(x)?(x)(A(x)B(x)):對所有的x,有A(x)或B(x)成立.(x)(A(x)B(x)):存在著x,使A(x)和B(x)同時成立.例

D:整數(shù)集合,A(x):x是偶數(shù),B(x):x是奇數(shù)(x)A(x)(x)B(x)(T)

(x)(A(x)B(x))(F)

謂詞邏輯>等價與蘊含式(x)A(x)(x)B(x):對所有的x,A(x)成立;或對所有的x,B(x)成立.(x)A(x)(x)B(x):存在著x,使A(x)成立,且存在x,使B(x)成立.第四十八頁，共一百一十七頁，編輯于2023年，星期一(5)量詞與聯(lián)結詞之間的一些蘊含式(x)A(x)(x)B(x)(x)(A(x)B(x))(x)(A(x)B(x))((x)A(x)(x)B(x)(x)(A(x)B(x))(x)A(x)(x)B(x)(x)(A(x)B(x))(x)A(x)(x)B(x)常見的等價式與蘊含式見表2-5.1同理可得謂詞邏輯>等價與蘊含式第四十九頁，共一百一十七頁，編輯于2023年，星期一(6)多個量詞的使用公式中多個量詞的出現(xiàn)次序關系到命題的含義,不能隨意交換.例如xyA(x,y):對任意x,都存在y,使得A成立.例(x)(y)(x+y=0)為真命題,y=-x

yxA(x,y)

:存在著y,對所有的x都有A成立.(y)(x)(x+y=0)為假命題∵謂詞邏輯>等價與蘊含式

y的值獨立于x.y的值依賴于x.第五十頁，共一百一十七頁，編輯于2023年，星期一特殊情況:全稱量詞之間可交換,存在量詞之間可交換.全稱與存在之間存在如下關系:I18(x)(y)A(x,y)(y)(x)A(x,y)I19(x)(y)A(x,y)(x)(y)A(x,y)I20(y)(x)A(x,y)(x)(y)A(x,y)I21(x)(y)A(x,y)(y)(x)A(x,y)I22(x)(y)A(x,y)(y)(x)A(x,y)I23(y)(x)A(x,y)(x)(y)A(x,y)謂詞邏輯>等價與蘊含式xyyxyxyxyxxy

xyyx第五十一頁，共一百一十七頁，編輯于2023年，星期一例題謂詞邏輯>等價與蘊含式右式驗證(x)(A(x)B(x))(x)A(x)(x)B(x)

(x)A(x)

(x)

B(x)(x)A(x)

(x)

B(x)(x)(A(x)

B(x))(x)(A(x)B(x))證明(x)P(x)(x)P(x)為永真式。

證明(P(x)(Q(x)P(x)))為永假式。

第五十二頁，共一百一十七頁，編輯于2023年，星期一例題謂詞邏輯>等價與蘊含式

(x)P(x)

(x)P(x)

分析真值法:左右且右左.給定公式(x)P(x)(x)P(x)一組解釋I,若(x)P(x)

在I下為真,則(x)P(x)為假,即存在aD,使P(a)為假,即P(a)為真,即(x)P(x)為真.給定(x)P(x)(x)P(x)一組解釋I,若(x)P(x)在I下為真,則存在aD,使P(a)為真,即P(a)為假,即(x)P(x)為真.則(x)P(x)為假,第五十三頁，共一百一十七頁，編輯于2023年，星期一２-1謂詞的概念與表示２-2量詞２-3謂詞公式２-5等價式與蘊含式２-7

謂詞演算的推理理論2－6前束范式謂詞邏輯２-4謂詞公式的解釋第五十四頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>前束范式2-6前束范式定義2-6.1

一個公式,如果量詞均在全式的開頭,它們的作用域,延伸到整個公式的末尾,則該公式叫做前束范式。前束范式簡記為:(□v1)(□v2)...(□vn)A或指導變元母式(不含量詞)例如(x)(y)(z)(

Q(x,y)

R(z))

(x)P(x)

(

x)Q(x)?

Q(x,y)

R(z)定理2-6.1

任一謂詞公式,均和一個前束范式等價.第五十五頁，共一百一十七頁，編輯于2023年，星期一化前束范式的方法(1).將公式中的連接詞化為,,.(非必須)

(2).利用否定律,德.摩根律,及量詞轉化律,將否定深入到謂詞字母前.

(3).利用換名規(guī)則或代入規(guī)則使所有約束變元均不相同且使所有的自由變元與約束變元不同.

(4).利用量詞的的擴張與收縮,擴大量詞的轄域至整個公式.謂詞邏輯>前束范式例如(x)P(x,y)Q(x)(x)P(x)(x)Q(x)第五十六頁，共一百一十七頁，編輯于2023年，星期一因為(x)P(x)(y)P(y),(x)P(x)(y)P(y),所以,若謂詞公式中有變元既約束出現(xiàn),又自由出現(xiàn),為避免混淆,可對約束變元進行換名或對自由變元代入,使得一個變元在公式中只呈一種出現(xiàn).

(1)對約束變元換名,其更改的變元名稱范圍是:量詞中的指導變元及該量詞轄域中出現(xiàn)的該變元,而公式中其余變元不變.(2)對約束變元換名時一定要更改為轄域中未出現(xiàn)的變元名.換名規(guī)則

例如

(x)P(x)(x)Q(x)

(x)P(x)(y)Q(y)謂詞邏輯>前束范式(x)(y)(P(x)Q(y))

(x)(P(x)R(x,y))Q(x,y)=?第五十七頁，共一百一十七頁，編輯于2023年，星期一代入規(guī)則(1).代入須對公式中該自由變元的所有出現(xiàn)同時進行.(2).代入的變元不能與公式中其它變元同名.例如

(x)P(x)

Q(x,y)(x)P(x)

Q(r,y)

(x)(y)P(x,y)

R(x,y,z)(x)(y)P(x,y)

R(u,v,z)(x)(y)(P(x,y)

R(u,v,z))謂詞邏輯>前束范式第五十八頁，共一百一十七頁，編輯于2023年，星期一(□v1)(□v2)…(□vn)(其中□可能是量詞或,vi(i=1,2,…,n)是指導變元,Aij是原子公式或其否定。定義2-6.2

一個wffA如果具有如下形式稱為前束合取范式例如

(x)(z)(y)((

P(x,y)

(z=b))

(Q(y)(a=b)))定理2-6.2

每一個wffA都可以轉換為與它等價的前束合取范式。謂詞邏輯>前束范式第五十九頁，共一百一十七頁，編輯于2023年，星期一其中□可能是量詞或,vi(i=1,2,…,n)是客體變元,Aij是原子公式或其否定。定義2-6.3一個wffA如果具有如下形式稱為前束析取范式例如(x)(z)(y)((

P(x,y)

(z=b))

(Q(y)(a=b)))定理2-6.3每一個wffA都可以轉換為與它等價的前束析取范式。(□v1)(□v2)…(□vn)(謂詞邏輯>前束范式第六十頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>前束范式化前束范式的方法(1).將公式中的連接詞化為,,.(非必須)(2).利用否定律,德.摩根律,及量詞轉化律,將否定深入到謂詞字母前.(3).利用換名規(guī)則或代入規(guī)則使所有約束變元均不相同且使所有的自由變元與約束變元不同.(4).利用量詞的的擴張與收縮,擴大量詞的轄域至整個公式.前束范式：(□v1)(□v2)...(□vn)A第六十一頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>前束范式例題xyz(P(x,z)P(y,z))uQ(x,y,u)化為前束析取范式.第六十二頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>前束范式例題x[yP(x)zQ(z,y)

yR(x,y)]的前束合取范式原式消去多余x[P(x)zQ(z,y)y

R(x,y)]換名x[P(x)zQ(z,y)wR(x,w)]自由w消去其它x[(P(x)zQ(z,y))wR(x,w)]否定深入x[(P(x)zQ(z,y))wR(x,w)]量詞提出x

zw[(P(x)Q(z,y))R(x,w)]分配律xzw[(P(x)R(x,w)]

(Q(z,y))R(x,w)]量詞w聯(lián)結詞前束析取范式第六十三頁，共一百一十七頁，編輯于2023年，星期一作業(yè)2-5（4）,（6）2-6(1)(a)(2)(a),(b)謂詞邏輯>前束范式本節(jié)重點掌握的概念:謂詞演算的永真式，重言式，等價式,蘊含式;前束范式.本節(jié)重點掌握的方法:證明永真式，等價式,求前束合取范式,析取范式.第六十四頁，共一百一十七頁，編輯于2023年，星期一２-1謂詞的概念與表示２-2量詞２-3謂詞公式２-5等價式與蘊含式2－6前束范式謂詞邏輯２-4謂詞公式的解釋２-7

謂詞演算的推理理論第六十五頁，共一百一十七頁，編輯于2023年，星期一2-7謂詞演算的推理理論設H1,H2…Hn和C是謂詞公式,當且僅當H1H2…,HnC稱C是一組前提H1,H2…Hn的有效結論.等價演算、分析真值、證明法。判定謂詞公式永真的各種方法都可用于判斷推理正確性謂詞邏輯>謂詞演算的推理...等價演算：AB即ABT例：

xP(x)

xQ(x)x（P(x)Q(x)）分析真值：設前件在一組解釋下為真,推出后件也真；或證明后件在一組解釋下為假時，前件也為假。第六十六頁，共一百一十七頁，編輯于2023年，星期一要證C是一組前提H1,H2…Hn的有效結論,需證:H1H2…,HnC是重言式即證:H1,H2…Hn均為真時,C必為真.為描述這樣一個推理過程,可構造一個命題公式序列:其中每個公式或是前提,或是由某些前提利用推理規(guī)則推出的.序列的最后一個命題公式就是所要結論.這樣一個描述推理過程的命題公式序列稱為形式論證(證明或演繹法).證明法謂詞邏輯>謂詞演算的推理...第六十七頁，共一百一十七頁，編輯于2023年，星期一P規(guī)則(前提引入規(guī)則):前提在推理過程中的任何時候均可引用.T規(guī)則(結論引入規(guī)則):在推理過程中,如有一個或多個公式蘊含公式S,則S可引入推導過程.推理規(guī)則命題邏輯>推理理論

由于謂詞公式中包含量詞,還需增加一組處理量詞的推理規(guī)則.

首先命題邏輯中的推理規(guī)則都可應用于謂詞邏輯的推理中:第六十八頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>謂詞演算的推理...(1)全稱指定規(guī)則US含義:若D中所有個體使A真,則

D中任一個體t也使A真.例

⑴(x)(y)(x<y)P(不存在最大實數(shù))例

⑴(x)P(x):所有的人都是要死的P

⑵P(a):蘇格拉底是要死的.US⑵(y)(a<y)US

或⑵(y)(x<y)US(y)(y<y)?或⑵P(x):x是要死的.US使用限制:t不能與其它指導變元同名.第六十九頁，共一百一十七頁，編輯于2023年，星期一(2)全稱推廣規(guī)則UG含義:若D中任意一個體使A真,則D中所有個體都使A真.使用限制:x不能是前提中的自由變元.例:P(x):x是偶數(shù)D:正整數(shù).(1)P(x)P(2)(x)P(x)UG?謂詞邏輯>謂詞演算的推理...第七十頁，共一百一十七頁，編輯于2023年，星期一(3)存在指定規(guī)則ES含義:若D中存在個體使A真,則D中必有某個體c使A真.使用限制:(x)A(x)為閉式,c為一個新常元(歧義名稱).(4)存在推廣規(guī)則EG含義:若項t使A真,則D中存在個體使A為真.謂詞邏輯>謂詞演算的推理...

使用限制:x不能與A(t)中的自由變元或指導變元同名第七十一頁，共一百一十七頁，編輯于2023年，星期一例

(2)(y)(x

<y)US

(3)x

<aES(1)(x)(y)(x<y)P取D:有理數(shù)(4)(x)(x<a)UG(5)(y)(x)(x<y)EG謂詞邏輯>謂詞演算的推理...不是閉式例

(2)F(a)

ES

證明:

(x)F(x)F(a)

(1)(x)F(x)P不是新常元第七十二頁，共一百一十七頁，編輯于2023年，星期一(1)(x)Q(x)P(2)(x)Q(x)P(3)Q(a)T1,ES(4)Q(a)T2,ES(5)Q(a)Q(a)T3,4(6)(x)(Q(x)Q(x))T5,EG

例Q(x):x是有理數(shù)D:實數(shù)(1)(x)Q(x)P(2)(x)Q(x)P(3)Q(a)T1,ES(4)Q(b)T2,ES(5)...謂詞邏輯>謂詞演算的推理...不是新常元第七十三頁，共一百一十七頁，編輯于2023年，星期一例

(2)(x)F(x)

P

(3)F(a)G(a),

US(1)(x)(F(x)G(x))P前提:(x)(F(x)G(x)),(x)F(x)結論:(x)G(x)(4)F(a)ES(5)G(a)EG不是新常元(6)(x)G(x)

EG

(2)(x)F(x)

P

(4)F(a)G(a)

ES(1)(x)(F(x)G(x))P(3)F(a)UG(5)G(a)EG(6)(x)G(x)

EG謂詞邏輯>謂詞演算的推理...第七十四頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯>謂詞演算的推理...例題1證明(x)(H(x)M(x))H(s)M(s)證明(1).(x)(H(x)M(x))P(2).H(s)M(s) US,T1(3).H(s) P(4).M(s) T2,3,I13(蘇格拉底三段論)P76例題1第七十五頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞例題2證明(x)(C(x)W(x)R(x))(x)(C(x)

Q(x))(x)(Q(x)R(x))證明(1).(x)(C(x)Q(x))

P(2).C(a)Q(a

)

T2,ES(3).C(a)T3,I1(5).(x)(C(x)W(x)R(x))P(6).C(a)W(a)R(a)

T1,3,US(4).Q(a)T3(7).W(a)R(a)T4,5,I(8).R(a)T6,I(9).Q(a)R(a)T7,8,I1P77例題2(10).(x)(Q(x)R(x))T9,EG第七十六頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞例題3(x)(P(x)

Q(x))(x)P(x)(x)Q(x)(CP規(guī)則)

x(P(x)Q(x))xP(x)xQ(x)

(1).

xP(x)附加P

(2).

xP(x)T1,E

(3).

P(c))T2,ES

(6).

Q(c))

T3,5,I

(4).

x(P(x)Q(x))

P(7).xQ(x)T6,ES(5).P(c)Q(c)

T4,US(8).xP(x)xQ(x)CP規(guī)則P77例題3第七十七頁，共一百一十七頁，編輯于2023年，星期一例題3(x)(P(x)

Q(x))(x)P(x)(x)Q(x)(歸謬法)(1).((x)P(x)(x)Q(x))

附加P(2).(x)P(x)(x)Q(x))

T1,E(3).(x)P(x)T2,E(4).(x)P(x)T3,E(5).(x)Q(x))

T2,I1(6).(x)Q(x))

T5,E(7).P(c))

T4,ES(8).Q(c))

T6,US(9).P(c)Q(c)T7,8,I(10).(P(c)Q(c))T9,E(11).(x)(P(x)Q(x))

P(13).(P(c)Q(c))(P(c)

Q(c))T10,12(12).P(c)Q(c)T11,USP77例題3第七十八頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞補例所有的有理數(shù)是實數(shù).某些有理數(shù)是整數(shù).因此,某些實數(shù)是整數(shù).

設:R(x):x是實數(shù)

Q(x):x是有理數(shù)P(x):x是整數(shù)x(Q(x)R(x)),(x)(Q(x)P(x))

(x)(R(x)P(x))x（Q(x)R(x)）(x)(Q(x)P(x))(x)(R(x)P(x))第七十九頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞補例每個用功的學生考試不會不及格。小張是用功的學生。所以，小張考試及格。設:P(x):x考試及格Q(x):x是學生R(x):x是用功的。a:小張x（Q(x)R(x)P(x)）R

(a)Q(a)

P

(a)Q(a)第八十頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞4.設R(x):x是實數(shù),P(x):x是有理數(shù),“并非每個實數(shù)都是有理數(shù)”符號化為()A.x((R(x)P(x))B.

x(R(x)P(x))

5.謂詞公式xP(x)xQ(x)xP(x)的類型是____.6.在解釋I:DI={1,2},P(1,1)=P(1,2)=0,P(2,2)=P(2,1)=1下,謂詞公式

x

yP(x,y)的真值為_____.7.公式xP(x)xQ(x,y)前束合取范式為______.課堂練習1.在謂詞邏輯中,永真式都是重言式。()2.任意謂詞公式都有唯一的前束范式與之等價。()3.(x)(A(x)B(x))(x)A(x)(x)B(x)()

第八十一頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞8所有的有理數(shù)是實數(shù).所有的無理數(shù)是實數(shù).虛數(shù)不是實數(shù)，所以虛數(shù)不是有理數(shù)也不是無理數(shù).設:R(x):x是實數(shù)

Q(x):x是有理數(shù)P(x):x是無理數(shù)。S(x):x是虛數(shù)x（Q(x)R(x)）

x（P(x)R(x)）x（S(x)R(x)）x（S(x)Q(x)

P(x)）第八十二頁，共一百一十七頁，編輯于2023年，星期一命題邏輯>邏輯連接詞作業(yè)2-7（1）（a）,（b）（2）本節(jié)重點掌握的概念:4個推理規(guī)則本節(jié)重點掌握的方法:推理的形式證明方法第八十三頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯PredicateLogic第二章本章小結謂詞邏輯小結第八十四頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯小結一.謂詞的概念和表示量詞和特性謂詞謂詞重點掌握的基本概念和方法(一)個體和個體域謂詞公式的翻譯(命題符號化)一元謂詞:A(x)n元謂詞:A(x1,...xn)個體常元:a,b,c...個體變元:x,y,z...D:個體域全稱量詞:(x)A(x)存在量詞:(x)A(x)

(x)(P(x)A(x))(x)(P(x)A(x))特性謂詞P(x)第八十五頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯小結重點掌握的基本概念和方法(二)二.謂詞公式及其解釋謂詞公式的遞歸定義謂詞公式的解釋與賦值變元的約束求謂詞公式在一組解釋下的真值有限域無限域指導變元與轄域自由變元與約束變元開式與閉式1).指定個體域DI.2).指定個體常元3).指定個體函數(shù).4).指定謂詞5).指定自由變元開式閉式第八十六頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯小結三.公式類型及相互關系重點掌握的基本概念和方法(三)判別公式的類型或等價公式的類型等價公式AB:即

AB永真蘊含公式AB:即AB永真代入定理等價演算分析真值永真式與重言式永假式

可滿足式ABIffAB且BA第八十七頁，共一百一十七頁，編輯于2023年，星期一謂詞邏輯小結四.前束范式重點掌握的基本概念和內容(四)