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

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

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

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

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

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

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

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

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

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

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

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

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

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

14、鴉一般黑 火車都比汽車跑得快 有的火車比所有汽車快。,課堂練習(xí),在謂詞邏輯中符號(hào)化：,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-5 等價(jià)式與蘊(yùn)含式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,2-3謂詞公式,如 P, P(x), P(x,y), P( f(x), y ), P(a, y) 均原子公式。,1. 謂詞公式,補(bǔ)充定義(項(xiàng)) 1).個(gè)體常元和個(gè)體變?cè)琼?xiàng). 2).若f 是n元個(gè)體函數(shù),t1,.,tn是項(xiàng),則 f(t1,.tn)是項(xiàng). 3).只有有限次運(yùn)用1),2)規(guī)則得到的符號(hào)串是項(xiàng).,如 x, a, f(x), g(x,y), g( f (x

15、),a).,謂詞邏輯 謂詞公式,項(xiàng)代表公式中以各種形式出現(xiàn)的個(gè)體.,原子公式: 把A(t1, t2, tn)稱為謂詞演算的原子公式, 其中, t1, t2, tn是項(xiàng).,不含個(gè)體變?cè)脑庸绞窃用}.,定義 2-3.1 謂詞演算的合式公式wff,由下述各條組成： (1)原子謂詞公式是合式公式。 (2)若A是合式公式,則A是合式公式。 (3)若A和B都是合式公式,則(AB),(AB), (AB)和(AB) 是合式公式。 (4)如果A是合式公式,x是A中出現(xiàn)的任何變?cè)? 則 (x)A和 (x)A都是合式公式。 (5)只有經(jīng)過有限次的應(yīng)用規(guī)則(1),(2),(3),(4) 所得到的公式是合式公式

16、。,簡(jiǎn)稱謂詞公式,如,xy P( x, y),x P( f(x), y),謂詞邏輯 謂詞公式,P(a,y) Q,2.變?cè)募s束,若給定為一謂詞公式,它可帶有如下子公式:,( x) A( x ) 或 ( x) A( x ),指導(dǎo)變?cè)?轄域,約束變?cè)?其中,、 后的 x 稱為該量詞的指導(dǎo)變?cè)? A(x)稱為量詞的作用域或轄域(scope);在轄域中 x 的一切出現(xiàn)稱為x在中的約束出現(xiàn),x稱為約束變?cè)?在中除約束變?cè)酝馑霈F(xiàn)的變?cè)Q為自由變?cè)?P63例題1,如,x(M(x)R(x) ,yP(x, y)R(y),謂詞邏輯 謂詞公式,閉式:不含自由變?cè)墓? 開式:含有自由變?cè)墓? 其中,含有

17、k個(gè)自由變?cè)?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,使得xy.（不存在最大實(shí)數(shù)）,令 P(x,y): xy , R( x): x是實(shí)數(shù),x y(R( x)R(y) P( x, y ) ),謂詞邏輯 謂詞公式,閉式 (T),二元謂詞,一元謂詞,由命題符號(hào)化得到的公式是閉式.,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-4 謂詞公式的解釋,-5 等價(jià)式與蘊(yùn)含式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,謂詞公式

18、的真值與那些因素有關(guān)?謂詞公式的真值能否像命題邏輯那樣總可由真值表給出?,例,xy (P(x) Q( f(x,a), y ,z )R) 的真值,給出個(gè)體域,指定謂詞,2-4.謂詞公式的解釋,指定個(gè)體函數(shù)和個(gè)體,指定自由變?cè)?謂詞邏輯 謂詞公式的解釋,令 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),為公式中的每個(gè)自由

