課件代數(shù)結(jié)構(gòu)第二章

1、 1.1.個體、謂詞和量詞個體、謂詞和量詞 2.2.謂詞公式謂詞公式 3.3.等值演算等值演算 4.4.范式范式 5.5.推理理論推理理論 6.6.謂詞邏輯在計算機科學中的應(yīng)用謂詞邏輯在計算機科學中的應(yīng)用考慮如下考慮如下3 3個命題或推理：個命題或推理：1 1 “有一個整數(shù)大于其他每個整數(shù)有一個整數(shù)大于其他每個整數(shù)”2 2 “任給任給 0 0，存在，存在 0 0，如果，如果|x-a|x-a| ，則，則|f(x)-b|f(x)-b|y) x(Z(x)y(Z(y) N(x,y) (xy)2.1 個體、謂詞和量詞個體、謂詞和量詞2 2 “任給任給 00，存在，存在 00，如果，如果|x-a|x-a|

2、 ，則，則|f(x)-b|f(x)-b|0)( )( 0) (|x-a| )(f(x)-b|x) y(yy)5 推理理論推理理論2 2 全稱量詞引入規(guī)則（全稱量詞引入規(guī)則（UGUG規(guī)則）規(guī)則）A(y) A(y) xA(x)xA(x)成立的條件是：成立的條件是：(1).(1). y y在在A(y)A(y)中自由出現(xiàn)中自由出現(xiàn)，且任意，且任意y y，A(y)A(y)為真為真；(2).(2). 替換替換y y的的x x要選擇在要選擇在A(y)A(y)中不出現(xiàn)的變元符號；中不出現(xiàn)的變元符號； z(zy) z z(zz)5 推理理論推理理論3 3 存在量詞引入規(guī)則（存在量詞引入規(guī)則（EGEG規(guī)則）規(guī)則）

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

4、ES規(guī)則）規(guī)則） xA(x) xA(x) A(c) A(c)成立的條件是：成立的條件是：(1).c(1).c是特定的個體常量，是特定的個體常量，c c不能在前面的公式序列中出現(xiàn)；不能在前面的公式序列中出現(xiàn)；(2).c(2).c不在不在A(x)A(x)中出現(xiàn)；中出現(xiàn)；(3).A(x)(3).A(x)中自由出現(xiàn)的個體變元只有中自由出現(xiàn)的個體變元只有x 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ī)則，因為不能使用存在量詞消除規(guī)則，因為

