§2谓词公式语义解释 ■个体变元,谓词,函数词和个体常元 需要逐层解决
§2 谓词公式语义解释 个体变元，谓词，函数词和个体常元 需要逐层解决
一、P(Y)的解释域 P(Y)的解释域是一个四元组(Up1293) 其中: (1)U是非空集,称为论域。 (2)q1是CU的函数。 n(3)q2是P(Y)上的函数词集合到U上运算 集的函数,使得φ2(E)=fn这里fn是U 上的n元运算。 (4)3是P(Y)上的谓词集合到U上关系集 的函数,使得q3(R)=R'm,这里R'n是U 上的n元关系
一、P(Y)的解释域 P(Y)的解释域是一个四元组(U,1 ,2 ,3 )， 其中： (1)U是非空集，称为论域。 (2)1是C→U的函数。 (3)2是P(Y)上的函数词集合到U上运算 集的函数，使得2 (fn i )=f'n i ，这里f'n i是U 上的n元运算。 (4)3是P(Y)上的谓词集合到U上关系集 的函数，使得3 (Rn i )=R'n i ，这里R'n i是U 上的n元关系
解释域(U,q1293)简记为U, 在给定解释域U后,P(Y中只涉及闭项的 原子公式就可视作为关于U上的命题。它 不需要经过变元的指派就可以确定命题 的真假值
解释域(U, 1 ,2 ,3 )简记为U， 在给定解释域U后，P(Y)中只涉及闭项的 原子公式就可视作为关于U上的命题。它 不需要经过变元的指派就可以确定命题 的真假值
例:设P(Y中的个体常元集C={c1,C2}, 函数词集合T=,谓词集合R={R2}, P(Y)的解释域现定义为:U={2,3}, q1(c1)=c'1=2,φ1(c2)=C2=3,φ3(R2)= R'2,这里R'2表示“小于”关系。 对于P(Y)中只含有闭项的原子公式 R 2(c 2),在此解释域下,p解释为 “2与3是小于关系”,是真命题。 若把解释域中关系的解释R2修改为“相 等”关系,则p解释为“2与3是相等关 系”,则是假命题
例：设P(Y)中的个体常元集C={c1 ,c2 }， 函数词集合T(1)=，谓词集合R={R2 1 } ， P(Y)的解释域现定义为： U={2，3}， 1 (c1 )=c'1 =2，1 (c2 )=c'2 =3，3 (R2 1 )= R'2 1 ，这里R'2 1表示“小于”关系。 对 于 P(Y) 中只含有闭项的原子公式 p=R2 1 (c1 ,c2 )，在此解释域下，p解释为 “2与3是小于关系” ，是真命题。 若把解释域中关系的解释R'2 1修改为“相 等”关系，则p解释为“2与3是相等关 系” ，则是假命题
■有了解释域,就可以对只含有闭项的原子 公式讨论其真假值,但由于对个体变元并 没有赋值,因此一般的原子公式还是无法 确定其真假值。 下面就必须考虑对个体变元的赋值 由于项与变元有密切联系:由变元集和常 元集生成(自由T)-代数)
有了解释域，就可以对只含有闭项的原子 公式讨论其真假值，但由于对个体变元并 没有赋值，因此一般的原子公式还是无法 确定其真假值。 下面就必须考虑对个体变元的赋值 由于项与变元有密切联系:由变元集和常 元集生成(自由T(1)-代数)
二、变元的指派和项解释 定理211:设U为P(Y)的一个解释域,q为 X→U的映射,则q可唯一扩张为I→U的 同态映射φ,使得φ(c;)=c;o这里c为U中 的元素 φ为I→U的同态映射,对任意的f∈T和 t∈I,有 φ(fn(t1,…,tn)=fn(φ(t1),…,g(t1)), 这里f为U中第个m元运算。 定义219X→U的映射q称为个体变元的 指派,IU的同态映射φ称为项解释
二、变元的指派和项解释 定理21.1:设U为P(Y)的一个解释域，0为 X→U的映射，则0可唯一扩张为I→U的 同态映射，使得(ci )=c'i。这里c'i为U中 的元素 为I→U的同态映射，对任意的fn iTn和 t1 ,,tnI，有 (fn i (t1 ,,tn ))= f'n i ((t1 ),,(tn )), 这里f'n i为U中第i个n元运算。 定义21.9:X→U的映射0称为个体变元的 指派，I→U的同态映射称为项解释
例:P(Y)中的个体常元集C=,函数词集合为 {f1,f,f2},谓词集合R={R2},P(Y)的解释域定义为: 0,1,2,,n,…};q2(f1)=f1,使得 1(n=n+1 q2(f2)=f2l;使得f2(ij)=计+j,这里i∈U;φ4(2)=f2 使得f2(i)=×j,i∈U;q3R2)=R2,使得R'2表示 “相等”关系。 p=R2(2(x1,x2),f2(x3,f1(x4)) 变元指派为φo:X→U,使得φo(x1)=5,q0(x2)=6 q(x3)=70(x4)=8,则p解释为“5+6-7×(8+1)” 是假命题。 把变元指派修改为φ:X→U,使得 q'0(x1)=6,90(x2)=8,0(x3)=7,qpo(x4=1 则p就解释为“6+8=7×(1+1)” 是真命题
例 ： P(Y) 中 的 个 体 常 元 集 C=， 函 数 词 集 合 为 {f1 1 ,f2 1 ,f2 2}，谓词集合R={R2 1}，P(Y)的解释域定义为： U={0,1,2,…,n,…}；2 (f1 1 )=f'1 1 ， 使 得 f'1 1 (n)=n+1； 2 (f2 1 )=f'2 1；使得f'2 1 (i,j)=i+j，这里i,jU；2 (f2 2 )=f'2 2 ， 使得f'2 2 (i,j)=i×j，i,jU; 3 (R2 1 )=R'2 1 ，使得R'2 1表示 “相等”关系。 p=R2 1 (f2 1 (x1 ,x2 ),f2 2 (x3 ,f1 1 (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)”， 是真命题
、P(Y)的赋值 ■首先引进两个记号:对给定解释域U和项 解释q的原子公式集Y记为Y,而谓词公 式集P(Y)则相应记为P(Y9)
三、P(Y)的赋值 首先引进两个记号：对给定解释域U和项 解释的原子公式集Y记为YU, ,而谓词公 式集P(Y)则相应记为P(YU, )
n定义21.10:谓词公式的应值函数 v:P(Y09)Z2分三步(ab和(c1),定义如 下 a(a)对于原子公式p-Rn(t,…,)Y定义: v(P)= (qp(41)2…q(tn)∈Rn 0否则 (b)yv是{F,}-代数的同态。即,v(F)=0 对任何p2q∈P(Y9),有v(p>q) (p)→v(q)
定义21.10:谓词公式的赋值函数 v:P(YU, )→Z2分三步(a),(b)和(ck )，定义如 下: (a)对于原子公式p=Rn i (t1 ,…,tn )YU,定义： = 0 否则 1 ( ( ), ( )) ' ( ) 1 i n R n t t v p •(b)v是{F,→}-代数的同态。即，v(F)=0 •对任何 p,qP(YU, )， 有 v(p→q)= v(p)→v(q)
p=x>3与q=xx>3是不同的 设P(Y9)={plp∈P(Y9),d(p)≤k},于是 POYUP=UP(YU, o) k≥0 引理211:设v为YZ2的映射,则v可 唯一扩张为PQY9)Z2的同态映射v,这里 的同态是指关于{F,}的同态。 如果取某个新变量 XEXUC,当无论怎样 指派x',q(x)都为真,则可认为xq(x)为 真
p=x>3与q=x x>3是不同的 设Pk (YU, )={p|pP(YU, ),d(p)k},于是 P(YU, )= 0 , ( ) k Pk Y U •引理21.1:设v0为YU,→Z2的映射，则v0可 唯一扩张为P0 (YU, )→Z2的同态映射v' 0 ,这里 的同态是指关于{F,→}的同态。 •如果取某个新变量x'X∪C，当无论怎样 指派 x'，q(x') 都为真，则可认为x q(x)为 真