離散數(shù)學(xué)(第8講)

1、馮偉森Email：07 八月 2022離散數(shù)學(xué)計(jì)算機(jī)學(xué)院2022/8/7計(jì)算機(jī)學(xué)院2主要內(nèi)容 量詞化邏輯 1、謂詞 2、量詞 3、全總個(gè)體域 4、自由變?cè)c約束變?cè)?2022/8/7計(jì)算機(jī)學(xué)院3 命題邏輯是數(shù)理邏輯的基礎(chǔ)，主要研究命題和命題間的演算。原子命題是命題演算的基本單位，并把它看作是不可再分解。這就帶來了命題邏輯的局限性。命題邏輯研究的范圍限制在命題及其外部關(guān)系上，無法研究命題內(nèi)部的成份、結(jié)構(gòu)以及命題之間所具有的邏輯特征（共同性和差異性） 例2-11 設(shè)基本命題，P：李明是大學(xué)生 Q：王芳是大學(xué)生 R：松樹是植物 很明顯，P與Q在內(nèi)部關(guān)系上，應(yīng)該比R密切得多。然而，命題邏輯無法反映這種

2、區(qū)別，也無法反映P、Q間的共同性。序2022/8/7計(jì)算機(jī)學(xué)院4 例2-1.2 (著名的蘇格拉底三段論) 設(shè)自然語言中的三個(gè)命題：1）所有的人都是要死的；2）蘇格拉底是人；3）所以，蘇格拉底是要死的。解：假設(shè) P：所有的人都是要死的；Q：蘇格拉底是人。R：蘇格拉底是要死的。顯然，無論用什么方法也無法推論出 P，Q R。 但是，這樣簡(jiǎn)單的，憑直覺就知蘇格拉底的論證是正確的推理，命題邏輯卻無能為力。這是由命題邏輯的局限性造成的，因此，需要對(duì)命題的內(nèi)部關(guān)系進(jìn)行研究。2022/8/7計(jì)算機(jī)學(xué)院52.1 量詞化邏輯謂詞和量詞一、謂詞 Predlicate 在對(duì)命題的內(nèi)部邏輯關(guān)系進(jìn)行研究時(shí)，把基本命題分成

3、客體(個(gè)體）和謂詞。客體獨(dú)立存在的具體事物或抽象概念（即命題中所描述的對(duì)象。如主語，客觀實(shí)體等）。謂詞刻劃客體的性質(zhì)（特征）或描述客體間的關(guān)系。謂詞一般用大寫字母（串）表示;個(gè)體用小寫字母表示。2022/8/7計(jì)算機(jī)學(xué)院6例2-1.3如有句子：張紅是一個(gè)四川大學(xué)的學(xué)生；王南是一個(gè)四川大學(xué)的學(xué)生；李華是一個(gè)四川大學(xué)的學(xué)生。則在命題邏輯中必須要用三個(gè)命題P，Q，R來表示。但是，它們都具有一個(gè)共同的特征： “是一個(gè)四川大學(xué)的學(xué)生”因此，若將句子分解成：“主語謂語”用P表示“是一個(gè)四川大學(xué)的學(xué)生”，P后緊跟“某某人”。則上述句子可寫為：P(張紅)；P(王南)；P(李華)。一般地，P(x)：x是一個(gè)四川

4、大學(xué)的學(xué)生。P：謂詞x：客體詞P(x)：命題函數(shù)2022/8/7計(jì)算機(jī)學(xué)院7與謂詞相聯(lián)系的個(gè)體的數(shù)目，就是謂詞的元數(shù)。描述一個(gè)個(gè)體的性質(zhì)的謂詞叫“一元謂詞”。描述兩個(gè)個(gè)體間的關(guān)系的謂詞叫“二元謂詞”。如A：比大命題4比3大表示成A（4，3）描述三個(gè)個(gè)體間的關(guān)系的謂詞叫“三元謂詞”。如B：在和之間 B（n,c,z）：內(nèi)江在成都與重慶之間。定義2.1 設(shè)D是由客體構(gòu)成的稱為個(gè)體域的非空集合，以D中元素為值的變?cè)Q為客體變?cè)?。由形?謂詞標(biāo)識(shí)符（客體變?cè)?，客體變?cè)?，客體變?cè)猲） 構(gòu)成的、其值為“真”或“假”的表達(dá)式，稱為n元謂詞。即n元謂詞是描述n個(gè)個(gè)體間的關(guān)系。2022/8/7計(jì)算機(jī)學(xué)院8命題

5、函數(shù) 設(shè)D為非空的個(gè)體域，定義在Dn(表示n個(gè)客體都在個(gè)體域(論域) D上取值)上取值于0,1上的n元函數(shù)，稱為n元命題函數(shù),記為P(x1,x2,xn)。此時(shí)，客體變?cè)獂1,x2,xn的定義域都為D， P(x1,x2,xn)的值域?yàn)?，1。 因此，n元謂詞也可稱為n元命題函數(shù)。 注意：n元謂詞中的客體或客體變?cè)怯幸欢ù涡虻摹?如A（4，3）為T，A（3，4）為F。2022/8/7計(jì)算機(jī)學(xué)院9 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,

