第十九章 泛代数优秀课件.ppt

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

1、第十九章 泛代数第1页，本讲稿共26页定义函数定义函数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的一个元素。的一个元素。第2页，本讲稿共26页定定义义19.8:T-代代数数A的的元元素素a1,a2,an上上的的字字(word)，就就是是元元素素wA(a1,a2,an)A，这里这

2、里w是变量是变量x1,x2,xn上的一个上的一个T-字。字。定定 义义 19.9:一一 个个 T-代代 数数 变变 量量(T-algebra variable)是是一一个个自自由由T-代代数数的的自自由由生生成成集集的元素。的元素。第3页，本讲稿共26页研究真假值和形式证明之间的关系研究真假值和形式证明之间的关系构造一个简单的数学推理模型构造一个简单的数学推理模型命题逻命题逻辑辑构造较为精细的模型构造较为精细的模型 一阶谓词逻辑一阶谓词逻辑第4页，本讲稿共26页2 命题代数命题代数定定 义义 20.1:设设 T=F,，这这 里里 ar(F)=0，ar()=2。称称任任何何这这样样的的T-代代数

3、数为为命命题题代代数数。例例:对于对于Z2=0,1，构造构造T-代数。代数。令令FZ2:Z20=Z2,FZ2()=0,Z2:Z22Z2,Z2(m,n)=1+m(1+n)“+,”是模是模2加法和乘法运算加法和乘法运算.构成了一个命题代数。构成了一个命题代数。ab简写为简写为ab。第5页，本讲稿共26页由由可可列列集集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

4、,aj P1(,ai,aj)|ai P1,aj P0P(X)为：为：P(X)=按类型按类型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),即命题代数即命题代数自由代数自由代数第6页，本讲稿共26页定定义义20.2:设设X是是可可列列集集，X上上的的自自由由T（=(F,ar)）-代代数数称称为为X上上关关于于命命题题演演算算的的命命题题代代数数，记记为为P(X)，并并称称X为为命命题题变变

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

6、的运算之间，先左后右。第9页，本讲稿共26页3 命题演算的语义命题演算的语义一、一、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。第10页，本讲稿共26页定义定义20.4:设设v0为为XZ2的映射，称的映

7、射，称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(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)第11页，本讲稿共26页二、二、P(X)中元素的解释和真值表中元素的解释和真值表把把P(X)中中的的每每个个元元素素(即即

8、命命题题演演算算的的合合式式公式公式)解释为可判断真假的语句解释为可判断真假的语句原原子子公公式式集集中中的的每每个个原原子子公公式式(命命题题变变元元x)表示任意的简单命题表示任意的简单命题(即原子命题即原子命题)P(X)中的其它元素表示复合命题。中的其它元素表示复合命题。对对任任意意p P(X)和和给给定定的的赋赋值值v:P(X)Z2，若若v(p)=1，则则说说p 所所表表示示的的命命题题为为真真，简简称称p为为真真；若若v(p)=0，则则说说p所所表表示示的的命题为假，简称命题为假，简称p为假。为假。第12页，本讲稿共26页在在P(X)上上所所定定义义的的一一元元和和二二元元运运算算,可

9、可分分别别解解释释为为命命题题联联结结词词“非非”，“合合取取”，“析析取取”，“蕴含蕴含”和和“等价等价”。列出下述表格列出下述表格(在表中在表中p表示表示v(p)：通过对通过对P(X)的解释的解释,命题代数命题代数P(X)所建所建立的形式系统就可以立的形式系统就可以表示我们所熟悉的命表示我们所熟悉的命题题.第13页，本讲稿共26页对对任任意意的的v1,v2,vn Z2,将将v1,v2,vn分分别别指指派给派给x1,x2,xn由由定定理理20.1知知此此指指派派可可唯唯一一扩扩张张为为赋赋值值v:P(Xn)Z2,此此时时对对任任意意p P(Xn),都都有有确确定定的的真真值值v(p)Z2由由

10、此此定定义义n元元真真值值函函数数fp:Z2nZ2,使使得得fp(v1,v2,vn)=v(p).定定义义20.5:函函数数f:Z2nZ2称称为为n元元真真值值函函数数第14页，本讲稿共26页定定 义义 20.6:设设p P(X)，定定义义p的的n元元 真真 值值 函函 数数fp:Z2nZ2为为：fp=v(p)，称称fp为为p的的真真值值函函数数。由由p的真值函数所建立的函数值表称为的真值函数所建立的函数值表称为p的真值表的真值表。例例:写出合式公式写出合式公式(x1 x2)(x3x1)真值表第15页，本讲稿共26页以后可简写为以后可简写为:第16页，本讲稿共26页三、语言蕴含三、语言蕴含定定义

11、义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(X)P(X)的的子子集集，但但A A本本身身不不是是命命题公式。题公式。由由定定义义知知，对对于于A中中的的任任意意元元素素p，对对所所有有使使得得A中中元元素素的的赋赋值值为为1的的赋赋值值v，都都有有v(p)=1，因此，因此A Con(A).第17页，本讲稿共

12、26页又又因因为为不不存存在在赋赋值值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)的的任任意意赋赋值值v都都有有v(p)=0，则称，则称p是是永假式永假式。因因此此若若p，则则p就就是是重重言言式式，简简记记为为p注注意意Ap是是命命题题逻逻辑辑元元语语言言中中的的陈陈述述句句，但它本身不是但它本身不是P(X)中的元素。中的元素。第18页，本讲稿共2

13、6页例：例：ppq例：例：x1(x2x3),x2x1x3第19页，本讲稿共26页引理引理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(q)，则称，则称p,q等值等值。第20页，本讲稿共26页定理定理20.2:下述结论是等价的。下述结论是等价的。(1)p,q等值。等值。(2)pq。(3)p,q有相同的真值函数和真值表。有相同的真值函数和真值表。定定理理20.3:对对任任意意p,q,r

14、 P(X)有有下下述述结结论：论：(1)pp；(2)(p q)pq；(3)(p q)pq；(4)(p1 p2 pn)p1p2 pn(5)(p1 p2 pn)p1p2 pn第21页，本讲稿共26页四、析取范式和合取范式四、析取范式和合取范式定义定义20.10:形式为形式为的合式公式称为的合式公式称为析取范式析取范式，形式为，形式为的合式公式称的合式公式称为为合合取取范范式式，这这里里yij为为某某个个命命题题变变元元xk或其否定或其否定 xk。例例：(x1 x2)(x1 x2)(x1x2x3)是是析析取取范范式式，而而(x1x2)(x1 x3)是合取范式。是合取范式。第22页，本讲稿共26页定定

15、理理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,使得使得:目标是目标是v(yi)=1第23页，本讲稿共26页定定义义20.11:一一个个合合式式公公式式若若不不是是

16、永永假假式式，则则用用定定理理20.4的的证证明明方方法法得得到到的的等等值值析析取取范式称为该合式公式的范式称为该合式公式的标准析取范式标准析取范式。推推论论20.1:每每个个非非重重言言式式必必等等值值于于一一个个合合取范式。取范式。定定义义20.12:一一个个合合式式公公式式若若不不是是重重言言式式，则则用用推推论论20.1的的证证明明方方法法得得到到的的等等值值合合取取范式称为该合式公式的范式称为该合式公式的标准合取范式标准合取范式。第24页，本讲稿共26页例例：求求与与(x1x2)(x3)等等值值的的标标准准析析取取范式和标准合取范式。范式和标准合取范式。第25页，本讲稿共26页作业作业:P400 5,6,7第26页，本讲稿共26页