一階邏輯等值演算與推理課件離散數(shù)學(xué)

1、第五章 一階邏輯等值演算與推理,1,本章主要內(nèi)容,5.1一階邏輯等值式與置換規(guī)則5.2一階邏輯前束范式5.3一階邏輯的推理理論,2,5.1一階邏輯等值式與置換規(guī)則,等值式的概念基本等值式等值演算與置換規(guī)則,3,所有的學(xué)生都上課了，這是錯(cuò)的。,令 F(x): x是學(xué)生, G(x): x上課了。,這句話(huà)相當(dāng)于“有些學(xué)生沒(méi)有上課”。,4,一、等值式的概念,定義：若A?B為永真式，則稱(chēng)A與B是等值的，記作 A?B，并稱(chēng)A?B為等值式

2、。其中A、B是一階邏輯中任意的兩個(gè)合式公式。,5,二、基本等值式,命題邏輯中16組基本等值式的代換實(shí)例,例：?xF(x)??yG(y) ? ??xF(x)??yG(y) ?(?xF(x)??yG(y)) ? ??xF(x)???yG(y),即命題邏輯中的基本等值式在謂詞邏輯中均適用。,6,二、基本等值式,有限個(gè)體域中，消去量詞等值式,設(shè)個(gè)體域?yàn)镈={a1,a2,…,an} ?xA(x) ? A(a1)?A(a2)?

3、…?A(an) ?xA(x) ? A(a1)?A(a2)?…?A(an),,7,二、基本等值式,量詞否定等值式,“并不是所有的人都是黃皮膚?！?這句話(huà)相當(dāng)于“有的人不是黃皮膚?！?8,二、基本等值式,量詞轄域收縮與擴(kuò)張等值式,設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn)。,關(guān)于全稱(chēng)量詞： ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)

4、?B ?x(B?A(x))?B??xA(x),,9,二、基本等值式,關(guān)于存在量詞: ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B ?x(B?A(x))?B??xA(x),,10,二、基本等值式,量詞分配等值式,?x(A(x)?B(x))??xA(x)??xB(x)?x(A(x)?B(x))??xA(x)??xB(x),注意

5、：?對(duì)?無(wú)分配律，?對(duì)?無(wú)分配律,11,三、等值演算與置換規(guī)則,置換規(guī)則：設(shè)?(A)是含有公式A的公式，用公式B置換?(A)中所有的A后得到新的公式?(B)，若A?B, 則?(B)??(A),等值演算的基礎(chǔ)：（1）一階邏輯的基本等值式；（2）置換規(guī)則、換名規(guī)則、代替規(guī)則。,12,例題,例1：下面的命題都有兩種不同的符號(hào)化形式，寫(xiě)出其中的一種，然后通過(guò)等值演算得到另一種。 (1) 沒(méi)有不犯錯(cuò)誤的人 (2) 不是所有的人

6、都愛(ài)看電影,13,(1) 沒(méi)有不犯錯(cuò)誤的人,令F(x)：x是人，G(x)：x犯錯(cuò)誤,,例題,14,(2) 不是所有的人都愛(ài)看電影,令F(x)：x是人，G(x)：愛(ài)看電影,,例題,15,例2：設(shè)個(gè)體域D={a,b,c}，在D中消去下列公式中的量詞。,兩次使用“消去等值式”,例題,16,量詞轄域收縮與擴(kuò)張等值式,解法二：,小結(jié)：采用不同的演算過(guò)程同樣可以達(dá)到消去量詞的目的，但是如何演算才更簡(jiǎn)單呢？結(jié)論是將量詞轄域盡可能的縮小，然后再消量詞。

7、,例題,17,方法2：,例題,18,(3)當(dāng)個(gè)體域D={a,b},提問(wèn)：如果先消去全稱(chēng)量詞，后消去存在量詞，結(jié)果會(huì)怎樣？,例題,19,該題量詞的轄域已經(jīng)不能再縮小了，所以演算過(guò)程無(wú)法再簡(jiǎn)化，演算結(jié)果也不易化的更簡(jiǎn)單。,兩種消去順序得到的結(jié)果相同。,例題,20,例3 給定解釋I 如下: (a) 個(gè)體域 D={2，3} (b) (c) (d) 謂詞如下頁(yè)所示,例題,21,在 I 下求下列各式的真值。,例

8、題,22,計(jì)算過(guò)程見(jiàn)教材,例題,23,例4：證明下面的謂詞公式是永真式。,證明謂詞公式是永真式不能像命題公式那樣使用真值表。常用的方法是等值演算。,例題,24,經(jīng)過(guò)等值演算可知該公式是永真式。,例題,25,例題,26,兔子比烏龜跑得快。,令：F(x):x是兔子 G(y):y是烏龜 L(x,y):x比y跑得快,命題符號(hào)化為：,另外一種等值的符號(hào)化形式為：,27,5.2 前束范式,定義：設(shè)A為一個(gè)一階邏輯公式

