離散數(shù)學(xué)第2.1陳瑜 1

1、陳瑜,Email：chenyu.inbox@gmail.com2024年3月18日星期一,離散　　數(shù)學(xué),計算機(jī)學(xué)院,2024/3/18,計算機(jī)學(xué)院,2/70,主要內(nèi)容,量詞化邏輯 1.謂詞 2.量詞 3.全總個體域 4.自由變元與約束變元 5.兩個量詞量化謂詞的真值,,,2024/3/18,計算機(jī)學(xué)院,3/70,命題邏輯是數(shù)理邏輯的基礎(chǔ)，主要研究命題和命題演算。原子命題是命題演算的基本單位，并把它看作是不可再分

2、解。這就帶來了命題邏輯的局限性。命題邏輯研究的范圍限制在命題及其外部關(guān)系上，無法研究命題內(nèi)部的成份、結(jié)構(gòu)，命題之間所具有的邏輯特征（如，共同性和差異性）例1.1 設(shè)基本命題，P：李明是大學(xué)生；Q：王芳是大學(xué)生 R：松樹是植物。 很明顯，P與Q在內(nèi)部關(guān)系上，應(yīng)該比R密切得多。然而，命題邏輯無法反映這種區(qū)別，也無法反映P、Q間的共同性。,第二章:一階謂詞邏輯,2024/3/18,計算機(jī)學(xué)院,4/70,命題邏輯是數(shù)理邏輯的基礎(chǔ)，

3、主要研究命題和命題演算。原子命題是命題演算的基本單位，并把它看作是不可再分解。這就帶來了命題邏輯的局限性。命題邏輯研究的范圍限制在命題及其外部關(guān)系上，無法研究命題內(nèi)部的成份、結(jié)構(gòu)，命題之間所具有的邏輯特征（共同性和差異性）例1.1 設(shè)基本命題，P：李明是大學(xué)生；Q：王芳是大學(xué)生 R：松樹是植物。 很明顯，P與Q在內(nèi)部關(guān)系上，應(yīng)該比R密切得多。然而，命題邏輯無法反映這種區(qū)別，也無法反映P、Q間的共同性。,第二章:一階謂詞邏輯

4、,2024/3/18,計算機(jī)學(xué)院,5/70,,解：假設(shè)：,例1.2 (著名的蘇格拉底三段論) 設(shè)自然語言中的三個命題： 1）所有的人都是要死的； 2）蘇格拉底是人； 3）所以，蘇格拉底是要死的。,P：所有的人都是要死的； Q：蘇格拉底是人。 R：所以，蘇格拉底是要死的。 顯然，無論用什么方法也無法推論出 P，Q ?R。 但是，這樣簡單

5、的，憑直覺就知蘇格拉底的論證是正確的推理，命題邏輯卻無能為力。這是由命題邏輯的局限性造成的，因此，需要對命題的內(nèi)部關(guān)系進(jìn)行研究。,2024/3/18,計算機(jī)學(xué)院,6/70,,解：假設(shè)：,例1.2 (著名的蘇格拉底三段論) 設(shè)自然語言中的三個命題： 1）所有的人都是要死的； 2）蘇格拉底是人； 3）所以，蘇格拉底是要死的。,P：所有的人都是要死的； Q：蘇格拉底是人。 R：所以，蘇格拉底是要死的

6、。 顯然，無論用什么方法也無法推論出 P，Q ?R。 但是，這樣簡單的，憑直覺就知蘇格拉底的論證是正確的推理，命題邏輯卻無能為力。這是由命題邏輯的局限性造成的，因此，需要對命題的內(nèi)部關(guān)系進(jìn)行研究。,2024/3/18,計算機(jī)學(xué)院,7/70,,解：假設(shè)：,例1.2 (著名的蘇格拉底三段論) 設(shè)自然語言中的三個命題： 1）所有的人都是要死的； 2）蘇格拉底是人；

7、 3）所以，蘇格拉底是要死的。,P：所有的人都是要死的； Q：蘇格拉底是人。 R：所以，蘇格拉底是要死的。 顯然，無論用什么方法也無法推論出 P，Q ?R。 但是，這樣簡單的、憑直覺就知蘇格拉底的論證是正確的推理，命題邏輯卻無能為力。這是由命題邏輯的局限性造成的，因此，需要對命題的內(nèi)部關(guān)系進(jìn)行研究。,2024/3/18,計算機(jī)學(xué)院,8/70,§

