第十九章 泛代数.ppt

《第十九章 泛代数.ppt》由会员分享，可在线阅读，更多相关《第十九章 泛代数.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、定义18.2:设X是可列集，X上的自由T-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。,在任何命题代数中，可利用F和定义一元运算和其它二元运算,，定义为：,(p)(q)可简写为pq。运算的优先次序排列为： 在相同优先级的运算之间，先左后右。,2 命题演算的语义,一、P(X)的赋值定义18.3:设P(X)是X上关于命题演算的命题代数，称P(X)Z2的同态映射v为P(X)的赋值。对于任意的pP(X)，若v(p)=1

2、则称p按赋值v为真，若v(p)=0则称p按赋值v为假。定理18.1:设A为命题代数，v0为XA的映射，则v0可唯一扩张为P(X)A的同态映射v。,定义18.4:设v0为XZ2的映射，称v0为命题变元的一个指派。v(pq)=v(p)v(q)=1+v(p)(1+v(q) =1+v(p)+v(p)v(q)；v(p)=v(pF)=v(p)v(F)=1+v(p)(1+v(F) =1+v(p)(1+0)=1+v(p)；v(pq)=v(pq)=v(p)v(q)=1+(1+v(p)(1+v(q) =v(p)+v(q)+v(p)v(q)；v(pq)=v(pq)=1+v(pq)=v(p)v(q);v(pq)=v(

3、pq)(qp)=1+v(p)+v(q),二、P(X)中元素的解释和真值表把P(X)中的每个元素(即命题演算的合式公式)解释为可判断真假的语句原子公式集中的每个原子公式(命题变元x)表示任意的简单命题(即原子命题)P(X)中的其它元素表示复合命题。对任意pP(X)和给定的赋值v:P(X)Z2，若v(p)=1，则说p 所表示的命题为真，简称p为真；若v(p)=0，则说p所表示的命题为假，简称p为假。,在P(X)上所定义的一元和二元运算, ,可分别解释为命题联结词“非”，“合取”，“析取”，“蕴含”和“等价”。列出下述表格(在表中p表示v(p)：,通过对P(X)的解释,命题代数P(X)所建立的形式系

4、统就可以表示我们所熟悉的命题.,对任意的v1,v2,vnZ2,将v1,v2,vn分别指派给x1,x2,xn由定理18.1知此指派可唯一扩张为赋值v:P(Xn)Z2,此时对任意pP(Xn),都有确定的真值v(p)Z2由此定义n元真值函数fp:Z2nZ2,使得fp(v1,v2,vn)=v(p).定义18.5:函数f: Z2nZ2称为n元真值函数,定义18.6:设pP(X)，定义p的n元真值函数fp:Z2nZ2为：fp=v(p)，称fp为p的真值函数。由p的真值函数所建立的函数值表称为p的真值表。例:写出合式公式(x1x2)(x3x1)真值表,以后可简写为:,三、语言蕴含定义18.7：设AP(X),

5、qP(X)，若对所有使得v(p)=1(对一切pA)的赋值v，都有v(q)=1，则称q是假设集A的后件，或称A语义蕴含q，记为Aq，用Con(A)表示A的后件全体，即Con(A)=pP(X)|Ap。注意：A是P(X)的子集，但A本身不是命题公式。由定义知，对于A中的任意元素p，对所有使得A中元素的赋值为1的赋值v，都有v(p)=1，因此ACon(A).,又因为不存在赋值v使得v(F)1，所以对任意的pP(X)总有pCon(F)。即对任意qP(X)，有Fq。定义18.8:设pP(X)，若对P(X)的任意赋值v都有v(p)=1，则称p是有效的，也称为重言式。若对P(X)的任意赋值v都有v(p)=0，

6、则称p是永假式。因此若p，则p就是重言式，简记为p注意Ap是命题逻辑元语言中的陈述句，但它本身不是P(X)中的元素。,例：ppq例：x1(x2x3),x2x1x3,引理18.1:Con 有如下性质：(i)ACon(A)(ii)若A1A2，则Con(A1) Con(A2)(iii)Con(Con(A)=Con(A)定义18.9：设p,qP(X)，若对P(X)的任意赋值v有v(p)=v(q)，则称p,q等值。,定理18.2:下述结论是等价的。(1)p,q等值。(2)pq。(3)p,q有相同的真值函数和真值表。定理18.3:对任意p,q,rP(X)有下述结论：(1)pp；(2)(pq)pq；(3)(

7、pq)pq；(4)(p1p2pn)p1p2pn(5)(p1p2pn)p1p2pn,四、析取范式和合取范式,定义18.10:形式为,的合式公式称为,析取范式，形式为,的合式公式称,为合取范式，这里yij为某个命题变元xk或其否定xk。例：(x1x2)(x1x2)(x1x2x3)是析取范式，而 (x1x2) (x1 x3)是合取范式。,定理18.4:任何命题合式公式(即P(X)中的元素)都有只含命题变元及,这三种运算的合式公式与该命题合式公式等值证明:对任意p=p(x1,x2,xn)P(Xn)1.对P(Xn)中任一赋值v恒有v(p(x1,x2,xn) =02.存在P(Xn)中的赋值v使得v(p(x1,x2,xn) =1构造与该指派所对应的合式公式y1y2 yn, 使得:,目标是v(yi)=1,定义18.11:一个合式公式若不是永假式，则用定理18.4的证明方法得到的等值析取范式称为该合式公式的标准析取范式。推论18.1:每个非重言式必等值于一个合取范式。定义18.12:一个合式公式若不是重言式，则用推论18.1的证明方法得到的等值合取范式称为该合式公式的标准合取范式。,例：求与(x1x2)(x3)等值的标准析取范式和标准合取范式。,作业: P241 5,6,7,