9、, 若A具有如下形式Q1x1Q2x2…QkxkB, 則稱(chēng)A為前束范式, 其中Qi (1?i?k)為?或?，B為不含量詞的公式。,例：?x?y(F(x)?(G(y)?H(x,y))) ?x?(F(x)?G(x)),??x(F(x)?G(x))不是前束范式。,,B,前束范式,,B,,28,5.2 前束范式,(1) ??x(M(x)?F(x))解： ??x(M(x)?F(x)) ? ?x(?M(x)??F(x

10、)) （量詞否定等值式） ? ?x(M(x)??F(x)),兩步結(jié)果都是原公式的前束范式。,例1：求下列公式的前束范式,29,5.2 前束范式,(2) ?xF(x)???xG(x)解： ?xF(x)???xG(x) ??xF(x)??x?G(x) （量詞否定等值式） ??x(F(x)??G(x)) （量詞分配等值式）,另有一種形式如下：,30,5.2 前束范式,?xF(x)???

11、xG(x) ??xF(x)??x?G(x) ??xF(x)??y?G(y) ( 換名規(guī)則 ) ??x(F(x)??y?G(y) ) ( 量詞轄域擴(kuò)張 ) ??x?y(F(x)??G(y)) ( 量詞轄域擴(kuò)張 ),31,5.2 前束范式,(3) ?xF(x)???xG(x) 解 ?xF(x)???xG(x) ??xF(x)??x?G(x)

12、 ??x(F(x)??G(x)) 或 ??x?y(F(x)??G(y)),32,5.2 前束范式,(4) ?xF(x)??y(G(x,y)??H(y)) 解 ?xF(x)??y(G(x,y)??H(y)) ??zF(z)??y(G(x,y)??H(y)) (換名規(guī)則) ??z?y(F(z)?(G(x,y)??H(y)))或 ? ?xF(x)??y(G(t,y)??H(y))

13、(代替規(guī)則) ? ?x?y (F(x)?(G(t,y)??H(y))),,,33,5.2 前束范式,(5) ?x(F(x,y)??y(G(x,y)?H(x,z)))解：既可用換名規(guī)則, 也可用代替規(guī)則 ?x(F(x,y)??y(G(x,y)?H(x,z))) ??x(F(x,u)??y(G(x,y)?H(x,z))) ??x?y(F(x,u)?G(x,y)?H(x,z)))注意：?x與?y不能顛

14、倒,(換名規(guī)則),,,34,5.2 前束范式,（6）,35,5.2 前束范式,例題小結(jié)：公式的前束范式不惟一；求公式的前束范式的方法: 利用基本等值式、置換規(guī)則、換名規(guī)則、代替規(guī)則進(jìn)行等值演算。,定理：一階邏輯中的任何公式都存在與之等值的前束范式。,36,5.3一階邏輯的推理理論,推理的形式結(jié)構(gòu)重要的推理定律推理規(guī)則構(gòu)造證明（附加前提證明法）,37,一、推理的形式結(jié)構(gòu),推理的形式結(jié)構(gòu)有兩種： 第一

15、種 A1?A2?…?Ak?B (*) 第二種 前提：A1，A2，…，Ak 結(jié)論： B 其中 A1,A2,…,Ak,B為一階邏輯公式. 若(*)為永真式, 則稱(chēng)推理正確, 否則稱(chēng)推理不正確,38,一、推理的形式結(jié)構(gòu),判斷推理是否正確的方法：等值演算法，應(yīng)用這種方法時(shí)采用第一種形式結(jié)構(gòu)；構(gòu)造證明法

