離散數(shù)學(xué)第二章

1、離散數(shù)學(xué)第二章第1頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六用命題邏輯處理蘇格拉底三段論：謂詞邏輯又例: 張華是大學(xué)生,李明也是大學(xué)生。所有的自然數(shù)都等于1.(F); 存在著自然數(shù)等于1.(T)PQR人總是要死的,蘇格拉底是人,蘇格拉底是要死的。若論證有效則有: PQR,即 PQR 永真.第2頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯對簡單命題作進(jìn)一步分析,分離出個體和謂詞,并考慮到泛指和特指 (全稱和存在),在此基礎(chǔ)上,研究命題的邏輯結(jié)構(gòu)及命題間的推理關(guān)系。Predicate Logic第二章第3頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期

2、六-1 謂詞的概念與表示-2 量詞-3 謂詞公式-5 等價式與重言式 -7 謂詞演算的推理理論26 前束范式謂詞邏輯 -4 謂詞公式的解釋第4頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題是具有確定真值的陳述句。2-1謂詞的概念和表示如 “電子計(jì)算機(jī)是科學(xué)技術(shù)的工具。”個體:思維的對象,可以是具體的事物或抽象的概念謂詞:刻畫個體性質(zhì)或個體之間關(guān)系的詞。1. 個體和謂詞 陳述句由主語和謂語兩部分構(gòu)成，主語謂語個體謂詞一元謂詞: 與一個個體相關(guān)聯(lián)的謂詞.(描述個體性質(zhì))N元謂詞: 與N個個體相關(guān)聯(lián)的謂詞.(描述個體間的關(guān)系)謂詞邏輯 謂詞的概念和表示第5頁，共117頁，2022年，

3、5月20日，1點(diǎn)52分，星期六(a).他是三好學(xué)生。(b).7 是質(zhì)數(shù)。(c).每天作廣播操是好習(xí)慣。(d).5 大于 3.(e).地球繞著太陽轉(zhuǎn)。一元謂詞。謂詞刻畫個體性質(zhì)(f).張明和張亮是兄弟。(e).上海位于南京和杭州之間。謂詞刻畫個體間關(guān)系。在謂詞邏輯中,命題是由一個謂詞和若干有序個體組成的。謂詞邏輯 謂詞的概念和表示二元謂詞二元謂詞二元謂詞三元謂詞第6頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六2.個體和謂詞的表示 命題由一個謂詞和若干個體組成謂詞邏輯 謂詞的概念和表示用大寫字母 A, B , C, D,. 代表謂詞。用小寫字母代表個體 ： 用小寫字母 a , b,

4、c. 表示特定個體: 個體常元 用小寫字母 x,y,z.表示任意個體：個體變元. 一個 n 元謂詞記作: A ( x1 , x2, xn)其中 x1 , x2,xn 為個體變元.當(dāng)A ( x1 , xn)中個體變元用個體常元: a1,an 代入后, A(a1an) 就成為一個命題。則 A (a) 表示命題: 張華是大學(xué)生, A (b) 表示命題: 李明是大學(xué)生。例: 令 A(x) : x 是大學(xué)生; a:張華 , b:李明第7頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題由一個謂詞和若干個體組成，但并非任意個體都和任意謂詞都能構(gòu)成命題。如 2 是偶數(shù),(T)個體域:個體的取值范

5、圍,用D表示 如謂詞 “. 是偶數(shù)” 的個體域 D: 全體整數(shù)。 “.是要死的” D:全體生物 或 D: 人類全總個體域:所有個體的集合稱之。謂詞邏輯 謂詞的概念和表示3 是偶數(shù),(F)x 是偶數(shù) (不是命題)當(dāng)謂詞確定后,其允許的個體取值范圍稱為個體域。則 A (a) 表示命題: 張華是大學(xué)生, A (b) 表示命題: 李明是大學(xué)生。例: 令 A(x) : x 是大學(xué)生; D:人類 a:張華 ,b:李明第8頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六又例: 上海位于南京和杭州之間。 令 L (x ,y,z) : x 位于 y 和 z 之間, D: 城市則命題符號化為: L(a,

6、b,c)謂詞邏輯 謂詞的概念和表示 則 L(2,3) 表示命題: 23. (真)又例: 設(shè) L (x,y) : x 小于 y, D: 實(shí)數(shù)集合 則 L(5,1):表示命題: 5謂詞的概念和表示3.復(fù)合命題第10頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例如: 張華的母親愛張華. 設(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)