19、變?cè)付▊€(gè)體域DI中的一個(gè)個(gè)體.,謂詞公式的一個(gè)解釋I(Interpretation),解釋I下的一個(gè)賦值,1).指定一個(gè)個(gè)體域DI. 2).為每個(gè)個(gè)體常元符號(hào)指定DI中的一個(gè)個(gè)體. 3).為每個(gè)n元個(gè)體函數(shù)符號(hào)指定DI上的n元個(gè)體函數(shù). 4).為每個(gè)n元謂詞符號(hào)指定一個(gè)DI上的n元謂詞,閉式在一解釋下有一確定真值.,開式在一組解釋I及I下一個(gè)賦值下, 有一確定真值.,補(bǔ)例,謂詞邏輯 謂詞公式的解釋,給定解釋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,當(dāng)賦值為v1時(shí),命題解釋為:對(duì)任意自然數(shù)y,均有0y (T),當(dāng)賦值為v2時(shí),命題解釋為:對(duì)任意自然數(shù)y,均有1y (F),解 在解釋I下, E( h( y,z ), x ) 為 yz =x,當(dāng)賦值為v1時(shí),命題為:對(duì)任意自然數(shù)y,存在z 使得 yz=0 (T) 當(dāng)賦值為v2時(shí),命題為:對(duì)任意自然數(shù)y,存在z 使得 yz =1 (F),謂詞邏輯 謂詞公式的解釋,補(bǔ)例,補(bǔ)例,設(shè)解釋I的個(gè)體域?yàn)?a1, a2, an , 則在解釋I下,xA(x) A(a1)

21、A(a1).A(an),xA(x) A(a1)A(a1).A(an),當(dāng)個(gè)體域DI中的元素個(gè)數(shù)有限時(shí),可將變?cè)乃?可能取值一一列舉出來,此時(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)的真值?,補(bǔ)例,謂詞邏輯 謂詞公式的解釋,求(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,補(bǔ)例,謂詞邏輯 謂詞公式的解釋,課堂練習(xí) 1.“并非一切推理都能用計(jì)算機(jī)完成”符號(hào)化為( ) 2.設(shè)R(x):x是實(shí)數(shù), P(x,y): x=y, 則命題“對(duì)任意的實(shí)數(shù) x, y, 有x+y= y+ x”符號(hào)化為( ) 3.不含有自由變?cè)闹^詞公式是命題. ( ) 4. y E(x,y) L(x, y, z )是二元謂詞( ) 5.使一階邏輯公式 y x F(y ,x) 為真的解釋是 ( ) A.個(gè)體域?yàn)樽匀粩?shù)集合，F(xiàn)(x,y)為 xy B.

24、個(gè)體域?yàn)樽匀粩?shù)集合，F(xiàn)(x,y)為 yx C.個(gè)體域?yàn)樽匀粩?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é)重點(diǎn)掌握的概念: 謂詞公式, 自由變?cè)?約束變?cè)? 開式, 閉式。 本節(jié)重點(diǎn)掌握的方法: 求謂詞公式的真值,要點(diǎn)回顧,謂詞邏輯 等價(jià)與蘊(yùn)含式,1.個(gè)體和謂詞 2.謂詞的表示: P(x1,x2,.xn) 3.量詞 4.特

