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

第五章

一階邏輯等值演算與推理1本章主要內(nèi)容5.1一階邏輯等值式與置換規(guī)那么5.2一階邏輯前束范式5.3一階邏輯的推理理論25.1一階邏輯等值式與置換規(guī)那么等值式的概念根本等值式等值演算與置換規(guī)那么3所有的學(xué)生都上課了，這是錯(cuò)的。

令F(x):x是學(xué)生,G(x):x上課了。

這句話相當(dāng)于“有些學(xué)生沒有上課”。4一、等值式的概念定義：假設(shè)AB為永真式，那么稱A與B是等值的，記作AB，并稱AB為等值式。其中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)

…

A(an)

xA(x)

A(a1)

A(a2)

…

A(an)7二、根本等值式量詞否認(rèn)等值式“并不是所有的人都是黃皮膚?！?/p>

這句話相當(dāng)于“有的人不是黃皮膚?！?二、根本等值式量詞轄域收縮與擴(kuò)張等值式設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn)。

關(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)

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)注意：

對(duì)

無分配律，

對(duì)

無分配律11三、等值演算與置換規(guī)那么置換規(guī)那么：設(shè)(A)是含有公式A的公式，用公式B置換(A)中所有的A后得到新的公式(B)，假設(shè)AB,那么(B)(A)等值演算的根底：〔1〕一階邏輯的根本等值式；〔2〕置換規(guī)那么、換名規(guī)那么、代替規(guī)那么。12例題

例1：下面的命題都有兩種不同的符號(hào)化形式，寫出其中的一種，然后通過等值演算得到另一種。

(1)沒有不犯錯(cuò)誤的人

(2)不是所有的人都愛看電影13(1)沒有不犯錯(cuò)誤的人令F(x)：x是人，G(x)：x犯錯(cuò)誤例題14(2)不是所有的人都愛看電影令F(x)：x是人，G(x)：愛看電影例題15例2：設(shè)個(gè)體域D={a,b,c}，在D中消去以下公式中的量詞。兩次使用“消去等值式”例題16量詞轄域收縮與擴(kuò)張等值式解法二：小結(jié)：采用不同的演算過程同樣可以到達(dá)消去量詞的目的，但是如何演算才更簡(jiǎn)單呢？結(jié)論是將量詞轄域盡可能的縮小，然后再消量詞。例題17方法2：例題18(3)當(dāng)個(gè)體域D={a,b}提問：如果先消去全稱量詞，后消去存在量詞，結(jié)果會(huì)怎樣？例題19該題量詞的轄域已經(jīng)不能再縮小了，所以演算過程無法再簡(jiǎn)化，演算結(jié)果也不易化的更簡(jiǎn)單。

兩種消去順序得到的結(jié)果相同。例題20

例3給定解釋I如下:

(a)個(gè)體域D={2，3}(b)(c)(d)謂詞如下頁(yè)所示例題21

在I下求下列各式的真值。例題22計(jì)算過程見教材例題23例4：證明下面的謂詞公式是永真式。

證明謂詞公式是永真式不能像命題公式那樣使用真值表。常用的方法是等值演算。例題24經(jīng)過等值演算可知該公式是永真式。例題25例題26兔子比烏龜跑得快。令：F(x):x是兔子G(y):y是烏龜

L(x,y):x比y跑得快命題符號(hào)化為：另外一種等值的符號(hào)化形式為：275.2前束范式定義：設(shè)A為一個(gè)一階邏輯公式,假設(shè)A具有如下形式Q1x1Q2x2…QkxkB,那么稱A為前束范式,其中Qi(1ik)為或，B為不含量詞的公式。例：

x

y(F(x)

(G(y)

H(x,y)))

x

(F(x)

G(x))

x(F(x)

G(x))不是前束范式。B前束范式B285.2前束范式(1)x(M(x)F(x))解：x(M(x)F(x))x(M(x)F(x))〔量詞否認(rèn)等值式〕x(M(x)F(x))兩步結(jié)果都是原公式的前束范式。例1：求以下公式的前束范式295.2前束范式(2)xF(x)xG(x)解：xF(x)xG(x)xF(x)xG(x)〔量詞否認(rèn)等值式〕x(F(x)G(x))〔量詞分配等值式〕另有一種形式如下：305.2前束范式xF(x)xG(x)xF(x)xG(x)xF(x)yG(y)(換名規(guī)那么)x(F(x)yG(y))(量詞轄域擴(kuò)張)xy(F(x)G(y))(量詞轄域擴(kuò)張)315.2前束范式(3)

xF(x)

xG(x)

解

xF(x)

xG(x)

xF(x)

x

G(x)

x(F(x)

G(x))

或

x

