離散數(shù)學(xué)第2章第1節(jié)

1、1,離 散 數(shù) 學(xué)Discrete Mathematics,山東科技大學(xué)信息科學(xué)與工程學(xué)院,2,第一章 內(nèi)容回顧 一、知識(shí)點(diǎn)1．命題的概念、表示方法；聯(lián)結(jié)詞的邏輯意義。2．命題公式的遞歸定義，自然語(yǔ)言翻譯成命題公式3．真值表的構(gòu)造、命題公式等價(jià)的概念。4．重言式與蘊(yùn)含式的定義、邏輯意義，邏輯等價(jià)與邏輯蘊(yùn)含的意義和證明方法。常用的邏輯等價(jià)公式和邏輯蘊(yùn)含公式。,3,5．命題公式的對(duì)偶式、合取范式、析取范

2、式、主合取范式、主析取范式。邏輯小項(xiàng)、邏輯大項(xiàng)。任給公式化為析取范式、任給公式化為主析取范式、（所有等價(jià)公式的為主析【合】取范式是唯一的）任給公式化為合取范式、任給公式化為主合取范式。 6．命題邏輯的推理理論，主要的推理方法：真值表法、直接證明法、間接證明法。常用推理規(guī)則：P規(guī)則、T規(guī)則、CP規(guī)則。,為什么要研究謂詞邏輯？,為了刻劃命題內(nèi)部的邏輯結(jié)構(gòu)，需要研究謂詞邏輯。為了對(duì)論斷進(jìn)行推證，也要對(duì)命題的內(nèi)部關(guān)系進(jìn)行深入地研究。

3、例如簡(jiǎn)單而有名的蘇格拉底三段論都無(wú)法用命題邏輯予以推證，但可用謂詞邏輯進(jìn)行推證。,邏輯學(xué)中著名的三段論方法，是由一個(gè)大前提，一個(gè)小前提推出結(jié)論的方法。這方面的例子如： 所有的人都是要死的。 蘇格拉底是人。 所以蘇格拉底是要死的。又如： 所有的自然數(shù)都是有理數(shù)。 100是自然數(shù)。

4、 所以100是有理數(shù)。 顯然這些都是正確的推理，但在命題邏輯中卻無(wú)法得到證明，因?yàn)槿握摰拿烤湓挾际且粋€(gè)原子命題，我們可分別用P，Q，R來(lái)表示。這樣，三段論方法用形式符號(hào)表示應(yīng)為 P∧Q ? R即 P∧Q→ R?T但在命題邏輯里， P∧Q→ R顯然不是重言式。,出現(xiàn)問(wèn)題的原因在于，三段論中，結(jié)論R與前提P，Q的內(nèi)在聯(lián)系不可能在命題邏輯中表示出來(lái)。,蘇格拉

5、底三段論是正確的。但用命題邏輯卻無(wú)法推出。這是因?yàn)槊}邏輯基本組成單位是原子命題，并把它看作不可再分解的。但兩個(gè)原子命題間，常常有一些共同特征，為了刻劃命題內(nèi)部的邏輯結(jié)構(gòu)，就需研究謂詞邏輯（簡(jiǎn)稱為L(zhǎng)p）。在研究某些推理時(shí)，有必要對(duì)原子命題作進(jìn)一步分析，分析出其中的個(gè)體詞，謂詞和量詞，研究它們的形式結(jié)構(gòu)的邏輯關(guān)系、正確的推理形式和規(guī)則，這些正是謂詞邏輯的基本內(nèi)容。,所有的人都是要死的。 蘇格拉底是人。所以蘇格拉底是要死的。,蘇格拉底

6、（前469-前399） 古希臘唯心主義哲學(xué)家。,第1講 §2—1 謂詞的概念與表示 §2—2 命題函數(shù)與量詞 §2—3 謂詞公式與翻譯,要求： 1、掌握如下概念： 謂詞、謂詞填式、n元謂詞、命題函數(shù)、復(fù)合命題函數(shù)、個(gè)體域、全總個(gè)體域、全稱量詞、存在量詞、存在唯一量詞、特性謂詞 2、會(huì)用謂詞表達(dá)式寫出命題。,§2—1 謂詞的概念與表示

7、 一、謂詞的概念在Ls中，命題是具有確定真值的陳述句。從語(yǔ)法上分析，一個(gè)陳述句由主語(yǔ)和謂語(yǔ)兩部分組成。主語(yǔ)是謂語(yǔ)陳述的對(duì)象（稱為客體或個(gè)體），指出謂語(yǔ)說(shuō)的是“誰(shuí)”或者“什么”；謂語(yǔ)是用來(lái)陳述主語(yǔ)的，說(shuō)明主語(yǔ)“怎么樣”或者“是什么”（稱為謂詞）。 如： 李寧是體操運(yùn)動(dòng)員。 主語(yǔ) 謂語(yǔ) 蘇格拉底是古希臘哲學(xué)家。 主語(yǔ)

