1、1上节课内容u谓词公式的符号化u谓词演算的合式公式u自由出现和约束出现u约束 变元的 换名 规则u自由 变元的 代入 规则2第 3讲 永真性和可满足性 谓词公式的赋值 可满足性 代换实例 等价式3/663.4.1 真假性四个因素(1) 个体域(2) 自由变元(3) 谓词变元(4) 命题变元xA(x) A(y) P4/66(1) 个体域例 设 A(e)表示 e为偶数,考察 xA(x) 当个体域 I为 1,2,3时,公式的值为假; 当个体域 I为 2,4,6时,公式的值为真 。5/66(2) 自由变元例 设 A(e)表示 e为偶数,考察 A(y) 当 y取 1时,其值为 F; 当 y取 2时,其值
2、为 T。6/66(3) 谓词变元例 个体域 I=2, 4. 考察 xA(x) 当 A(e)表示 e为偶数时, xA(x)=T; 当 A(e)表示 e为奇数时, xA(x)=F;7/66(4) 命题变元例 个体域 I=2, 4, A(e)表示 e为偶数 .考察xA(x)P 当 P=T 时,公式的值为真; 当 P=F 时,公式的值为假。8/66谓词演算公式设 为任何一个谓词演算公式,其中自由变元为 x1, x2, , xn;谓词变元为 X1, X2, , Xm;命题变元为 P1, P2, , Pk。此时 可表示为:(x1, , xn; X1, , Xm; P1, , Pk)9/66谓词演算公式的解
3、释 设个体域 I解释为常个体域 I0; 自由变元 x1, , xn解释为:I0中的个体 a1, , an; 谓词变元 X1, , Xm解释为:I0上的谓词 A1, , Am; 命题变元 P1, , Pk解释为:P10, , Pk0,其中 Pi0=T或 F(i=1, 2, , k)。10/66成真解释、成假解释给定公式 一个解释:(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)为 成假解释 。