math-chap2-2.離散數(shù)學(xué)-謂詞邏輯

1第二章謂詞邏輯2主要內(nèi)容謂詞邏輯的根本概念謂詞公式謂詞邏輯等值式謂詞邏輯推理3命題邏輯的缺乏之處命題邏輯研究的對(duì)象為命題(為一個(gè)完整的陳述句)，對(duì)于原子命題不可分。例魚兒離不開水。鯽魚是魚。所以鯽魚離不開水。簡(jiǎn)單命題之間的內(nèi)在聯(lián)系需要通過(guò)進(jìn)一步分析原子命題中主、謂等之間的關(guān)系。個(gè)體謂詞量詞4個(gè)體定義：可以獨(dú)立存在的客觀實(shí)體稱為個(gè)體。具體事物抽象概念例小王和小明是同學(xué)。a能被2整除。x是有理數(shù)。個(gè)體常項(xiàng)：表示具體或特定的個(gè)體，常用字母a,b,c...表示；個(gè)體變項(xiàng)：表示抽象或泛指的個(gè)體，常用字母x,y,z...表示；個(gè)體域：個(gè)體變項(xiàng)的取值范圍，也稱論域。全總個(gè)體域：宇宙間一切事物組成的個(gè)體域。5謂詞定義：刻畫個(gè)體具有的性質(zhì)或個(gè)體之間關(guān)系的詞。謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系的謂詞。謂詞變項(xiàng)：表示抽象的或泛指的謂詞。謂詞符號(hào)通常用大寫字母表示。例：F：...和...是同學(xué)。G：...能被...整除。H：...是有理數(shù)。6謂詞元數(shù)：謂詞中包含的個(gè)體變項(xiàng)數(shù)。含n個(gè)個(gè)體變項(xiàng)的謂詞稱為n元謂詞。0元謂詞：不帶個(gè)體變項(xiàng)的謂詞。命題均可以表示成0元謂詞。例：4=3+1如果2是素?cái)?shù)，那么3是素?cái)?shù)。7量詞定義：表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞。全稱量詞：一切的、所有的、每一個(gè)、任意的、都...。符號(hào)化為“

”。表示個(gè)體域里的所有個(gè)體關(guān)系。存在量詞：存在、有一個(gè)、有的、至少有一個(gè)...。符號(hào)化為“