8、2.1 量詞化邏輯——謂詞和量詞,一、謂詞 Predicate 在對命題的內(nèi)部邏輯關(guān)系進(jìn)行研究時，把基本命題分成客體(個體）和謂詞?？腕w——命題中所描述的對象。（命題中的主語，客觀實體，可以獨立存在的物體）。謂詞——命題中描述的個體性質(zhì)（特征）或關(guān)系的部分。謂詞一般用大寫字母（串）表示;個體用小寫字母表示。,2024/3/18,計算機(jī)學(xué)院,9/70,§2.1 量詞化邏輯——謂詞和量詞,一、謂詞 Predicat

9、e 在對命題的內(nèi)部邏輯關(guān)系進(jìn)行研究時，把基本命題分成客體(個體）和謂詞。客體——命題中所描述的對象。（命題中的主語，客觀實體，可以獨立存在的物體）。謂詞——命題中描述的個體性質(zhì)（特征）或關(guān)系的部分。謂詞一般用大寫字母（串）表示;個體用小寫字母表示。,2024/3/18,計算機(jī)學(xué)院,10/70,§2.1 量詞化邏輯——謂詞和量詞,一、謂詞 Predicate 在對命題的內(nèi)部邏輯關(guān)系進(jìn)行研究時，把基本命題分成客體

10、(個體）和謂詞?？腕w——命題中所描述的對象。（命題中的主語，客觀實體，可以獨立存在的物體）。謂詞——命題中描述的個體性質(zhì)（特征）或關(guān)系的部分。謂詞一般用大寫字母（串）表示;個體用小寫字母表示。,2024/3/18,計算機(jī)學(xué)院,11/70,,例1.3　如有句子：張紅是一個四川大學(xué)的學(xué)生；王南是一個四川大學(xué)的學(xué)生；李華是一個四川大學(xué)的學(xué)生。 則在命題中必須要用三個命題P，Q，R來表示。,但是，它們都具有一個共同的特征

11、： “…是一個四川大學(xué)的學(xué)生”因此，若將句子分解成：“主語＋謂語”用P表示“是一個四川大學(xué)的學(xué)生”，P后緊跟“某某人”。則上述句子可寫為：P(張紅)；P(王南)；P(李華)。一般地，P(x)：x是一個四川大學(xué)的學(xué)生。,2024/3/18,計算機(jī)學(xué)院,12/70,,例1.3　如有句子：張紅是一個四川大學(xué)的學(xué)生；王南是一個四川大學(xué)的學(xué)生；李華是一個四川大學(xué)的學(xué)生。 則在命題中必須要用三個命題P，

12、Q，R來表示。,但是，它們都具有一個共同的特征： “…是一個四川大學(xué)的學(xué)生”因此，若將句子分解成：“主語＋謂語”用P表示“是一個四川大學(xué)的學(xué)生”，P后緊跟“某某人”。則上述句子可寫為：P(張紅)；P(王南)；P(李華)。一般地，P(x)：x是一個四川大學(xué)的學(xué)生。,2024/3/18,計算機(jī)學(xué)院,13/70,,例1.3　如有句子：張紅是一個四川大學(xué)的學(xué)生；王南是一個四川大學(xué)的學(xué)生；李華是一個四川大

13、學(xué)的學(xué)生。 則在命題中必須要用三個命題P，Q，R來表示。,但是，它們都具有一個共同的特征： “…是一個四川大學(xué)的學(xué)生”因此，若將句子分解成：“主語＋謂語”用P表示“是一個四川大學(xué)的學(xué)生”，P后緊跟“某某人”。則上述句子可寫為：P(張紅)；P(王南)；P(李華)。一般地，P(x)：x是一個四川大學(xué)的學(xué)生。,P：謂詞x：客體詞P(x)：命題函數(shù),2024/3/18,計算機(jī)學(xué)院,14/70,,與謂詞相聯(lián)系

14、的個體的數(shù)目，就是謂詞的元數(shù)。 ①描述一個個體的性質(zhì)的謂詞叫“一元謂詞”。 ②描述兩個個體間的關(guān)系的謂詞叫“二元謂詞”。 如A：‘…比…大’ 命題4比3大表示成A（4，3） ③描述三個個體間的關(guān)系的謂詞叫“三元謂詞”。 如B：‘…在…和…之間’ B（n,c,z）：內(nèi)江在成都與重慶之間。定義2.1：設(shè)D是由客體構(gòu)成的稱為個體域的非空集合，以D中元素為值的變元稱為客體變元。由形如 謂

15、詞標(biāo)識符（客體變元1，客體變元2，…，客體變元n） 構(gòu)成的、其值為“真”或“假”的表達(dá)式，稱為n元謂詞。 即n元謂詞是描述n個個體間的關(guān)系。,2024/3/18,計算機(jī)學(xué)院,15/70,,與謂詞相聯(lián)系的個體的數(shù)目，就是謂詞的元數(shù)。 ①描述一個個體的性質(zhì)的謂詞叫“一元謂詞”。 ②描述兩個個體間的關(guān)系的謂詞叫“二元謂詞”。 如A：‘…比…大’ 命題4比3大表示成A（4，3） ③描述三個個體間的關(guān)系的謂

16、詞叫“三元謂詞”。 如B：‘…在…和…之間’ B（n,c,z）：內(nèi)江在成都與重慶之間。定義2.1：設(shè)D是由客體構(gòu)成的稱為個體域的非空集合，以D中元素為值的變元稱為客體變元。由形如 謂詞標(biāo)識符（客體變元1，客體變元2，…，客體變元n） 構(gòu)成的、其值為“真”或“假”的表達(dá)式，稱為n元謂詞。 即n元謂詞是描述n個個體間的關(guān)系。,2024/3/18,計算機(jī)學(xué)院,16/70,,定義2.1′：設(shè)D為非空的個體域，定

17、義在Dn(表示n個客體都在個體域D上取值)上取值于｛0,1｝上的n元函數(shù)，稱為n元命題函數(shù)或n元謂詞,記為P(x1,x2,…,xn)。此時，客體變元x1,x2,…,xn的定義域都為D， P(x1,x2,…,xn)的值域為{0，1｝。注意：n元謂詞中的客體或客體變元是有一定次序的。 如A（4，3）為T，A（3，4）為F。 如果謂詞中為客體變元,我們稱為謂詞填式(謂詞命名式,n元命題函數(shù))。 如S(x),A(x,y

18、)，不能判斷真和假。 只有將具體的客體代替客體變元，才能判斷真和假。,2024/3/18,計算機(jī)學(xué)院,17/70,,定義2.1′：設(shè)D為非空的個體域，定義在Dn(表示n個客體都在個體域D上取值)上取值于｛0,1｝上的n元函數(shù)，稱為n元命題函數(shù)或n元謂詞,記為P(x1,x2,…,xn)。此時，客體變元x1,x2,…,xn的定義域都為D， P(x1,x2,…,xn)的值域為{0，1｝。注意：n元謂詞中的客體或客體變元是有一定次序的

19、。 如A（4，3）為T，A（3，4）為F。 如果謂詞中為客體變元,我們稱為謂詞填式(謂詞命名式,n元命題函數(shù))。 如S(x),A(x,y)，不能判斷真和假。 只有將具體的客體代替客體變元，才能判斷真和假。,2024/3/18,計算機(jī)學(xué)院,18/70,,客體取值的范圍叫個體域(論域)。 謂詞通常用于高級程序語言的控制語句中， 如 if x>3 then y:=5 ‘x>3’是謂

20、詞，x>3的值由x的現(xiàn)行值確定。n元謂詞和命題的關(guān)系： P(x,y,z):x+y=z 3元謂詞 x=3,P(3,y,z):3+y=z 2元謂詞 x=3,y=4,P(3,4,z):3+4=z 1元謂詞 x=3,y=4,z=5,P(3,4,5):3+4=5 0元謂詞(命題)F可見， 0元謂詞就是命題；命題是謂詞的特殊情況，謂詞是命題的擴(kuò)充。,202

21、4/3/18,計算機(jī)學(xué)院,19/70,,客體取值的范圍叫個體域(論域)。 謂詞通常用于高級程序語言的控制語句中， 如 if x>3 then y:=5 ‘x>3’是謂詞，x>3的值由x的現(xiàn)行值確定。n元謂詞和命題的關(guān)系： P(x,y,z):x+y=z 3元謂詞 x=3,P(3,y,z):3+y=z 2元謂詞 x=3,y=4,P(3,4,z)

22、:3+4=z 1元謂詞 x=3,y=4,z=5,P(3,4,5):3+4=5 0元謂詞(命題)F可見， 0元謂詞就是命題；命題是謂詞的特殊情況，謂詞是命題的擴(kuò)充。,2024/3/18,計算機(jī)學(xué)院,20/70,,客體取值的范圍叫個體域(論域)。 謂詞通常用于高級程序語言的控制語句中， 如 if x>3 then y:=5 ‘x>3’是謂詞，x>3的值由x的現(xiàn)行值確定。n元謂詞

23、和命題的關(guān)系： P(x,y,z):x+y=z 3元謂詞 x=3,P(3,y,z):3+y=z 2元謂詞 x=3,y=4,P(3,4,z):3+4=z 1元謂詞 x=3,y=4,z=5,P(3,4,5):3+4=5 0元謂詞(命題)F可見， 0元謂詞就是命題；命題是謂詞的特殊情況，謂詞是命題的擴(kuò)充。,2024/3/18,計算機(jī)學(xué)院,21/70,,個體域?qū)?/p>

24、命題的真值有直接的影響。 如P(x) :x是科學(xué)家。 x在科學(xué)家范圍內(nèi)，則P(x)為T，x不在科學(xué)家范圍內(nèi)，則P(x)為F。 x只在科學(xué)家范圍內(nèi)，則P(x)為永真。每個謂詞一般都有各自的個體域，把各種個體域綜合在一起作為論述范圍的域叫全總個體域（全論域）用E表示。,2024/3/18,計算機(jī)學(xué)院,22/70,,個體域?qū)γ}的真值有直接的影響。 如P(x) :x是科學(xué)家。 x在科學(xué)家范圍內(nèi)，則P(x)為T，x不

25、在科學(xué)家范圍內(nèi)，則P(x)為F。 x只在科學(xué)家范圍內(nèi)，則P(x)為永真。每個謂詞一般都有各自的個體域，把各種個體域綜合在一起作為論述范圍的域叫全總個體域（全論域）用E表示。,2024/3/18,計算機(jī)學(xué)院,23/70,幾個結(jié)論,1）謂詞中個體詞的順序是十分重要的，不能隨意變更。2）一元謂詞用以描述某一個客體的某種特性或性質(zhì)，而n元謂詞（二個以上）則用以描述n個客體之間的關(guān)系。3）0元謂詞(不含客體詞的)實際上就是一般的命題。

26、4）具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。5）一個n元謂詞不是一個命題，但將n元謂詞中的客體變元都用個體域中具體的客體取代后，就成為一個命題。而且，客體變元在不同的個體域中取不同的值對是否成為命題及命題的真值有很大的影響。,2024/3/18,計算機(jī)學(xué)院,24/70,幾個結(jié)論,1）謂詞中個體詞的順序是十分重要的，不能隨意變更。2）一元謂詞用以描述某一個客體的某

27、種特性或性質(zhì)，而n元謂詞（二個以上）則用以描述n個客體之間的關(guān)系。3）0元謂詞(不含客體詞的)實際上就是一般的命題。4）具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。5）一個n元謂詞不是一個命題，但將n元謂詞中的客體變元都用個體域中具體的客體取代后，就成為一個命題。而且，客體變元在不同的個體域中取不同的值對是否成為命題及命題的真值有很大的影響。,2024/3/18,計

28、算機(jī)學(xué)院,25/70,幾個結(jié)論,1）謂詞中個體詞的順序是十分重要的，不能隨意變更。2）一元謂詞用以描述某一個客體的某種特性或性質(zhì)，而n元謂詞（二個以上）則用以描述n個客體之間的關(guān)系。3）0元謂詞(不含客體詞的)實際上就是一般的命題。4）具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。5）一個n元謂詞不是一個命題，但將n元謂詞中的客體變元都用個體域中具體的客體取代后，就

29、成為一個命題。而且，客體變元在不同的個體域中取不同的值對是否成為命題及命題的真值有很大的影響。,2024/3/18,計算機(jī)學(xué)院,26/70,幾個結(jié)論,1）謂詞中個體詞的順序是十分重要的，不能隨意變更。2）一元謂詞用以描述某一個客體的某種特性或性質(zhì)，而n元謂詞（二個以上）則用以描述n個客體之間的關(guān)系。3）0元謂詞(不含客體詞的)實際上就是一般的命題。4）具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者

30、不是命題，它的真值是不確定的。5）一個n元謂詞不是一個命題，但將n元謂詞中的客體變元都用個體域中具體的客體取代后，就成為一個命題。而且，客體變元在不同的個體域中取不同的值對是否成為命題及命題的真值有很大的影響。,2024/3/18,計算機(jī)學(xué)院,27/70,幾個結(jié)論,1）謂詞中個體詞的順序是十分重要的，不能隨意變更。2）一元謂詞用以描述某一個客體的某種特性或性質(zhì)，而n元謂詞（二個以上）則用以描述n個客體之間的關(guān)系。3）0元謂詞(不含

31、客體詞的)實際上就是一般的命題。4）具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。5）一個n元謂詞不是一個命題，但將n元謂詞中的客體變元都用個體域中具體的客體取代后，就成為一個命題。而且，客體變元在不同的個體域中取不同的值對是否成為命題及命題的真值有很大的影響。,2024/3/18,計算機(jī)學(xué)院,28/70,二、量詞 Quantifier,在蘇格拉底三段論的例子中，如要對

32、句子： P：H(x)→D(x)（所有的人都是要死的）求否定，則有：～(H(x)→D(x))＝～～H(ｘ)∧～Ｄ(ｘ)＝H(ｘ)∧～Ｄ(ｘ) 上述式子說明：“命題P”的否定是：“所有的人都不死”。 但這與人們在日常生活中對命題：“所有人都是要死的”的否定為：“并非一切的人都是要死的”。顯然相差甚遠(yuǎn)。 其原因在于： 命題P的確切含義是：“對任意的x，如果x是人，則x是要死的”。但H(x)→D(x)并沒有確切地表示出“對任意x”這

33、個意思，亦即H(x)→D(x)不是一個命題,2024/3/18,計算機(jī)學(xué)院,29/70,二、量詞 Quantifier,在蘇格拉底三段論的例子中，如要對句子： P：H(x)→D(x)（所有的人都是要死的）求否定，則有：～(H(x)→D(x))＝～～H(ｘ)∧～Ｄ(ｘ)＝H(ｘ)∧～Ｄ(ｘ) 上述式子說明：“命題P”的否定是：“所有的人都不死”。但這與人們在日常生活中對命題：“所有人都是要死的”的否定為：“并非一切的人都是要死的”。顯

34、然相差甚遠(yuǎn)。 其原因在于： 命題P的確切含義是：“對任意的x，如果x是人，則x是要死的”。但H(x)→D(x)并沒有確切地表示出“對任意x”這個意思，亦即H(x)→D(x)不是一個命題,2024/3/18,計算機(jī)學(xué)院,30/70,二、量詞 Quantifier,在蘇格拉底三段論的例子中，如要對句子： P：H(x)→D(x)（所有的人都是要死的）求否定，則有：～(H(x)→D(x))＝～～H(ｘ)∧～Ｄ(ｘ)＝H(ｘ)∧～Ｄ(

35、ｘ)上述式子說明：“命題P”的否定是：“所有的人都不死”。但這與人們在日常生活中對命題：“所有人都是要死的”的否定為：“并非一切的人都是要死的”。顯然相差甚遠(yuǎn)。 其原因在于： 命題P的確切含義是：“對任意的x，如果x是人，則x是要死的”。但H(x)→D(x)并沒有確切地表示出“對任意x”這個意思，亦即H(x)→D(x)不是一個命題,2024/3/18,計算機(jī)學(xué)院,31/70,例1.4：,符號化下述命題： 1）所有的老虎都要

36、吃人； 2）每一個人都會犯錯誤； 3）有一些人會摔跤； 4）有一些人是大學(xué)生； 5）每一個帶傘的人都不怕雨； 6）有一些自然數(shù)是素數(shù)。 上述每一個描述量詞的語句下劃有“下劃線”。,2024/3/18,計算機(jī)學(xué)院,32/70,例1.4（續(xù)1）,解：設(shè)立如下謂詞： R(x)：x會吃人；P(x)：x會犯錯誤； N(x)：x會摔跤；Q(x)：x是大學(xué)生； C(x)：x不

37、怕雨；S(x)：x是素數(shù)。 則有： 1）所有的x，R(x) x?{老虎｝； 2）每一個x，P(x) x?{人}； 3）有一些x，N(x) x?{人}； 4）有一些x，Q(x) x?{人}； 5）每一個x，C(x) x?{帶傘的人}； 6）有一些x，S(x) x ?{自然數(shù)}。,20

38、24/3/18,計算機(jī)學(xué)院,33/70,量詞的定義：,上述一系列例子，都僅僅只符號化了一部分內(nèi)容，而對句子中的“對每一個”，“對任意的”，“有一些”等等無法用謂詞來表示，這些都是與客體詞的數(shù)量有關(guān)的語句。為了把它們符號化，引進(jìn)如下兩個符號： (?x):所有的x； (?x):有些x； 任意的x； 至少有一個x； 一切的x； 存在x； 每一個x；等等。 等等。定義2.1.2:(?x)稱為全稱量詞。(

39、?x)為存在量詞,其中的x稱為作用變量。一般將量詞加在謂詞之前，記為(?x)F(x), (?x)F(x)。,2024/3/18,計算機(jī)學(xué)院,34/70,量詞的定義：,上述一系列例子，都僅僅只符號化了一部分內(nèi)容，而對句子中的“對每一個”，“對任意的”，“有一些”等等無法用謂詞來表示，這些都是與客體詞的數(shù)量有關(guān)的語句。為了把它們符號化，引進(jìn)如下兩個符號： (?x):所有的x； (?x):有些x； 任意的x； 至少有一個

40、x； 一切的x； 存在x； 每一個x；等等。 等等。定義2.2:(?x)稱為全稱量詞。(?x)為存在量詞,其中的x稱為作用變量。一般將量詞加在謂詞之前，記為(?x)F(x), (?x)F(x)。,2024/3/18,計算機(jī)學(xué)院,35/70,量詞的定義：,上述一系列例子，都僅僅只符號化了一部分內(nèi)容，而對句子中的“對每一個”，“對任意的”，“有一些”等等無法用謂詞來表示，這些都是與客體詞的數(shù)量有關(guān)的語句。為了把它們符號

41、化，引進(jìn)如下兩個符號： (?x):所有的x； (?x):有些x； 任意的x； 至少有一個x； 一切的x； 存在x； 每一個x；等等。 等等。定義2.2:(?x)稱為全稱量詞。(?x)為存在量詞,其中的x稱為作用變量。一般將量詞加在謂詞之前，記為(?x)F(x), (?x)F(x)。,,全稱量化命題,,存在量化命題,2024/3/18,計算機(jī)學(xué)院,36/70,例1.4 (續(xù)2),在例1.4中，利用量

42、詞則有： (?x)R(x)(x?{老虎}) (?x)P(x) (x?{人}) (?x)N(x)(x?{人}) (?x)Q(x)(x?{人}) (?x)C(x)(x?{帶傘的人}) (?x)S(x)(x?{自然數(shù)})前面蘇格拉底三段論中的P也可表示為：(?x)(H(x)→D(x))。,2024/3/18,計算機(jī)學(xué)院,37/70,例1.4 (續(xù)2),在例1.4中，利用量詞則

43、有： (?x)R(x)(x?{老虎}) (?x)P(x) (x?{人}) (?x)N(x)(x?{人}) (?x)Q(x)(x?{人}) (?x)C(x)(x?{帶傘的人}) (?x)S(x)(x?{自然數(shù)})前面蘇格拉底三段論中的P也可表示為：(?x)(H(x)→D(x))。,2024/3/18,計算機(jī)學(xué)院,38/70,不便之處,1)從書寫上十分不便，總要特別注明個體

44、域。 2)在同一個比較復(fù)雜的句子中，對于不同命題函數(shù)中的個體可能屬于不同的個體域，此時無法清晰表達(dá)。 3)有時，由于個體域的注明不清楚，造成無法確定其真值。對于同一個公式，不同的個體域有可能帶來不同的真值。如(?x)(x＋6＝5):1）在實數(shù)范圍內(nèi)時，確有x＝-1使得x＋6＝5， 因此，(?x)(x＋6＝5)為“真”。2）在正整數(shù)范圍內(nèi)時，則找不到任何x，使得 x＋6＝5為“真”，所以，(?x)(x＋6＝5)為

