第七章謂詞邏輯ppt課件

1、離散數(shù)學(xué)離散數(shù)學(xué)第七章第七章 謂詞邏輯謂詞邏輯廣東工業(yè)大學(xué)計算機(jī)學(xué)院廣東工業(yè)大學(xué)計算機(jī)學(xué)院為何引入謂詞邏輯v 只用命題無法描畫一切的推理過程。只用命題無法描畫一切的推理過程。v 蘇格拉底三段論：蘇格拉底三段論：v 一切的人都是要死的，一切的人都是要死的，v 蘇格拉底是人，蘇格拉底是人，v 所以蘇格拉底是要死的。所以蘇格拉底是要死的。v 眾所周知，這是真命題。眾所周知，這是真命題。v 命題邏輯中的求解：令命題邏輯中的求解：令v P:P:一切的人都是要死的，一切的人都是要死的，v Q:Q:蘇格拉底是人，蘇格拉底是人，v R:R:所以蘇格拉底是要死的。所以蘇格拉底是要死的。v 在命題邏輯中，將只能用

2、在命題邏輯中，將只能用 (P Q) (P Q) R R 表示上述命題，無表示上述命題，無法證明法證明(PQ)(PQ)R R 。v 所以，這個簡單而著名的結(jié)論就無法用命題邏輯予以推證。所以，這個簡單而著名的結(jié)論就無法用命題邏輯予以推證。為何引入謂詞邏輯v命題邏輯無法準(zhǔn)確描畫蘇格拉底三段論的根本命題邏輯無法準(zhǔn)確描畫蘇格拉底三段論的根本緣由是：緣由是：P,Q,RP,Q,R這樣的命題表示太粗略，沒有這樣的命題表示太粗略，沒有把命題之間的內(nèi)在聯(lián)絡(luò)反映出來。把命題之間的內(nèi)在聯(lián)絡(luò)反映出來。v要反映這種內(nèi)在聯(lián)絡(luò)，就要對原子命題作進(jìn)一要反映這種內(nèi)在聯(lián)絡(luò)，就要對原子命題作進(jìn)一步的細(xì)化，分析出其中的客體、謂詞、量詞

3、等，步的細(xì)化，分析出其中的客體、謂詞、量詞等，研討它們之間的方式構(gòu)造及邏輯關(guān)系，這就是研討它們之間的方式構(gòu)造及邏輯關(guān)系，這就是謂詞邏輯所研討的內(nèi)容。謂詞邏輯所研討的內(nèi)容。v謂詞邏輯也叫一階邏輯。謂詞邏輯也叫一階邏輯。謂詞邏輯謂詞邏輯 v7.1.1 7.1.1 謂詞與命題函數(shù)謂詞與命題函數(shù)v 謂詞謂詞v7.1.2 7.1.2 量詞量詞v1. 1. 全稱量詞全稱量詞v2. 2. 存在量詞存在量詞v7.1.3 7.1.3 謂詞合式謂詞合式v7.1.4 7.1.4 約束元與自在元約束元與自在元v改名規(guī)那么改名規(guī)那么1. 謂詞謂詞v 定義定義 個體詞客體個體詞客體v 命題所陳說的對象命題所陳說的對象v

4、可以是一個詳細(xì)的事物可以是一個詳細(xì)的事物v 也可以是一個籠統(tǒng)的概念也可以是一個籠統(tǒng)的概念v 例如：例如：v 劉德華是香港人。劉德華是香港人。v 自然數(shù)集是整數(shù)集的子集。自然數(shù)集是整數(shù)集的子集。v 定義定義 謂詞謂詞v 描寫個體詞的性質(zhì)或個體詞之間的關(guān)系的詞描寫個體詞的性質(zhì)或個體詞之間的關(guān)系的詞v 例如：例如：v “ “是香港人是香港人 是謂詞，表示個體詞的性質(zhì)：是謂詞，表示個體詞的性質(zhì)：v “ “是是的子集的子集 是謂詞，描畫個體詞之間的關(guān)系是謂詞，描畫個體詞之間的關(guān)系個體詞的分類個體詞的分類v 定義定義 個體常量個體常量v表示詳細(xì)的或特定的個體表示詳細(xì)的或特定的個體v普通用小寫字母普通用小寫

