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

1、1,離 散 數 學Discrete Mathematics,山東科技大學信息科學與工程學院,2,第一章 內容回顧 一、知識點1．命題的概念、表示方法；聯結詞的邏輯意義。2．命題公式的遞歸定義，自然語言翻譯成命題公式3．真值表的構造、命題公式等價的概念。4．重言式與蘊含式的定義、邏輯意義，邏輯等價與邏輯蘊含的意義和證明方法。常用的邏輯等價公式和邏輯蘊含公式。,3,5．命題公式的對偶式、合取范式、析取范

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

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

4、 所以100是有理數。 顯然這些都是正確的推理，但在命題邏輯中卻無法得到證明，因為三段論的每句話都是一個原子命題，我們可分別用P，Q，R來表示。這樣，三段論方法用形式符號表示應為 P∧Q ? R即 P∧Q→ R?T但在命題邏輯里， P∧Q→ R顯然不是重言式。,出現問題的原因在于，三段論中，結論R與前提P，Q的內在聯系不可能在命題邏輯中表示出來。,蘇格拉

5、底三段論是正確的。但用命題邏輯卻無法推出。這是因為命題邏輯基本組成單位是原子命題，并把它看作不可再分解的。但兩個原子命題間，常常有一些共同特征，為了刻劃命題內部的邏輯結構，就需研究謂詞邏輯（簡稱為Lp）。在研究某些推理時，有必要對原子命題作進一步分析，分析出其中的個體詞，謂詞和量詞，研究它們的形式結構的邏輯關系、正確的推理形式和規(guī)則，這些正是謂詞邏輯的基本內容。,所有的人都是要死的。 蘇格拉底是人。所以蘇格拉底是要死的。,蘇格拉底

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

7、 一、謂詞的概念在Ls中，命題是具有確定真值的陳述句。從語法上分析，一個陳述句由主語和謂語兩部分組成。主語是謂語陳述的對象（稱為客體或個體），指出謂語說的是“誰”或者“什么”；謂語是用來陳述主語的，說明主語“怎么樣”或者“是什么”（稱為謂詞）。 如： 李寧是體操運動員。 主語 謂語 蘇格拉底是古希臘哲學家。 主語

8、 謂語 哲學是研究世界觀的學問。 主語 謂語,在謂詞邏輯中，為揭示命題內部結構及不同命題的內部結構關系，按照主語、謂語兩部分對命題進行分析，并且把主語稱為個體或客體，把謂語稱為謂詞。客體可以獨立存在，它可以是具體的，也可以是抽象的。上面的“李寧”、“蘇格拉底”、“哲學” 是客體?！笆恰?是謂詞，表達了客體的性質。 又如：5大于3。

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

10、稱，這樣就能把“XX是個大學生”（這2個命題的本質屬性）刻劃出來。,三、謂詞的表示1. 客體和謂詞的表示方法 約定：用大寫字母表示謂詞；表示特定謂詞，稱為謂詞常元，表示不確定的謂詞，稱為謂詞變元，謂詞常元和謂詞變元都用大寫英文字母或大寫英文字母帶下標來表示，如P,Q,R, …或A1,A2,A3,…。用小寫字母表示客體名稱。表示特定的客體，稱為客體常元，以a,b,c,…或a1,b1,c1,…表示；表示不確定的客體，稱為