”。表示個(gè)體域里有的個(gè)體關(guān)系。例所有人都需要呼吸空氣。有的人沒(méi)來(lái)上課。8量詞量詞需要注意個(gè)體域的問(wèn)題。在不同的個(gè)體域內(nèi)，命題的真值可能不同。例：存在x，使得x+3=2。個(gè)體域?yàn)樽匀粩?shù)個(gè)體域?yàn)檎麛?shù)特性謂詞：將某類個(gè)體從個(gè)體域中區(qū)分出來(lái)的謂詞。M(x)：x是人；F(x)：x是魚；Z(x)：x是整數(shù)。9命題符號(hào)化明確命題個(gè)體域，分別找出個(gè)體常項(xiàng)、個(gè)體變項(xiàng)、量詞和謂詞；按照命題的意思用邏輯聯(lián)結(jié)詞將其組合；注意：引入特性謂詞時(shí)，全稱量詞的特性謂詞作為命題的前提引入，而存在量詞的特性謂詞作為命題的合取項(xiàng)引入；多個(gè)量詞同時(shí)出現(xiàn)，需要注意量詞的順序不能隨意顛倒。例：并非所有的人都愛看電視。10一階謂詞的例火車比汽車跑得快。有理數(shù)可以表示成分?jǐn)?shù)。有的女孩不喜歡穿裙子。11謂詞公式謂詞公式的符號(hào)集個(gè)體常項(xiàng)：a,b,c,...個(gè)體變項(xiàng)：x,y,z,...函數(shù)符號(hào)：f,g,h,...謂詞符號(hào)：F,G,H,...量詞：,;聯(lián)結(jié)詞符號(hào)：?,∧,∨,→,?;括號(hào)：),(12謂詞公式謂詞公式的項(xiàng)的遞歸定義個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng)；假設(shè)f(x1,x2,...,xn)是任意的n元函數(shù)，t1,t2,...,tn是任意n個(gè)項(xiàng)，那么f(t1,t2,...,tn)是項(xiàng)；所有的項(xiàng)都由有限次使用上述兩條規(guī)定得到。原子公式：設(shè)R(x1,x2,...,xn)是符號(hào)集上任意n元謂詞，t1,t2,...,tn是符號(hào)集的任意n個(gè)項(xiàng)，那么稱R(t1,t2,...,tn)為原子公式。13合式公式定義(1)原子公式是合式公式；(2)假設(shè)A是合式公式，那么(?A)也是合式公式(3)假設(shè)A，B是合式公式，那么(A∧B)，(A∨B)，(A→B)，(A?B)也是合式公式；(4)假設(shè)A是合式公式，那么xA，xA也是合式公式；(5)只有有限次的應(yīng)用(1)-(4)得到的符號(hào)串才是合式公式。14約束變項(xiàng)及自由變項(xiàng)定義：xF，xF中，x稱為指導(dǎo)變項(xiàng)，F(xiàn)稱為相應(yīng)量詞的轄域。轄域中x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變項(xiàng)，F(xiàn)中不是約束出現(xiàn)的其他變項(xiàng)稱為自由變項(xiàng)。例xF(x)→yG(x,y)x(F(x,y)∧y(G(x,y))xy(F(x,y)∧G(y,z))∨H(x,y)閉式：假設(shè)合式公式中無(wú)自由出現(xiàn)的個(gè)體變項(xiàng)，那么稱A為封閉的公式，簡(jiǎn)稱閉式。15變項(xiàng)替換規(guī)那么變項(xiàng)替換的目的：為了防止個(gè)體變項(xiàng)的混淆。規(guī)那么約束變項(xiàng)換名規(guī)那么：將量詞轄域中出現(xiàn)的某個(gè)約束變項(xiàng)及其對(duì)應(yīng)的指導(dǎo)變項(xiàng)改成公式中未出現(xiàn)的個(gè)體變項(xiàng)符號(hào)，其余局部不變。自由變項(xiàng)代替規(guī)那么：將公式中某自由變項(xiàng)用原公式中未出現(xiàn)過(guò)的某個(gè)個(gè)體變項(xiàng)符號(hào)代替，且處處代替。16謂詞公式的解釋定義：為使公式成為真值確定的命題而指定的有關(guān)規(guī)定，稱為謂詞公式的一個(gè)解釋。解釋I的組成特定的個(gè)體域DD中一局部特定元素D上每個(gè)函數(shù)變項(xiàng)所取得的具體函數(shù)D上每個(gè)謂詞變項(xiàng)所取的具體謂詞例：x(F(f(x))→G(x))17謂詞公式的分類謂詞公式的分類：如果A在任何解釋下都為真，那么稱A為永真式〔邏輯有效式〕。如果A在任何解釋下都為假，那么稱A為永假式〔矛盾式〕。假設(shè)至少存在一組A的解釋使A為真，那么稱A為可滿足式。代換實(shí)例：設(shè)A0是含命題變項(xiàng)p1,p2,...,pn的命題公式，A1,A2,...,An是n個(gè)謂詞公式。用Ai代換A0中的每一個(gè)pi，所得的公式A稱為A0的代換實(shí)例。18謂詞公式的定理定理：命題公式中的重言式的代換實(shí)例在謂詞公式中為邏輯有效式；命題公式中的矛盾式的代換實(shí)例是謂詞公式中仍為矛盾式。19謂詞邏輯等值式等值式的定義：設(shè)謂詞邏輯中任意兩個(gè)公式A和B，假設(shè)A?B是是邏輯有效式，那么稱A與B為等值式。記作AB。原命題等值式的代換實(shí)例都是等值式。消去量詞等值式：設(shè)個(gè)體域D＝{a1,a2,...,an}xA(x)A(a1)∧A(a2)∧...∧A(an)xA(x)A(a1)∨A(a2)∨...∨A(an)量詞否認(rèn)等值式?xA(x)x?A(x)?xA(x)x?A(x)20謂詞邏輯等值式量詞轄域擴(kuò)張和伸縮等值式

x(A(x)∨B)

xA(x)∨B

x(A(x)∨B)

xA(x)∨B

x(A(x)∧B)

xA(x)∧B

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)

x(B→A(x))

B→

xA(x)21謂詞邏輯等值式量詞分配等值式

x(A(x)∧B(x))

xA(x)∧

xB(x)

x(A(x)∨B(x))

xA(x)∨

xB(x)量詞交換等值式

x

yA(x,y)

y

xA(x,y)

x

yA(x,y)

y

xA(x,y)22前束范式定義：設(shè)A為謂詞邏輯公式，假設(shè)A具有形式Q1x1Q2x2...QnxnB，其中Qi為或，B為不含量詞的公式。存在定理：任何謂詞邏輯公式都存在與之等值的前束范式。前束范式例：

xF(x)→xG(x)(

xF(x,y)→yG(y))→

xH(x,y)23