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

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

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

3、是特定的個(gè)體常量，c不能在前面的公式序列中出現(xiàn)；(2).c不在A(yíng)(x)中出現(xiàn)；(3).A(x)中自由出現(xiàn)的個(gè)體變?cè)挥衳。(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ī)則，因?yàn)?2)中含有除y以外的自由變?cè)獄。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ī)則法。當(dāng)要推理的結(jié)論是蘊(yùn)含式時(shí)才能用CP規(guī)則法，能用CP規(guī)則法的盡量用CP規(guī)則法，因?yàn)榇朔椒ㄔ黾恿艘粋€(gè)前提條件。該題只能用直接證法、反正法。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 推理理論示例 將下列推理符號(hào)化并給出形式證明: 晚會(huì)上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（個(gè)體域?yàn)閰⒓油頃?huì)的人）解 設(shè)P(x)：x唱歌了，Q(x)：x跳舞了，則前提：x(P(x)Q(x)結(jié)論：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),矛盾 因此，假設(shè)不成立，原推理形式正確。5 推理理論示例 所有的有理數(shù)都是實(shí)數(shù)；所有的無(wú)理數(shù)也是實(shí)數(shù)；虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無(wú)理數(shù)。解 個(gè)體域?yàn)槿傆?，需要引入的謂詞包括：Q(x): x 是有理數(shù)；R(x): x是實(shí)數(shù)；N(x): x是無(wú)理數(shù)；C(x): x是虛數(shù)。上述推理可符號(hào)化為：前提：x(Q(x)R(x)、x(N(x)R(x)、x(C(x) R(x)結(jié)論：x(C(x) (Q(x) N(x)， 驗(yàn)證該結(jié)

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 推理理論示例 每個(gè)旅客或者坐頭等艙或者坐二等艙；每個(gè)旅客當(dāng)且僅當(dāng)他富裕時(shí)坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等艙。解 個(gè)體域?yàn)槿傆颍胂铝兄^詞：P(x): x是旅客；Q(x): x坐頭等艙；R(x): x坐二等艙；S(x): x是富裕的。原推理可符號(hào)化為：前提：x(P(x)(Q(x)R(x)、x(P(x)(Q(x)S(x)、x (P(x)S(x)、(x(P(x)S(x)結(jié)論：x(P(x)R(x)，驗(yàn)證該結(jié)論的公式序列如下：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 推理理論練習(xí) 每一個(gè)大學(xué)生不是文科生就是理科生；有的大學(xué)生愛(ài)好文學(xué)；小張不是文科生但他愛(ài)好文學(xué)。因此，如果小張是大學(xué)生，他就是理科生；解：個(gè)體域取全總域，要引入的謂詞包括：P(x): x 是一個(gè)大學(xué)生；Q(x): x是文科生；S(x): x 是理科生；T(x): x 愛(ài)好文學(xué)。要引入的個(gè)體常量是：c : 小張。因此上述推理可符號(hào)化為： 前提：x(P(x)(Q(x)S(x)、x(P(x)T(x)、Q(c)T(c)結(jié)論：P(c)S(c)，驗(yàn)證該結(jié)論的公式序列為：