离散数学第三章谓词演算基础-永真性和可满足性课件.ppt

《离散数学第三章谓词演算基础-永真性和可满足性课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章谓词演算基础3.1谓词与个体3.2函数与量词3.3自由变元和约束变元3.4永真性和可满足性3.4.1真假性3.4.2同真假性、永真性和可满足性3.4.3范式3.5唯一性量词与摹状词真假性：四个因素(1)个体域设A(e)表示e为偶数，考察xA(x)当个体域I为{1，2，3}时，公式的值为假；当个体域I为{2，4，6}时，公式的值为真。真假性：四个因素(2)自由变元设A(e)表示e为偶数，考察A(x)当x取2时，其值为T；当x取为3时，其值为F。真假性：四个因素(3)谓词变元个体域I={2，4，6，8}.考察x

2、A(x)当A(e)表示e为偶数时，xA(x)=T；当A(e)表示e为奇数时，xA(x)=F；真假性：四个因素(4)命题变元个体域I={2，4，6，8}，A(e)表示e为偶数.考察xA(x)P当P=T时，公式的值为真；当P=F时，公式的值为假。谓词演算公式设为任何一个谓词演算公式，其中自由变元为x1，x2，…，xn；谓词变元为X1，X2，…，Xm；命题变元为P1，P2，…，Pk。此时可表示为：(x1，…，xn；X1，…，Xm；P1，…，Pk)谓词演算公式的解释◇设个体域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、解释。含有量词的谓词演算公式设个体域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；③函数为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；③函数为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；③函数为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；③函数为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量词指导变元次序不能随意例(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为偶数；e1e2)之下的值。