1、第二章數(shù)理邏輯,張玉平,第二章謂詞邏輯,謂詞和量詞項和公式解釋和賦值永真式等值演算邏輯推論,謂詞和量詞,論域和個體謂詞量詞,論域和個體,論域：研究對象組成一個非空集合，稱這個非空集合為論域。（例如：點、線、面、體組成了幾何學(xué)的論域，數(shù)論的論域是所有正整數(shù)組成的集合。）論域要求不能為空集。個體：論域中的元素稱為個體。,謂詞,論域的子集可看做從論域到集合0,1的函數(shù)，稱這樣的函數(shù)為論域上的一元謂詞。學(xué)生的集合是人的集合的子集，是一個一元謂詞，用表示，張華用a表示?！皬埲A是學(xué)生”可表示為(a).從D2到集合0,1的函數(shù)，稱為論域D上的二元謂詞。從Dn到集合0,1的函數(shù)，稱為論域D上的N元謂詞。,量詞

2、,量詞：論域中某種性質(zhì)個體的數(shù)量。用表示論域中每個元素。用表示論域中至少有一個元素。量詞的意義取決于論域。,特征謂詞,對論域的一部分，即論域的真子集做全稱判斷或存在判斷，則需要引進(jìn)一個一元謂詞表示這個子集，我們稱這個一元謂詞為特征謂詞。如果是全稱判斷，特征謂詞后應(yīng)該用蘊(yùn)涵聯(lián)結(jié)詞；如果是存在判斷，特征謂詞后應(yīng)該用合取聯(lián)結(jié)詞。,項和公式,項原子公式公式約束出現(xiàn)自由出現(xiàn)基項、語句與開公式代換代入,項,項的定義如下：(1)個體變元是項；(2)個體常元是項；(3)若f是n元函數(shù)符號，t1,tn是項，則f(t1,tn)是項。,原子公式,若P是n元謂詞符號，t1,tn是項，則P(t1,tn)是原子公式。原子

3、公式用于表示簡單命題。設(shè)f,g是一元函數(shù)符號，P是一元謂詞符號，Q是二元謂詞符號，則Q(f(x),g(f(x)，P(f(a)是原子公式。,公式,公式的定義如下：(1)每個原子公式是公式；(2)若A是公式，則是公式；(3)若A,B是公式，則(AB)是公式；(4)若A是公式，x是變元，則是公式。若公式B在公式A中出現(xiàn)，則稱B為A的子公式。,約束出現(xiàn),稱變元x在公式中的出現(xiàn)為約束出現(xiàn)，并稱該次出現(xiàn)的轄域為A。如果變元x在公式A中的某次出現(xiàn)是在A的一個子公式中的約束出現(xiàn)，則稱x的該次出現(xiàn)為在A中的約束出現(xiàn)。,自由出現(xiàn),如果變元x在公式A中的某次出現(xiàn)不是約束出現(xiàn)，則稱該出現(xiàn)為在A中的自由出現(xiàn)。在公式A中

4、有自由出現(xiàn)的變元稱為A的自由變元，在公式A中有約束出現(xiàn)的變元稱為A的約束變元。將A中自由變元的集合記為Var(A)。,基項、語句與開公式,不出現(xiàn)變元的項稱為基項。沒有自由變元的公式稱為語句。沒有約束變元的公式稱為開公式。,代換,若x1,xn是不同的變元，t1,tn是項，則x1/t1,xn/tn稱為代換。若t是項，x1/t1,xn/tn是代換，則tx1/t1,xn/tn是用t1,tn分別同時代替t中t1,tn的所有出現(xiàn)得到的項，簡記為。若A是公式，x1/t1,xn/tn是代換，則Ax1/t1,xn/tn是用t1,tn分別同時代替A中的x1,xn所有自由出現(xiàn)得到的公式，簡記為。,代入,設(shè)x1,xn

5、是不同的變元，t1,tn是項，A是公式。如果在公式和A中變元的約束出現(xiàn)次數(shù)相同，則稱t1,tn對于A中的x1,xn是可代入的。否則稱t1,tn對于A中的x1,xn是不可代入的。,解釋和賦值,解釋賦值,解釋,一個解釋I由以下四部分組成。(1)指定一個非空集合DI，稱為I的論域。(2)對于每個常元a，指定DI中一個元素aI。(3)對于每個n元函數(shù)符號f，指定一個DI上的一個n元運算fI。(4)對于每個n元謂詞符號$P$，指定一個DI上的一個n元謂詞PI。,賦值,從所有變元組成的集合到解釋I的論域DI的函數(shù)稱為I中的賦值。,永真式,永真式替換實例,永真式,設(shè)A是公式。(1)如果A在每個解釋中為真，則

6、稱A為永真式，也稱A為邏輯有效的公式。(2)如果A在每個解釋中為假，則稱A為永假式，也稱為矛盾式，不可滿足式。(3)如果有解釋I和I中的賦值使I(A)(v)=1，則稱A為可滿足式，并稱解釋I和賦值v滿足A。,替換實例,用謂詞邏輯公式B1,Bn分別替換命題邏輯公式A中命題變元p1,pn得到的謂詞邏輯公式記為，稱為A的替換實例。命題邏輯永真式的替換實例稱為重言式。,等值演算,邏輯等價常用等值模式,邏輯等價,如果對于每個解釋I和解釋I中每個賦值v，I(A)(v)=I(B)(v)，則稱A和B等值，也稱A和B邏輯等價，記為AB。,常用等值模式,邏輯推論,滿足與不可滿足邏輯推論,滿足與不可滿足,若解釋I和I中賦值v滿足公式集合中的每個公式，則稱I