复旦大学：《离散数学——代数结构与数理逻辑》PPT课件_21/29

定义176:设X是集合,G是一个T-代数,σ 为X到G的函数,若对每个T代数A和X到A 的函数τ,都存在唯一的G到A的同态映射o 使得qo=τ,则称G(更严格的说是(G,o)是 生成集X上的自由T代数。X中的元素称为 生成元。 A变,φ变 变,φ也变 对给定的τ和A,q是唯一的

 定义17.6:设X是集合，G是一个T-代数， 为X到G的函数,若对每个T-代数A和X到A 的函数，都存在唯一的G到A的同态映射, 使得=，则称G(更严格的说是(G,))是 生成集X上的自由T-代数。X中的元素称为 生成元。  A变， 变  变， 也变  对给定的 和A，是唯一的

定理171:对任何集合X和类型T,存在X 上的自由T代数,并且这种T代数在同 构意义下是唯一的。 ■证明:1唯一性 P1 G

 定理17.1:对任何集合X和类型T，存在X 上的自由T-代数，并且这种T-代数在同 构意义下是唯一的。  证明:1.唯一性  X G 1  G1 1  1 G X G1

■存在性证明采用构造法,在证明之前,先看个 例子

 存在性证明采用构造法,在证明之前,先看个 例子   1º G X G

设X={x1…,xm},T={F,}其中 ar(F)=0ar(→→)=2, } P1={(,an川ana∈Po} ={(→,F,F)}∪{(,F,x川x∈X}U (一,x1F)x∈U{(一→,x)xX∈好 P2={(→,an4)a∈P0aeP1yU{(→)a1)a∈ P1a∈P0}

 设 X={x1 ,…,xn ,…}，T={F,→}， 其 中 ar(F)=0,ar(→)=2，  令： P0={F,x1 ,…,xn ,…} P1={(→,ai ,aj )|ai ,ajP0 } ={(→,F,F)}∪{(→,F,xi )|xiX}∪ {(→,xi ,F)|xiX}∪{(→,xi ,xj )|xi ,xjX} P2={(→,ai ,aj )|aiP0 ,ajP1 }∪{(→,ai ,aj )|ai P1 ,ajP0 }

随着n的增大P将更为复杂。 n令P(X)为:P(X)=U n∈N 按类型I=({F,→},ar)定义P(X上的运算: 把0元运算Fx规定为P(X中的特定元素 二元运算→Px定义为: pox(p, =(,P, q 构成了X上T代数P(X),F,→exl 并且是自由T代数 这个T代数就是以后要讨论的命题代数

 随着n的增大Pn将更为复杂。  令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)] 并且是自由T-代数 这个T-代数就是以后要讨论的命题代数

(2)存在性 n采用递归构造方法 iG。=T0UX 这里假定Tx=② i假设G(0rn已经确定,则: Gn=(ta1…ak)t∈Ta.-1 ∑ ⅲG=∪Gn n∈ N

 (2)存在性  采用递归构造方法  ⅰG0=T0∪X.  这里假定T0∩X=  ⅱ假设Gr (0r<n)已经确定，则： G {(t,a , ,a ) | t T , , 1} 1 n = 1 k  k   = − = a G r n k i i r i  i ⅲ  n N G Gn  =

ⅳ定义G中运算te;GarG v对任何x∈X,o(x)=x 构造φ 称X中的元素为生成元 Gn是T表达式集,其复杂程度随着n的增大而 增加。 推论171:设G是可列集X={x1…,xm}上的自 由T代数。则G中每个元素都是某个有限子集 Xn={X1x…,n}所生成的自由T代数中的元素

 ⅳ定义G中运算tG:Gar(t)→G  ⅴ对任何xX,(x)=x  构造  称X中的元素为生成元  Gn是T-表达式集，其复杂程度随着n的增大而 增加。  推论17.1:设G是可列集X={x1 ,…,xn ,…}上的自 由T-代数。则G中每个元素都是某个有限子集 Xn={x1 ,…,xn }所生成的自由T-代数中的元素

设A是任一T代数,(G,o)是按定理171的构 造方法生成的Xn={x1,x2…,Xn上的自由T代 数,σ是Xn→G的映射,且o(x)=x Xn到A中的映射τ,τ(x)=a1,a1a2…an为A 中的任何元素允许a=a,j) 由自由代数定义,存在唯一的同态映射 φ:G→A,使得φo=τ q(x=p(o(x)=poσ(x}=τ(x)=a,(i=1,,n) 当W∈G时,φ(w)由A中元素a1a2an唯 确定

 设A是任一T-代数，(G,)是按定理17.1的构 造方法生成的Xn={x1 ,x2 ,…xn }上的自由T-代 数，是Xn→G的映射，且(xi )=xi。  Xn到A中的映射,(xi )=ai，a1 ,a2 ,…an为A 中的任何元素(允许ai=aj ,ij)。  由自由代数定义，存在唯一的同态映射 :G→A，使得=.   ( xi )=((xi ))=(xi )=(xi )=ai，(i=1,…,n)， 当wG时，(w)由A中元素a1 ,a2 ,…an唯一 确定

定义函数W:AnA,使得WA(a1,a2yan =(w)简写为w(a1,a2yan 特别,当A=G,a=x(i=1,,n)时,因 q(x)=x;,故q是恒等映射 有φw)=W w(x,,X2,-.X,)=Wo 定义177:一个T代数变量( T-algebra variable)是一个自由T代数的自由生成 集的元素

 定义函数wA:An→A，使得wA (a1 ,a2 ,…an ) = (w)。简写为w(a1 ,a2 ,…an )  特别，当 A=G，ai=xi (i=1,…,n)时，因 (xi )=xi，故是恒等映射，  有(w)=w，  w(x1 ,x2 ,…xn )=w。  定义17.7:一个T-代数变量(T-algebra variable)是一个自由T-代数的自由生成 集的元素

第十八章命题逻辑

第十八章 命题逻辑