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

符號體系： 個體常元符號：a,b,c,a1,a2,a3, 個體變元:x,y,z,x1,x2,x3, 函數(shù)符號:f,g,h,f1,f2,f3, 謂詞符號:F,G,H, 量詞符號: 聯(lián)結(jié)詞: 項的定義 個體變元、個體常元是項； 若 是任意n元函數(shù)，t1,t2,tn 是項，則 是項； 有限次的應(yīng)用1，2得到項。,2.2 一階邏輯合式公式及解釋,原子公式： 為n元謂詞符號，t1,t2,tn 是項，則 是原子公式； 合式公式的歸納定義： 1、任意的原子公式是公式 2、若A是公式，則xA、xA是公式； 3、若A、B是公式，則 A、A B、AB、A B、A B是公式； 有限次地應(yīng)用前三條，得到公式。,判斷下列符號串是否為合式公式： 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)變元，在轄域中,x的所有出現(xiàn)稱為約束變元（約束出現(xiàn)）；y是自由變元（自由出現(xiàn)）。 量詞的轄域 (x)P(x)或(x)P(x)中的公式P(x)，通稱為量詞的轄域。換言之，量詞的轄域是鄰接其后的公式，除非轄域是原子公式，否則應(yīng)在所轄公式的兩側(cè)插入圓括號。,二、約束部分,量詞轄域舉例,例如：x F(x)G(x,y) 解：x的轄域僅F(x),x是指導(dǎo)變元，變元x第一次出現(xiàn)是約束出現(xiàn)，第二次出現(xiàn)是自由出現(xiàn)，y的出現(xiàn)是自由出現(xiàn)。所以第一個x是約束變元，第二個x是自由變元，本質(zhì)上這兩個x的含義是不同的；而y僅是自由變元。,換名規(guī)則,可以看出,在謂詞公式中一個變元可能既是約束出現(xiàn),同時又有自由出現(xiàn),則該變元既是自由變元又是約束變元,本質(zhì)上這兩種出現(xiàn),用的是一個符號,實質(zhì)上是不同的含義。為避免混淆,需要改名。改名要采用以下規(guī)則,使謂詞公式的含義不改變。 1、 換名規(guī)則：對約束變元進行換名。 將量詞轄域內(nèi)出現(xiàn)的某個約束變元及其相應(yīng)量詞中的指導(dǎo)變元，可以換成一個其他變元，改變元不能與本轄域內(nèi)的其他變元同名，公式中的其他部分不改變。 2、 代替規(guī)則：對自由變元進行代入。 整個謂詞公式中同一個字母的自由變元是指同一個個體名詞。因此可以用整個公式中沒有的變元符號來代替，且要求整個公式中該變元同時用同一個符號代替。,換名規(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) 對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),謂詞公式的解釋,謂詞邏輯中的解釋(賦值) 在命題邏輯對每個命題符號作個真值指定可以得一個公式的一個指派,又稱賦值,又稱解釋。如公式中共出現(xiàn)n個不同的命題符號,則共有2n個解釋,因而可以列出公式的真值表。而謂詞邏輯中公式的賦值解釋是怎樣的呢？ 例如公式：x F(x,a)x G(f(x),a),三、謂詞公式的賦值(解釋),一個解釋由4部分組成： （1） 非空個體域D； （2）D中特定元素； （3）D上特定函數(shù)； （4）D上特定謂詞。 公式x F(x,a)x G(f(x),a) 指定：D=實數(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：已知指定一個解釋N如下： (1)個體域為自然數(shù)集合DN (2)指定常項a=0 (3)DN上的指定函數(shù)f(x,y)=x+y,g(x,y)=x*y (4)指定謂詞F(x,y)為x=y 在以上指定的解釋N下,說明下列公式的真值 (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 此時,x,y,z均為自由變元,解釋不對自由變元進行指定。因而該公式是命題函數(shù),不是命題,真值不能確定。,解釋的說明,(1) 一個謂詞公式如果不含自由變元,則在一個解釋下,可以得到確定的真值,不同的解釋下可能得到不同的真值。 (2) 公式的解釋并不對變元進行指定,如果公式中含有自由變元,即使對公式進行了一個指派,也得不到確定的真值,其僅是個命題函數(shù),但約束變元不受此限制。 3）有公式的解釋定義可以看出,公式的解釋有許多的解釋,當D為無限集時,公式有無限多個解釋,根本不可能將其一一列出,因而謂詞邏輯的公式不可能有真值表可列。,四、謂詞公式的類型,設(shè)A是公式。如果A在任何的解釋下都是真的，則A是永真式；如果A在任何的解釋下都是假的，則A是永假式；如果A在一些解釋下為假，一些解釋下為真，則A是非永真的可滿足式。,例如： x A(x) x A(x)是永真式； x A(x)x A(x）是永假式。,代換實例,設(shè)A0是含命題變元p1, p2, , pn的命題邏輯公式，A1, A2, , An是一階邏輯公式，用Ai(1 i n)替換A0中的pi的處處出現(xiàn)所得到的一階邏輯公式A稱為命題邏輯公式A0的替換實例。 定理：命題邏輯中的永真式的任意替換實例在一階邏輯中都是永真式；命題邏輯中的矛盾式的任意替換實例在一階邏輯中都是矛盾式 。,1、永真式和永假式的代入實例是永真、永假式； 2. 對于某些簡單的公式，特別對于簡單的閉式，可在假定給定任意解釋的前提下該公式的真值都為真（或者為假）來證明該公式是永真式（或矛盾式）。 3. 要證明一個公式是可滿足式，只要找到一個解釋，使得該公式的真值為真即可。同時為了證明它不是永真式，只要找一個解釋，使得該公式的真值為假即可。,公式類型舉例,判斷下列公式的類型： 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 ) 的替換實例。容易知道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)為真。 從而，在蘊涵式的前件x F(x) 為1或0的情況，蘊涵式都為真。 又由解釋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