離散數(shù)學 第二章.ppt

1、第四篇圖論,1.命題邏輯,2.謂詞邏輯,3.集合與關(guān)系,4.函數(shù),6.布爾代數(shù),5.代數(shù)結(jié)構(gòu),目錄,.圖論,第一篇數(shù)理邏輯,第二篇集合論,第三篇代數(shù)結(jié)構(gòu),緒論,用命題邏輯處理蘇格拉底三段論：,謂詞邏輯,又例: 張華是大學生,李明也是大學生。,所有的自然數(shù)都等于1.(F); 存在著自然數(shù)等于1.(T),P,Q,R,人總是要死的,蘇格拉底是人,蘇格拉底是要死的。,若論證有效則有: PQR,即 PQR 永真.,謂詞邏輯,對簡單命題作進一步分析,分離出個體和謂詞, 并考慮到泛指和特指 (全稱和存在),在此基礎(chǔ) 上,研究命題的邏輯結(jié)構(gòu)及命題間的推理關(guān)系。,Predicate Logic,第二章,-1 謂

2、詞的概念與表示,-2 量詞,-3 謂詞公式,-5 等價式與重言式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,命題是具有確定真值的陳述句。,2-1謂詞的概念和表示,如 “電子計算機是科學技術(shù)的工具。”,個體:思維的對象,可以是具體的事物或抽象的概念,謂詞:刻畫個體性質(zhì)或個體之間關(guān)系的詞。,1. 個體和謂詞,陳述句由主語和謂語兩部分構(gòu)成，,主語,謂語,個體,謂詞,一元謂詞: 與一個個體相關(guān)聯(lián)的謂詞.(描述個體性質(zhì)),N元謂詞: 與N個個體相關(guān)聯(lián)的謂詞.(描述個體間的關(guān)系),謂詞邏輯 謂詞的概念和表示,(a).他是三好學生。,(b).7 是質(zhì)數(shù)。,(c).每天作廣播操

3、是好習慣。,(d).5 大于 3.,(e).地球繞著太陽轉(zhuǎn)。,一元謂詞。 謂詞刻畫個體性質(zhì),(f).張明和張亮是兄弟。,(e).上海位于南京和杭州之間。,謂詞刻 畫個體 間關(guān)系。,在謂詞邏輯中,命題是由一個謂詞和若干有序個體組成的。,謂詞邏輯 謂詞的概念和表示,二元謂詞,二元謂詞,二元謂詞,三元謂詞,2.個體和謂詞的表示,命題由一個謂詞和若干個體組成,謂詞邏輯 謂詞的概念和表示,用大寫字母 A, B , C, D,. 代表謂詞。 用小寫字母代表個體 ： 用小寫字母 a , b, c. 表示特定個體: 個體常元 用小寫字母 x,y,z.表示任意個體：個體變元.,一個 n 元謂詞記作: A ( x

4、1 , x2, xn) 其中 x1 , x2,xn 為個體變元.當A ( x1 , xn)中個體變元用個體常元: a1,an 代入后, A(a1an) 就成為一個命題。,則 A (a) 表示命題: 張華是大學生, A (b) 表示命題: 李明是大學生。,例: 令 A(x) : x 是大學生; a:張華 , b:李明,命題由一個謂詞和若干個體組成，但并非任意個體都和任意謂詞都能構(gòu)成命題。,如 2 是偶數(shù),(T),個體域:個體的取值范圍,用D表示,如謂詞 “. 是偶數(shù)” 的個體域 D: 全體整數(shù)。 “.是要死的” D:全體生物 或 D: 人類,全總個體域:所有個體的集合稱之。,謂詞邏輯 謂詞的概念

5、和表示,3 是偶數(shù),(F),x 是偶數(shù) (不是命題),當謂詞確定后,其允許的個體取值范圍稱為個體域。,則 A (a) 表示命題: 張華是大學生, A (b) 表示命題: 李明是大學生。,例: 令 A(x) : x 是大學生; D:人類 a:張華 ,b:李明,又例: 上海位于南京和杭州之間。,令 L (x ,y,z) : x 位于 y 和 z 之間, D: 城市,則命題符號化為: L(a,b,c),謂詞邏輯 謂詞的概念和表示,則 L(2,3) 表示命題: 23. (真),又例: 設(shè) L (x,y) : x 小于 y, D: 實數(shù)集合,則 L(5,1):表示命題: 51. (假),a:上海 b:

6、南京 c:杭州,當謂詞及其個體域確定后，命題的真值與個體的取值有關(guān)，因此一個謂詞可看作是一個以個體為自變量,函數(shù)值取真值的函數(shù)。,由簡單命題及連接詞可構(gòu)成復合命題。,與命題邏輯同,張華和李明都是大學生。,例1,P (x) : x 是大學生 , D:人, a:張華, b:李明,命題符號化: P(a)P(b),如果張三比李四高, 李四比王五高, 則張三比王五高。,命題符號化: P(a,b) P(b,c) P( a,c),例3,p:(x,y) x 比 y 高, D: 人;,a: 張三, b: 李四, c: 王五,2 既是偶數(shù)又是素數(shù)。,例2,P (x) : x 是偶數(shù) , Q(x): x 是素數(shù) ,

7、 D:整數(shù), a: 2,命題符號化: P(a) Q(a),謂詞邏輯 謂詞的概念和表示,3.復合命題,例如: 張華的母親愛張華. 設(shè) P(x,y):x愛y; D:人; f(x): x的母親; a:張華 命題符號化: P ( f (a), a ),例如: 2與3之和小于2與3之積. 設(shè) 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, 23 ),自變量和函數(shù)值均為個體域中的個體.用小寫字母f,g.表示.,謂詞邏輯 量詞,4.個體函數(shù),例如: 張華的母親愛

8、張華.,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-5 等價式與蘊含式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,例如: 任何人都是要死的.(T),有些人是聰明的.(T),所有的自然數(shù)都等于1.(F),存在著自然數(shù)等于1.(T),對個體域中的 所有個體成立,對個體域中的 某些個體成立,當命題的主語是泛指時,命題的真值還取決于謂詞與個體域中個體的數(shù)量關(guān)系.,謂詞邏輯 量詞,2-2量詞,1.全稱量詞與存在量詞,兩種,量詞:命題中表示個體數(shù)量的詞。,全稱量詞(Universal Quantifier): 表示個體域中全體個體的詞，記作 相當于 “任意”,“凡

9、是”,“所有”.,若個體域中所有個體x,均使A(x)為真,記作(x)A(x),存在量詞(Existential Quantifier): 表示個體域中部分個體的詞， 記作 相當于 “存在”,“至少有一個”,“有些”.,若個體域中存在某些個體x,使A(x)為真,記作(x)A(x),謂詞邏輯 量詞,設(shè)H(x): x 是要死的,任何人都是要死的。,例如:,則命題表示為: (x)H(x),個體域D: 人類,又例如: 有些人是聰明的.,設(shè)A(x): x是聰明的,個體域 D:人類,則命題表示為: (x)A(x),謂詞邏輯 量詞,當在全總個體域中討論命題時,需在命題表示中增加一個特性謂詞,以給出個體變元的個