45、“假”。,2024/3/18,計算機(jī)學(xué)院,39/70,不便之處,1)從書寫上十分不便，總要特別注明個體域。 2)在同一個比較復(fù)雜的句子中，對于不同命題函數(shù)中的個體可能屬于不同的個體域，此時無法清晰表達(dá)。 3)有時，由于個體域的注明不清楚，造成無法確定其真值。對于同一個公式，不同的個體域有可能帶來不同的真值。如(?x)(x＋6＝5):1）在實數(shù)范圍內(nèi)時，確有x＝-1使得x＋6＝5， 因此，(?x)(x＋6＝5)為“真”。

46、2）在正整數(shù)范圍內(nèi)時，則找不到任何x，使得 x＋6＝5為“真”，所以，(?x)(x＋6＝5)為“假”。,2024/3/18,計算機(jī)學(xué)院,40/70,三、全總個體域,基于上述情況，有必要對個體域進(jìn)行統(tǒng)一，全部使用全總個體域，此時，對每一個句子中客體變量的變化范圍用一定的特性謂詞刻劃之。而統(tǒng)一成全總個體域后，此全總個體域在謂詞公式中就不必特別說明，常常省略不記。同時，這種特性謂詞在加入到命題函數(shù)中時必定遵循如下原則：,1）對于全稱