7、, g(a,b) ) 或 P( 2+3, 23 ) 自變量和函數(shù)值均為個體域中的個體.用小寫字母f,g.表示.謂詞邏輯 量詞4.個體函數(shù)例如: 張華的母親愛張華.第11頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六-1 謂詞的概念與表示-2 量詞-3 謂詞公式-5 等價式與蘊(yùn)含式 -7 謂詞演算的推理理論26 前束范式謂詞邏輯 -4 謂詞公式的解釋第12頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例如: 任何人都是要死的.(T)有些人是聰明的.(T)所有的自然數(shù)都等于1.(F)存在著自然數(shù)等于1.(T)對個體域中的所有個體成立對個體域中的某些個體成立當(dāng)命題的主語是泛指

8、時,命題的真值還取決于謂詞與個體域中個體的數(shù)量關(guān)系.謂詞邏輯 量詞2-2量詞1.全稱量詞與存在量詞第13頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六兩種量詞:命題中表示個體數(shù)量的詞。全稱量詞(Universal Quantifier):表示個體域中全體個體的詞，記作 相當(dāng)于 “任意”,“凡是”,“所有”.若個體域中所有個體x,均使A(x)為真,記作(x)A(x)存在量詞(Existential Quantifier):表示個體域中部分個體的詞， 記作 相當(dāng)于 “存在”,“至少有一個”,“有些”.若個體域中存在某些個體x,使A(x)為真,記作(x)A(x)謂詞邏輯 量詞第14頁，共

9、117頁，2022年，5月20日，1點(diǎn)52分，星期六設(shè)H(x): x 是要死的, 任何人都是要死的。例如:則命題表示為: (x)H(x) 個體域D: 人類 又例如: 有些人是聰明的.設(shè)A(x): x是聰明的, 個體域 D:人類則命題表示為: (x)A(x)謂詞邏輯 量詞第15頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六當(dāng)在全總個體域中討論命題時,需在命題表示中增加一個特性謂詞,以給出個體變元的個體域。2.特性謂詞(1)帶全稱量詞的命題,特性謂詞作為 加入. 任何人都是要死的例如:M(x):x是人則命題表示為：(x)(M(x)H(x)改為:謂詞邏輯 量詞設(shè) H(x):x是要死的 個

10、體域D: 全人類 則命題表示為：(x)H(x)。H(x):x是要死的條件式的前件第16頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例如:有些人是聰明的.個體域 D：人設(shè)A(x)：x是聰明的,則命題表示為: (x)A(x)改為:A(x)：x是聰明的,則命題表示為: (x)(M(x)A(x)(2)帶存在量詞的命題,特性謂詞作為合取項(xiàng)加入。為何特性謂詞以前件加在全稱量詞后,而以合取項(xiàng)加在存在量詞后? 能否改為:(x)(H(x) M(x) 和 (x)(M(x) A(x) ?謂詞邏輯 量詞M(x):x是人第17頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六3.命題符號化謂詞邏輯

11、 量詞日常用語翻譯第18頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六用謂詞邏輯處理蘇格拉底三段論：人總是要死的,蘇格拉底是人,所以,蘇格拉底是要死的。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.判斷是否復(fù)合命題(看有幾個主謂結(jié)構(gòu)或連接詞).2.對復(fù)合命題找出每個原子命題.3.對每個原子命題分出主語和謂語,主語若是泛指需加量 詞和特性謂詞.并用符號表示.4.分析各原子命題的關(guān)系,確定連接詞.第19頁，共117頁，2022年，5月

12、20日，1點(diǎn)52分，星期六存在著最小的自然數(shù).謂詞邏輯 量詞P61 例題補(bǔ)例 兔子比烏龜跑的快例題3 盡管有人聰明, 但未必一切人都聰明.例題1 并非每個實(shí)數(shù)都是有理數(shù).每個人都有自己喜歡的職業(yè).R(x): x是實(shí)數(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)第20頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞作 業(yè)2-1， 2-2 （1）（e）,（f）,（g）,（h）2-3 （3） 本節(jié)重點(diǎn)掌握的概念: 個體，謂詞, 量詞, 個體域

13、。 本節(jié)重點(diǎn)掌握的方法: 命題符號化。特別注意特 性謂詞的兩種使用方法。第21頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 謂詞公式1.個體和謂詞2.謂詞的表示: P(x1,x2,.xn) 每個命題有一個謂詞和若干個體組成.當(dāng)謂詞確定后,命題的真值依賴個體,因此采用函數(shù)的記法表示謂詞,自變量的取值范圍稱為個體域 D3.量詞:當(dāng)句子的主語是泛指的時候,必須引入量詞符號4.特性謂詞: 若在全總個體域討論問題,還需在命題表達(dá)中增加特性謂詞,以說明命題中個體的取值范圍.5.命題符號化 “每個計(jì)算機(jī)系的學(xué)生都學(xué)離散數(shù)學(xué)“ “存在著偶素數(shù)”第22頁，共117頁，2022年，5月20日

14、，1點(diǎn)52分，星期六謂詞邏輯 謂詞公式北京是中國的首都甲是乙的父親3介于2與4之間3大于2僅當(dāng)3大于4。張三和李四是同班同學(xué)天下烏鴉一般黑火車都比汽車跑得快有的火車比所有汽車快。 課堂練習(xí)在謂詞邏輯中符號化：第23頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六-1 謂詞的概念與表示-2 量詞-3 謂詞公式-5 等價式與蘊(yùn)含式 -7 謂詞演算的推理理論26 前束范式謂詞邏輯 -4 謂詞公式的解釋第24頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六2-3謂詞公式如 P, P(x), P(x,y), P( f(x), y ), P(a, y) 均原子公式。1. 謂詞公式 補(bǔ)充

15、定義(項(xiàng))1).個體常元和個體變元是項(xiàng). 2).若f 是n元個體函數(shù),t1,.,tn是項(xiàng),則 f(t1,.tn)是項(xiàng).3).只有有限次運(yùn)用1),2)規(guī)則得到的符號串是項(xiàng).如 x, a, f(x), g(x,y), g( f (x),a).謂詞邏輯 謂詞公式項(xiàng)代表公式中以各種形式出現(xiàn)的個體.原子公式: 把A(t1, t2, tn)稱為謂詞演算的原子公式,其中, t1, t2, tn是項(xiàng).不含個體變元的原子公式是原子命題.第25頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六定義 2-3.1 謂詞演算的合式公式wff,由下述各條組成：(1)原子謂詞公式是合式公式。(2)若A是合式公式,則