10、體域。,2.特性謂詞,(1)帶全稱量詞的命題,特性謂詞作為 加入.,任何人都是要死的,例如:,M(x):x是人,則命題表示為：(x)(M(x)H(x),改為:,謂詞邏輯 量詞,設(shè) H(x):x是要死的 個體域D: 全人類 則命題表示為：(x)H(x)。,H(x):x是要死的,條件式的前件,例如:有些人是聰明的.,個體域 D：人,設(shè)A(x)：x是聰明的,則命題表示為: (x)A(x),改為:,A(x)：x是聰明的,則命題表示為: (x)(M(x)A(x),(2)帶存在量詞的命題,特性謂詞作為合取項加入。,為何特性謂詞以前件加在全稱量詞后,而以合取項加在存在量詞后? 能否改為:,(x)(H(x)

11、M(x) 和 (x)(M(x) A(x) ?,謂詞邏輯 量詞,M(x):x是人,3.命題符號化,謂詞邏輯 量詞,日常用語翻譯,用謂詞邏輯處理蘇格拉底三段論：,人總是要死的, 蘇格拉底是人,所以,蘇格拉底是要死的。,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.判斷是否復合命題(看有幾個主謂結(jié)構(gòu)或連接詞). 2.對復合命題找出每個原子命題. 3.對每個原子命題分出主語和謂語,主語若是泛指需加量 詞和特性謂詞.并用符號表示. 4.分析各

12、原子命題的關(guān)系,確定連接詞.,存在著最小的自然數(shù).,謂詞邏輯 量詞,P61 例題,補例 兔子比烏龜跑的快,例題3 盡管有人聰明, 但未必一切人都聰明.,例題1 并非每個實數(shù)都是有理數(shù).,每個人都有自己喜歡的職業(yè).,R(x): x是實數(shù),設(shè) Q(x): x是有理數(shù),故符號化為: (x) (R(x) Q(x),M(x): x是人,設(shè) P(x): x是聰明的,(x)(P(x) M(x) ) (x)(M(x)P(x),命題邏輯 邏輯連接詞,作 業(yè),2-1， 2-2 （1）（e）,（f）,（g）,（h） 2-3 （3）,本節(jié)重點掌握的概念: 個體，謂詞, 量詞, 個體域。 本節(jié)重點掌握的方法: 命題符號

13、化。特別注意特 性謂詞的兩種使用方法。,謂詞邏輯 謂詞公式,1.個體和謂詞 2.謂詞的表示: P(x1,x2,.xn) 每個命題有一個謂詞和若干個體組成.當謂詞確定后, 命題的真值依賴個體,因此采用函數(shù)的記法表示謂詞,自變 量的取值范圍稱為個體域 D 3.量詞:當句子的主語是泛指的時候,必須引入量詞符號 4.特性謂詞: 若在全總個體域討論問題,還需在命題表達中 增加特性謂詞,以說明命題中個體的取值范圍. 5.命題符號化 “每個計算機系的學生都學離散數(shù)學“ “存在著偶素數(shù)”,謂詞邏輯 謂詞公式,北京是中國的首都 甲是乙的父親 3介于2與4之間 3大于2僅當3大于4。 張三和李四是同班同學 天下烏

14、鴉一般黑 火車都比汽車跑得快 有的火車比所有汽車快。,課堂練習,在謂詞邏輯中符號化：,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-5 等價式與蘊含式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,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

15、),a).,謂詞邏輯 謂詞公式,項代表公式中以各種形式出現(xiàn)的個體.,原子公式: 把A(t1, t2, tn)稱為謂詞演算的原子公式, 其中, t1, t2, tn是項.,不含個體變元的原子公式是原子命題.,定義 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) 所得到的公式是合式公式

16、。,簡稱謂詞公式,如,xy P( x, y),x P( f(x), y),謂詞邏輯 謂詞公式,P(a,y) Q,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),謂詞邏輯 謂詞公式,閉式:不含自由變元的公式. 開式:含有自由變元的公式. 其中,含有

17、k個自由變元 x1, x2,.xk的公式稱為 k元謂詞,記作A(x1,x2,.xk ),0元謂詞為閉式.,例如 ( x) P( x,y,z ),x是小于100的質(zhì)數(shù): L(x,100),又如 任意的實數(shù)x,都存在著實數(shù)y,使得xy.（不存在最大實數(shù)）,令 P(x,y): xy , R( x): x是實數(shù),x y(R( x)R(y) P( x, y ) ),謂詞邏輯 謂詞公式,閉式 (T),二元謂詞,一元謂詞,由命題符號化得到的公式是閉式.,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-4 謂詞公式的解釋,-5 等價式與蘊含式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,謂詞公式

18、的真值與那些因素有關(guān)?謂詞公式的真值能否像命題邏輯那樣總可由真值表給出?,例,xy (P(x) Q( f(x,a), y ,z )R) 的真值,給出個體域,指定謂詞,2-4.謂詞公式的解釋,指定個體函數(shù)和個體,指定自由變元,謂詞邏輯 謂詞公式的解釋,令 P(x,y): xy , D:自然數(shù),x y P( x, y )(閉命題),(F),例,(T);,令 P(x,y): x+y=0 ,D:自然數(shù),Q(x,y)P( x, y )(開命題),例,令D: 自然數(shù); P(x,y): xy; Q(x,y): x+y=0 ,令x=2, y=1, (T) ; 令 x=1, y=2, (F),為公式中的每個自由

19、變元指定個體域DI中的一個個體.,謂詞公式的一個解釋I(Interpretation),解釋I下的一個賦值,1).指定一個個體域DI. 2).為每個個體常元符號指定DI中的一個個體. 3).為每個n元個體函數(shù)符號指定DI上的n元個體函數(shù). 4).為每個n元謂詞符號指定一個DI上的n元謂詞,閉式在一解釋下有一確定真值.,開式在一組解釋I及I下一個賦值下, 有一確定真值.,補例,謂詞邏輯 謂詞公式的解釋,給定解釋I和I 中的賦值如下: DI:自然數(shù)集, L(x,y):xy, E(x,y):x=y, h(x,y):xy, v1: x=0, v2: x=1 求公式在解釋I下的真值.,(1) y (E(

20、x,y) L(x, y ),(2) yz E( h( y,z ), x ),解 在解釋I下 E(x,y)為 x=y; L(x, y )為xy,當賦值為v1時,命題解釋為:對任意自然數(shù)y,均有0y (T),當賦值為v2時,命題解釋為:對任意自然數(shù)y,均有1y (F),解 在解釋I下, E( h( y,z ), x ) 為 yz =x,當賦值為v1時,命題為:對任意自然數(shù)y,存在z 使得 yz=0 (T) 當賦值為v2時,命題為:對任意自然數(shù)y,存在z 使得 yz =1 (F),謂詞邏輯 謂詞公式的解釋,補例,補例,設(shè)解釋I的個體域為 a1, a2, an , 則在解釋I下,xA(x) A(a1)

21、A(a1).A(an),xA(x) A(a1)A(a1).A(an),當個體域DI中的元素個數(shù)有限時,可將變元的所有 可能取值一一列舉出來,此時量詞可消除.,謂詞邏輯 謂詞公式的解釋,謂詞邏輯 謂詞公式的解釋,求下列閉式在解釋I下的真值,給定解釋I如下:D= 2, 3 , f (2)=3, f (3)=2, P(2)=T P(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) )