47、量詞，刻劃其對應(yīng)個體域的特性謂詞作為蘊涵的前件加入。 2）對于存在量詞，刻劃其對應(yīng)個體域的特性謂詞作為合取式之合取項加入。,2024/3/18,計算機(jī)學(xué)院,41/70,三、全總個體域,基于上述情況，有必要對個體域進(jìn)行統(tǒng)一，全部使用全總個體域，此時，對每一個句子中客體變量的變化范圍用一定的特性謂詞刻劃之。而統(tǒng)一成全總個體域后，此全總個體域在謂詞公式中就不必特別說明，常常省略不記。同時，這種特性謂詞在加入到命題函數(shù)中時必定遵循如下原則

48、：,1）對于全稱量詞，刻劃其對應(yīng)個體域的特性謂詞作為蘊涵的前件加入。(P29) 2）對于存在量詞，刻劃其對應(yīng)個體域的特性謂詞作為合取式之合取項加入。(P29),2024/3/18,計算機(jī)學(xué)院,42/70,例1.4 (續(xù)3),對于例1．4 中的例子運用特性謂詞描述。,解：U(x)：x是老虎；(?x)(U(x)→R(x))H(x)：x是人； (?x)(H(x)→P(x))H(x)：x是人； (?x)(H(

49、x)∧N(x))H(x)：x是人；(?x)(H(x)∧Q(x))M(x)：x是帶傘的人；(?x)(M(x)→C(x))T(x)：x是自然數(shù)；(?x)(T(x)∧S(x)),蘇格拉底三段論可完整翻譯為： (?x)(H(x)→D(x))，H(S)?D(S) ～(?x)(H(x)→D(x))＝(?x)(H(ｘ)∧～D(ｘ)),2024/3/18,計算機(jī)學(xué)院,43/70,例1.4 (續(xù)3),對于例1．4 中的例子運用特

