離散數(shù)學第五版第二章(耿素云、屈婉玲、張立昂編著)-資料下載頁
2025-08-07 10:55本頁面
【正文】 ?G(y)?H(z)?L(x,y,z)) ?x(F(x)??y(G(y)?H(x,y))) ?x(F(x)??y(G(y)?H(x,y))) 三、前束范式 定義（定義 ） 45 一階邏輯等值式 例 6：求下列公式的前束范式 1) ?xF(x)???xG(x) 2) ?xF(x)???xG(x) 3) ?xF(x)??xG(x) 4) ?xF(x)??xG(x) 注意： (1)由于 ?對 ?適合分配律，所以 1)式才有只帶一個 量詞的前束范式。而 ?對 ?不適合分配律，因此 2)式不能有帶一個量詞的前束范式。 5) (?xF(x,y)??yG(y))??xH(x,y) (2) 使用 ?x(A(x)?B)??xA(x)?B ?x(A(x)?B)??xA(x)?B時，必須注意條件。 (3) 公式的前束范式不唯一。 46 第二章 一階邏輯基本概念 一階邏輯的基本概念 一階邏輯合式公式及解釋 一階邏輯等值式 一階邏輯推理理論 47 一階邏輯推理理論 1. 一階邏輯的推理正確性 一、一階邏輯推理理論 在一階邏輯中，從前題 A1,A2,……,Ak出發(fā)推結(jié)論 B的推理的 形式結(jié)構(gòu)，若 A1?A2?……?Ak?B為永真式，則稱推理正確。 2. 一階邏輯的推理定律 (1)命題邏輯推理定律的代入實例。 例如： ?xF(x)??yG(y)??xF(x) ?xF(x)??xF(x)??yG(y) 48 一階邏輯推理理論 (2)基本等值式生成的推理定律 例如： ?xF(x)????xF(x) ???xF(x)??xF(x) ??xF(x)???F(x) ??F(x)???xF(x) (3)幾個重要的推理定律 例如： ?xA(x)??xB(x)??x(A(x)?B(x)) ?x(A(x)?B(x))??xA(x)??xB(x) ?x(A(x)?B(x))??xA(x)??xB(x) ?x(A(x)?B(x))??xA(x)??xB(x) 49 一階邏輯推理理論 3. 一階邏輯的推理規(guī)則 兩式成立的條件是： 1) 在第一式中，取代 x的 y應為任意的不在 A(x)中 約束出現(xiàn)的個體變項。 2) 在第二式中， c為任意的不在 A(x)中出現(xiàn)過的個體常項。 3) 用 y或 c去取代 A(x)中的自由出現(xiàn)的 x時，一定要在 x自由 出現(xiàn)的一切地方進行取代。 （ 1）全稱量詞消去規(guī)則（簡記為 UI規(guī)則或 UI） 50 一階邏輯推理理論 該式成立的條件是： 1) 無論 A(y)中自由出現(xiàn)的個體變項 y取何值， A(y)應該均 為真。 2) 取代自由出現(xiàn)的 y的 x也不能在 A(y)中約束出現(xiàn)，否則也 可能產(chǎn)生 A(y)為真而 ?xA(x)為假的情況 。 （ 2）全稱量詞引入規(guī)則（簡記為 UG規(guī)則或 UG） 51 一階邏輯推理理論 該式成立的條件是： 1) c是使 A為真的特定的個體常項。 2) c不在 A(x)中出現(xiàn)。 3) 若 A(x)中除自由出現(xiàn)的 x外，還有其它自由出現(xiàn)的個體 變項，此規(guī)則不能使用。 （ 4）存在量詞消去規(guī)則（簡記為 EI規(guī)則） 52 例 1：設(shè)個體域為實數(shù)集合， F(x,y)為 xy。指出在推理系統(tǒng) F中， 以 ?x?yF(x,y)(真命題 )為前提，推出 ?xF(x,c)(假命題 )的 原因 。 ① ?x?yF(x,y) ② ?yF(z,y) ③ F(z,c) ④ ?xF(x,c) 53 例 2：在自然推理系統(tǒng) F中，構(gòu)造下面推理的證明： 任何自然數(shù)都是整數(shù)，存在著自然數(shù)。所以存在著整數(shù)。個 體域為實數(shù)集合 R。 例 3：在自然推理系統(tǒng) F中，構(gòu)造下面推理的證明。 前提： ?x(F(x)?G(x)),?x(F(x)?H(x)) 結(jié)論： ?x(G(x)?H(x)) 54 例 4：在自然推理系統(tǒng) F中，構(gòu)造下面推理的證明： 不存在能表示成分數(shù)的無理數(shù)，有理數(shù)都能表示成分數(shù)。因 此，有理數(shù)都不是無理數(shù)。 例 5：在自然推理系統(tǒng) F中，構(gòu)造下面推理的證明。 (1)前提： ?xF(x),?xF(x)??y((F(y)?G(y))?R(y)) 結(jié)論： ?xR(x) (2)前提： ?xF(x),?x(F(x)?(G(y)?R(x))) 結(jié)論： ?x(F(x)?R(x))
高考資料相關(guān)推薦
鄂ICP備17016276號-1