6、5):3+4=5 0元謂詞(命題)F 可見，0元謂詞就是命題；命題是謂詞的特殊情況，謂詞是命題的擴(kuò)充。 每個(gè)謂詞一般都有各自的個(gè)體域，把各種個(gè)體域綜合在一起作為論述范圍的域叫全總個(gè)體域（全論域）用E表示。2022/8/7計(jì)算機(jī)學(xué)院10幾個(gè)結(jié)論1) 謂詞中個(gè)體詞的順序是十分重要的，不能隨意變更。2) 一元謂詞用以描述某一個(gè)客體的某種特性或性質(zhì)，而n元謂詞（二個(gè)以上）則用以描述n個(gè)客體之間的關(guān)系。3) 0元謂詞(不含客體詞的)實(shí)際上就是一般的命題。具體命題的謂詞表示形式和n元命題函數(shù)(n元謂詞)是不同的，前者是有真值的，而后者不是命題，它的真值是不確定的。一個(gè)n元謂詞不是一個(gè)命題，但將n元謂詞中的

7、客體變?cè)加脗€(gè)體域中具體的客體取代后，就成為一個(gè)命題。而且，客體變?cè)诓煌膫€(gè)體域中取不同的值對(duì)是否成為命題及命題的真值有很大的影響。2022/8/7計(jì)算機(jī)學(xué)院11二、量詞 Quantifier 在蘇格拉底三段論的例子中，如要對(duì)句子： P：H(x)D(x)（所有的人都是要死的）求否定，則有：(H(x)D(x)H()()H()()上述式子說明：“命題P”的否定是：“所有的人都不死”。但這與人們?cè)谌粘Ｉ钪袑?duì)命題：“所有人都是要死的”。的否定為：“并非一切的人都是要死的”。顯然相差甚遠(yuǎn)。其原因在于：命題P的確切含義是：“對(duì)任意的x，如果x是人，則x是要死的”。但H(x)D(x)并沒有確切地表示出“

8、對(duì)任意x”這個(gè)意思，亦即H(x)D(x)不是一個(gè)命題2022/8/7計(jì)算機(jī)學(xué)院12例2-14符號(hào)化下述命題：所有的老虎都要吃人；每一個(gè)人都會(huì)犯錯(cuò)誤；有一些人會(huì)摔跤；有一些人是大學(xué)生；每一個(gè)帶傘的人都不怕雨；有一些自然數(shù)是素?cái)?shù)。 上述每一個(gè)描述量詞的語句下劃有“下劃線”。2022/8/7計(jì)算機(jī)學(xué)院13例2-14(續(xù)1)解：設(shè)立如下謂詞：R(x)：x會(huì)吃人；P(x)：x會(huì)犯錯(cuò)誤；N(x)：x會(huì)摔跤；Q(x)：x是大學(xué)生；C(x)：x不怕雨；S(x)：x是素?cái)?shù)。則有：（1）所有的x，R(x) x老虎； （2）每一個(gè)x，P(x) x人； （3）有一些x，N(x) x人； （4）有一些x，Q(x) x人

9、； （5）每一個(gè)x，C(x) x帶傘的人； （6）有一些x，S(x) x 自然數(shù)。 計(jì)算機(jī)學(xué)院14量詞的定義 上述一系列例子，都僅僅只符號(hào)化了一部分內(nèi)容，而對(duì)句子中的“對(duì)每一個(gè)”，“對(duì)任意的”，“有一些”等等無法用謂詞來表示，這些都是與客體詞的數(shù)量有關(guān)的語句。為了把它們符號(hào)化，引進(jìn)如下兩個(gè)符號(hào)： (x):所有的x； (x)：有些x； 任意的x；至少有一個(gè)x； 一切的x；存在x； 每一個(gè)x；等等。 等等。2022/8/7計(jì)算機(jī)學(xué)院15定義2.2 (x)稱為全稱量詞,其中的x稱為作用變量。一般將量詞加在謂詞之前，記為(x)Q(x)。 (x)Q(x)取值為真的充分必要條件是對(duì)論域中的每個(gè)客體a，Q(

10、a)都取值為真。定義2.3 (x)為存在量詞, 記為 (x)Q(x)。 (x)Q(x)取值為真的充分必要條件是對(duì)論域中至少存在一個(gè)客體a，使Q(a)取值為真。全稱量化命題存在量化命題2022/8/7計(jì)算機(jī)學(xué)院16例2-14 (續(xù)2)在例14中，利用量詞則有：(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ù))2022/8/7計(jì)算機(jī)學(xué)院17三、全總個(gè)體域1、從書寫上十分不便，總要特別注明個(gè)體域。2、在同一個(gè)比較復(fù)雜的句子中，對(duì)于不同命題函數(shù)中的個(gè)體可能屬于不同的個(gè)體域，此時(shí)無法清晰表達(dá)。3、有時(shí)，由于個(gè)