50、性謂詞描述。,解：U(x)：x是老虎；(?x)(U(x)→R(x))H(x)：x是人； (?x)(H(x)→P(x))H(x)：x是人； (?x)(H(x)∧N(x))H(x)：x是人；(?x)(H(x)∧Q(x))M(x)：x是帶傘的人；(?x)(M(x)→C(x))T(x)：x是自然數(shù)；(?x)(T(x)∧S(x)),蘇格拉底三段論可完整翻譯為： (?x)(H(x)→D(x))，H

51、(S)?D(S) ～(?x)(H(x)→D(x))＝(?x)(H(ｘ)∧～D(ｘ)),2024/3/18,計算機(jī)學(xué)院,44/70,例1.5:,符號化下述語句：天下烏鴉一般黑；那位身體強(qiáng)健的、用功的、肯于思考的大學(xué)生，解決了一個數(shù)學(xué)難題；張強(qiáng)和李平都是足球運動員；每個實數(shù)都存在比它大的另外的實數(shù)。并非所有的動物都是脊椎動物；盡管有人很聰明，但未必一切人都聰明；對于任意給定的?>0，必存在著?>0，使得對任意

52、的x，只要|x-a|<?，就有： |f(x)-f(a)|<?成立。,2024/3/18,計算機(jī)學(xué)院,45/70,例1.5 (續(xù)1),解： 1）設(shè) F(x)：x是烏鴉；G(x,y)：x與y一般黑。 則句子1）可完整地符號化為： (?x)(?y)(F(x)∧F(y)→G(x，y)) 或 ～(?x)(?y)(F(x)∧F(y)∧～G(x，y)) 2）設(shè) P(x)：x是身體強(qiáng)健的；Q(x)