22、=(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) = (T F) (F T) =T, yx Q( x, y)的真值?,補例,謂詞邏輯 謂詞公式的解釋,求(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,

23、1)(P(1) Q( 1, 2 ) (P(2) Q(2,1)(P(2) Q( 2,2 ),= (FT) (F T) (F F) ( T T) ),= F,補例,謂詞邏輯 謂詞公式的解釋,課堂練習 1.“并非一切推理都能用計算機完成”符號化為( ) 2.設(shè)R(x):x是實數(shù), P(x,y): x=y, 則命題“對任意的實數(shù) x, y, 有x+y= y+ x”符號化為( ) 3.不含有自由變元的謂詞公式是命題. ( ) 4. y E(x,y) L(x, y, z )是二元謂詞( ) 5.使一階邏輯公式 y x F(y ,x) 為真的解釋是 ( ) A.個體域為自然數(shù)集合，F(xiàn)(x,y)為 xy B.

24、個體域為自然數(shù)集合，F(xiàn)(x,y)為 yx C.個體域為自然數(shù)集合，F(xiàn)(x,y)為 x=y D. 均不屬于A、B、C 6.在解釋I:DI=a,b, P(a,a)=p(b,b)=0 P(a,b)=p(b,a)=1下, 公式x y P(x,y)的真值為_,作 業(yè),2-4 （2）（b）,（c） （3） (4) 2-5 （1）（b） （2） (a), (d),謂詞邏輯 謂詞公式的解釋,本節(jié)重點掌握的概念: 謂詞公式, 自由變元,約束變元, 開式, 閉式。 本節(jié)重點掌握的方法: 求謂詞公式的真值,要點回顧,謂詞邏輯 等價與蘊含式,1.個體和謂詞 2.謂詞的表示: P(x1,x2,.xn) 3.量詞 4.特

25、性謂詞 5.謂詞公式 6.謂詞公式的賦值: 對謂詞公式一個賦值稱為一個解釋。閉式在一組解釋下會求得一個真值；開式還需在此基礎(chǔ)上對自由變元賦值，才能求出一個真值。 例: 對任意的自然數(shù)x存在著自然數(shù)y ,使得 p(x,y) 成立. 解釋1：p(x,y) :x=y,(T) 解釋2：p(x,y) :x+y=0,(F),-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,-5 等價式與蘊含式,定義2-5.2, 2-5.3 如果公式A在任何解釋下均為真,稱A為永真式; 如果 A在某個解釋I和I的一個賦值下為真,稱A可滿足; 如果公

26、式在任何解釋下均 為假,稱A為永假式.,2-5 等價與蘊含,1.永真式,當個體域有限時,原則上可用真值表法判定一公式永真永假或可滿足；但當個體域無限時,真值表法失效.,代入定理 、 等價演算,永真(永假)式的判定：,謂詞邏輯 等價與蘊含式,命題邏輯永真式（永假式）的代換實例是謂詞邏輯的永真式（永假式）。,設(shè)A是包含命題變元 P1, P2,.Pn的命題公式, B1,B2,.Bn是謂詞公式, 用 B1,B2,.Bn 分別代替P1,P2,.Pn 在A中的所有出現(xiàn),得到的謂詞公式B稱A的代換實例,命題邏輯永真式的代換實例稱為重言式.,謂詞邏輯 等價與蘊含式,命題邏輯的代入定理:一個重言式,對同一分量都

27、用任何合式公式置換,結(jié)果仍重言.,謂詞邏輯 等價與蘊含式,上式可看作命題公式PP的代入實例,1) (x)P(x) (x)P(x),2 ) (xP(x)(xQ(x)xP(x) ),上式可看作命題公式 ( P(Q P) )的代入實例,而(P(Q P)(P (QP)F,所以, (xP(x)(xQ(x)x P(x) )為永假式,而PP T,所以, (x)P(x) (x)P(x)為重言式,判定公式的類型,重言式是永真式 ,但永真未必重言.,例如 xP( x ) xP( x ) 是永真式，但不是重言式.,補例,2.等價與蘊含,定義 2-5.1 設(shè)A,B是公式,若AB是永真式,則稱 A,B等價.記作AB.,

28、等價式的判定,等價演算:利用基本公式、等價的性質(zhì) 和 置換 定理，推演出其他等價式.,定義 2-5.2 設(shè)A,B是公式,若AB是永真式,則稱 A蘊含B.記作AB.,謂詞邏輯 等價與蘊含式,AB 當且僅當 A B且B A,(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),利用代入定理,將命題邏輯的所有等價式推廣到謂詞邏輯.,謂詞邏輯 等價與蘊含式,(2) 量詞與聯(lián)結(jié)詞的關(guān)

29、系,例 設(shè) 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),謂詞邏輯 等價與蘊含式,(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

30、) B),B (x) A(x) (B (x)A(x),B (x)A(x) (B (x)A(x),由上式可推出,謂詞邏輯 等價與蘊含式,(4) 量詞與聯(lián)結(jié)詞之間的一些等價式,例,第一式中用 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)歡會上所有人即唱歌又跳舞

31、. ”,謂詞邏輯 等價與蘊含式,(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) ?,(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)成立; 或?qū)λ械膞, B

32、(x)成立.,(x)A(x)(x)B(x):存在著x,使A(x)成立, 且存在x, 使B(x)成立.,(5) 量詞與聯(lián)結(jié)詞之間的一些蘊含式,(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,同理可得,謂詞邏輯 等價與蘊含式,(6) 多個量詞的使用,公式中多個量詞的出現(xiàn)次序關(guān)系到命題的含義,不能隨意交換.,例如,xy A(x,y): 對任意x ,都存在y, 使得A成立.,例 (x

33、) (y)(x+y=0) 為真命題 , y = -x,yxA (x,y) : 存在著y, 對所有的x 都有A成立.,(y) (x)(x+y=0) 為假命題,謂詞邏輯 等價與蘊含式,y 的值獨立于x .,y 的值依賴于x .,特殊情況:,全稱量詞之間可交換,存在量詞之間可交換.,全稱與存在之間存在如下關(guān)系:,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)

34、( y)(x)A(x,y),I23 (y) (x)A(x,y) ( x)(y)A(x,y),謂詞邏輯 等價與蘊含式,例題,謂詞邏輯 等價與蘊含式,右式,驗證 (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) 為永假式。,例題,謂詞邏輯 等價與蘊含式,(x)P(x) (x)P(x),分析真值法:左右 且 右左., 給定公式(x)P(x)(x)P(x) 一組解釋I,若 (x)P(

35、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)為假,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-5 等價式與蘊含式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,謂詞邏輯 前束范式,2-6前束范式,定義 2-6.1 一個公式,如果量詞均在全式的開頭,它們的作用域,延伸到整個公式的末尾,則該公式叫做前束范式。,前束范式簡記為:

36、,(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 任一謂詞公式,均和一個前束范式等價.,化前束范式的方法,(1).將公式中的連接詞化為,.(非必須) (2).利用否定律,德.摩根律,及量詞轉(zhuǎn)化律,將否 定深入到謂詞字母前. (3).利用換名規(guī)則或代入規(guī)則使所有約束變元均 不相同且使所有的自由變元與約束變元不同. (4).利用量詞的的擴張與收縮,擴大量詞的轄域 至整個公式.,謂詞邏輯 前束范式,例如 (x) P(x,y)Q(x),(x)P(x) (

37、x)Q(x),因為 (x)P(x) (y)P(y), (x)P(x) (y)P(y), 所以,若謂詞公式中有變元既約束出現(xiàn),又自由出現(xiàn),為避免混淆,可對約束變元進行換名或?qū)ψ杂勺冊? 使得一個變元在公式中只呈一種出現(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)

38、=?,代入規(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),謂詞邏輯 前束范式,(v1) (v2) (vn)(,其中可能是量詞或,vi (i=1,2,n)是指導變元, Aij是原子公式或其否定。,定義2-6.2 一個wff A如果具有如下形式稱為前束合取范式,例如 (x) (z) (y)( P(x ,y) (z=b) (Q(y)(a=

39、b),定理2-6.2 每一個wff A都可以轉(zhuǎn)換為與它等價的 前束合取范式。,謂詞邏輯 前束范式,其中可能是量詞或,vi (i=1,2,n)是客體變元,Aij是原子公式或其否定。,定義2-6.3 一個wff A如果具有如下形式稱為前束析取范式,例如 (x) (z) (y)( P(x, y) (z=b) (Q(y) (a=b),定理2-6.3 每一個wff A都可以轉(zhuǎn)換為與它等價的前束析取范式。,(v1) (v2) (vn)(,謂詞邏輯 前束范式,謂詞邏輯 前束范式,化前束范式的方法,(1).將公式中的連接詞化為,.(非必須) (2).利用否定律,德.摩根律,及量詞轉(zhuǎn)化律,將否 定深入到謂詞字母

40、前. (3).利用換名規(guī)則或代入規(guī)則使所有約束變元均 不相同且使所有的自由變元與約束變元不同. (4).利用量詞的的擴張與收縮,擴大量詞的轄域 至整個公式.,前束范式：(v1)(v2).(vn) A,謂詞邏輯 前束范式,例題 xyz(P(x,z)P(y,z)uQ(x,y,u) 化為前束析取范式 .,謂詞邏輯 前束范式,例題 x yP(x) zQ(z, y) yR(x, y) 的前束合取范式,原式,消去多余,xP(x)zQ(z, y)y R(x, y),換名,xP(x)zQ(z, y)wR(x, w),自由,w,消去其它,x(P(x)zQ(z, y)wR(x, w),否定深入,x(P(x)zQ(

41、z,y)wR(x,w),量詞提出,x zw(P(x)Q(z,y)R(x, w),分配律,xz w(P(x) R(x, w) (Q(z,y) R(x,w),量詞,w,聯(lián)結(jié)詞,前束析取范式,作 業(yè),2-5 （4）, （6） 2-6 (1) (a) (2) (a), (b),謂詞邏輯 前束范式,本節(jié)重點掌握的概念: 謂詞演算的永真式，重言式，等價式, 蘊含式; 前束范式. 本節(jié)重點掌握的方法: 證明永真式，等價式, 求前束合取范式, 析取范式.,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-5 等價式與蘊含式,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,-7 謂詞演算的推理理論,2-7

42、謂詞演算的推理理論,設(shè)H1,H2Hn和C是謂詞公式, 當且僅當 H1H2,HnC 稱C是一組前提H1,H2Hn的有效結(jié)論.,等價演算、 分析真值、 證明法。,判定謂詞公式永真的各種方法都可用于判斷推理正確性,謂詞邏輯 謂詞演算的推理.,等價演算：AB 即 A B T,例： xP(x) xQ(x) x（P(x) Q(x) ）,分析真值：設(shè)前件在一組解釋下為真,推出后件也真； 或證明后件在一組解釋下為假時，前件也為假。,要證C是一組前提H1,H2Hn的有效結(jié)論, 需證 : H1H2,HnC 是重言式 即證: H1,H2Hn 均為真時, C必為真. 為描述這樣一個推理過程,可構(gòu)造一個命題公式序列:

43、其中每個公式或是前提,或是由某些前提利用推理規(guī)則推出的.序列的最后一個命題公式就是所要結(jié)論.這樣一個描述推理過程的命題公式序 列稱為形式論證 (證明或演繹法).,證明法,謂詞邏輯 謂詞演算的推理.,P規(guī)則(前提引入規(guī)則):前提在推理過程中的任何 時候均可引用. T規(guī)則(結(jié)論引入規(guī)則):在推理過程中,如有一個或 多個公式蘊含公式 S,則 S可引入推導過程.,推理規(guī)則,命題邏輯 推理理論,由于謂詞公式中包含量詞,還需增加一組處理量詞的推理規(guī)則.,首先命題邏輯中的推理規(guī)則都可應用于謂詞邏輯的推理中:,謂詞邏輯 謂詞演算的推理.,(1)全稱指定規(guī)則 US,含義:若D中所有個體使A真,則 D中任一個體t

44、也使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 不能與其它指導變元同名.,(2)全稱推廣規(guī)則 UG,含義: 若D中任意一個體使A真,則D中所有個體都 使A真.,使用限制: x 不能是前提中的自由變元.,例: P(x) : x是偶數(shù) D:正整數(shù) . (1) P(x) P (2) (x) P(x) UG ?,謂詞邏輯 謂詞演算的推理.,(3)存在指定規(guī)則

45、 ES,含義:若D中存在個體使A真,則D中必有某個體c使A真.,使用限制:(x)A(x)為閉式,c為一個新常元(歧義名稱).,(4)存在推廣規(guī)則 EG,含義: 若項t使A真,則D中存在個體使A為真.,謂詞邏輯 謂詞演算的推理.,使用限制: x 不能與A(t)中的自由變元或指導變元同名,例,(2) (y) (x y) US,(3) x a ES,(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(

46、x) P,不是新常元,(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) .,謂詞邏輯 謂詞演算的推理.,不是新常元,例,(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)

47、 結(jié)論: (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,謂詞邏輯 謂詞演算的推理.,謂詞邏輯 謂詞演算的推理.,例題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,命題邏輯 邏輯連接

48、詞,例題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, I1,P77例題2,(10). (x)(Q(x)R(x) T9, EG,命題邏輯 邏輯連接詞,例題3 ( x)(P(x

49、) 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,例題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)

50、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, US,P77例題3,命題邏輯 邏輯連接詞,補例 所有的有理數(shù)是實數(shù). 某些有理數(shù)是整數(shù). 因此, 某些實數(shù)是整數(shù).,設(shè): R(x): x是實數(shù) Q(x): x是有理

51、數(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) ),命題邏輯 邏輯連接詞,補例 每個用功的學生考試不會不及格。 小張是用功的學生。 所以，小張考試及格。,設(shè): 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),命題邏輯 邏輯連接詞,4. 設(shè)R(x):x是實數(shù), P(x): x是有理數(shù), “并非每個實數(shù)都是有理數(shù)” 符號化為 (

52、) A. x ( ( R(x) P( x ) ) B. x ( R(x) P( x ) ) 5. 謂詞公式 x P(x)x Q(x)x P(x) 的類型是_. 6. 在解釋I:DI=1,2, P(1,1)= P(1,2) =0, P(2,2)=P(2,1)=1下, 謂詞公式 x y P(x,y)的真值為_ . 7. 公式x P(x)x Q(x,y) 前束合取范式為_.,課堂練習 1. 在謂詞邏輯中,永真式都是重言式。( ) 2. 任意謂詞公式都有唯一的前束范式與之等價。( ) 3. (x)(A(x)B(x) (x)A(x) (x)B(x) ( ),命題邏輯 邏輯連接詞,8 所有的有理數(shù)是實數(shù).

53、 所有的無理數(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) ）,命題邏輯 邏輯連接詞,作 業(yè),2-7 （1）（a）,（b） （2）,本節(jié)重點掌握的概念: 4個推理規(guī)則 本節(jié)重點掌握的方法: 推理的形式證明方法,謂 詞 邏 輯,Predicate Logic,第二章,本 章 小 結(jié),謂詞邏輯小結(jié),謂詞邏輯小結(jié),一. 謂詞的概念和表示,量詞和特性謂詞,謂詞,重點掌握的基本概念和

54、方法(一),個體和個體域,謂詞公式的翻譯 (命題符號化),一元謂詞: 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),謂詞邏輯小結(jié),重點掌握的基本概念和方法(二),二.謂詞公式及其解釋,謂詞公式的遞歸定義,謂詞公式的解釋 與賦值,變元的約束,求謂詞公式在一組解釋下的真值,有限域,無限域,指導變元與轄域 自由變元與約束變元 開式與閉式,1).指定個體域DI. 2).指定個體常元 3).指定個體函數(shù).

55、4).指定謂詞 5).指定自由變元,開 式,閉 式,謂詞邏輯小結(jié),三. 公式類型及相互關(guān)系,重點掌握的基本概念和方法(三),判別公式的類型或等價,公式的類型,等價公式AB : 即 AB 永真,蘊含公式AB : 即 AB 永真,代入定理,等價演算,分析真值,永真式與重言式 永假式 可滿足式,AB Iff AB且BA,謂詞邏輯小結(jié),四. 前束范式,重點掌握的基本概念和內(nèi)容(四),前束范式 (v1)(v2).(vn) A,前束析取范式 前束合取范式,換名規(guī)則,求前束范式的方法步驟,對約束變元換名 對自由變元代入,謂詞邏輯小結(jié),構(gòu)造推理證明,歸謬法,CP規(guī)則,直接證法,五. 推理理論,有效推理: H1H2,Hn C,推理規(guī)則:,重點掌握的基本概念和方法(五),前提引入規(guī)則 P 結(jié)論引入規(guī)則 T 全稱推廣規(guī)則 UG 存在推廣規(guī)則 EG 全稱指定規(guī)則 US 存在指定規(guī)則 ES,一.在謂詞邏輯中將命題符號化,1.判斷是否復合命題(看有幾個主謂結(jié)構(gòu)或連接詞). 2.對復合命題找出每個原子命題. 3.對每個原子命題分出主語和謂語,主語若是泛指需加量 詞和特性謂詞.并用符號表示. 4.分析各原子命題的關(guān)系,確定連接詞.,1.直線A平行于直線B ，當且僅當直線A不相交于直線B. 2.如果有限個數(shù)的乘積為0,則至少有一個因子等于0 3.對每一個實數(shù)x存在著一個更大的實數(shù)y. 4.存在著實數(shù)x,y,z