§2 谓词公式语义解释 个体变元，谓词，函数词和个体常元 需要逐层解决.

Presentation on theme: "§2 谓词公式语义解释 个体变元，谓词，函数词和个体常元 需要逐层解决."— Presentation transcript:

1 §2 谓词公式语义解释 个体变元，谓词，函数词和个体常元 需要逐层解决

2 一、P(Y)的解释域 P(Y)的解释域是一个四元组(U,1,2,3)，其中： (1)U是非空集，称为论域。 (2)1是C→U的函数。 (3)2是P(Y)上的函数词集合到U上运算集的函数，使得2(fni)=f'ni，这里f'ni是U上的n元运算。 (4)3是P(Y)上的谓词集合到U上关系集的函数，使得3(Rni)=R'ni，这里R'ni是U上的n元关系。

3 解释域(U, 1,2,3)简记为U， 在给定解释域U后，P(Y)中只涉及闭项的原子公式就可视作为关于U上的命题。它不需要经过变元的指派就可以确定命题的真假值。

4 例：设P(Y)中的个体常元集C={c1,c2}，函数词集合T(1)=，谓词集合R={R21} ，P(Y)的解释域现定义为：U={2，3}，1(c1)=c'1=2，1(c2)=c'2=3，3 (R21)= R'21，这里R'21表示“小于”关系。 对于P(Y)中只含有闭项的原子公式p=R21(c1,c2)，在此解释域下，p解释为“2与3是小于关系”，是真命题。 若把解释域中关系的解释R'21修改为“相等”关系，则p解释为“2与3是相等关系”，则是假命题。

5 有了解释域，就可以对只含有闭项的原子公式讨论其真假值，但由于对个体变元并没有赋值，因此一般的原子公式还是无法确定其真假值。
下面就必须考虑对个体变元的赋值 由于项与变元有密切联系:由变元集和常元集生成(自由T(1)-代数)

6 二、变元的指派和项解释 定理21.1:设U为P(Y)的一个解释域，0为X→U的映射，则0可唯一扩张为I→U的同态映射，使得(ci)=c'i。这里c'i为U中的元素 为I→U的同态映射，对任意的fniTn和t1,,tnI，有 (fni(t1,,tn))= f'ni((t1),,(tn)), 这里f'ni为U中第i个n元运算。 定义21.9:X→U的映射0称为个体变元的指派，I→U的同态映射称为项解释。

7 例：P(Y)中的个体常元集C=，函数词集合为{f11,f21,f22}，谓词集合R={R21}，P(Y)的解释域定义为：U={0,1,2,…,n,…}；2(f11)=f'11，使得f'11(n)=n+1；2(f21)=f'21；使得f'21(i,j)=i+j，这里i,jU；2(f22)=f'22，使得f'22(i,j)=i×j，i,jU; 3(R21)=R'21，使得R'21表示“相等”关系。 p=R21(f21(x1,x2),f22(x3,f11(x4)))， 变元指派为0:X→U，使得0(x1)=5, 0(x2)=6, 0(x3)=7,0(x4)=8，则p解释为“5+6=7×(8+1)”， 是假命题。 把变元指派修改为‘0:X→U,使得 '0(x1)=6, ' 0(x2)=8,'0(x3)=7,'0(x4)=1， 则p就解释为“6+8=7×(1+1)”， 是真命题。

8 三、P(Y)的赋值 首先引进两个记号：对给定解释域U和项解释的原子公式集Y记为YU,,而谓词公式集P(Y)则相应记为P(YU,).

9 定义21.10:谓词公式的赋值函数v:P(YU,)→Z2分三步(a),(b)和(ck)，定义如下:
(a)对于原子公式p=Rni(t1,…,tn)YU,定义： (b)v是{F,→}-代数的同态。即，v(F)=0 对任何p,qP(YU,)，有v(p→q)= v(p)→v(q)。

10 p=x>3与q=x x>3是不同的
设Pk(YU,)={p|pP(YU,),d(p)k},于是P(YU,)= 引理21.1:设v0为YU,→Z2的映射，则v0可唯一扩张为P0(YU,)→Z2的同态映射v'0,这里的同态是指关于{F,→}的同态。 如果取某个新变量x'X∪C，当无论怎样指派 x'，q(x') 都为真，则可认为x q(x)为真。

11 v(p→q)=v(p)→v(q)=1+v(p)+v(p)v(q)
v(p)=v(p→F)=1+v(p)； v(pq)=v(p→q)=v(p)+v(q)+v(p)v(q) v(pq)=v((pq))=v(p)v(q); v(pq)=v((p→q)(q→p)) =1+v(p)+v(q) v(xp)=v(xp)=1+v(xp)

12 定义21.11:设pP(Y)，若在解释域U和项解释下，有v(p)=1，则称p在解释域U和下取值为真。若在某解释域U下，对任一项解释，p的取值总为真，则称p在解释域 U下是有效的。若对任一解释域U和任一项解释，p都是有效的，则称p为有效式，也称为重言式。

13 四、语义推论 定义21.12:设AP(Y)，pP(Y)，v(A)={v(q)|qA}，若不存在一个使得v(A){1}而v(p)=0的解释域和项解释，则称p是假设集A的后件，或称A语义蕴含p，记为A╞p，用Con(A)表示A的后件全体，即Con(A)={pP(Y)|A╞p}。 若╞p，则p就是重言式，简记为╞p。 ACon(A) 例：证明：{x(p(x)→q(x))}╞xp(x)→xq(x)

14 例：证明：{x(p(x)→q(x))}╞xp(x)→xq(x)
证明:若不成立,则存在解释域U和项解释,使得v(x(p(x)→q(x)))=1,但 v(xp(x)→xq(x))=0 由此导出矛盾 说明:v(xp(x))=1,表示对x'任意的指派,都有v(p(x'))=1 v(xp(x))=0表示存在一个对x‘的指派,使得在此指派下有v(p(x'))=0

15 例: 下述结论是否成立:{xp(x)}╞p(x)
不正确 关键是找到解释域U和项解释,使得 v(xp(x))=1,但v(p(x))=0 根据x的定义,即要求v(xp(x))=1 而v(p(x))=0

16 作业:P423 12(4)(5), 13,14 期中成绩说明：85分及以上：10人 80到84：9人 75到79：11人
60到74：30人 人 50到59：14人 人 40到49：11人 40以下：7人 以下没有成绩，认领？ ， ， ， ， ， ， ， ，