设A是任一T代数,(G,o)是按定理19的构 造方法生成的Xn={x12x2…,xn上的自由T代 数,是Xn→G的映射,且σ(x)=x;o X到A中的映射vτ(x)=a1,a1a2,,1an为A中 的任何元素允许a=a1,1j 由自由代数定义,存在唯一的同态映射 q:G→A,使得 q(x)=q(o(x)=qo(x)=τ(x;)=a;(i=1,,n) 当w∈G时,q(w)由A中元素a,a2…,an唯一确 定
设A是任一T-代数,(G,)是按定理19.1的构 造方法生成的Xn={x1 ,x2 ,…xn }上的自由T-代 数,是Xn→G的映射,且(xi )=xi。 Xn到A中的映射,(xi )=ai,a1 ,a2 ,…an为A 中 的任何元素(允许ai=aj ,ij)。 由自由代数定义,存在唯一的同态映射 :G→A,使得=. ( xi )=((xi ))=(xi )=(xi )=ai,(i=1,…,n), 当wG时,(w)由A中元素a1 ,a2 ,…an唯一确 定
定义函数f:A→A,使得f(a1;a2,an) q(w)。简写为f(a1a2,an) 特别,当A=G,a=x(i=1,,n)时,因 φ(x)=x;,故q是恒等映射, 有g(w)=w 定义197:变量x1,x2xn上的T字(T word),就是自由生成集Xn={x1,x2yxn} 上的自由T代数G的一个元素
定义函数fA:An→A,使得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字(Tword),就是自由生成集Xn ={x1 ,x2 ,…xn } 上的自由T-代数G的一个元素
定义19.8:T-代数A的元素a1a2an上的 字(word),就是元素wA(a1a2,an)∈A, 这里w是变量x1,x2,,xn上的一个T字。 定义19.9:一个T代数变量(T- algebra variable)是一个自由T-代数的自由生成 集的元素
定义19.8:T-代数A的元素a1 ,a2 ,…an上的 字(word),就是元素wA(a1 ,a2 ,…an ) A, 这里w是变量x1 ,x2 ,…xn上的一个T-字。 定义1 9 .9 :一个T-代数变量(T-algebra variable)是一个自由T-代数的自由生成 集的元素
研究真假值和形式证明之间的关系 构造一个简单的数学推理模型—命题逻 辑 构造较为精细的模型—一阶谓词逻辑
研究真假值和形式证明之间的关系 构造一个简单的数学推理模型——命题逻 辑 构造较为精细的模型—— 一阶谓词逻辑
82命题代数 定义20.1:设T={F,},这里ar(F)=0, ar(→)=2。称任何这样的T代数为命题代 数。 例对于Z2={0,1},构造T代数。 令F2:2={}Z2,F2,()=0, 2:2-Z2,→z2(m,n)=1+m(+n) “+,”是模2加法和乘法运算 构成了一个命题代数。a·b简写为ab
§2 命题代数 定义2 0 .1 :设T={F,→},这里ar(F)=0, ar(→)=2。称任何这样的T-代数为命题代 数。 例:对于Z2={0,1},构造T-代数。 令FZ2 :Z2 0={}→Z2 , FZ2 ()=0, →Z2 :Z2 2→Z2 , →Z2 (m,n)=1+m·(1+n) “+,·”是模2加法和乘法运算. 构成了一个命题代数。a·b简写为ab
由可列集X={x1,xm}生成的自由{,代数P(X), 这也是命题代数。 0={F,x1…,yxn2… P1={(→,a12a)lara;∈Po ={(→,F,F)∪{(→,F,xx;∈x}∪ (→→,x;F)x∈X}U{(,x,x小)xx∈x} P2={(→,a;,4)a∈P0,a1∈P1U{(→,pap)a∈P1,1∈P0} P(X)为:P(X)=∪ 按类型T=({E,→},ar)定义P(X)上的运算: 把0元运算Fx规定为P(X)中的特定元素F 二元运算→a定义为: Px(p,q)=(→,P,q), 构成了X上T代数P(X,Fx,→Pxl,即命题代数 自由代数
由可列集X={x1 ,…,xn ,…}生成的自由{F,→}代数P(X), 这也是命题代数。 P0={F,x1 ,…,xn ,…} P1={(→,ai ,aj )|ai ,ajP0 } ={(→,F,F)}∪{(→,F,xi )|xiX}∪ {(→,xi ,F)|xiX}∪{(→,xi ,xj )|xi ,xjX} P2={(→,ai ,aj )|aiP0 ,ajP1 }∪{(→,ai ,aj )|aiP1 , ajP0 } P(X)为:P(X)= n N Pn 按类型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)],即命题代数 自由代数
定义202:设X是可列集,X上的自由T (=({F,→},ar))代数称为X上关于命题 演算的命题代数,记为PX),并称X为 命题变量集,X中的元素称为命题变元, P(X)中的每个元素称为命题演算的合式 公式,简记为wf,仅由一个命题变元符 组成的合式公式称为原子公式,所有原 子公式全体称为原子公式集
定义20.2:设X是可列集,X上的自由T ( =({F,→},ar) )-代数称为X上关于命题 演算的命题代数,记为P(X),并称X为 命题变量集,X中的元素称为命题变元, P(X)中的每个元素称为命题演算的合式 公式,简记为wff,仅由一个命题变元符 组成的合式公式称为原子公式,所有原 子公式全体称为原子公式集
在任何命题代数中,可利用F和→定义 元运算一和其它二元运算,,,定义为: def p=p→>F pVq=(-p)→>q p入q=-(p)(q)) p<>q=(p>q)∧(q→p)
在任何命题代数中,可利用F和→定义一 元运算和其它二元运算,,,定义为: ( ) ( ) (( p) ( )) ( p) p p def p q p q q p p q q p q q F def def def = → → = = → = →
(p)y(q)可简写为p∨-q 运算的优先次序排列为: >∧>V>>4 在相同优先级的运算之间,先左后右
(p)(q)可简写为pq。 运算的优先次序排列为: > > > → > 在相同优先级的运算之间,先左后右
§3命题演算的语义 、P(X)的赋值 定义20.3:设P(X是X上关于命题演算的命 题代数,称P(X)→Z2的同态映射v为P(X)的 值。对于任意的p∈P(X),若vp)=1则称 p按败值为萇,若vp)=0则称p按赋值为 。 定理20,1设A为命题代数,v为X→A的映 射,则v可唯一扩张为PX)A的同态映 射v
§3 命题演算的语义 一、P(X)的赋值 定义20.3:设P(X)是X上关于命题演算的命 题代数,称P(X)→Z2的同态映射v为P(X)的 赋值。对于任意的pP(X),若v(p)=1则称 p按赋值v为真,若v(p)=0则称p按赋值v为 假。 定理20.1:设A为命题代数,v0为X→A的映 射,则v0可唯一扩张为P(X)→A的同态映 射v