《離散數(shù)學(xué)第三章謂詞演算基礎(chǔ)-自由變元和約束變元.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第三章謂詞演算基礎(chǔ)-自由變元和約束變元.ppt（21頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、第三章 謂詞演算基礎(chǔ),3.1 謂詞與個體 3.2 函數(shù)與量詞 3.3 自由變元和約束變元 3.3.1 自由出現(xiàn)和約束出現(xiàn) 3.3.2 改名和代入 3.4 永真性和可滿足性 3.5 唯一性量詞與摹狀詞,,復(fù)習(xí): 項(xiàng),例 考察謂詞 WRITE(x,y)表示x 寫了y 的謂詞填式：,WRITE(Shakespeare，Hamlet) WRITE(Shakespeare，y) WRITE(son(Shakespeare)，Hamlet),變量符號,函數(shù)！,實(shí)體,謂詞演算公式的原子公式,謂詞填式A(x1，x2，，xn) 其中x1，，xn是項(xiàng)(實(shí)體、變量符號、函數(shù))。,原子公式是公式的最
2、小單位，是最小的句子單位。 項(xiàng)不是公式。 函數(shù)f(t1,...，tm)不是句子，僅是詞，因而不是公式僅是項(xiàng)。項(xiàng)的結(jié)果仍是個體名稱集合中的名詞，而公式的結(jié)果(真值)是成立或不成立(是1或0)。,合式公式的定義,定義1：謂詞演算的合式公式(簡稱公式)是由 原子命題、 謂詞填式（原子公式）、 或由它們利用聯(lián)結(jié)詞和量詞 構(gòu)成的式子。,合式公式的形式定義,(1) 原子命題P是合式公式； (2) 謂詞填式A(x1，x2，x3，，xn)是合式公式； (3) 若A是公式，則A是合式公式； (4) 若A和B是合式公式，則 (AB)，(AB)，(AB)，(AB)為公式； (5) 若A是合式公式，x是A中出現(xiàn)的任
3、何個體變元，則xA(x)，xA(x)為合式公式。 (6)只有有限次使用(1)、(2)、(3)、(4)、(5)所得到的式子才是合式公式。,自由出現(xiàn)和約束出現(xiàn),定義2：設(shè)為任何一個謂詞演算公式，并設(shè) xA(x)，xA(x)為公式的子公式， 此時緊跟在、之后的x稱為量詞的指導(dǎo)變元或作用變元， A(x)稱為相應(yīng)量詞的作用域或轄域， 在作用域中x 的一切出現(xiàn)均稱為約束出現(xiàn)， 在中除了約束出現(xiàn)外的一切出現(xiàn)x均稱為自由出現(xiàn)。,例 x(A(x，y)),,例(29) x(A(x，y)y(B(x，y)C(z))),指出合式公式的作用域、約束出現(xiàn)和自由出現(xiàn)。,解：x的作用域?yàn)椋? A(x，y)y(B(x，y
4、)C(z))； y的作用域?yàn)椋? B(x，y)C(z)； 公式中的x為約束出現(xiàn)， 第一個y和z是自由出現(xiàn)， B(x，y)C(z)中的y為約束出現(xiàn)。,自由變元和約束變元,定義3：一個變元x 若在公式中有自由出現(xiàn)，則稱此變元為自由變元； 若有約束出現(xiàn)，則稱為約束變元。,,例 x(A(x，y)) x為約束變元， y為自由變元，不受全稱量詞約束，可以看作為公式中的參數(shù)。,,例 x(p(x)yQ(x,y)),指出公式的指導(dǎo)變元，轄域、約束變元和自由變元。,解：由x后的()，x是指導(dǎo)變元，x的轄域是后面整個式子 p(x)yQ(x,y) ， y是指導(dǎo)變元，轄域僅Q(x，y)此部分。
5、x兩次出現(xiàn)均是約束出現(xiàn)，y的一次出現(xiàn)是約束出現(xiàn)，故x，y是約束變元，而不是自由變元。,例 xF(x)G(x,y),指出公式的指導(dǎo)變元，轄域、約束變元和自由變元。,解：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僅是自由變元。,例 x(x=yx2+x<5x
6、x=yx2+x<5x
7、改名，改名時應(yīng)對量詞的指導(dǎo)變元及其作用域中所出現(xiàn)的約束變元處處進(jìn)行； (2) 改名前后不能改變變元的約束關(guān)系； (3) 改名用的新名應(yīng)是該作用域中沒有使用過的變元名稱。,例： x(A(x，y)y(B(x，y))) 解： 可把公式改名為： x(A(x，y)z(B(x，z))),例 對下面公式實(shí)施改名,(1) x(A(x，y)y(B(x，y)C(z))) (2) xF(x，y)xG(x，y),解：(1) 可把公式改名為： x(A(x，y)u(B(x，u)C(z))) (2) x是約束變元,y是自由變元。而x的兩次出現(xiàn)盡管均是約束的,但分別在不同的轄域。含義是互相無關(guān)的?？梢詫⒁惶帗Q名,但不能
8、與y同名?？梢愿拿麨椋? xF(x，y)uG(u，y),例 x(F(x,y) P(x)) y(Q(x,y) R(x)),解： x前兩次出現(xiàn)是約束的,后兩次出現(xiàn)是自由的。y第一次出現(xiàn)是自由的,第二次是約束的,準(zhǔn)備將約束變元x改為u,約束變元y改為v,成為 u(F(u,y) P(u)) v(Q(x,v) R(x)),二、代入,謂詞演算公式中的自由變元可以更改，稱為代入。,代入是對自由變元而言， 約束變元不能代入。 代入后的式子是原式的特例,代入規(guī)則,(1) 代入必須處處進(jìn)行，即代入時必須對公式中出現(xiàn)的所有同名的自由變元進(jìn)行。 (2) 代入后不能改變原式和代入式的約束關(guān)系。 (3) 代入也
9、可以對謂詞填式而言，但也要遵循上面兩條規(guī)則； (4) 命題變元也可以實(shí)施代入。,例 x(A(x，y)y(B(x，y)C(z))),試把公式中的自由變元y 代以式子x2+2。,解：先對原式改名，x改為u，y改為v，改名后得： u(A(u，y)v(B(u，v)C(z))) 最后代入得： u(A(u，x2+2)v(B(u，v)C(z))) 驗(yàn)證公式可知，沒有改變變元的約束關(guān)系，所以這種代入符合代入規(guī)則。,例 x(A(x，y)y(B(x，y)C(z))),試把公式中的謂詞變元A(e1，e2)代以 yD(e1，e2，y，x)。,解: 現(xiàn)在先對原式改名，x改為u，y改為v得： u(A(u，y)v(B(u，v)C(z)))， 再對代入式改名，y改為t得： tD(e1，e2，t，x)， 最后代入，得： u(tD(u，y，t，x)v(B(u，v)C(z))),第三章 謂詞演算基礎(chǔ),3.1 謂詞與個體 3.2 函數(shù)與量詞 3.3 自由變元和約束變元 3.3.1 自由出現(xiàn)和約束出現(xiàn) 3.3.2 改名和代入 3.4 永真性和可滿足性 3.5 唯一性量詞與摹狀詞,,
離散數(shù)學(xué)第三章謂詞演算基礎(chǔ)-自由變元和約束變元.ppt