25、性謂詞 5.謂詞公式 6.謂詞公式的賦值: 對(duì)謂詞公式一個(gè)賦值稱為一個(gè)解釋。閉式在一組解釋下會(huì)求得一個(gè)真值；開式還需在此基礎(chǔ)上對(duì)自由變?cè)x值，才能求出一個(gè)真值。 例: 對(duì)任意的自然數(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 等價(jià)式與蘊(yùn)含式,定義2-5.2, 2-5.3 如果公式A在任何解釋下均為真,稱A為永真式; 如果 A在某個(gè)解釋I和I的一個(gè)賦值下為真,稱A可滿足; 如果公

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

27、用任何合式公式置換,結(jié)果仍重言.,謂詞邏輯 等價(jià)與蘊(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)P(x)為重言式,判定公式的類型,重言式是永真式 ,但永真未必重言.,例如 xP( x ) xP( x ) 是永真式，但不是重言式.,補(bǔ)例,2.等價(jià)與蘊(yùn)含,定義 2-5.1 設(shè)A,B是公式,若AB是永真式,則稱 A,B等價(jià).記作AB.,

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

29、系,例 設(shè) P(x) : x今天來校上課, D:學(xué)生 則 P(x)表示: x今天沒來校上課,“并非所有人今天來校上課” (x)P(x) 等價(jià) “有人今天沒來校上課” (x)P(x),(x)P(x) (x)P(x),“ 沒有人今天來校上課” (x) P(x) 等價(jià) “所有人今天都沒來校上課” (x)P(x),(x) P(x) (x)P(x),謂詞邏輯 等價(jià)與蘊(yùn)含式,(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

30、) B),B (x) A(x) (B (x)A(x),B (x)A(x) (B (x)A(x),由上式可推出,謂詞邏輯 等價(jià)與蘊(yùn)含式,(4) 量詞與聯(lián)結(jié)詞之間的一些等價(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)歡會(huì)上所有人唱歌且所有人跳舞”意義相同,(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),對(duì)滿足分配律,對(duì)滿足分配律,“聯(lián)歡會(huì)上所有人即唱歌又跳舞

31、. ”,謂詞邏輯 等價(jià)與蘊(yù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) ?,(x)(A(x)B(x): 對(duì)所有的x, 有A(x)或B(x)成立.,(x)(A(x)B(x): 存在著x ,使A(x)和B(x)同時(shí)成立.,例 D:整數(shù)集合, A(x): x是偶數(shù), B(x): x是奇數(shù),(x)A(x)(x)B(x) (T) (x)(A(x)B(x) (F),謂詞邏輯 等價(jià)與蘊(yùn)含式,(x)A(x) (x)B(x): 對(duì)所有的x , A(x)成立; 或?qū)λ械膞, B

32、(x)成立.,(x)A(x)(x)B(x):存在著x,使A(x)成立, 且存在x, 使B(x)成立.,(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),常見的等價(jià)式與蘊(yùn)含式見表2-5.1,同理可得,謂詞邏輯 等價(jià)與蘊(yùn)含式,(6) 多個(gè)量詞的使用,公式中多個(gè)量詞的出現(xiàn)次序關(guān)系到命題的含義,不能隨意交換.,例如,xy A(x,y): 對(duì)任意x ,都存在y, 使得A成立.,例 (x

33、) (y)(x+y=0) 為真命題 , y = -x,yxA (x,y) : 存在著y, 對(duì)所有的x 都有A成立.,(y) (x)(x+y=0) 為假命題,謂詞邏輯 等價(jià)與蘊(yùn)含式,y 的值獨(dú)立于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),謂詞邏輯 等價(jià)與蘊(yùn)含式,例題,謂詞邏輯 等價(jià)與蘊(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(x) 為永假式。,例題,謂詞邏輯 等價(jià)與蘊(yùn)含式,(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 等價(jià)式與蘊(yùn)含式,-7 謂詞演算的推理理論,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,謂詞邏輯 前束范式,2-6前束范式,定義 2-6.1 一個(gè)公式,如果量詞均在全式的開頭,它們的作用域,延伸到整個(gè)公式的末尾,則該公式叫做前束范式。,前束范式簡(jiǎn)記為:

36、,(v1)(v2).(vn) A,或,指導(dǎo)變?cè)?母式(不含量詞),例如 (x) (y) (z)( Q(x,y) R(z),(x)P(x) ( x)Q(x) ?,Q(x,y) R(z),定理2-6.1 任一謂詞公式,均和一個(gè)前束范式等價(jià).,化前束范式的方法,(1).將公式中的連接詞化為,.(非必須) (2).利用否定律,德.摩根律,及量詞轉(zhuǎn)化律,將否 定深入到謂詞字母前. (3).利用換名規(guī)則或代入規(guī)則使所有約束變?cè)?不相同且使所有的自由變?cè)c約束變?cè)煌? (4).利用量詞的的擴(kuò)張與收縮,擴(kuò)大量詞的轄域 至整個(gè)公式.,謂詞邏輯 前束范式,例如 (x) P(x,y)Q(x),(x)P(x) (

37、x)Q(x),因?yàn)?(x)P(x) (y)P(y), (x)P(x) (y)P(y), 所以,若謂詞公式中有變?cè)燃s束出現(xiàn),又自由出現(xiàn),為避免混淆,可對(duì)約束變?cè)M(jìn)行換名或?qū)ψ杂勺冊(cè)? 使得一個(gè)變?cè)诠街兄怀室环N出現(xiàn).,(1)對(duì)約束變?cè)獡Q名,其更改的變?cè)Q范圍是:量詞 中的指導(dǎo)變?cè)霸摿吭~轄域中出現(xiàn)的該變?cè)?而 公式中其余變?cè)蛔?,(2)對(duì)約束變?cè)獡Q名時(shí)一定要更改為轄域中未出現(xiàn) 的變?cè)?,換 名 規(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).代入須對(duì)公式中該自由變?cè)乃谐霈F(xiàn)同 時(shí)進(jìn)行. (2).代入的變?cè)荒芘c公式中其它變?cè)?,例如 (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)是指導(dǎo)變?cè)? Aij是原子公式或其否定。,定義2-6.2 一個(gè)wff A如果具有如下形式稱為前束合取范式,例如 (x) (z) (y)( P(x ,y) (z=b) (Q(y)(a=

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

40、前. (3).利用換名規(guī)則或代入規(guī)則使所有約束變?cè)?不相同且使所有的自由變?cè)c約束變?cè)煌? (4).利用量詞的的擴(kuò)張與收縮,擴(kuò)大量詞的轄域 至整個(gè)公式.,前束范式：(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é)重點(diǎn)掌握的概念: 謂詞演算的永真式，重言式，等價(jià)式, 蘊(yùn)含式; 前束范式. 本節(jié)重點(diǎn)掌握的方法: 證明永真式，等價(jià)式, 求前束合取范式, 析取范式.,-1 謂詞的概念與表示,-2 量詞,-3 謂詞公式,-5 等價(jià)式與蘊(yùn)含式,26 前束范式,謂詞邏輯,-4 謂詞公式的解釋,-7 謂詞演算的推理理論,2-7

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

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