16、A是合式公式。(3)若A和B都是合式公式,則(AB),(AB), (AB)和(AB) 是合式公式。(4)如果A是合式公式,x是A中出現(xiàn)的任何變元, 則 (x)A和 (x)A都是合式公式。(5)只有經(jīng)過有限次的應(yīng)用規(guī)則(1),(2),(3),(4) 所得到的公式是合式公式。簡稱謂詞公式如 xy P( x, y), x P( f(x), y),謂詞邏輯 謂詞公式P(a,y) Q 第26頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六2.變元的約束 若給定為一謂詞公式,它可帶有如下子公式: ( x) A( x ) 或 ( x) A( x )指導(dǎo)變元轄域約束變元其中,、 后的 x 稱為該量詞

17、的指導(dǎo)變元; A(x)稱為量詞的作用域或轄域(scope);在轄域中 x 的一切出現(xiàn)稱為x在中的約束出現(xiàn),x稱為約束變元;在中除約束變元以外所出現(xiàn)的變元稱為自由變元。P63例題1如x(M(x)R(x) , yP(x, y)R(y) 謂詞邏輯 謂詞公式第27頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六 閉式:不含自由變元的公式. 開式:含有自由變元的公式. 其中,含有k個自由變元 x1, x2,.xk的公式稱為 k元謂詞,記作A(x1,x2,.xk ),0元謂詞為閉式.例如 ( x) P( x,y,z ) x是小于100的質(zhì)數(shù): L(x,100)又如 任意的實(shí)數(shù)x,都存在著實(shí)數(shù)y,

18、使得xy.（不存在最大實(shí)數(shù)） 令 P(x,y): x謂詞公式 閉式 (T) 二元謂詞一元謂詞由命題符號化得到的公式是閉式.第28頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六-1 謂詞的概念與表示-2 量詞-3 謂詞公式 -4 謂詞公式的解釋-5 等價式與蘊(yùn)含式 -7 謂詞演算的推理理論26 前束范式謂詞邏輯第29頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞公式的真值與那些因素有關(guān)?謂詞公式的真值能否像命題邏輯那樣總可由真值表給出?例xy (P(x) Q( f(x,a), y ,z )R) 的真值給出個體域指定謂詞2-4.謂詞公式的解釋指定個體函數(shù)和個體指定自由變

19、元謂詞邏輯 謂詞公式的解釋令 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): x謂詞公式的解釋第31頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六 給定解釋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(x,y) L(x, y )(2) yz E( h( y,z ), x ) 解 在解釋I

