離散數(shù)學(xué)謂詞公式與解釋.ppt

符號(hào)體系： 個(gè)體常元符號(hào)：a,b,c,a1,a2,a3, 個(gè)體變?cè)?x,y,z,x1,x2,x3, 函數(shù)符號(hào):f,g,h,f1,f2,f3, 謂詞符號(hào):F,G,H, 量詞符號(hào): 聯(lián)結(jié)詞: 項(xiàng)的定義 個(gè)體變?cè)?、個(gè)體常元是項(xiàng)； 若 是任意n元函數(shù)，t1,t2,tn 是項(xiàng)，則 是項(xiàng)； 有限次的應(yīng)用1，2得到項(xiàng)。,2.2 一階邏輯合式公式及解釋,原子公式： 為n元謂詞符號(hào)，t1,t2,tn 是項(xiàng)，則 是原子公式； 合式公式的歸納定義： 1、任意的原子公式是公式 2、若A是公式，則xA、xA是公式； 3、若A、B是公式，則 A、A B、AB、A B、A B是公式； 有限次地應(yīng)用前三條，得到公式。,判斷下列符號(hào)串是否為合式公式： x(P(x) Q(x) xy(P(x) Q(y) yx P(x) x f(x) x(g(x,y) f(x) ),一、合式公式的定義：,在謂詞公式中，形如xP(x)或xP(x)以及 xP(x，y)的部分中x稱為指導(dǎo)變?cè)?，在轄域?x的所有出現(xiàn)稱為約束變?cè)s束出現(xiàn)）；y是自由變?cè)ㄗ杂沙霈F(xiàn)）。 量詞的轄域 (x)P(x)或(x)P(x)中的公式P(x)，通稱為量詞的轄域。換言之，量詞的轄域是鄰接其后的公式，除非轄域是原子公式，否則應(yīng)在所轄公式的兩側(cè)插入圓括號(hào)。,二、約束部分,量詞轄域舉例,例如：x F(x)G(x,y) 解：x的轄域僅F(x),x是指導(dǎo)變?cè)冊(cè)獂第一次出現(xiàn)是約束出現(xiàn)，第二次出現(xiàn)是自由出現(xiàn)，y的出現(xiàn)是自由出現(xiàn)。所以第一個(gè)x是約束變?cè)?，第二個(gè)x是自由變?cè)?，本質(zhì)上這兩個(gè)x的含義是不同的；而y僅是自由變?cè)?換名規(guī)則,可以看出,在謂詞公式中一個(gè)變?cè)赡芗仁羌s束出現(xiàn),同時(shí)又有自由出現(xiàn),則該變?cè)仁亲杂勺冊(cè)质羌s束變?cè)?本質(zhì)上這兩種出現(xiàn),用的是一個(gè)符號(hào),實(shí)質(zhì)上是不同的含義。為避免混淆,需要改名。改名要采用以下規(guī)則,使謂詞公式的含義不改變。 1、 換名規(guī)則：對(duì)約束變?cè)M(jìn)行換名。 將量詞轄域內(nèi)出現(xiàn)的某個(gè)約束變?cè)捌湎鄳?yīng)量詞中的指導(dǎo)變?cè)?，可以換成一個(gè)其他變?cè)?，改變?cè)荒芘c本轄域內(nèi)的其他變?cè)街械钠渌糠植桓淖儭?2、 代替規(guī)則：對(duì)自由變?cè)M(jìn)行代入。 整個(gè)謂詞公式中同一個(gè)字母的自由變?cè)侵竿粋€(gè)個(gè)體名詞。因此可以用整個(gè)公式中沒(méi)有的變?cè)?hào)來(lái)代替，且要求整個(gè)公式中該變?cè)瑫r(shí)用同一個(gè)符號(hào)代替。,換名規(guī)則舉例,x F(x,y)x G(x,y) 改為：x F(x,y)u G(u,y) 或者為： z F(z,y)x G(x,y) 對(duì)x (F(x,y)y G(x,y) F(x,y) 改為： x (F(x,t)y G(x,y) F(s,t) 或者為：t (F(t,y)y G(t,y) F(x,y),謂詞公式的解釋,謂詞邏輯中的解釋(賦值) 在命題邏輯對(duì)每個(gè)命題符號(hào)作個(gè)真值指定可以得一個(gè)公式的一個(gè)指派,又稱賦值,又稱解釋。如公式中共出現(xiàn)n個(gè)不同的命題符號(hào),則共有2n個(gè)解釋,因而可以列出公式的真值表。而謂詞邏輯中公式的賦值解釋是怎樣的呢？ 例如公式：x F(x,a)x G(f(x),a),三、謂詞公式的賦值(解釋),一個(gè)解釋由4部分組成： （1） 非空個(gè)體域D； （2）D中特定元素； （3）D上特定函數(shù)； （4）D上特定謂詞。 公式x F(x,a)x G(f(x),a) 指定：D=實(shí)數(shù)集合；a=0；f(x):3x;F(x,y):xy；G(x,y):x=y。 則x (x 0) x (3x=0) 假命題。,解釋舉例1,給定解釋I如下：,x(F(x) G(x,2) (F(2) G(2,2) (F(3) G(3,2) 0 1 1,y L(2,y) y L(3,y) (L(2,2)L(2,3) (L(3,2) L(3,3) ( 1 0 ) (0 1) 1,解釋舉例2,例2：已知指定一個(gè)解釋N如下： (1)個(gè)體域?yàn)樽匀粩?shù)集合DN (2)指定常項(xiàng)a=0 (3)DN上的指定函數(shù)f(x,y)=x+y,g(x,y)=x*y (4)指定謂詞F(x,y)為x=y 在以上指定的解釋N下,說(shuō)明下列公式的真值 (1)xF(g(x,a),x) 即x(x*0=x)該命題假的 (2)xy(F(f(x,a),y)F(f(y,a),x) 在解釋N下此公式：xy(x+0=yy+0=x)此命題為真 (3)F(f(x,y),f(y,z)在解釋N下該公式x+y=y+z 此時(shí),x,y,z均為自由變?cè)?解釋不對(duì)自由變?cè)M(jìn)行指定。因而該公式是命題函數(shù),不是命題,真值不能確定。,解釋的說(shuō)明,(1) 一個(gè)謂詞公式如果不含自由變?cè)?則在一個(gè)解釋下,可以得到確定的真值,不同的解釋下可能得到不同的真值。 (2) 公式的解釋并不對(duì)變?cè)M(jìn)行指定,如果公式中含有自由變?cè)?即使對(duì)公式進(jìn)行了一個(gè)指派,也得不到確定的真值,其僅是個(gè)命題函數(shù),但約束變?cè)皇艽讼拗啤?3）有公式的解釋定義可以看出,公式的解釋有許多的解釋,當(dāng)D為無(wú)限集時(shí),公式有無(wú)限多個(gè)解釋,根本不可能將其一一列出,因而謂詞邏輯的公式不可能有真值表可列。,四、謂詞公式的類型,設(shè)A是公式。如果A在任何的解釋下都是真的，則A是永真式；如果A在任何的解釋下都是假的，則A是永假式；如果A在一些解釋下為假，一些解釋下為真，則A是非永真的可滿足式。,例如： x A(x) x A(x)是永真式； x A(x)x A(x）是永假式。,代換實(shí)例,設(shè)A0是含命題變?cè)猵1, p2, , pn的命題邏輯公式，A1, A2, , An是一階邏輯公式，用Ai(1 i n)替換A0中的pi的處處出現(xiàn)所得到的一階邏輯公式A稱為命題邏輯公式A0的替換實(shí)例。 定理：命題邏輯中的永真式的任意替換實(shí)例在一階邏輯中都是永真式；命題邏輯中的矛盾式的任意替換實(shí)例在一階邏輯中都是矛盾式 。,1、永真式和永假式的代入實(shí)例是永真、永假式； 2. 對(duì)于某些簡(jiǎn)單的公式，特別對(duì)于簡(jiǎn)單的閉式，可在假定給定任意解釋的前提下該公式的真值都為真（或者為假）來(lái)證明該公式是永真式（或矛盾式）。 3. 要證明一個(gè)公式是可滿足式，只要找到一個(gè)解釋，使得該公式的真值為真即可。同時(shí)為了證明它不是永真式，只要找一個(gè)解釋，使得該公式的真值為假即可。,公式類型舉例,判斷下列公式的類型： 1) x F(x) (x yG(x,y) x F(x) ) 2) x F(x) x F(x) 3) x y F(x,y) y x F(x,y),x F(x) (x yG(x,y) x F(x) ),解：顯然該公式是：P (Q P ) 的替換實(shí)例。容易知道P (Q P ) 是永真式，從而x F(x) (x yG(x,y) x F(x) )是永真式。,2) x F(x) x F(x),設(shè)在任意的解釋I下， 1） x F(x) 為真，則 a，使得 F(a)為真，使得 x F(x)為真， 在這種情況下，x F(x) x F(x)為真； 2） x F(x) 為假，x F(x) x F(x)為真。 從而，在蘊(yùn)涵式的前件x F(x) 為1或0的情況，蘊(yùn)涵式都為真。 又由解釋I的任意性，知公式x F(x) x F(x)永真。,3) x y F(x,y) y x F(x,y),1）取解釋I1為：D=R,F(x,y):xy 則公式為： x y (xy) y x(xy) =10=0，從而公式不是永真式； 2) 取解釋I2為：D=R,F(x,y):x.y=0 則公式為：xy(xy=0)yx(xy=0) =1