16、，采用第二種形式結(jié)構(gòu)。,39,二、重要的推理定律,第一組 命題邏輯推理定律代換實(shí)例 如：?xF(x)??yG(y)??xF(x) 化簡(jiǎn)律代換實(shí)例.,第二組 由基本等值式生成的推理定律,如：由 ??xA(x)??x?A(x) 生成 ??xA(x)??x?A(x), ?x?A(x)???xA(x), …,40,二、重要的推理定律,第三組 ?xA(x)??xB(x)??x(A(x)?B(x)) ?x(A(x)?B

17、(x))??xA(x)??xB(x),41,三、推理規(guī)則,(1)前提引入規(guī)則 (2)結(jié)論引入規(guī)則(3)置換規(guī)則 (4)假言推理規(guī)則(5)附加規(guī)則 (6)化簡(jiǎn)規(guī)則(7)拒取式規(guī)則 (8)假言三段論規(guī)則(9)析取三段論規(guī)則 (10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則,42,(12) 全稱(chēng)量詞消去規(guī)則（記為UI）,注意：下面的規(guī)

18、則只能用于前束范式。,在(1)式中，y應(yīng)為任意的不在A(yíng)(x)中約束出現(xiàn)的個(gè)體變項(xiàng)。在第二式中，c為任意的未在A(yíng)(x)中出現(xiàn)過(guò)的個(gè)體常項(xiàng)。用y或c去取代A(x)中的自由出現(xiàn)的x時(shí)，一定要在x自由出現(xiàn)的一切地方進(jìn)行取代。,43,(13) 全稱(chēng)量詞引入規(guī)則（記為UG）,無(wú)論A(y)中自由出現(xiàn)的個(gè)體變項(xiàng)y取何值，A(y)應(yīng)該均為真。 x不約束出現(xiàn)在A(yíng)(y)中。,若對(duì)A(y) 應(yīng)用UG規(guī)則時(shí)，用在A(yíng)(y) 中約束出現(xiàn)的x代替y，則得到,44

19、,(14) 存在量詞消去規(guī)則（記為EI）,c是個(gè)體域中使A為真的某個(gè)確定的個(gè)體，且c不在A(yíng)(x)中出現(xiàn)。若A(x)中除自由出現(xiàn)的x外，還有其他自由出現(xiàn)的個(gè)體變項(xiàng)，此規(guī)則不能使用。,對(duì)公式 能否用EI規(guī)則？,提問(wèn)：,45,三、推理規(guī)則,前提引入,(1)UI規(guī)則,(2)EI規(guī)則,(3)UG規(guī)則,,46,(15) 存在量詞引入規(guī)則（記為EG）,該式成立的條件是：c是使A為真的特定個(gè)體常項(xiàng)

20、.取代c的x不能在A(yíng)(c)中出現(xiàn)過(guò).,47,四、構(gòu)造推理證明,一階邏輯自然推理系統(tǒng)F1.字母表，即一階語(yǔ)言的字母表。2.合式公式。3.推理規(guī)則,構(gòu)造推理證明的方法：直接法，附加前提引入法和歸謬法。,48,四、構(gòu)造推理證明,例1：在自然推理系統(tǒng)中，指出下面各證明序列中的錯(cuò)誤。,49,四、構(gòu)造推理證明,50,四、構(gòu)造推理證明,例2： 證明蘇格拉底三段論: “人都是要死的, 蘇格拉底是人，所以蘇格拉底是要死的。”,令：F(x): x是

21、人, G(x): x是要死的, a: 蘇格拉底 前提：?x(F(x)?G(x))，F(xiàn)(a) 結(jié)論：G(a),51,四、構(gòu)造推理證明,證明：① F(a) 前提引入 ② ?x(F(x)?G(x)) 前提引入 ③ F(a)?G(a) ②UI ④ G(

22、a) ①③假言推理注意：使用UI時(shí)，用a取代x。,52,四、構(gòu)造推理證明,例3：烏鴉都不是白色的。 北京鴨是白色的。 因此，北京鴨不是烏鴉。,令：F(x): x是烏鴉, G(x): x是北京鴨, H(x): x是白色的 前提：?x(F(x)??H(x))， ?x(G(x)?H(x)) 結(jié)論：?x(G(x)??F(x)),53,四、構(gòu)造推理證明,證

23、明： ① ?x(F(x)??H(x)) 前提引入 ② F(y)??H(y) ①UI ③ ?x(G(x)?H(x)) 前提引入 ④ G(y)?H(y) ③UI ⑤ H(y)??F(y) ②置換 ⑥ G(y)??F(y

24、) ④⑤假言三段論 ⑦ ?x(G(x)??F(x)) ⑥UG,54,四、構(gòu)造推理證明,例4：構(gòu)造下述推理證明 前提：?x(F(x)?G(x))，?xF(x) 結(jié)論：?xG(x),證明：① ?xF(x) 前提引入 ② ?x(F(x)?G(x)) 前提引入,55,四、構(gòu)造推理證明

25、,③ F(c) ①EI④ F(c)?G(c) ②UI⑤ G(c) ③④假言推理⑥ ?xG(x) ⑤EG,56,四、構(gòu)造推理證明,例5： 構(gòu)造下述推理證明 前提：?xF(x)??xG(x) 結(jié)論：?x(F(x)?G(x)),證明：

26、① ?xF(x)??xG(x) 前提引入 ② ?x?y(F(x)?G(y)) ①置換 ③ ?x(F(x)?G(z)) ②UI,57,四、構(gòu)造推理證明,④ F(z)?G(z) ③UI ⑤ ?x(F(x)?G(x)) ④UG 說(shuō)明: 不能對(duì)?xF(x)??xG(x)消量詞, 因?yàn)樗皇乔笆?/p>

27、范式。對(duì)此題不能用附加前提證明法。,58,四、構(gòu)造推理證明,例6：構(gòu)造下述推理證明 前提：?x(F(x)?G(x)) 結(jié)論：?xF(x)??xG(x),59,四、構(gòu)造推理證明,證明：① ?xF(x) 附加前提引入 ② F(y) ①UI ③ ?x(F(x)?G(x)) 前提引入

28、 ④ F(y)?G(y) ③UI ⑤ G(y) ②④假言推理 ⑥ ?xG(x) ⑤UG,60,四、構(gòu)造推理證明,例7：構(gòu)造下述推理證明前提： ?x(F(x)?G(x)) ， ?x(F(x)ÙH(x))結(jié)論： ?x(G(x)ÙH(x)

29、),證明： ① ?x(F(x)ÙH(x)) 前提引入 ② F(c)ÙH(c) ① EI,61,四、構(gòu)造推理證明,③ F(c) ②化簡(jiǎn)④ H(c) ②化簡(jiǎn)⑤ ?x(F(x)?G(x))