5、字母a a、b b、c c等表示等表示v 定義定義 個體變元個體變元v表示籠統(tǒng)的或泛指的個體的詞表示籠統(tǒng)的或泛指的個體的詞v常用小寫字母常用小寫字母x x、y y、z z等表示等表示v例如：例如：v x x是香港人。是香港人。v y y是是z z的子集。的子集。個體域或論述域個體域或論述域v 定義定義 個體域個體域v 個體變元的取值范圍。個體變元的取值范圍。v可以是有限個體的集合可以是有限個體的集合v如：如：aa、b b、cc、 計算機(jī)學(xué)院的學(xué)生計算機(jī)學(xué)院的學(xué)生 v也可以是無限個體的集合也可以是無限個體的集合v如：實數(shù)集合、自然數(shù)集合如：實數(shù)集合、自然數(shù)集合v全總個體域：全總個體域：v宇宙間的

6、一切事物和概念構(gòu)成的集合。當(dāng)沒宇宙間的一切事物和概念構(gòu)成的集合。當(dāng)沒有特別聲明時，將全總個體域作為個體域。有特別聲明時，將全總個體域作為個體域。謂詞的函數(shù)表示謂詞的函數(shù)表示v謂詞可用大寫英文字母表示謂詞可用大寫英文字母表示v 例如：例如：v A A：是香港人。：是香港人。v B B：年輕：年輕2020歲。歲。v v謂詞的函數(shù)表示謂詞的函數(shù)表示v用不同的個體變元取代謂詞表示中要填入的個體詞用不同的個體變元取代謂詞表示中要填入的個體詞v 例如：例如：v A(x) A(x)：x x是香港人。是香港人。v B(x,y) B(x,y)：x x比比y y年輕年輕2020歲。歲。v這樣的函數(shù)稱為這樣的函數(shù)稱

7、為( (簡單簡單) )命題函數(shù)原子公式。命題函數(shù)原子公式。復(fù)合命題函數(shù)復(fù)合命題函數(shù) 復(fù)合命題函數(shù)復(fù)合命題函數(shù) 由簡單命題函數(shù)與結(jié)合詞運算后構(gòu)成由簡單命題函數(shù)與結(jié)合詞運算后構(gòu)成舉例：舉例：A(x): xA(x): x有一條足夠長的杠桿有一條足夠長的杠桿 B(x): x B(x): x可以翹起整個地球可以翹起整個地球 那么那么A(x)A(x) B(x) B(x) 表示：假設(shè)表示：假設(shè)x x有一條足夠長的杠有一條足夠長的杠桿，那么桿，那么x x可以翹起整個地球?？梢月N起整個地球。n n元謂詞元數(shù)元謂詞元數(shù)定義定義 n元謂詞元謂詞含有含有n個個體變元的謂詞。個個體變元的謂詞。一元謂詞表示個體詞的性質(zhì)一