53、：x是用功的；R(x)：x是肯于思考的； S(x)：x是大學(xué)生；T(x，y)：x解決了y；a：那位；b：一個數(shù)學(xué)難題。 則句子2）可完整地符號化為：P(a)∧Q(a)∧R(a)∧S(a)∧T(a，b),2024/3/18,計算機(jī)學(xué)院,46/70,例1.5 (續(xù)1),解： 1）設(shè) F(x)：x是烏鴉；G(x,y)：x與y一般黑。 則句子1）可完整地符號化為： (?x)(?y)(F(x)∧F(y)→G

54、(x，y)) 或 ～(?x)(?y)(F(x)∧F(y)∧～G(x，y)) 2）設(shè) P(x)：x是身體強(qiáng)健的；Q(x)：x是用功的；R(x)：x是肯于思考的； S(x)：x是大學(xué)生；T(x，y)：x解決了y；a：那位；b：一個數(shù)學(xué)難題。 則句子2）可完整地符號化為：P(a)∧Q(a)∧R(a)∧S(a)∧T(a，b),2024/3/18,計算機(jī)學(xué)院,47/70,例1.5 (續(xù)2),3）設(shè)Z(x)：

55、x是足球運動員；c：張強(qiáng)，d：李平。則句子3）可完整地符號化為： Z(c)∧Z(d)4）設(shè)R(x)：x是實數(shù)；L(x,y)：x小于y。則句子4)可以完整地符號化為：(?x)(R(x)→(?y)(R(y)∧L(x，y))。5）設(shè)A(x)：x是動物；B(x)：x是脊椎動物。則句子5）可以完整地符號化為：～(?x)(A(x)→B(x))或 (?x)(A(x)∧～B(x)),2024/3/18,計算機(jī)學(xué)院,48/70,例1

56、.5 (續(xù)2),3）設(shè)Z(x)：x是足球運動員；c：張強(qiáng)，d：李平。則句子3）可完整地符號化為： Z(c)∧Z(d)4）設(shè)R(x)：x是實數(shù)；L(x,y)：x小于y。則句子4)可以完整地符號化為：(?x)(R(x)→(?y)(R(y)∧L(x，y))。5）設(shè)A(x)：x是動物；B(x)：x是脊椎動物。則句子5）可以完整地符號化為：～(?x)(A(x)→B(x))或 (?x)(A(x)∧～B(x)),2024/3/1

57、8,計算機(jī)學(xué)院,49/70,例1.5 (續(xù)2),3）設(shè)Z(x)：x是足球運動員；c：張強(qiáng)，d：李平。則句子3）可完整地符號化為： Z(c)∧Z(d)4）設(shè)R(x)：x是實數(shù)；L(x,y)：x小于y。則句子4)可以完整地符號化為：(?x)(R(x)→(?y)(R(y)∧L(x，y))。5）設(shè)A(x)：x是動物；B(x)：x是脊椎動物。則句子5）可以完整地符號化為：～(?x)(A(x)→B(x))或 (?x)(A(x)

58、∧～B(x)),2024/3/18,計算機(jī)學(xué)院,50/70,例1.5 (續(xù)3),6）設(shè)M(x)：x是人。 C(x)：x很聰明。 則句子6）可以完整地符號化為： (?x)(M(x)∧C(x))∧～(?x)(M(x)→C(x))7）設(shè)個體域為實數(shù)集合，則原命題可符號化為： (??)((?>0)→(??)((?>0)∧ ((|x-a|<?)→(|f(x)-f(a)|<?)))),202

59、4/3/18,計算機(jī)學(xué)院,51/70,例1.5 (續(xù)3),6）設(shè)M(x)：x是人。 C(x)：x很聰明。 則句子6）可以完整地符號化為： (?x)(M(x)∧C(x))∧～(?x)(M(x)→C(x))7）設(shè)個體域為實數(shù)集合，則原命題可符號化為： (??)((?>0)→(??)((?>0)∧ ((|x-a|<?)→(|f(x)-f(a)|<?)))),2024/3/18,計算機(jī)學(xué)

60、院,52/70,四、自由變元與約束變元,定義2.3：在表達(dá)式?xA(x)或?xA(x)中，x稱為指導(dǎo)（作用）變元，A(x)稱為相應(yīng)量詞的轄域（作用域）。在轄域中x的所有出現(xiàn)稱為x在公式A中的約束出現(xiàn)， 此時的變元x稱為約束變元。 A中不是約束出現(xiàn)的其它變元稱為自由變元。例1.6： a）?x(P(x)→Q(x)):?x的轄域為P（x）→Q(x),x為約 束變元。 b）?xP(x)→Q(x):?x的轄域為P(x),x為約

61、束出現(xiàn)， Q(x)中的x為自由出現(xiàn)。,2024/3/18,計算機(jī)學(xué)院,53/70,四、自由變元與約束變元,定義2.3：在表達(dá)式?xA(x)或?xA(x)中，x稱為指導(dǎo)（作用）變元，A(x)稱為相應(yīng)量詞的轄域（作用域）。在轄域中x的所有出現(xiàn)稱為x在公式A中的約束出現(xiàn)， 此時的變元x稱為約束變元。 A中不是約束出現(xiàn)的其它變元稱為自由變元。例1.6： a）?x(P(x)→Q(x)):?x的轄域為P（x）→Q(x),x為約

62、 束變元。 b）?xP(x)→Q(x):?x的轄域為P(x),x為約束出現(xiàn)， Q(x)中的x為自由出現(xiàn)。,2024/3/18,計算機(jī)學(xué)院,54/70,四、自由變元與約束變元,定義2.3：在表達(dá)式?xA(x)或?xA(x)中，x稱為指導(dǎo)（作用）變元，A(x)稱為相應(yīng)量詞的轄域（作用域）。在轄域中x的所有出現(xiàn)稱為x在公式A中的約束出現(xiàn)， 此時的變元x稱為約束變元。 A中不是約束出現(xiàn)的其它變元稱為 自由變元。例1.6：

63、 a）?x(P(x)→Q(x)):?x的轄域為P（x）→Q(x),x為約 束變元。 b）?xP(x)→Q(x):?x的轄域為P(x),x為約束出現(xiàn)， Q(x)中的x為自由出現(xiàn)。,2024/3/18,計算機(jī)學(xué)院,55/70,,c)?x?y(P(x,y)∧Q(y,z))∧?xP(x,y): ?x?y的轄域是P(x,y) ∧Q(y,z),x,y為約束變元，z為自由變元， ?x的轄域是P(x,y),x是約束變元，y

