《离散数学 教学课件 ppt 作者 赵一鸣 阚海斌 吴永辉 dshu26n》由会员分享，可在线阅读，更多相关《离散数学 教学课件 ppt 作者 赵一鸣 阚海斌 吴永辉 dshu26n（16页珍藏版）》请在金锄头文库上搜索。
1、2 谓词公式语义解释,个体变元，谓词，函数词和个体常元 需要逐层解决,一、P(Y)的解释域 P(Y)的解释域是一个四元组(U,1,2,3)，其中： (1)U是非空集，称为论域。 (2)1是CU的函数。 (3)2是P(Y)上的函数词集合到U上运算集的函数，使得2(fni)=fni，这里fni是U上的n元运算。 (4)3是P(Y)上的谓词集合到U上关系集的函数，使得3(Rni)=Rni，这里Rni是U上的n元关系。,解释域(U, 1,2,3)简记为U， 在给定解释域U后，P(Y)中只涉及闭项的原子公式就可视作为关于U上的命题。它不需要经过变元的指派就可以确定命题的真假值。,例：设P(Y)中的个体常
2、元集C=c1,c2，函数词集合T(1)=，谓词集合R=R21 ，P(Y)的解释域现定义为：U=2，3，1(c1)=c1=2，1(c2)=c2=3，3 (R21)= R21，这里R21表示“小于”关系。 对于P(Y)中只含有闭项的原子公式p=R21(c1,c2)，在此解释域下，p解释为“2与3是小于关系”，是真命题。 若把解释域中关系的解释R21修改为“相等”关系，则p解释为“2与3是相等关系”，则是假命题。,有了解释域，就可以对只含有闭项的原子公式讨论其真假值，但由于对个体变元并没有赋值，因此一般的原子公式还是无法确定其真假值。 下面就必须考虑对个体变元的赋值 由于项与变元有密切联系:由变元集
3、和常元集生成(自由T(1)-代数),二、变元的指派和项解释 定理19.1:设U为P(Y)的一个解释域，0为XU的映射，则0可唯一扩张为IU的同态映射，使得(ci)=ci。这里ci为U中的元素 为IU的同态映射，对任意的fniTn和t1,tnI，有 (fni(t1,tn)= fni(t1),(tn), 这里fni为U中第i个n元运算。 定义19.9:XU的映射0称为个体变元的指派，IU的同态映射称为项解释。,例：P(Y)中的个体常元集C=，函数词集合为f11,f21,f22，谓词集合R=R21，P(Y)的解释域定义为：U=0,1,2,n,；2(f11)=f11，使得f11(n)=n+1；2(f2
4、1)=f21；使得f21(i,j)=i+j，这里i,jU；2(f22)=f22，使得f22(i,j)=ij，i,jU; 3(R21)=R21，使得R21表示“相等”关系。 p=R21(f21(x1,x2),f22(x3,f11(x4)， 变元指派为0:XU，使得0(x1)=5, 0(x2)=6, 0(x3)=7,0(x4)=8，则p解释为“5+6=7(8+1)”， 是假命题。 把变元指派修改为0:XU,使得 0(x1)=6, 0(x2)=8,0(x3)=7,0(x4)=1， 则p就解释为“6+8=7(1+1)”， 是真命题。,三、P(Y)的赋值 首先引进两个记号：对给定解释域U和项解释的原子公
5、式集Y记为YU,而谓词公式集P(Y)则相应记为P(YU,).,定义19.10:谓词公式的赋值函数v:P(YU,)Z2分三步(a),(b)和(ck)，定义如下: (a)对于原子公式p=Rni(t1,tn)YU,定义：,(b)v是F,-代数的同态。即，v(F)=0 对任何p,qP(YU,)，有v(pq)= v(p)v(q)。,p=x3与q=x x3是不同的 设Pk(YU,)=p|pP(YU,),d(p)k,于是P(YU,)=,引理19.1:设v0为YU,Z2的映射，则v0可唯一扩张为P0(YU,)Z2的同态映射v0,这里的同态是指关于F,的同态。 如果取某个新变量xXC，当无论怎样指派 x，q(x
6、) 都为真，则可认为x q(x)为真。,v(pq)=v(p)v(q)=1+v(p)+v(p)v(q) v(p)=v(pF)=1+v(p)； v(pq)=v(pq)=v(p)+v(q)+v(p)v(q) v(pq)=v(pq)=v(p)v(q); v(pq)=v(pq)(qp) =1+v(p)+v(q) v(xp)=v(xp)=1+v(xp),定义19.11:设pP(Y)，若在解释域U和项解释下，有v(p)=1，则称p在解释域U和下取值为真。若在某解释域U下，对任一项解释，p的取值总为真，则称p在解释域 U下是有效的。若对任一解释域U和任一项解释，p都是有效的，则称p为有效式，也称为重言式。,四
7、、语义推论 定义19.12:设AP(Y)，pP(Y)，v(A)=v(q)|qA，若不存在一个使得v(A)1而v(p)=0的解释域和项解释，则称p是假设集A的后件，或称A语义蕴含p，记为Ap，用Con(A)表示A的后件全体，即Con(A)=pP(Y)|Ap。 若p，则p就是重言式，简记为p。 ACon(A) 例：证明：x(p(x)q(x)xp(x)xq(x),例：证明：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,例: 下述结论是否成立:xp(x)p(x) 不正确 关键是找到解释域U和项解释,使得 v(xp(x)=1,但v(p(x)=0 根据x的定义,即要求v(xp(x)=1 而v(p(x)=0,作业:P257 12(4)(5), 13,14,
