資源描述：
《離散數(shù)學(xué)第三章謂詞演算基礎(chǔ)-永真性和可滿足性課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第三章謂詞演算基礎(chǔ)3.1謂詞與個體3.2函數(shù)與量詞3.3自由變元和約束變元3.4永真性和可滿足性3.4.1真假性3.4.2同真假性、永真性和可滿足性3.4.3范式3.5唯一性量詞與摹狀詞真假性：四個因素(1)個體域設(shè)A(e)表示e為偶數(shù)，考察?xA(x)當個體域I為{1，2，3}時，公式的值為假；當個體域I為{2，4，6}時，公式的值為真。真假性：四個因素(2)自由變元設(shè)A(e)表示e為偶數(shù)，考察A(x)當x取2時，其值為T；當x取為3時，其值為F。真假性：四個因素(3)謂詞變元個體域I={2，4，6，8}.考察?x
2、A(x)當A(e)表示e為偶數(shù)時，?xA(x)=T；當A(e)表示e為奇數(shù)時，?xA(x)=F；真假性：四個因素(4)命題變元個體域I={2，4，6，8}，A(e)表示e為偶數(shù).考察?xA(x)?P當P=T時，公式的值為真；當P=F時，公式的值為假。謂詞演算公式設(shè)?為任何一個謂詞演算公式，其中自由變元為x1，x2，…，xn；謂詞變元為X1，X2，…，Xm；命題變元為P1，P2，…，Pk。此時?可表示為：?(x1，…，xn；X1，…，Xm；P1，…，Pk)謂詞演算公式的解釋◇設(shè)個體域I解釋為常個體域I0；◇自由變元x1
3、，…，xn解釋為：I0中的個體a1，…，an；◇謂詞變元X1，…，Xm解釋為：I0上的謂詞A1，…，Am；◇命題變元P1，…，Pk解釋為：P10，…，Pk0，其中Pi0=T或F(i=1，2，…，k)。成真解釋、成假解釋給定公式?一個解釋：(I0；a1，…，an；A1，…，Am；P10，…，Pk0)公式?在該解釋下的值記為：?(a，A，P0)=?(a1，…，an；A1，…，Am；P10，…，Pk0)若?(a，A，P0)=T，則稱(I0；a；A；P0)為成真解釋；若?(a，A，P0)=F，則稱(I0；a；A；P0)為成假
4、解釋。含有量詞的謂詞演算公式設(shè)個體域I中所有實體變元為a1，a2，…，an，則有：?x?(x)=?(a1)??(a2)?…??(an)?x?(x)=?(a1)??(a2)?…??(an)含有量詞的謂詞演算公式的真假性?x?(x)為真?個體域I中的每一個個體均使得?取為真?x?(x)為真?個體域I中有一個個體使得?取為真例在給定解釋下，求?x(F(x)?G(x,a))給定解釋①I＝{2,3};②I中特定元素a=2；③函數(shù)為f(2)=3,f(3)=2;④謂詞F(x)為F(2)=0,F(3)=1G(x,y)為G(2,2)=
5、G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)為L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0解：原式=(F(2)?G(2,a))?(F(3)?G(3,a))=(0?0)?(1?0)=0?0=0例在給定解釋下，求?x(F(f(x))?G(x,f(x)))給定解釋①I＝{2,3};②I中特定元素a=2；③函數(shù)為f(2)=3,f(3)=2;④謂詞F(x)為F(2)=0,F(3)=1G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)為L(2,2)=L(3,
6、3)=1,L(2,3)=L(3,2)=0解：原式=(F(f(2))?G(2,f(2)))?(F(f(3))?G(3,f(3)))=(F(3)?G(2,3))?(F(2)?G(3,2))=(1?0)?(0?0)=0?0=0例在給定解釋下，求?x?yL(x,y)給定解釋①I＝{2,3};②I中特定元素a=2；③函數(shù)為f(2)=3,f(3)=2;④謂詞F(x)為F(2)=0,F(3)=1G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)為L(2,2)=L(3,3)=1,L(2,3)=L
7、(3,2)=0解：原式=(?yL(2,y))?(?yL(3,y))=(L(2,2)?L(2,3))?(L(3,2)?L(3,3))=(1?0)?(0?1)=1?1=1例在給定解釋下，求?y?xL(x,y)給定解釋①I＝{2,3};②I中特定元素a=2；③函數(shù)為f(2)=3,f(3)=2;④謂詞F(x)為F(2)=0,F(3)=1G(x,y)為G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1L(x,y)為L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0解：原式=(?xL(x,2))?(?xL
8、(x,3))=(L(2,2)?L(3,2))?(L(2,3)?L(3,3))=(1?0)?(0?1)=0?0=0量詞指導(dǎo)變元次序不能隨意例(p31)已知?x?y((X(x，y)?Y(z))?Z(x，y))試求公式在解釋(I；z；X(e1，e2)，Y(e)，Z(e1，e2))=({1，2，3，4}；2；e1?e2；e為偶數(shù)；e1?e2)之下的值。