8、 謂語(yǔ) 哲學(xué)是研究世界觀的學(xué)問(wèn)。 主語(yǔ) 謂語(yǔ),在謂詞邏輯中，為揭示命題內(nèi)部結(jié)構(gòu)及不同命題的內(nèi)部結(jié)構(gòu)關(guān)系，按照主語(yǔ)、謂語(yǔ)兩部分對(duì)命題進(jìn)行分析，并且把主語(yǔ)稱為個(gè)體或客體，把謂語(yǔ)稱為謂詞?？腕w可以獨(dú)立存在，它可以是具體的，也可以是抽象的。上面的“李寧”、“蘇格拉底”、“哲學(xué)” 是客體?！笆恰?是謂詞，表達(dá)了客體的性質(zhì)。 又如：5大于3。

9、 張三比李四高。 這里5，3，張三，李四是客體，大于，比…高是謂詞，表達(dá)了客體之間的關(guān)系。在反映判斷的句子中，用以刻劃客體的性質(zhì)或關(guān)系的部分即是謂詞。,二、用謂詞刻劃命題的本質(zhì)屬性 P：張三是個(gè)大學(xué)生。 Q：李四是個(gè)大學(xué)生。是兩個(gè)不同的命題，但謂詞“是個(gè)大學(xué)生”是相同的。引入一個(gè)符號(hào)來(lái)表示“是個(gè)大學(xué)生”，比如用A來(lái)表示，再引入一種方法表示客體的名

10、稱，這樣就能把“XX是個(gè)大學(xué)生”（這2個(gè)命題的本質(zhì)屬性）刻劃出來(lái)。,三、謂詞的表示1. 客體和謂詞的表示方法 約定：用大寫字母表示謂詞；表示特定謂詞，稱為謂詞常元，表示不確定的謂詞，稱為謂詞變?cè)?，謂詞常元和謂詞變?cè)加么髮懹⑽淖帜富虼髮懹⑽淖帜笌聵?biāo)來(lái)表示，如P,Q,R, …或A1,A2,A3,…。用小寫字母表示客體名稱。表示特定的客體，稱為客體常元，以a,b,c,…或a1,b1,c1,…表示；表示不確定的客體，稱為

11、客體變?cè)詘,y,z,…或x1,y1,z1,…表示。,三、謂詞的表示,2. 命題的表示方法用謂詞表達(dá)命題，必須包括客體和謂詞字母兩個(gè)部分。單獨(dú)一個(gè)謂詞不是完整的命題，必須在謂詞字母后填以客體才能表示命題。謂詞字母后填以客體所得的式子稱為謂詞填式 。對(duì)于給定的命題，當(dāng)用表示其客體的小寫字母和表示其謂詞的大寫字母來(lái)表示時(shí)，規(guī)定把小寫字母寫在大寫字母右側(cè)的圓括號(hào)( )內(nèi)。如A表示“是個(gè)大學(xué)生” ，a表示張三，b表示李四，則A(a

12、)表示命題“張三是個(gè)大學(xué)生”。A(b)表示命題“李四是個(gè)大學(xué)生”。,例如：H表示“高于”，a表示客體“張三”，b表示客體“李四”，則H(a,b)就表示命題：“張三高于李四”?！癰是A”類型的命題用A(b)表達(dá)。如命題：他是三好學(xué)生。用G表示 謂詞“是三好學(xué)生”，t表示客體“他”，則該命題可表示為G (t) 。對(duì)于“a小于b”這種表示兩個(gè)客體之間關(guān)系的命題，可表達(dá)為B(a,b)，這里B(a,b)表示“小于”。,A(b)， G(t)

13、 稱作一元謂詞；一元謂詞了表達(dá)客體的性質(zhì)。 B(a,b)稱作二元謂詞。 推廣到n元謂詞：A是謂詞，a1，a2，…an是客體的名稱，則A(a1，a2，…an)是n元謂詞。多元謂詞表達(dá)了客體之間的關(guān)系，在多元謂詞中客體的次序與事先約定有關(guān)。,§2—2 命題函數(shù)與量詞一、命題函數(shù)1、簡(jiǎn)單命題函數(shù)：由一個(gè)謂詞、一些客體變?cè)M成的表達(dá)式稱為簡(jiǎn)單命題函數(shù)。例如： A(x)表示“x學(xué)習(xí)好”，x是客體變?cè)?/p>