y(F(x)

G(y))325.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ī)那么)zy(F(z)(G(x,y)H(y)))或xF(x)y(G(t,y)H(y))(代替規(guī)那么)xy(F(x)(G(t,y)H(y)))335.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)))xy(F(x,u)G(x,y)H(x,z)))注意：x與y不能顛倒(換名規(guī)那么)345.2前束范式〔6〕355.2前束范式例題小結(jié)：公式的前束范式不惟一；求公式的前束范式的方法:利用根本等值式、置換規(guī)那么、換名規(guī)那么、代替規(guī)那么進(jìn)行等值演算。

定理：一階邏輯中的任何公式都存在與之等值的前束范式。365.3一階邏輯的推理理論推理的形式結(jié)構(gòu)重要的推理定律推理規(guī)那么構(gòu)造證明〔附加前提證明法〕37一、推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)有兩種：第一種A1A2…AkB(*)第二種前提：A1，A2，…，Ak結(jié)論：B其中A1,A2,…,Ak,B為一階邏輯公式.假設(shè)(*)為永真式,那么稱推理正確,否那么稱推理不正確38一、推理的形式結(jié)構(gòu)

判斷推理是否正確的方法：等值演算法，應(yīng)用這種方法時(shí)采用第一種形式結(jié)構(gòu)；構(gòu)造證明法，采用第二種形式結(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(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)全稱量詞消去規(guī)那么〔記為UI〕注意：下面的規(guī)那么只能用于前束范式。在(1)式中，y應(yīng)為任意的不在A(x)中約束出現(xiàn)的個(gè)體變項(xiàng)。在第二式中，c為任意的未在A(x)中出現(xiàn)過的個(gè)體常項(xiàng)。用y或c去取代A(x)中的自由出現(xiàn)的x時(shí)，一定要在x自由出現(xiàn)的一切地方進(jìn)行取代。43(13)全稱量詞引入規(guī)那么〔記為UG〕無論A(y)中自由出現(xiàn)的個(gè)體變項(xiàng)y取何值，A(y)應(yīng)該均為真。x不約束出現(xiàn)在A(y)中。假設(shè)對(duì)A(y)應(yīng)用UG規(guī)那么時(shí)，用在A(y)中約束出現(xiàn)的x代替y，那么得到44(14)存在量詞消去規(guī)那么〔記為EI〕c是個(gè)體域中使A為真的某個(gè)確定的個(gè)體，且c不在A(x)中出現(xiàn)。假設(shè)A(x)中除自由出現(xiàn)的x外，還有其他自由出現(xiàn)的個(gè)體變項(xiàng)，此規(guī)那么不能使用。對(duì)公式能否用EI規(guī)則？提問：45三、推理規(guī)那么前提引入(1)UI規(guī)那么(2)EI規(guī)那么(3)UG規(guī)那么46(15)存在量詞引入規(guī)那么〔記為EG〕

該式成立的條件是：c是使A為真的特定個(gè)體常項(xiàng).取代c的x不能在A(c)中出現(xiàn)過.47四、構(gòu)造推理證明一階邏輯自然推理系統(tǒng)F1.字母表，即一階語言的字母表。2.合式公式。3.推理規(guī)那么

構(gòu)造推理證明的方法：直接法，附加前提引入法和歸謬法。48四、構(gòu)造推理證明

例1：在自然推理系統(tǒng)中，指出下面各證明序列中的錯(cuò)誤。（1）

前提引入

EI規(guī)則（2）

前提引入

EI規(guī)則49四、構(gòu)造推理證明（3）

前提引入

EG規(guī)則（4）

前提引入

EG規(guī)則（5）

前提引入

UG規(guī)則50四、構(gòu)造推理證明

例2：證明蘇格拉底三段論:“人都是要死的,蘇格拉底是人，所以蘇格拉底是要死的?！?/p>

令：F(x):x是人,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(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)造推理證明證明：①

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)④⑤假言三段論

⑦

x(G(x)

F(x))⑥UG54四、構(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)造推理證明③F(c)①EI④F(c)

G(c)②UI⑤G(c)③④假言推理⑥

xG(x)⑤EG56四、構(gòu)造推理證明

例5：構(gòu)造下述推理證明前提：

xF(x)

xG(x)

結(jié)論：

x(F(x)

G(x))證明：①

xF(x)

xG(x)前提引入

②

x

y(F(x)

G(y))①置換

③

x(F(x)

G(z))②UI57四、構(gòu)造推理證明④F(z)

G(z)③UI⑤

x(F(x)

G(x))④UG

說明:不能對(duì)

xF(x)

xG(x)消量詞,因?yàn)樗皇乔笆妒?。?duì)此題不能用附加前提證明法。58四、構(gòu)造推理證明

例6：構(gòu)造下述推理證明前提：

x(F(x)

G(x))

結(jié)論：

xF(x)

xG(x)59四、構(gòu)造推理證明證明：①

xF(x)附加前提引入

②F(y)