11、體域的注明不清楚，造成無法確定其真值。對(duì)于同一個(gè)公式，不同的個(gè)體域有可能帶來不同的真值。如(x)(x65)，1）在實(shí)數(shù)范圍內(nèi)時(shí)，確有x-1使得x65， 因此，(x)(x65)為“真”。2）在正整數(shù)范圍內(nèi)時(shí)，則找不到任何x，使得x65為“真”，所以，(x)(x65)為“假”。2022/8/7計(jì)算機(jī)學(xué)院18基于上述情況，有必要對(duì)個(gè)體域進(jìn)行統(tǒng)一，全部使用全總個(gè)體域，此時(shí)，對(duì)每一個(gè)句子中客體變量的變化范圍用一定的特性謂詞刻劃之。而統(tǒng)一成全總個(gè)體域后，此全總個(gè)體域在謂詞公式中就不必特別說明，常常省略不記。同時(shí)，這種特性謂詞在加入到命題函數(shù)中時(shí)必定遵循如下原則：對(duì)于全稱量詞，刻劃其對(duì)應(yīng)個(gè)體域的特性謂詞作為

12、條件聯(lián)結(jié)詞的前件加入。對(duì)于存在量詞，刻劃其對(duì)應(yīng)個(gè)體域的特性謂詞作為合取式之合取項(xiàng)加入。2022/8/7計(jì)算機(jī)學(xué)院19例2-14 (續(xù)3)對(duì)于例14 中的例子運(yùn)用特性謂詞描述。解：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(S)D(S) (x)(H(x)D(x)(x)(H()D()2022/8/7計(jì)算機(jī)學(xué)院20例2-

13、15符號(hào)化下述語句：天下烏鴉一般黑；那位身體強(qiáng)健的、用功的、肯于思考的大學(xué)生，解決了一個(gè)數(shù)學(xué)難題；張強(qiáng)和李平都是足球運(yùn)動(dòng)員；每個(gè)實(shí)數(shù)都存在比它大的另外的實(shí)數(shù)。并非所有的動(dòng)物都是脊椎動(dòng)物；盡管有人很聰明，但未必一切人都聰明；對(duì)于任意給定的0，必存在著0，使得對(duì)任意的x，只要|x-a|，就有： |f(x)-f(a)|0)()(0)(|x-a|)(|f(x)-f(a)|)2022/8/7計(jì)算機(jī)學(xué)院24四、自由變?cè)c約束變?cè)x2.4：在表達(dá)式xA(x)或xA(x)中，x稱為指導(dǎo)（作用）變?cè)珹(x)稱為相應(yīng)量詞的轄域（作用域）。在轄域中x的所有出現(xiàn)稱為x在公式A中的約束出現(xiàn)， 此時(shí)的變?cè)獂稱為約束變

14、元。 A中不是約束出現(xiàn)的其它變?cè)Q為 自由變?cè)?022/8/7計(jì)算機(jī)學(xué)院25 一個(gè)公式中允許一個(gè)變?cè)仁羌s束出現(xiàn),又是自由出現(xiàn)。為了避免由于變?cè)募s束與自由同時(shí)出現(xiàn),引起概念上的混亂,故可對(duì)約束變?cè)獡Q名,對(duì)自由變?cè)?使得一個(gè)變?cè)谝粋€(gè)公式中只以一種形式出現(xiàn),即把變?cè)淖杂沙霈F(xiàn)和約束出現(xiàn)分開。2022/8/7計(jì)算機(jī)學(xué)院26兩個(gè)規(guī)則規(guī)則1(約束變?cè)膿Q名規(guī)則)：1）將量詞中出現(xiàn)的變?cè)约霸摿吭~轄域中此變量之所有約束出現(xiàn)都用新的個(gè)體變?cè)鎿Q。2）新的變?cè)欢ㄒ袆e于改名轄域中的所有其它變量。規(guī)則2(自由變?cè)拇胍?guī)則)：1）將公式中出現(xiàn)該自由變?cè)拿恳惶幎加眯碌膫€(gè)體變?cè)鎿Q。2）新變?cè)辉试S在

15、原公式中以任何約束形式出現(xiàn)。2022/8/7計(jì)算機(jī)學(xué)院27例2-1.6設(shè)P(x)：x是素?cái)?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)(x)(y)(I(x)(I(y)Q(x，y)2022/8/7計(jì)算機(jī)學(xué)院28可描述為：“對(duì)任意的整數(shù)x，x一定是素?cái)?shù)”,真值為“假”?？擅枋鰹椋骸按嬖谝恍┱麛?shù)x，x是素?cái)?shù)”，真值為“真”。可描述為：“對(duì)任意的整數(shù)x，y，都有x+y=0”，真值為“假”?？擅枋鰹椋骸皩?duì)任意的整數(shù)x，都存在著整數(shù)y，使得x+y=0”，真值為“真”。可描述為：“存在著整數(shù)x，使得對(duì)任意的整數(shù)y，都有x+y=0”，真值為“假”。2022/8/7計(jì)算機(jī)學(xué)院29說 明 從上面的例子可知，如有多個(gè)量詞，則讀的順序按從左到右的順序，即： (x)(y)G(x,y)(x)(y)(G(x，y) 另外，量詞對(duì)變?cè)募s束，