14、 A(x)是簡(jiǎn)單命題函數(shù)。A(x)是簡(jiǎn)單命題函數(shù)，此時(shí)A(x)沒(méi)有確定的真值，所以A(x)不是命題，只有當(dāng)x取特定的客體時(shí)， A(x)才確定了一個(gè)命題。 注意：n元謂詞就是有n個(gè)客體變?cè)拿}函數(shù)。,2、復(fù)合命題函數(shù)：由一個(gè)或n個(gè)簡(jiǎn)單命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式稱復(fù)合命題函數(shù)。 邏輯聯(lián)結(jié)詞┐、∧、∨、→、 的意義與命題演算中的解釋完全類似。例如，A(x)表示“x學(xué)習(xí)好”，B(x)表示“x工作好”，A

15、(x) ∧B(x)表示“x的工作、學(xué)習(xí)都好”， A(x) ∧B(x)是復(fù)合命題函數(shù)。,例1 設(shè)S(x)表示“x學(xué)習(xí)很好”，用W(x)表示“x工作很好”。 則┐S(x)表示“x學(xué)習(xí)不是很好”。 S(x)∧W(x)表示“x的學(xué)習(xí)，工作都很好”。 S(x)→W(x)表示“若x的學(xué)習(xí)很好，則x工作得很好”。,,例2 用H(x,y)表示“x比y長(zhǎng)得高”。設(shè)a表示李四，c表示張三。則 ┐H(a,c)表示“李四不比張三長(zhǎng)得高”

16、。┐H(a,c) ∧ ┐H(c,a)表示“李四不比張三長(zhǎng)得高”且“張三不比李四長(zhǎng)得高”即“張三與李四同樣高”。,3、個(gè)體域在命題函數(shù)中，客體變?cè)恼撌龇秶Q作個(gè)體域。把各個(gè)個(gè)體域綜合在一起作為論述范圍的域稱全總個(gè)體域。命題函數(shù)不是一個(gè)命題，只有其中的個(gè)體變?cè)锰囟▊€(gè)體或個(gè)體常元替代時(shí)，才能成為一個(gè)命題。但是客體變?cè)谀男┓秶鷥?nèi)取特定的值，對(duì)命題函數(shù)是否成為命題及命題的真值極有影響。,,,例4 R(x)表示“x是個(gè)大學(xué)生

17、”：如果x的討論范圍為某大學(xué)里班級(jí)的學(xué)生，則R(x)是永真式。 如果x的討論范圍為某中學(xué)里班級(jí)的學(xué)生，則R(x)是永假式。如果x的討論范圍為一個(gè)劇場(chǎng)中的觀眾，觀眾中有大學(xué)生也有非大學(xué)生，那么，對(duì)某些觀眾，R(x)為真，對(duì)另一些觀眾，R(x)為假。,如果P(x,y)解釋為 “x距離y 10米”，若x，y，z表示地面上的房子，那么“x距離y10米且y距離z10米則x距離z10米”。這個(gè)命題的真值將由x，y，z的具體位置而

18、定，它可能為T，也可能為F。,,,,,,,x,y,z,x,y,z,例5,若P(x,y)解釋為“x小于y”，當(dāng)x，y，z都在實(shí)數(shù)域中取值，則這個(gè)式子表示為“若x小于y且y小于z，則x小于z”。這是一永真式。,如果P(x,y)解釋為“x為y的兒子”，當(dāng)x，y，z都指人，則“若x為y的兒子且y是z的兒子則x是z的兒子”。這個(gè)式子表達(dá)的是一個(gè)永假公式。,二、量詞表示客體之間的數(shù)量關(guān)系。(量詞記號(hào)由邏輯學(xué)家Fray引入),三、用謂詞表達(dá)式表示命

19、題 命題可以由量詞、簡(jiǎn)單命題函數(shù)、邏輯聯(lián)結(jié)詞構(gòu)成的謂詞表達(dá)式表示。,,,如設(shè) M(x)：x是人，D(X)：ｘ是要死的，s：蘇格拉底。,則三段論的三個(gè)命題：　　所有的人都是要死的。 　 蘇格拉底是人?！　∷蕴K格拉底是要死的。,可表示為：,四、特性謂詞 在討論帶有量詞的命題函數(shù)時(shí)，必須確定其個(gè)體域，為了方便，將所有命題函數(shù)的個(gè)體域全部統(tǒng)一，使用全總個(gè)體域。對(duì)每一個(gè)客體變?cè)淖兓秶?，用特性謂詞加以限制。,限