64、是自由變元。一個公式中允許一個變元既是約束出現(xiàn),又是自由出現(xiàn)。為了避免由于變元的約束與自由同時出現(xiàn),引起概念上的混亂,故可對約束變元換名,對自由變元代入,使得一個變元在一個公式中只以一種形式出現(xiàn),即把變元的自由出現(xiàn)和約束出現(xiàn)分開。,2024/3/18,計算機(jī)學(xué)院,56/70,,c)?x?y(P(x,y)∧Q(y,z))∧?xP(x,y): ?x?y的轄域是P(x,y) ∧Q(y,z),x,y為約束變元，z為自由變元， ?x的轄域是

65、P(x,y),x是約束變元，y是自由變元。一個公式中允許一個變元既是約束出現(xiàn),又是自由出現(xiàn)。為了避免由于變元的約束與自由同時出現(xiàn),引起概念上的混亂,故可對約束變元換名,對自由變元代入,使得一個變元在一個公式中只以一種形式出現(xiàn),即把變元的自由出現(xiàn)和約束出現(xiàn)分開。,2024/3/18,計算機(jī)學(xué)院,57/70,兩個規(guī)則:,規(guī)則1 (約束變元的換名規(guī)則)：1）將量詞中出現(xiàn)的變元以及該量詞轄域中此變量之所有約束出現(xiàn)都用新的個體變元替換。2）

