《離散數(shù)學》課件第二章

1、“人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的?！?蘇格拉底三段論第二講 謂詞邏輯（Predicate Qogic） 1.個體、謂詞和量詞 2.謂詞公式 3.等值演算 4.范式 5.推理理論 6.謂詞邏輯在計算機科學中的應用考慮如下3個命題或推理：1 “有一個整數(shù)大于其他每個整數(shù)”2 “任給 0，存在 0，如果|x-a|，則|f(x)-b|y) x(Z(x)y(Z(y) N(x,y) (xy)2.1 個體、謂詞和量詞2 “任給0，存在0，如果|x-a|，則|f(x)-b|0)()(0)(|x-a|)(f(x)-b|x)y(yy)5 推理理論2 全稱量詞引入規(guī)則（UG規(guī)則）A(y) xA(x

2、)成立的條件是：(1).y在A(y)中自由出現(xiàn)，且任意y，A(y)為真；(2).替換y的x要選擇在A(y)中不出現(xiàn)的變元符號；z(zy)zz(zz)5 推理理論3 存在量詞引入規(guī)則（EG規(guī)則）A(c) xA(x)成立的條件是：(1).c是特定的個體常量；(2).替換c的x要選擇在A(c)中不出現(xiàn)的變元符號；(1).P(x)Q(c) (2).(x)(P(x)Q(x)在使用存在量詞引入規(guī)則時，替換個體c的變元應選擇在公式中沒有出現(xiàn)的變元符號，正確的推理是：(1).P(x)Q(c)(2).(y)(P(x)Q(y)5 推理理論4 存在量詞消除規(guī)則（ES規(guī)則）xA(x) A(c)成立的條件是：(1).c

3、是特定的個體常量，c不能在前面的公式序列中出現(xiàn)；(2).c不在A(x)中出現(xiàn)；(3).A(x)中自由出現(xiàn)的個體變元只有x。(1)(x)(y)(x y)/ P(2).(y)(z y) / US(3).(z c) / ES(4).(x)(x c)/ UG(5).c c / US 由(2)得到(3)不能使用存在量詞消除規(guī)則，因為(2)中含有除y以外的自由變元z。5 推理理論推理方法直接法間接法（反證法、CP規(guī)則）5 推理理論示例 證明 (x)(C(x)W(x)R(x)(x) (C(x)Q(x)= (x) (Q (x)R(x)【分析】謂詞邏輯的推理演算不能用真值表法，所以證明方法有直接證法、反正法和C

4、P規(guī)則法。當要推理的結論是蘊含式時才能用CP規(guī)則法，能用CP規(guī)則法的盡量用CP規(guī)則法，因為此方法增加了一個前提條件。該題只能用直接證法、反正法。5 推理理論證明方法一（直接證法）：1) (x)(C(x)W(x)R(x) P2) (x) (C(x)Q(x) P3) (C(a)Q(a) ES, 2)4) C(a)W(a)R(a) US,1) 5) C(a) T,I,3)6) W(a)R(a) T,I,4)、5)7) Q(a) T,I,3)8) R(a) T,I,6)9) Q(a)R(a) T,I,7)、8)10) (x) (Q (x)R(x) EG,9)3) C(a)W(a)R(a) US,1)

5、4) (C(a)Q(a) ES, 2)(3)、4)次序不能顛倒)5 推理理論示例 將下列推理符號化并給出形式證明: 晚會上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（個體域為參加晚會的人）解 設P(x)：x唱歌了，Q(x)：x跳舞了，則前提：x(P(x)Q(x)結論：xP(x)xQ(x)推理形式：x(P(x)Q(x)xP(x)xQ(x)5 推理理論 (1) (xP(x)xQ(x) P(附加) (2) xP(x)xQ(x) R,E,(1) (3) xP(x) T,I,(2) (4) P(a) ES,(3) (5) xQ(x) T,I,(2) (6) Q(a) US,(5)

6、(7) x(P(x)Q(x) P (8) P(a)Q(a) US,(7) (9) Q(a) T,I,(4),(8) (10) Q(a)Q(a) T,I,(6),(9),矛盾 因此，假設不成立，原推理形式正確。5 推理理論示例 所有的有理數(shù)都是實數(shù)；所有的無理數(shù)也是實數(shù)；虛數(shù)不是實數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無理數(shù)。解 個體域為全總域，需要引入的謂詞包括：Q(x): x 是有理數(shù)；R(x): x是實數(shù)；N(x): x是無理數(shù)；C(x): x是虛數(shù)。上述推理可符號化為：前提：x(Q(x)R(x)、x(N(x)R(x)、x(C(x) R(x)結論：x(C(x) (Q(x) N(x)， 驗證該結

7、論的公式序列如下：5 推理理論(1). x(Q(x)R(x) / P(2). Q(y)R(y) / US(3). x(N(x)R(x) / P(4). N(y)R(y) / US(5). x(C(x) R(x) / P(6). C(y) R(y) / US(7). C(y) / P(附加)(8). R(y) / 分離規(guī)則，(6)和(7)(9). Q(y) / 拒取式，(8)和(2)(10). N(y) / 拒取式，(8)和(4)(11). Q(y) N(y) / 合取的引入(12). C(y)(Q(y) N(y) / T, I (7)和(11)(13). x(C(x) (Q(x) N(x) /

8、UG5 推理理論示例 每個旅客或者坐頭等艙或者坐二等艙；每個旅客當且僅當他富裕時坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等艙。解 個體域為全總域，引入下列謂詞：P(x): x是旅客；Q(x): x坐頭等艙；R(x): x坐二等艙；S(x): x是富裕的。原推理可符號化為：前提：x(P(x)(Q(x)R(x)、x(P(x)(Q(x)S(x)、x (P(x)S(x)、(x(P(x)S(x)結論：x(P(x)R(x)，驗證該結論的公式序列如下：5 推理理論(1). (x(P(x)S(x) / P(2). x(P(x)S(x) / T, I (2)(3). P(c)S(c) /

9、 ES(4). P(c) / T, I (3)(5). S(c) / T, I (3)(6). x(P(x)(Q(x)R(x) / P(7). P(c)(Q(c)R(c) / US, (6)(8). Q(c)R(c) / T, I (4)(7)(9).x(P(x)(Q(x)S(x)/P(10).P(c)(Q(c)S(c)/ US(9)(11).Q(c)S(c) / T, I (4)(11)(12).Q(c)S(c)/ T, I(11)(13). Q(c)/ T, I (12)(5)(14). R(c)/ T, I (13)(8)(15). P(c) R(c)/ T, I(4)(14)(16). x(P(x)R(x) / EG5 推理理論練習 每一個大學生不是文科生就是理科生；有的大學生愛好文學；小張不是文科生但他愛好文學。因此，如果小張是大學生，他就是理科生；解：個體域取全總域，要引入的謂詞包括：P(x): x 是一個大學生；Q(x): x是文科生；S(x): x 是理科生；T(x): x 愛好文學。要引入的個體常量是：c : 小張。因此上述推理可符號化為： 前提：x(P(x)(Q(x)S(x)、x(P(x)T(x)、Q(c)T(c)結論：P(c)S(c)，驗證該結論的公式序列為：