5、(2)中含有除中含有除y以外的以外的自由變元自由變元z。5 推理理論推理理論推理方法推理方法直接法直接法間接法（反證法、間接法（反證法、CPCP規(guī)則）規(guī)則）5 推理理論推理理論示例示例 證明證明 ( x)(C(x)W(x)R(x)( x) (C(x)Q(x)= ( x) (Q (x)R(x)【分析分析】謂詞邏輯的推理演算不能用真值表法，所以謂詞邏輯的推理演算不能用真值表法，所以證明方法有直接證法、反正法和證明方法有直接證法、反正法和CP規(guī)則法。當要規(guī)則法。當要推理的結(jié)論是蘊含式時才能用推理的結(jié)論是蘊含式時才能用CP規(guī)則法，能用規(guī)則法，能用CP規(guī)則法的盡量用規(guī)則法的盡量用CP規(guī)則法，因為此方法增

6、加了一規(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,

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

8、( xP(x)xQ(x) P(附加附加) (2) x P(x)x Q(x) R,E,(1) (3) x P(x) T,I,(2) (4) P(a) ES,(3) (5) x Q(x) T,I,(2) (6) Q(a) US,(5) (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è)不成立，原推理形式正確。因此，假設(shè)不成立，原推理形式正確。5 推理理論推理理論示例示例 所有的有理數(shù)都是實數(shù)；所有的無理數(shù)也是實數(shù)；虛數(shù)不是實數(shù)。所有的有理數(shù)都是實數(shù)；所有的無

9、理數(shù)也是實數(shù)；虛數(shù)不是實數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無理數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無理數(shù)。解解 個體域為全總域，需要引入的謂詞包括：個體域為全總域，需要引入的謂詞包括：Q(Q(x x): ): x x 是有理數(shù)；是有理數(shù)；R(R(x x): ): x x是實數(shù)；是實數(shù)；N(N(x x): ): x x是無理數(shù)；是無理數(shù)；C(C(x x): ): x x是是虛數(shù)。上述推理可符號化為：虛數(shù)。上述推理可符號化為：前提前提： x x(Q(Q(x x) )R(R(x x)、 x x(N(N(x x) )R(R(x x)、 x x(C(C(x x) ) R(R(x x)結(jié)論結(jié)論： x x(C

10、(C(x x) ) ( ( Q(Q(x x) ) N(N(x x)， 驗證該結(jié)論的公式序列如下：驗證該結(jié)論的公式序列如下：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ī)則，分離規(guī)則，(6)和和(7)(9). Q(y) / 拒取式，拒取式，(8)和和(2)(10). N(y) / 拒取式，拒取式，(8)和和(4)(11). Q(y)

11、 N(y) / 合取的引入合取的引入(12). C(y)( Q(y) N(y) / T, I (7)和和(11)(13). x(C(x) ( Q(x) N(x) /UG5 推理理論推理理論示例示例 每個旅客或者坐頭等艙或者坐二等艙；每個旅客當且僅當他富裕每個旅客或者坐頭等艙或者坐二等艙；每個旅客當且僅當他富裕時坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅時坐頭等艙；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等艙?？妥扰?。解解 個體域為全總域，引入下列謂詞：個體域為全總域，引入下列謂詞：P(P(x x): ): x x是旅客；是旅客；Q(Q(x x): ): x x

12、坐頭等坐頭等艙；艙；R(R(x x): ): x x坐二等艙；坐二等艙；S(S(x x): ): x x是富裕的。是富裕的。原推理可符號化為：原推理可符號化為：前提前提： x x(P(P(x x) )(Q(Q(x x) ) R(R(x x)、 x x(P(P(x x) )(Q(Q(x x) )S(S(x x)、 x (P(P(x x) ) S(S(x x)、 ( ( x x(P(P(x x) )S(S(x x)結(jié)論結(jié)論： x x(P(P(x x) ) R(R(x x)，驗證該結(jié)論的公式序列如下：，驗證該結(jié)論的公式序列如下：5 推理理論推理理論(1). (x(P(x)S(x) / P(2). x

13、(P(x)S(x) / T, I (2)(3). P(c)S(c) / 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).(9). x x(P(P(x x) )(Q(Q(x x) )S(S(x x)/P)/P(10).P(10).P(c c) )(Q(Q(c c) )S(S(c c)/ US(9)/ US(9)(11).Q(11).Q(c c) )S(S(c c) / T, I (4)(11) /

14、 T, I (4)(11)(12).Q(12).Q(c c) )S(S(c c)/ T, I(11)/ T, I(11)(13). (13). Q(Q(c c) )/ T, I (12)(5)/ T, I (12)(5)(14). R(14). R(c c) )/ T, I (13)(8)/ T, I (13)(8)(15). P(15). P(c c) ) R( R(c c)/ T, I(4)(14)/ T, I(4)(14)(16). (16). x x(P(P(x x) ) R(R(x x) / EG) / EG5 推理理論推理理論練習練習 每一個大學生不是文科生就是理科生；有的大學生愛

15、好文學；小張每一個大學生不是文科生就是理科生；有的大學生愛好文學；小張不是文科生但他愛好文學。因此，如果小張是大學生，他就是理科生；不是文科生但他愛好文學。因此，如果小張是大學生，他就是理科生；解解：個體域取全總域，要引入的謂詞包括：個體域取全總域，要引入的謂詞包括：P(P(x x): ): x x 是一個大學生；是一個大學生；Q(Q(x x): ): x x是文科生；是文科生；S(S(x x): ): x x 是理科生；是理科生；T(T(x x): ): x x 愛好文學。愛好文學。要引入的個體常量是：要引入的個體常量是：c c : : 小張。小張。因此上述推理可符號化為：因此上述推理可符號化為： 前提前提： x x(P(P(x x) )(Q(Q(x x) ) S(S(x x)、 x x(P(P(x x) ) T(T(x x)、