66、新的變元一定要有別于改名轄域中的所有其它變量。規(guī)則2 (自由變元的代入規(guī)則)：1）將公式中出現(xiàn)該自由變元的每一處都用新的個體變元替換。2）新變元不允許在原公式中以任何約束形式出現(xiàn)。,2024/3/18,計算機(jī)學(xué)院,58/70,兩個規(guī)則:,規(guī)則1 (約束變元的換名規(guī)則)：1）將量詞中出現(xiàn)的變元以及該量詞轄域中此變量之所有約束出現(xiàn)都用新的個體變元替換。2）新的變元一定要有別于改名轄域中的所有其它變量。規(guī)則2 (自由變元的代入規(guī)則

67、)：1）將公式中出現(xiàn)該自由變元的每一處都用新的個體變元替換。2）新變元不允許在原公式中以任何約束形式出現(xiàn)。,2024/3/18,計算機(jī)學(xué)院,59/70,例1.7：,設(shè)P(x)：x是素數(shù)I(x)：x是整數(shù)Q(x,y)：x+y=0 用語句描述下述句子，并判斷其真假值。(?x)(I(x)→P(x))(?x)(I(x)∧P(x))(?x)(?y)(I(x)∧I(y)→Q(x，y))(?x)(I(x)→(?y)(I

68、(y)∧Q(x，y)))(?x)(?y)(I(x)∧(I(y)→Q(x，y))),2024/3/18,計算機(jī)學(xué)院,60/70,例1.7：,設(shè)P(x)：x是素數(shù)I(x)：x是整數(shù)Q(x,y)：x+y=0 用語句描述下述句子，并判斷其真假值。(?x)(I(x)→P(x))(?x)(I(x)∧P(x))(?x)(?y)(I(x)∧I(y)→Q(x，y))(?x)(I(x)→(?y)(I(y)∧Q(x，y)))(

69、?x)(?y)(I(x)∧(I(y)→Q(x，y))),2024/3/18,計算機(jī)學(xué)院,61/70,例1.7： （續(xù)）,可描述為：“對任意的整數(shù)x，x一定是素數(shù)”,真值為“假”。(?x)(I(x)→P(x))可描述為：“存在一些整數(shù)x，x是素數(shù)”，真值為“真”。 (?x)(I(x)∧P(x))可描述為：“對任意的整數(shù)x，y，都有x+y=0”，真值為“假”。(?x)(?y)(I(x)∧I(y)→Q(x，y))可描述為：“對任意的整數(shù)