11、客體變元，以x,y,z,…或x1,y1,z1,…表示。,三、謂詞的表示,2. 命題的表示方法用謂詞表達命題，必須包括客體和謂詞字母兩個部分。單獨一個謂詞不是完整的命題，必須在謂詞字母后填以客體才能表示命題。謂詞字母后填以客體所得的式子稱為謂詞填式 。對于給定的命題，當用表示其客體的小寫字母和表示其謂詞的大寫字母來表示時，規(guī)定把小寫字母寫在大寫字母右側的圓括號( )內。如A表示“是個大學生” ，a表示張三，b表示李四，則A(a

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

13、 稱作一元謂詞；一元謂詞了表達客體的性質。 B(a,b)稱作二元謂詞。 推廣到n元謂詞：A是謂詞，a1，a2，…an是客體的名稱，則A(a1，a2，…an)是n元謂詞。多元謂詞表達了客體之間的關系，在多元謂詞中客體的次序與事先約定有關。,§2—2 命題函數與量詞一、命題函數1、簡單命題函數：由一個謂詞、一些客體變元組成的表達式稱為簡單命題函數。例如： A(x)表示“x學習好”，x是客體變元，

14、 A(x)是簡單命題函數。A(x)是簡單命題函數，此時A(x)沒有確定的真值，所以A(x)不是命題，只有當x取特定的客體時， A(x)才確定了一個命題。 注意：n元謂詞就是有n個客體變元的命題函數。,2、復合命題函數：由一個或n個簡單命題函數以及邏輯聯結詞組合而成的表達式稱復合命題函數。 邏輯聯結詞┐、∧、∨、→、 的意義與命題演算中的解釋完全類似。例如，A(x)表示“x學習好”，B(x)表示“x工作好”，A

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

16、。┐H(a,c) ∧ ┐H(c,a)表示“李四不比張三長得高”且“張三不比李四長得高”即“張三與李四同樣高”。,3、個體域在命題函數中，客體變元的論述范圍稱作個體域。把各個個體域綜合在一起作為論述范圍的域稱全總個體域。命題函數不是一個命題，只有其中的個體變元用特定個體或個體常元替代時，才能成為一個命題。但是客體變元在哪些范圍內取特定的值，對命題函數是否成為命題及命題的真值極有影響。,,,例4 R(x)表示“x是個大學生

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

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

19、題 命題可以由量詞、簡單命題函數、邏輯聯結詞構成的謂詞表達式表示。,,,如設 M(x)：x是人，D(X)：ｘ是要死的，s：蘇格拉底。,則三段論的三個命題：　　所有的人都是要死的。 　 蘇格拉底是人?！　∷蕴K格拉底是要死的。,可表示為：,四、特性謂詞 在討論帶有量詞的命題函數時，必須確定其個體域，為了方便，將所有命題函數的個體域全部統(tǒng)一，使用全總個體域。對每一個客體變元的變化范圍，用特性謂詞加以限制。,限

20、定客體變元變化范圍的謂詞，稱作特性謂詞。,一般地，對全稱量詞，特性謂詞常作蘊含的前件；對存在量詞，特性謂詞常作合取項。,三段論可如下表示：,特性謂詞,24,2-3 謂詞公式與翻譯一、謂詞公式,原子謂詞公式把A(x1,x2,…,xn)稱作謂詞演算的原子公式，其中x1,x2,…,xn是客體變元。,原子謂詞公式的特例：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,二、翻譯（符號化）把一個文字敘述的命題，用謂詞公式表示出來，稱為謂詞邏輯的翻譯或符號化；反之亦然。一般說來，符號化的步驟如下：,正確理解給定命題。必要時把命題改敘，使其中每個原子命題、原子命題之間的關系明顯表達出來。 把每個原子命題分解成個體、謂詞和量詞；在全總論域討論時，要給出特性謂詞。找出恰當量詞。應注意全稱量

22、詞后跟條件式，存在量詞后跟合取式。 用恰當的聯結詞把給定命題表示出來。,27,解：命題中“沒有最大的”顯然是對所有的自然數而言。所以可理解為“對所有的x，如果x是自然數，則一定還有比x大的自然數”。再具體點，即“對所有的x，如果x是自然數，則一定存在y，y也是自然數，并且y比x大”。則原命題表示為：,,例：將命題“沒有最大的自然數”符號化。,28,解： 本語句可理解為“若今天下雨又下雪，則存在x，x是人且x會跌跤”。則本語句可表

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

24、,解 本語句即為“不存在不犯錯誤的人。,31,例題3 盡管有人聰明，但未必一切人都聰明。,解 設 M(x)：x是人。 P(x)：x是聰明的。命題符號化為：,由于人們對命題的文字敘述含意理解的不同，強調的重點不同，會影響到命題符號化的形式不同。見例題4。,32,例題4 這只大紅書柜擺滿了那些古書。,解法1 這只大紅書柜擺滿了那些古書。,x,y,設 F(x,y)：x擺滿了y,再對x和y加以限制,R(x)：x是大紅

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