20、定客體變?cè)兓秶闹^詞，稱作特性謂詞。,一般地，對(duì)全稱量詞，特性謂詞常作蘊(yùn)含的前件；對(duì)存在量詞，特性謂詞常作合取項(xiàng)。,三段論可如下表示：,特性謂詞,24,2-3 謂詞公式與翻譯一、謂詞公式,原子謂詞公式把A(x1,x2,…,xn)稱作謂詞演算的原子公式，其中x1,x2,…,xn是客體變?cè)?原子謂詞公式的特例：A A(x)A(x,y)A(x,y,z)A(x,f(x))A(a,x)A(a,b),25,(5

21、)僅有有限次使用①、②、③和④形成的公式是合式謂詞公式。,2、合式公式：謂詞演算的合式公式，被遞歸定義如下：,26,二、翻譯（符號(hào)化）把一個(gè)文字?jǐn)⑹龅拿}，用謂詞公式表示出來(lái)，稱為謂詞邏輯的翻譯或符號(hào)化；反之亦然。一般說(shuō)來(lái)，符號(hào)化的步驟如下：,正確理解給定命題。必要時(shí)把命題改敘，使其中每個(gè)原子命題、原子命題之間的關(guān)系明顯表達(dá)出來(lái)。 把每個(gè)原子命題分解成個(gè)體、謂詞和量詞；在全總論域討論時(shí)，要給出特性謂詞。找出恰當(dāng)量詞。應(yīng)注意全稱量

22、詞后跟條件式，存在量詞后跟合取式。 用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來(lái)。,27,解：命題中“沒(méi)有最大的”顯然是對(duì)所有的自然數(shù)而言。所以可理解為“對(duì)所有的x，如果x是自然數(shù)，則一定還有比x大的自然數(shù)”。再具體點(diǎn)，即“對(duì)所有的x，如果x是自然數(shù)，則一定存在y，y也是自然數(shù)，并且y比x大”。則原命題表示為：,,例：將命題“沒(méi)有最大的自然數(shù)”符號(hào)化。,28,解： 本語(yǔ)句可理解為“若今天下雨又下雪，則存在x，x是人且x會(huì)跌跤”。則本語(yǔ)句可表

23、示為：,,,例：將語(yǔ)句“今天有雨雪，有些人跌跤”符號(hào)化。,29,,,再看61頁(yè)例題1，例題2，例題3。,例題1 并非每個(gè)實(shí)數(shù)都是有理數(shù)。,設(shè) R(x)：x是實(shí)數(shù)。 Q（x）：X是有理數(shù)。每個(gè)實(shí)數(shù)都是有理數(shù)表示為：,并非每個(gè)實(shí)數(shù)都是有理數(shù)表示為：,30,例題2 沒(méi)有不犯錯(cuò)誤的人。,設(shè) M(x)：x 是人。 F(x)：x犯錯(cuò)誤。命題符號(hào)化為 ：,此命題等價(jià)于“任何人都要犯錯(cuò)誤”或“所有人都要犯錯(cuò)誤”。所以此命題也可符號(hào)化為：

24、,解 本語(yǔ)句即為“不存在不犯錯(cuò)誤的人。,31,例題3 盡管有人聰明，但未必一切人都聰明。,解 設(shè) M(x)：x是人。 P(x)：x是聰明的。命題符號(hào)化為：,由于人們對(duì)命題的文字?jǐn)⑹龊饫斫獾牟煌?，?qiáng)調(diào)的重點(diǎn)不同，會(huì)影響到命題符號(hào)化的形式不同。見(jiàn)例題4。,32,例題4 這只大紅書柜擺滿了那些古書。,解法1 這只大紅書柜擺滿了那些古書。,x,y,設(shè) F(x,y)：x擺滿了y,再對(duì)x和y加以限制,R(x)：x是大紅

25、書柜,Q(y)：y是古書,a：這只 b：那些,此時(shí)可把命題符號(hào)化為：,解法2,設(shè) A(x)：x是書柜,B(x)：x是大的,C(x)：x是紅的,D(y)：y是古老的,E(y)：y是圖書,F(x,y)：x擺滿了y,a ：這只 b：那些,此時(shí)可把命題符號(hào)化為：,解法1中R(x)表示x是大紅書柜,解法2中A(x) ∧B(x) ∧C(x)也可表示大紅書柜,但用A(x) ∧B(x) ∧C(x)將更方便于對(duì)書柜的大小顏色進(jìn)行討論,對(duì)個(gè)體刻