20、下 E(x,y)為 x=y; L(x, y )為x謂詞公式的解釋補(bǔ)例第32頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六補(bǔ)例 設(shè)解釋I的個體域?yàn)?a1, a2, an , 則在解釋I下, xA(x) A(a1)A(a1).A(an)xA(x) A(a1)A(a1).A(an)當(dāng)個體域DI中的元素個數(shù)有限時,可將變元的所有可能取值一一列舉出來,此時量詞可消除.謂詞邏輯 謂詞公式的解釋第33頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 謂詞公式的解釋求下列閉式在解釋I下的真值 給定解釋I如下:D= 2, 3 , f (2)=3, f (3)=2, P(2)=T P

21、(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) = (T F) (F T) =T yx Q( x, y)的真值?補(bǔ)例第34頁，共117頁，2022年，5月2

22、0日，1點(diǎn)52分，星期六謂詞邏輯 謂詞公式的解釋 求(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) (F T) (F F) ( T T) )= F補(bǔ)例第35頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 謂詞公式的解釋課堂練習(xí)1.“并非一切推理都能用

23、計(jì)算機(jī)完成”符號化為( )2.設(shè)R(x):x是實(shí)數(shù), P(x,y): x=y, 則命題“對任意的實(shí)數(shù) x, y, 有x+y= y+ x”符號化為( ) 3.不含有自由變元的謂詞公式是命題. ( ) 4. y E(x,y) L(x, y, z )是二元謂詞( )5.使一階邏輯公式 y x F(y ,x) 為真的解釋是 ( )A.個體域?yàn)樽匀粩?shù)集合，F(xiàn)(x,y)為 xy B.個體域?yàn)樽匀粩?shù)集合，F(xiàn)(x,y)為 y謂詞公式的解釋 本節(jié)重點(diǎn)掌握的概念: 謂詞公式, 自由變元,約束變元, 開式, 閉式。本節(jié)重點(diǎn)掌握的方法: 求謂詞公式的真值第37頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六

24、要點(diǎn)回顧謂詞邏輯 等價與蘊(yùn)含式1.個體和謂詞2.謂詞的表示: P(x1,x2,.xn)3.量詞4.特性謂詞5.謂詞公式6.謂詞公式的賦值: 對謂詞公式一個賦值稱為一個解釋。閉式在一組解釋下會求得一個真值；開式還需在此基礎(chǔ)上對自由變元賦值，才能求出一個真值。 例: 對任意的自然數(shù)x存在著自然數(shù)y ,使得 p(x,y) 成立. 解釋1：p(x,y) :x等價與蘊(yùn)含式第40頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯永真式（永假式）的代換實(shí)例是謂詞邏輯的永真式（永假式）。設(shè)A是包含命題變元 P1, P2,.Pn的命題公式, B1,B2,.Bn是謂詞公式, 用 B1,B2,.Bn