44、也使A真.,例 (x) (y) (x y) P (不存在最大實(shí)數(shù)),例 (x) P(x) : 所有的人都是要死的 P, P(a) : 蘇格拉底是要死的. US, (y) (a y) US 或 (y) (x y) US,(y) (y y) ?,或 P(x) : x是要死的. US,使用限制: t 不能與其它指導(dǎo)變?cè)?,(2)全稱推廣規(guī)則 UG,含義: 若D中任意一個(gè)體使A真,則D中所有個(gè)體都 使A真.,使用限制: x 不能是前提中的自由變?cè)?,例: P(x) : x是偶數(shù) D:正整數(shù) . (1) P(x) P (2) (x) P(x) UG ?,謂詞邏輯 謂詞演算的推理.,(3)存在指定規(guī)則

45、 ES,含義:若D中存在個(gè)體使A真,則D中必有某個(gè)體c使A真.,使用限制:(x)A(x)為閉式,c為一個(gè)新常元(歧義名稱).,(4)存在推廣規(guī)則 EG,含義: 若項(xiàng)t使A真,則D中存在個(gè)體使A為真.,謂詞邏輯 謂詞演算的推理.,使用限制: x 不能與A(t)中的自由變?cè)蛑笇?dǎo)變?cè)?例,(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í)數(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,命題邏輯 邏輯連接詞,補(bǔ)例 所有的有理數(shù)是實(shí)數(shù). 某些有理數(shù)是整數(shù). 因此, 某些實(shí)數(shù)是整數(shù).,設(shè): R(x): x是實(shí)數(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) ),命題邏輯 邏輯連接詞,補(bǔ)例 每個(gè)用功的學(xué)生考試不會(huì)不及格。 小張是用功的學(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),命題邏輯 邏輯連接詞,4. 設(shè)R(x):x是實(shí)數(shù), P(x): x是有理數(shù), “并非每個(gè)實(shí)數(shù)都是有理數(shù)” 符號(hào)化為 (

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) 前束合取范式為_.,課堂練習(xí) 1. 在謂詞邏輯中,永真式都是重言式。( ) 2. 任意謂詞公式都有唯一的前束范式與之等價(jià)。( ) 3. (x)(A(x)B(x) (x)A(x) (x)B(x) ( ),命題邏輯 邏輯連接詞,8 所有的有理數(shù)是實(shí)數(shù).

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

54、方法(一),個(gè)體和個(gè)體域,謂詞公式的翻譯 (命題符號(hào)化),一元謂詞: A( x ) n元謂詞: A( x1,.xn),個(gè)體常元: a,b,c. 個(gè)體變?cè)? x,y,z. D:個(gè)體域,全稱量詞: (x)A(x) 存在量詞: (x)A(x) (x)(P(x)A(x) (x)( P(x)A(x) ),特性謂詞 P(x),謂詞邏輯小結(jié),重點(diǎn)掌握的基本概念和方法(二),二.謂詞公式及其解釋,謂詞公式的遞歸定義,謂詞公式的解釋 與賦值,變?cè)募s束,求謂詞公式在一組解釋下的真值,有限域,無限域,指導(dǎo)變?cè)c轄域 自由變?cè)c約束變?cè)?開式與閉式,1).指定個(gè)體域DI. 2).指定個(gè)體常元 3).指定個(gè)體函數(shù).

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