8、元謂詞表示個體詞的性質(zhì)多元謂詞反映個體詞之間的關(guān)系多元謂詞反映個體詞之間的關(guān)系0元謂詞是命題。元謂詞是命題。例如：例如： A(x)：x是香港人。是香港人。 (一元謂詞一元謂詞) B(x,y)：x比比y年輕年輕20歲。歲。(二元謂二元謂詞詞)命題函數(shù)與命題命題函數(shù)與命題v當(dāng)當(dāng)n n1 1，命題函數(shù)，命題函數(shù)(n(n元謂詞元謂詞)P(x1, , xn)P(x1, , xn)不是命不是命題，由于真值無法確定。題，由于真值無法確定。v只需當(dāng)用只需當(dāng)用n n 個個體詞替代個個體詞替代 x1, x2, , xn x1, x2, , xn之后，才之后，才是命題。是命題。v舉例：舉例：v L(x,y) L(x

9、,y)：表示：表示“x“x小于小于y y的二元謂詞，它的真值的二元謂詞，它的真值不能確定。不能確定。v L(2,3) L(2,3) 是命題是命題“2“2小于小于3 3命題函數(shù)的定義域和值域命題函數(shù)的定義域和值域v 命題函數(shù)的定義域個體域：命題函數(shù)的定義域個體域：v 命題函數(shù)包含的一切個體變元的取值范圍。命題函數(shù)包含的一切個體變元的取值范圍。v 例如：例如：v R(x): x R(x): x是大學(xué)生。是大學(xué)生。v x x的定義域可為：一切人的定義域可為：一切人/ /某大學(xué)的一切學(xué)生某大學(xué)的一切學(xué)生/ /某中學(xué)的一某中學(xué)的一切學(xué)生切學(xué)生v 留意：留意：(1)(1)定義域不同，對命題的真值有影響。定

10、義域不同，對命題的真值有影響。v (2) (2)假設(shè)無特殊闡明，個體變元的定義域為全總個體假設(shè)無特殊闡明，個體變元的定義域為全總個體域。域。v 命題函數(shù)的值域：命題函數(shù)的值域：v 對命題函數(shù)每種能夠的賦值所生成的命題的集合。對命題函數(shù)每種能夠的賦值所生成的命題的集合。v 例如：例如：v x x的定義域為：張三、李四的定義域為：張三、李四v 那么那么R(x)R(x)的值域為：的值域為： 張三是大學(xué)生，李四是大學(xué)生張三是大學(xué)生，李四是大學(xué)生 謂詞邏輯謂詞邏輯 v7.1.1 7.1.1 謂詞與命題函數(shù)謂詞與命題函數(shù)v 謂詞謂詞v7.1.2 7.1.2 量詞量詞v1. 1. 全稱量詞全稱量詞v2. 2

11、. 存在量詞存在量詞v7.1.3 7.1.3 謂詞合式謂詞合式v7.1.4 7.1.4 約束元與自在元約束元與自在元v改名規(guī)那么改名規(guī)那么量詞的引入量詞的引入v為了用謂詞表示假設(shè)干個體詞或全體個體詞具為了用謂詞表示假設(shè)干個體詞或全體個體詞具有某種性質(zhì)或具有某種關(guān)系，需求引入量詞。有某種性質(zhì)或具有某種關(guān)系，需求引入量詞。v v 例如：例如：v (1) (1) 某些人會跳舞；某些人會跳舞；v (2) (2) 一切人都會跳舞；一切人都會跳舞；量詞量詞v 定義定義 量詞量詞v 表示數(shù)量的詞表示數(shù)量的詞v 1. 1.全稱量詞全稱量詞: : v 表示恣意的表示恣意的, ,一切的一切的, ,每一個，凡是每一

12、個，凡是v x x 表示對個體域中一切的表示對個體域中一切的xxv 2. 2.存在量詞存在量詞: : v 表示存在表示存在, , 有的有的, , 至少有一個，有些至少有一個，有些v x x 表示在個體域中存在表示在個體域中存在xxv 在在x A(x)x A(x)和和x A(x)x A(x)中：中：v 緊跟量詞的緊跟量詞的x x稱為量詞的指點變元或作用變元稱為量詞的指點變元或作用變元v A A稱為量詞的轄域或作用域稱為量詞的轄域或作用域v 量詞舉例量詞舉例(1) (1) 一切的魚都生活在水中。一切的魚都生活在水中。 F(x) F(x)：x x是魚是魚 W(x) W(x)：x x生活在水中生活在水

13、中 一切的魚都生活在水中：一切的魚都生活在水中：( (x)(F(x) x)(F(x) W(x) W(x) 。(2) (2) 有些人會講粵語有些人會講粵語 M(x) M(x)：x x是人是人 Y(x): x Y(x): x會講粵語會講粵語 有些人會講粵語：有些人會講粵語：( (x) (M(x) x) (M(x) Y(x) Y(x)。全稱量詞和存在量詞與結(jié)合詞的搭配全稱量詞和存在量詞與結(jié)合詞的搭配v 描畫某類個體中包含的一切個體具有某種性質(zhì)描畫某類個體中包含的一切個體具有某種性質(zhì)v 與與 搭配搭配v 例如：設(shè)：例如：設(shè)：S(x)：x是學(xué)生。是學(xué)生。v P(x)：x經(jīng)過了考試。經(jīng)過了考試。v 一切學(xué)

14、生都經(jīng)過了考試一切學(xué)生都經(jīng)過了考試 v (x)(S(x)P(x)v (x)(S(x)P(x)？v 由于個體域必需是學(xué)生時，由于個體域必需是學(xué)生時，(x)(S(x)P(x)才為真才為真v 某類個體中部分個體具有某種性質(zhì)某類個體中部分個體具有某種性質(zhì)v 與與 搭配搭配v 例：有些學(xué)生經(jīng)過了考試。例：有些學(xué)生經(jīng)過了考試。v (x)(S(x)P(x)v (x)(S(x)P(x)？v 由于只需個體域中有非學(xué)生的個體由于只需個體域中有非學(xué)生的個體(x)(S(x)P(x)為真為真?zhèn)€體域與命題的符號化個體域與命題的符號化 (1) (1) 人都愛美人都愛美 (2) (2) 有人用左手寫字有人用左手寫字 分別取不

15、同的個體域集合：分別取不同的個體域集合： (a) (a) 個體域為人類集合個體域為人類集合, , (b) (b) 個體域為全總個體域個體域為全總個體域 宇宙中的一切事物宇宙中的一切事物. .解：設(shè)解：設(shè)M(x)M(x)：x x是人是人; F(x); F(x)：x x愛美；愛美； G(x) G(x)：x x用左手寫字用左手寫字 (a) (a) 個體域為人類集合的情況下：個體域為人類集合的情況下： (1) (1) x F(x) x F(x) 或或 x (M(x)x (M(x) F(x) F(x) (2) (2) x G(x) x G(x) 或或 x (M(x) x (M(x) G(x) G(x)

16、(b) (b)個體域為全總個體域的情況下：個體域為全總個體域的情況下： (1) (1) x (M(x)x (M(x) F(x) F(x) (2) (2) x (M(x) x (M(x) G(x) G(x)闡明：闡明：1個體域不同，同一個個體域不同，同一個命題符號化的結(jié)果不同。命題符號化的結(jié)果不同。量化的命題函數(shù)與命題量化的命題函數(shù)與命題v 命題函數(shù)不是命題，但僅包含被量化的變量的命題命題函數(shù)不是命題，但僅包含被量化的變量的命題函數(shù)是命題。函數(shù)是命題。v 如：如： M(x)：x是人。是人。v A(x)：x是聰明的。是聰明的。v B(x)：x要呼吸。要呼吸。v (1) M(x)B(x)v (2)

17、(x)(M(x)B(x)v (3) M(x) A(x) v (4) (x)(M(x)A(x)不是命題不是命題是命題是命題不是命不是命題題是命題是命題量詞的順序量詞的順序v 量詞順序普通不要隨意顛倒，顛倒后表示的含義能夠會改動。量詞順序普通不要隨意顛倒，顛倒后表示的含義能夠會改動。v 例：例：v 命題：對于任一給定的實數(shù)命題：對于任一給定的實數(shù)x，都存在著一個實數(shù)，都存在著一個實數(shù)y，使得，使得x + y = 0v 取個體域為實數(shù)集合，取個體域為實數(shù)集合， H(x, y): x + y = 0，v 那么命題可符號化為：那么命題可符號化為：xy H(x, y)v y x H(x, y) 那么表示：

18、那么表示：v 存在著一個實數(shù)存在著一個實數(shù)y，對于任一實數(shù)，對于任一實數(shù)x，使得，使得x + y = 0v x y H(x, y)是真命題，而是真命題，而y x H(x, y) 假命題假命題帶量詞的命題符號化舉例帶量詞的命題符號化舉例1請將以下命題符號化：請將以下命題符號化： (1) (1) 某些實數(shù)是有理數(shù)。某些實數(shù)是有理數(shù)。 (2) (2) 沒有不犯錯誤的人。沒有不犯錯誤的人。 (3) (3) 雖然有人聰明，但未必一切人都聰明。雖然有人聰明，但未必一切人都聰明。解：解：(1) R(x)(1) R(x)：x x是實數(shù)。是實數(shù)。Q(x)Q(x)：x x是有理數(shù)。是有理數(shù)。 ( (x)(R(x)

19、x)(R(x)Q(x) )Q(x) ) (2) M(x) (2) M(x)：x x是人。是人。F(x)F(x)：x x犯錯誤。犯錯誤。 ( (x)(M(x)x)(M(x)F(x)F(x) (3) M(x) (3) M(x)：x x是人。是人。S(x)S(x)：x x聰明。聰明。 ( (x)(M(x)x)(M(x)S(x) S(x) ( (x)(M(x)x)(M(x)S(x)S(x) 帶量詞的命題符號化舉例帶量詞的命題符號化舉例2 2 (4) (4) 正數(shù)都大于負(fù)數(shù)。正數(shù)都大于負(fù)數(shù)。 (5) (5) 直線直線a a與與b b平行當(dāng)且僅當(dāng)平行當(dāng)且僅當(dāng)a a與與b b不相交。不相交。解：解： (4)

20、 (4) 令令F(x): xF(x): x為正數(shù)。為正數(shù)。 G(y): y G(y): y為負(fù)數(shù)。為負(fù)數(shù)。 L(x,y): x L(x,y): x大于大于 y y。 x xy (F(x) y (F(x) G(y) G(y) L(x,y) L(x,y) (5) (5) 令令L(x): xL(x): x是直線。是直線。 P(x,y): x P(x,y): x與與y y平行。平行。 G(x,y): x G(x,y): x與與y y不相交不相交, , ( (x)(x)(y)(L(x)y)(L(x)L(y)L(y)(P(x,y) (P(x,y) G(x,y)G(x,y)命題符號化舉例命題符號化舉例3v只

21、運用全稱量詞，將以下命題符號化。只運用全稱量詞，將以下命題符號化。v 某些實數(shù)是有理數(shù)，但并非一切實數(shù)都是有理某些實數(shù)是有理數(shù)，但并非一切實數(shù)都是有理數(shù)。數(shù)。v解：原語句等價于：并非一切實數(shù)都不是有理數(shù)，解：原語句等價于：并非一切實數(shù)都不是有理數(shù)，并且并非一切實數(shù)都是有理數(shù)。并且并非一切實數(shù)都是有理數(shù)。v R(x) R(x)：x x是實數(shù)。是實數(shù)。v Q(x) Q(x)：x x是有理數(shù)。是有理數(shù)。v ( (x)(R(x)x)(R(x)Q(x)Q(x) ( (x)(R(x)x)(R(x)Q(x)Q(x)v 消去量詞v當(dāng)個體域為有限集時，如D=a1, a2, an，對于恣意的謂詞A(x)，都有：v

22、x (A(x) A(a1) A(a2) A(an)vx (A(x) A(a1) A(a2) A(an)v這兩個等價式稱為消去量詞等價式。消除量詞舉例消除量詞舉例v 設(shè)個體域設(shè)個體域D=a,b,D=a,b,請消除以下謂詞中的量詞。請消除以下謂詞中的量詞。v (1) ( (1) (x)(A(x)x)(A(x) B(x) B(x)v (2) ( (2) (x)(A(x)x)(A(x)B(x)B(x)v (3) ( (3) (x)(x)(y)R(x,y)y)R(x,y)v (4) ( (4) (y)(y)(x)R(x,y)x)R(x,y)v 解：解：v (1) (1) (A(a) (A(a)B(a)

23、B(a) (A(b) (A(b)B(b)B(b)v (2) (2) (A(a) (A(a)B(a) B(a) (A(b) (A(b)B(b)B(b)v (3) (3) ( (x)(R(x,a) x)(R(x,a) R(x,b) R(x,b)v (R(a,a)(R(a,a)R(a,b) R(a,b) (R(b,a) (R(b,a)R(b,b)R(b,b)v (4) (4) ( (y)(R(a,y) y)(R(a,y) R(b,y) R(b,y)v (R(a,a) (R(a,a) R(b,a) R(b,a) (R(a,b) (R(a,b) R(b,b) R(b,b)v 量化的謂詞函數(shù)的翻譯例量化的

24、謂詞函數(shù)的翻譯例v 設(shè)個體域為整數(shù)集，令設(shè)個體域為整數(shù)集，令v P(x, y): x + y = 1P(x, y): x + y = 1v Q(x, y): xy 0Q(x, y): xy 0v 闡明以下命題的意義，并指出哪些為真命題。闡明以下命題的意義，并指出哪些為真命題。v (1) (1) x x y P(x, y)y P(x, y)v v (2) (2) x xy Q(x, y) y Q(x, y) v (3) (3) x x y (Q(x, y) y (Q(x, y) P(x, y) P(x, y)對于恣意整數(shù)對于恣意整數(shù)x x，存在整數(shù)，存在整數(shù)y y，使，使得得x + y = 1x

25、 + y = 1存在整數(shù)存在整數(shù)x x，對于恣意整數(shù)，對于恣意整數(shù)y y，使得，使得xy 0 xy 0對于恣意整數(shù)對于恣意整數(shù)x x，存在整數(shù)，存在整數(shù)y y，使得，使得x + y = 1x + y = 1時當(dāng)且僅當(dāng)時當(dāng)且僅當(dāng)xy0 xy0謂詞邏輯謂詞邏輯 v7.1.1 7.1.1 謂詞與命題函數(shù)謂詞與命題函數(shù)v1. 1. 謂詞謂詞v7.1.2 7.1.2 量詞量詞v1. 1. 全稱量詞全稱量詞v2. 2. 存在量詞存在量詞v7.1.3 7.1.3 謂詞合式謂詞合式v7.1.4 7.1.4 約束元與自在元約束元與自在元v改名規(guī)那么改名規(guī)那么謂詞演算的原子公式謂詞演算的原子公式v 定義定義 原子

26、公式原子公式v 不含任何結(jié)合詞和量詞的簡單命題函數(shù)稱不含任何結(jié)合詞和量詞的簡單命題函數(shù)稱為原子公式。為原子公式。v 舉例：舉例：v M(x) M(x)：x x是人是人 v Y(x): x Y(x): x會講粵語會講粵語謂詞合式謂詞合式v 定義定義 謂詞合式謂詞合式/ /公式公式v 由簡單命題函數(shù)、邏輯結(jié)合詞和量詞組合成的謂詞表達(dá)式。由簡單命題函數(shù)、邏輯結(jié)合詞和量詞組合成的謂詞表達(dá)式。v 合式公式的方式化定義：合式公式的方式化定義：v (1) (1) 原子公式是合式公式；原子公式是合式公式；v (2) (2) 假設(shè)假設(shè)A A是合式公式，那么是合式公式，那么( (A)A)是合式公式；是合式公式；v

27、 (3) (3) 假設(shè)假設(shè)A A、B B是合式公式，那么是合式公式，那么(AB)(AB)、(AB)(AB)、(AB)(AB)、(A (A B) B)是合式公式；是合式公式；v (4) (4) 假設(shè)假設(shè)A A是合式公式，那么是合式公式，那么x A(x)x A(x)、x A(x)x A(x)是合式公式是合式公式; ;v (5) (5) 只需經(jīng)過有限次地運用規(guī)那么只需經(jīng)過有限次地運用規(guī)那么(1)(1)(4)(4)構(gòu)成的符號串才是構(gòu)成的符號串才是合式公式。合式公式。謂詞合式舉例謂詞合式舉例v判別以下符號串能否謂詞合式判別以下符號串能否謂詞合式v (1) (1) x(A(x) B(x) x(A(x) B

28、(x) v (2) (2) x (A(x) B(x) x (A(x) B(x) x C(x) x C(x) v (3) ( (3) (x) A(x) (x) A(x) (x) B(x)x) B(x)v (4) ( (4) (x) (x) (y) P(y) P(x,y)x,y)v回答：回答：(1)(2)(1)(2)是謂詞合式。是謂詞合式。謂詞邏輯謂詞邏輯 v7.1.1 7.1.1 謂詞與命題函數(shù)謂詞與命題函數(shù)v1. 1. 謂詞謂詞v2. 2. 命題函數(shù)命題函數(shù)v7.1.2 7.1.2 量詞量詞v1. 1. 全稱量詞全稱量詞v2. 2. 存在量詞存在量詞v7.1.3 7.1.3 謂詞合式謂詞合式v

29、7.1.4 7.1.4 約束元與自在元約束元與自在元v改名規(guī)那么改名規(guī)那么約束元和自在元約束元和自在元v 在謂詞公式在謂詞公式x A(x)x A(x)和和x A(x)x A(x)中：中：v 緊跟量詞的緊跟量詞的x x稱為量詞的指點變元或作用變元稱為量詞的指點變元或作用變元v A A稱為量詞的轄域或作用域稱為量詞的轄域或作用域v 轄域中轄域中x x的一切出現(xiàn)稱為約束出現(xiàn)，的一切出現(xiàn)稱為約束出現(xiàn)， x x稱為約束變元稱為約束變元v 除去約束變元以外所其它變元的出現(xiàn)稱除去約束變元以外所其它變元的出現(xiàn)稱“自在出現(xiàn)自在出現(xiàn)，這種，這種變元稱為自在變元變元稱為自在變元v 舉例：舉例：x(P(x) Q(y)

30、R(y)x(P(x) Q(y)R(y)v 的轄域是的轄域是P(x)Q(y)P(x)Q(y)，指點變元是，指點變元是x x。v 整個公式中，整個公式中，x x 是約束出現(xiàn)，受是約束出現(xiàn)，受x x 的約束，的約束，y y是自在是自在出現(xiàn)出現(xiàn)約束元與自在元舉例約束元與自在元舉例1討論以下合式公式中的約束元及自在元討論以下合式公式中的約束元及自在元2) (2) (x P(x,y) R(y,z) x P(x,y) R(y,z) y Q(y)y Q(y)解：解： 的指點變元是的指點變元是 ，轄域是，轄域是 , , ( (x P(x, y) R(y, z)x P(x, y) R(y, z)中，是中，是 約束

31、出現(xiàn)且受約束出現(xiàn)且受x x 的約束，的約束， 是自在出現(xiàn)。是自在出現(xiàn)。 y Q(y)y Q(y)中，中，的指點變元是的指點變元是 ，轄域是，轄域是 ， 是約束出現(xiàn)。是約束出現(xiàn)。 整個公式中，整個公式中， 約束出現(xiàn)，約束出現(xiàn)， 既有約束出現(xiàn)又有既有約束出現(xiàn)又有自在出現(xiàn)，自在出現(xiàn)， 是自在出現(xiàn)。是自在出現(xiàn)。x xP(x,y)P(x,y)x xy y、z zy yQ(y)Q(y)y yx xy yz z變元的約束討論v 從約束變元的概念可以看出，從約束變元的概念可以看出，P(x1,x2, ,xn)P(x1,x2, ,xn)是是n n元謂詞，元謂詞，它有它有n n個相互獨立的自在變元。個相互獨立的自在

32、變元。v 假設(shè)對其中假設(shè)對其中k k個變元進(jìn)展約束，那么個變元進(jìn)展約束，那么P P成為成為n-kn-k元謂詞。元謂詞。v 當(dāng)當(dāng)k = nk = n，即謂詞公式中沒有自在變元出現(xiàn)時，那么該公式，即謂詞公式中沒有自在變元出現(xiàn)時，那么該公式就成為一個命題。就成為一個命題。v 例如：例如： x P(x,y,z)x P(x,y,z)是二元謂詞。是二元謂詞。v y y x P(x,y,z)x P(x,y,z)是一元謂詞。是一元謂詞。v z z y y x P(x,y,z)x P(x,y,z)是零元謂詞，即命題。是零元謂詞，即命題。謂詞邏輯謂詞邏輯 v7.1.1 7.1.1 謂詞與命題函數(shù)謂詞與命題函數(shù)v1. 1. 謂詞謂詞v2. 2. 命題函數(shù)命題函數(shù)v7.1.2 7.1.2 量詞量詞v1. 1. 全稱量詞全稱量詞v2. 2. 存在量詞存在量詞v7.1.3 7.1.3 謂詞合式謂詞合式v7.1.4 7.1.4 約束元與自在元約束元與自在元v改名規(guī)那么改名規(guī)那么約束變元的改名規(guī)那么約束變元的改名規(guī)那么v 一個變元在公式中可以同時為約束變元與自在變元，因此有一個變元在公式中可以同時為約束變元與自在變元，因此有能夠引起