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

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

”。表示個體域里的所有個體關系。存在量詞：存在、有一個、有的、至少有一個...。符號化為“

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

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前束范式定義：設A為謂詞邏輯公式，假設A具有形式Q1x1Q2x2...QnxnB，其中Qi為或，B為不含量詞的公式。存在定理：任何謂詞邏輯公式都存在與之等值的前束范式。前束范式例：

xF(x)→xG(x)(

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

xH(x,y)23