25、 分別代替P1,P2,.Pn 在A中的所有出現(xiàn),得到的謂詞公式B稱A的代換實(shí)例,命題邏輯永真式的代換實(shí)例稱為重言式.謂詞邏輯 等價與蘊(yùn)含式命題邏輯的代入定理:一個重言式,對同一分量都用任何合式公式置換,結(jié)果仍重言.第41頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 等價與蘊(yùn)含式上式可看作命題公式PP的代入實(shí)例1) (x)P(x) (x)P(x) 2 ) (xP(x)(xQ(x)xP(x) ) 上式可看作命題公式 ( P(Q P) )的代入實(shí)例 而(P(Q P)(P (QP)F 所以, (xP(x)(xQ(x)x P(x) )為永假式而PP T,所以, (x)P(x) (x

26、)P(x)為重言式 判定公式的類型重言式是永真式 ,但永真未必重言. 例如 xP( x ) xP( x ) 是永真式，但不是重言式.補(bǔ)例第42頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六2.等價與蘊(yùn)含定義 2-5.1 設(shè)A,B是公式,若AB是永真式,則稱A,B等價.記作AB.等價式的判定等價演算:利用基本公式、等價的性質(zhì) 和 置換 定理，推演出其他等價式.定義 2-5.2 設(shè)A,B是公式,若AB是永真式,則稱A蘊(yùn)含B.記作AB.謂詞邏輯 等價與蘊(yùn)含式AB 當(dāng)且僅當(dāng) A B且B A第43頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(1) 命題公式的推廣例如 PQPQ

27、用 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) 利用代入定理,將命題邏輯的所有等價式推廣到謂詞邏輯.謂詞邏輯 等價與蘊(yùn)含式第44頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(2) 量詞與聯(lián)結(jié)詞的關(guān)系例 設(shè) P(x) : x今天來校上課, D:學(xué)生 則 P(x)表示: x今天沒來校上課 “并非所有人今天來校上課” (x)P(x) 等價 “有人今天沒來校上課” (x)P(x) (x)P(x) (x)

28、P(x) “ 沒有人今天來校上課” (x) P(x) 等價 “所有人今天都沒來校上課” (x)P(x) (x) P(x) (x)P(x)謂詞邏輯 等價與蘊(yùn)含式第45頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(3) 量詞作用域的擴(kuò)張與收縮(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)由上式可推出謂詞邏輯 等價與蘊(yùn)含式第46頁，共117頁，20

29、22年，5月20日，1點(diǎn)52分，星期六(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)歡會上所有人即唱歌又跳舞. ” 謂詞邏輯 等價與蘊(yùn)含式(x)(A(x)B(x) (x)A(x)(x)B(x)第47頁，共117頁，2022年

30、，5月20日，1點(diǎn)52分，星期六 (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) 謂詞邏輯 等價與蘊(yùn)含式(x)A(x) (x)B(x): 對所有的x , A(x)成立; 或?qū)λ械膞, B(x)成立. (x)A(x)(x)B(x):存在著x,使A(

31、x)成立, 且存在x, 使B(x)成立. 第48頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(5) 量詞與聯(lián)結(jié)詞之間的一些蘊(yù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)常見的等價式與蘊(yùn)含式見表2-5.1同理可得謂詞邏輯 等價與蘊(yùn)含式第49頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(6) 多個量詞的使用公式中多個量詞的出現(xiàn)次序關(guān)系到命題的含義,不能隨意交換.例如 xy A(x,y):

32、 對任意x ,都存在y, 使得A成立.例 (x) (y)(x+y=0) 為真命題 , y = -x yxA (x,y) : 存在著y, 對所有的x 都有A成立. (y) (x)(x+y=0) 為假命題謂詞邏輯 等價與蘊(yùn)含式 y 的值獨(dú)立于x .y 的值依賴于x .第50頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六特殊情況:全稱量詞之間可交換,存在量詞之間可交換.全稱與存在之間存在如下關(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

33、(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)謂詞邏輯 等價與蘊(yùn)含式xyy xyxy xyxxy xyyx第51頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例題謂詞邏輯 等價與蘊(yùn)含式右式驗(yàn)證 (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(

34、x) 為永假式。 第52頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例題謂詞邏輯 等價與蘊(yùn)含式 (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)為假,第53頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六-1 謂詞的概念

35、與表示-2 量詞-3 謂詞公式-5 等價式與蘊(yùn)含式 -7 謂詞演算的推理理論26 前束范式謂詞邏輯 -4 謂詞公式的解釋第54頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 前束范式2-6前束范式定義 2-6.1 一個公式,如果量詞均在全式的開頭,它們的作用域,延伸到整個公式的末尾,則該公式叫做前束范式。前束范式簡記為:(v1)(v2).(vn) A或指導(dǎo)變元母式(不含量詞)例如 (x) (y) (z)( Q(x,y) R(z) (x)P(x) ( x)Q(x) ? Q(x,y) R(z)定理2-6.1 任一謂詞公式,均和一個前束范式等價.第55頁，共117頁，2022年，

36、5月20日，1點(diǎn)52分，星期六化前束范式的方法 (1).將公式中的連接詞化為,.(非必須) (2).利用否定律,德.摩根律,及量詞轉(zhuǎn)化律,將否 定深入到謂詞字母前. (3).利用換名規(guī)則或代入規(guī)則使所有約束變元均 不相同且使所有的自由變元與約束變元不同. (4).利用量詞的的擴(kuò)張與收縮,擴(kuò)大量詞的轄域 至整個公式.謂詞邏輯 前束范式例如 (x) P(x,y)Q(x)(x)P(x) (x)Q(x) 第56頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六因?yàn)?(x)P(x) (y)P(y), (x)P(x) (y)P(y),所以,若謂詞公式中有變元既約束出現(xiàn),又自由出現(xiàn),為避免混淆,可對

37、約束變元進(jìn)行換名或?qū)ψ杂勺冊?使得一個變元在公式中只呈一種出現(xiàn). (1)對約束變元換名,其更改的變元名稱范圍是:量詞 中的指導(dǎo)變元及該量詞轄域中出現(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)=?第57頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六代入規(guī)則(1).代入須對公式中該自由變元的所有出現(xiàn)同 時進(jìn)行.(2).代入的變元不能與公式中其它變元

38、同名. 例如 (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) 謂詞邏輯 前束范式第58頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(v1) (v2) (vn)(其中可能是量詞或,vi (i=1,2,n)是指導(dǎo)變元, Aij是原子公式或其否定。定義2-6.2 一個wff A如果具有如下形式稱為前束合取范式例如 (x) (z) (y)( P(x ,y) (z=b) (Q(y)(a=b)定理2-6.2 每一個wff A都可以轉(zhuǎn)換為與它等價的

39、前束合取范式。謂詞邏輯 前束范式第59頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六其中可能是量詞或,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)(謂詞邏輯 前束范式第60頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 前束范式化前束范式的方法 (1).將公式中的連接詞化為,.(非必須) (2).利用否定律,

40、德.摩根律,及量詞轉(zhuǎn)化律,將否 定深入到謂詞字母前. (3).利用換名規(guī)則或代入規(guī)則使所有約束變元均 不相同且使所有的自由變元與約束變元不同. (4).利用量詞的的擴(kuò)張與收縮,擴(kuò)大量詞的轄域 至整個公式.前束范式：(v1)(v2).(vn) A第61頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 前束范式例題 xyz(P(x,z)P(y,z)uQ(x,y,u) 化為前束析取范式 .第62頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 前束范式例題 x yP(x) zQ(z, y) yR(x, y)的前束合取范式原式消去多余xP(x)zQ(z, y)y R

41、(x, y)換名xP(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)分配律 xz w(P(x) R(x, w) (Q(z,y) R(x,w)量詞w聯(lián)結(jié)詞前束析取范式第63頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六作 業(yè)2-5 （4）, （6） 2-6 (1) (a) (2) (a), (b)謂詞邏輯 前束范式本節(jié)重點(diǎn)掌握的概念: 謂詞演算的永真式，重言式，等價式, 蘊(yùn)含式; 前束范式.本節(jié)重點(diǎn)掌握的方法: 證明永真式，等價式, 求前

42、束合取范式, 析取范式.第64頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六-1 謂詞的概念與表示-2 量詞-3 謂詞公式-5 等價式與蘊(yùn)含式 26 前束范式謂詞邏輯 -4 謂詞公式的解釋 -7 謂詞演算的推理理論第65頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六2-7 謂詞演算的推理理論 設(shè)H1,H2Hn和C是謂詞公式, 當(dāng)且僅當(dāng) H1H2,HnC稱C是一組前提H1,H2Hn的有效結(jié)論.等價演算、 分析真值、 證明法。判定謂詞公式永真的各種方法都可用于判斷推理正確性謂詞邏輯 謂詞演算的推理. 等價演算：AB 即 A B T例： xP(x) xQ(x) x（P(x)

43、Q(x) ） 分析真值：設(shè)前件在一組解釋下為真,推出后件也真； 或證明后件在一組解釋下為假時，前件也為假。第66頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六要證C是一組前提H1,H2Hn的有效結(jié)論, 需證 : H1H2,HnC 是重言式 即證: H1,H2Hn 均為真時, C必為真. 為描述這樣一個推理過程,可構(gòu)造一個命題公式序列: 其中每個公式或是前提,或是由某些前提利用推理規(guī)則推出的.序列的最后一個命題公式就是所要結(jié)論.這樣一個描述推理過程的命題公式序列稱為形式論證 (證明或演繹法).證明法謂詞邏輯 謂詞演算的推理.第67頁，共117頁，2022年，5月20日，1點(diǎn)52分，星

44、期六P規(guī)則(前提引入規(guī)則):前提在推理過程中的任何時候均可引用.T規(guī)則(結(jié)論引入規(guī)則):在推理過程中,如有一個或多個公式蘊(yùn)含公式 S,則 S可引入推導(dǎo)過程.推理規(guī)則命題邏輯 推理理論 由于謂詞公式中包含量詞,還需增加一組處理量詞的推理規(guī)則. 首先命題邏輯中的推理規(guī)則都可應(yīng)用于謂詞邏輯的推理中:第68頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 謂詞演算的推理.(1)全稱指定規(guī)則 US含義:若D中所有個體使A真,則 D中任一個體t也使A真.例 (x) (y) (x y) P (不存在最大實(shí)數(shù)) 例 (x) P(x) : 所有的人都是要死的 P P(a) : 蘇格拉底是要死的

45、. US (y) (a y) US 或 (y) (x y) US (y) (y謂詞演算的推理.第70頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(3)存在指定規(guī)則 ES含義:若D中存在個體使A真,則D中必有某個體c使A真. 使用限制:(x)A(x)為閉式,c為一個新常元(歧義名稱).(4)存在推廣規(guī)則 EG含義: 若項(xiàng)t使A真,則D中存在個體使A為真.謂詞邏輯 謂詞演算的推理. 使用限制: x 不能與A(t)中的自由變元或指導(dǎo)變元同名第71頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例 (2) (y) (x y) US (3) x a ES(1) (x) (y) (

46、x y) P取 D:有理數(shù)(4) (x) (x a) UG(5) (y) (x) (x 謂詞演算的推理.不是閉式例 (2) F(a) ES 證明: (x) F(x) F(a) (1) (x) F(x) P不是新常元第72頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六(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í)數(shù)(1) (x)Q(x) P(2) (x)Q(x) P (3) Q(a) T1, ES (

47、4) Q(b) T2, ES(5) .謂詞邏輯 謂詞演算的推理.不是新常元第73頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例 (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)結(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謂詞邏輯 謂詞演算的推理.第74頁，共11

48、7頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯 謂詞演算的推理.例題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第75頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞例題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).

49、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第76頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞例題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)

50、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第77頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六例題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

51、 (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第78頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞補(bǔ)例 所有的有理數(shù)是實(shí)數(shù). 某些有理數(shù)是整數(shù). 因此, 某些實(shí)數(shù)是整數(shù). 設(shè): R(x): x是實(shí)數(shù) Q(x): x是有理數(shù) P(x): x是整數(shù)x(Q(x) R

52、(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) )第79頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞補(bǔ)例 每個用功的學(xué)生考試不會不及格。 小張是用功的學(xué)生。 所以，小張考試及格。設(shè): P(x): x考試及格 Q(x): x是學(xué)生 R(x): x是用功的。 a:小張x（Q(x) R(x) P(x)）R (a) Q(a) P (a) Q(a)第80頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞 4. 設(shè)R(x):x是實(shí)數(shù),

53、P(x): x是有理數(shù), “并非每個實(shí)數(shù)都是有理數(shù)” 符號化為 ( ) 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) 前束合取范式為_.課堂練習(xí)1. 在謂詞邏輯中,永真式都是重言式。( )2. 任意謂詞公式都有唯一的前束范式與之等價。( ) 3. (x)(A(x)B(x) (x)A(x) (x)B

54、(x) ( ) 第81頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞 8 所有的有理數(shù)是實(shí)數(shù). 所有的無理數(shù)是實(shí)數(shù). 虛數(shù)不是實(shí)數(shù)， 所以虛數(shù)不是有理數(shù)也不是無理數(shù). 設(shè): R(x): x是實(shí)數(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) ）第82頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六命題邏輯 邏輯連接詞作 業(yè)2-7 （1）（a）,（b） （2） 本節(jié)重點(diǎn)掌握的概念: 4個推理規(guī)則本節(jié)重點(diǎn)掌握的方法: 推理的形式

55、證明方法第83頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂 詞 邏 輯Predicate Logic第二章本 章 小 結(jié)謂詞邏輯小結(jié) 第84頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯小結(jié) 一. 謂詞的概念和表示 量詞和特性謂詞 謂詞重點(diǎn)掌握的基本概念和方法(一) 個體和個體域謂詞公式的翻譯 (命題符號化)一元謂詞: 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)第85頁，共1

56、17頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯小結(jié) 重點(diǎn)掌握的基本概念和方法(二)二.謂詞公式及其解釋 謂詞公式的遞歸定義 謂詞公式的解釋 與賦值 變元的約束 求謂詞公式在一組解釋下的真值有限域無限域 指導(dǎo)變元與轄域 自由變元與約束變元 開式與閉式1).指定個體域DI.2).指定個體常元3).指定個體函數(shù).4).指定謂詞5).指定自由變元開式閉式第86頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯小結(jié) 三. 公式類型及相互關(guān)系重點(diǎn)掌握的基本概念和方法(三)判別公式的類型或等價 公式的類型 等價公式AB : 即 AB 永真 蘊(yùn)含公式AB : 即 AB 永真代入定理

57、等價演算分析真值 永真式與重言式 永假式 可滿足式 AB Iff AB且BA第87頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯小結(jié) 四. 前束范式重點(diǎn)掌握的基本概念和內(nèi)容(四) 前束范式 (v1)(v2).(vn) A 前束析取范式 前束合取范式 換名規(guī)則求前束范式的方法步驟 對約束變元換名 對自由變元代入第88頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯小結(jié) 構(gòu)造推理證明歸謬法CP規(guī)則直接證法五. 推理理論 有效推理: H1H2,Hn C 推理規(guī)則:重點(diǎn)掌握的基本概念和方法(五) 前提引入規(guī)則 P 結(jié)論引入規(guī)則 T 全稱推廣規(guī)則 UG 存在推廣規(guī)則

58、 EG 全稱指定規(guī)則 US 存在指定規(guī)則 ES 第89頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六一.在謂詞邏輯中將命題符號化1.判斷是否復(fù)合命題(看有幾個主謂結(jié)構(gòu)或連接詞).2.對復(fù)合命題找出每個原子命題.3.對每個原子命題分出主語和謂語,主語若是泛指需加量 詞和特性謂詞.并用符號表示.4.分析各原子命題的關(guān)系,確定連接詞.1.直線A平行于直線B ，當(dāng)且僅當(dāng)直線A不相交于直線B.2.如果有限個數(shù)的乘積為0,則至少有一個因子等于03.對每一個實(shí)數(shù)x存在著一個更大的實(shí)數(shù)y.4.存在著實(shí)數(shù)x,y,z,使得x與y之和大于x與y之積.5.若xy, zy*z謂詞邏輯小結(jié) 第90頁，共117

59、頁，2022年，5月20日，1點(diǎn)52分，星期六謂詞邏輯小結(jié) 二.求公式在給定解釋下的真值P66 3) a) x( P(x) Q(x) ) (T)其中, P(x): x=1 ,Q(x):x=2 , D:1, 2 P66 3) b) x( PQ(x) ) R(a) (F)其中, P: 21 , Q(x):x5, a=5, D:-2, 3, 6 P72 2) d) xy (P(x)Q(x,y) ) (F)其中, D:1, 2 ,a=1; P(1)=F , P(2)=T, Q(1,1)=T , Q(1, 2)=T, Q(2,1)=F ,Q(2, 2)=F xA(x) A(a1)A(a1).A(an)

60、xA(x) A(a1)A(a1).A(an)DI為有限域第91頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六三.判定公式類型和等價1.證明謂詞公式A是命題永真式的代入實(shí)例(重言式)2.利用等價演算證明公式AT3.證明蘊(yùn)含AB, 只需證AB永真.P72 7) x y ( p(x) Q(y) ) x p(x) y Q(y) P72 4) x(A(x) B(x) xA(x) x B(x) 謂詞邏輯小結(jié) 第92頁，共117頁，2022年，5月20日，1點(diǎn)52分，星期六四.求前束范式P75 2) a) (xP(x) xQ(x) ) x (P(x) Q(x) T P75 2) b) x ( p