第十九章 泛代数 - Fudan University

1、 设设a是任一是任一t-代数，代数，(g, )是按定理是按定理19.1的构的构造方法生成的造方法生成的xn=x1,x2,xn上的自由上的自由t-代代数，数， 是是xng的映射，且的映射，且 (xi)=xi。 xn到到a中的映射中的映射 , (xi)=ai，a1,a2,an为为a 中中的任何元素的任何元素(允许允许ai=aj,i j)。 由自由代数定义，存在唯一的同态映射由自由代数定义，存在唯一的同态映射 :ga，使得使得 = . (xi)= ( (xi)=(xi)= (xi)=ai，(i=1,n)，当当w g时，时， (w)由由a中元素中元素a1,a2,an唯一确唯一确定。定。 定义函数定义函

2、数fa:ana，使得使得fa (a1,a2,an) = (w)。简写为简写为f (a1,a2,an) 特别，当特别，当 a=g，ai=xi(i=1,n)时，因时，因 (xi)=xi，故故 是恒等映射，是恒等映射， 有有 (w)=w， 定义定义19.7:变量变量x1,x2,xn上的上的t字字(t-word)，就是自由生成集就是自由生成集xn =x1,x2,xn上的自由上的自由t-代数代数g的一个元素。的一个元素。 定义定义19.8:t-代数代数a的元素的元素a1,a2,an上的上的字字(word)，就是元素就是元素wa(a1,a2,an) a，这里这里w是变量是变量x1,x2,xn上的一个上的一

3、个t-字。字。 定义定义19.9:一个一个t-代数变量代数变量(t-algebra variable)是一个自由是一个自由t-代数的自由生成代数的自由生成集的元素。集的元素。 研究真假值和形式证明之间的关系研究真假值和形式证明之间的关系 构造一个简单的数学推理模型构造一个简单的数学推理模型命题逻命题逻辑辑 构造较为精细的模型构造较为精细的模型 一阶谓词逻辑一阶谓词逻辑2 命题代数命题代数 定义定义20.1:设设t=f,，这里这里ar(f)=0，ar()=2。称任何这样的称任何这样的t-代数为代数为命题代命题代数数。 例例:对于对于z2=0,1，构造构造t-代数。代数。 令令fz2:z20=z2

4、, fz2()=0, z2:z22z2, z2(m,n)=1+m(1+n) “+,”是模是模2加法和乘法运算加法和乘法运算. 构成了一个命题代数。构成了一个命题代数。ab简写为简写为ab。 由可列集由可列集x=x1,xn,生成的自由生成的自由f,代数代数p(x)，这也是命题代数。这也是命题代数。p0=f,x1,xn, p1=(,ai,aj)|ai,aj p0 =(,f,f)(,f,xi)|xi x (,xi,f)|xi x(,xi,xj)|xi,xj xp2=(,ai,aj)|ai p0,aj p1(,ai,aj)|ai p1 , aj p0 p(x)为：为：p(x)=n nn nn np p

5、按类型按类型t=(f,ar)定义定义p(x)上的运算上的运算:把把0元运算元运算fp(x)规定为规定为p(x)中的特定元素中的特定元素f二元运算二元运算p(x)定义为定义为:p(x)(p,q)=(,p,q)，构成了构成了x上上t-代数代数p(x),fp(x),p(x),即命题代数即命题代数自由代数自由代数 定义定义20.2:设设x是可列集，是可列集，x上的自由上的自由t（ =(f,ar) ）-代数称为代数称为x上关于命题上关于命题演算的命题代数演算的命题代数，记为，记为p(x)，并称并称x为为命题变量集命题变量集，x中的元素称为中的元素称为命题变元命题变元，p(x)中的每个元素称为命题演算的中

6、的每个元素称为命题演算的合式合式公式公式，简记为，简记为wff，仅由一个命题变元符仅由一个命题变元符组成的合式公式称为组成的合式公式称为原子公式原子公式，所有原，所有原子公式全体称为子公式全体称为原子公式集原子公式集。 在任何命题代数中，可利用在任何命题代数中，可利用f和和定义一定义一元运算元运算 和其它二元运算和其它二元运算 , ,，定义为：，定义为：)()()(p)(p)(ppdefpqqpqpqqpqqpfdefdefdef ( p) ( q)可简写为可简写为 pq。 运算的优先次序排列为：运算的优先次序排列为： 在相同优先级的运算之间，先左后右。在相同优先级的运算之间，先左后右。3 命

7、题演算的语义命题演算的语义 一、一、p(x)的赋值的赋值 定义定义20.3:设设p(x)是是x上关于命题演算的命上关于命题演算的命题代数，称题代数，称p(x)z2的同态映射的同态映射v为为p(x)的的赋值赋值。对于任意的。对于任意的p p(x)，若，若v(p)=1则称则称p按赋值按赋值v为真为真，若，若v(p)=0则称则称p按赋值按赋值v为为假假。 定理定理20.1:设设a为命题代数，为命题代数，v0为为xa的映的映射，则射，则v0可唯一扩张为可唯一扩张为p(x)a的同态映的同态映射射v。 定义定义20.4:设设v0为为xz2的映射，称的映射，称v0为命为命题变元的题变元的一个指派一个指派。v

8、(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(p q)=v( pq)=v( p)v(q)=1+(1+v(p)(1+v(q) =v(p)+v(q)+v(p)v(q)；v(p q)=v( ( pq)=1+v( pq)=v(p)v(q);v(pq)=v(pq) (qp)=1+v(p)+v(q) 二、二、p(x)中元素的解释和真值表中元素的解释和真值表 把把p(x)中的每个元素中的每个元素(即命题演算的合式即命题演算的合式公式公式)解释为可判断真

9、假的语句解释为可判断真假的语句 原子公式集中的每个原子公式原子公式集中的每个原子公式(命题变元命题变元x)表示任意的简单命题表示任意的简单命题(即原子命题即原子命题) p(x)中的其它元素表示复合命题。中的其它元素表示复合命题。 对任意对任意p p(x)和给定的赋值和给定的赋值v:p(x)z2，若若v(p)=1，则说，则说p 所表示的命题为真，简所表示的命题为真，简称称p为真；若为真；若v(p)=0，则说，则说p所表示的命所表示的命题为假，简称题为假，简称p为假。为假。 在在p(x)上所定义的一元和二元运算上所定义的一元和二元运算 , , , ,可可分别解释为命题联结词分别解释为命题联结词“非

10、非”，“合取合取”，“析析取取”，“蕴含蕴含”和和“等价等价”。 列出下述表格列出下述表格(在表中在表中p表示表示v(p)：v v( (p p) ) v v( ( p p) ) 0 0 1 1 1 0 v v( (p p) ) v v( (q q) ) v v( (p pq q) ) 0 0 0 1 0 0 1 1 1 1 0 0 1 1 1 1 v v( (p p) ) v v( (q q) ) v v( (p p q q) ) 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 v v( (p p) ) v v( (q q) ) v v( (p p q q) ) 0 0 0 0

11、 0 0 1 0 1 1 0 0 1 1 1 1 v v( (p p) ) v v( (q q) ) v v( (p pq q) ) 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 通过对通过对p(x)的解释的解释,命题代数命题代数p(x)所建所建立的形式系统就可立的形式系统就可以表示我们所熟悉以表示我们所熟悉的命题的命题. 对任意的对任意的v1,v2,vn z2,将将v1,v2,vn分别分别指派给指派给x1,x2,xn 由定理由定理20.1知此指派可唯一扩张为赋值知此指派可唯一扩张为赋值v:p(xn)z2, 此时对任意此时对任意p p(xn),都有确定的真值都有确定的真值v(

12、p) z2 由此定义由此定义n元真值函数元真值函数fp:z2nz2,使得使得fp(v1,v2,vn)=v(p). 定义定义20.5:函数函数f: z2nz2称为称为n元真值函元真值函数数 定义定义20.6:设设p p(x)，定义，定义p的的n元真值函数元真值函数fp:z2nz2为：为：fp=v(p)，称，称fp为为p的真值函数的真值函数。由由p的真值函数所建立的函数值表称为的真值函数所建立的函数值表称为p的的真值表真值表。 例例:写出合式公式写出合式公式(x1 x2)( x3x1)真值表 以后可简写为以后可简写为:(x1 x2 ) ( x3 x1) 0 0 0 1 1 0 0 0 0 0 0

13、1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 三、语言蕴含三、语言蕴含 定义定义20.7：设：设a p(x),q p(x)，若对所有，若对所有使得使得v(p)=1(对一切对一切p a)的赋值的赋值v，都有，都有v(q)=1，则称，则称q是假设集是假设集a的后件的后件，或称，或称a语义蕴含语义蕴含q，记为，记为aq，用，用con(a)表示表示a的后件全体，即的后件全体，即con(a)=p p(x)|ap。 注意：注意：a a是是p(

14、x)p(x)的子集，但的子集，但a a本身不是命本身不是命题公式。题公式。 由定义知，对于由定义知，对于a中的任意元素中的任意元素p，对所，对所有使得有使得a中元素的赋值为中元素的赋值为1的赋值的赋值v，都有，都有v(p)=1，因此，因此a con(a). 又因为不存在赋值又因为不存在赋值v使得使得v(f) 1，所以，所以对任意的对任意的p p(x)总有总有p con(f)。 即对任意即对任意q p(x)，有，有fq。 定义定义20.8:设设p p(x)，若对，若对p(x)的任意赋的任意赋值值v都有都有v(p)=1，则称，则称p是是有效的有效的，也称，也称为为重言式重言式。若对。若对p(x)的

15、任意赋值的任意赋值v都有都有v(p)=0，则称，则称p是是永假式永假式。 因此若因此若p，则，则p就是重言式，简记为就是重言式，简记为p 注意注意ap是命题逻辑元语言中的陈述句，是命题逻辑元语言中的陈述句，但它本身不是但它本身不是p(x)中的元素。中的元素。 例：例： ppq 例：例：x1(x2x3),x2x1x3 引理引理20.1:con 有如下性质：有如下性质： (i)a con(a) (ii)若若a1 a2，则，则con(a1) con(a2) (iii)con(con(a)=con(a) 定义定义20.9：设：设p,q p(x)，若对，若对p(x)的任的任意赋值意赋值v有有v(p)=v

16、(q)，则称，则称p,q等值等值。 定理定理20.2:下述结论是等价的。下述结论是等价的。(1)p,q等值。等值。(2)pq。(3)p,q有相同的真值函数和真值表。有相同的真值函数和真值表。 定理定理20.3:对任意对任意p,q,r p(x)有下述结论：有下述结论：(1)pp；(2) (p q)pq；(3) (p q)pq；(4) (p1 p2 pn)p1p2 pn(5) (p1 p2 pn)p1p2 pn 四、析取范式和合取范式四、析取范式和合取范式定义定义20.10:形式为形式为)(11jinjmiy 的合式公式称为的合式公式称为析取范式析取范式，形式为，形式为)(11jinjmiy的合式

17、公式称的合式公式称为为合取范式合取范式，这里，这里yij为某个命题变元为某个命题变元xk或其否定或其否定 xk。例：例：(x1 x2) ( x1 x2) (x1x2x3)是是析取范式，而析取范式，而 (x1x2) ( x1 x3)是是合取范式。合取范式。 定理定理20.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构造构造与该指派所对应的合式公式与该指派所对应的合式公式y1 y2 yn, 使得使得:0)(1)(iiiiixvxxvxy目标是目标是v(yi)=1 定义定义20.11:一个合式公式若不是永假式，一个合式公式若不是永假式，则用定理则用定理20.4