定义17.6:设X是集合，G是一个T-代数，为X到G的函数,若对每个T-代数A和X到A的函数，都存在唯一的G到A的同态映射,使得=，则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变， 变 变， 也变 对给定的 和A，是唯一的
定理17.1:对任何集合X和类型T，存在X上的自由T-代数，并且这种T-代数在同构意义下是唯一的。 证明:1.唯一性 X G 1 G1 1 1 G X G1
存在性证明采用构造法,在证明之前,先看个例子 1º G X 存在性证明采用构造法,在证明之前,先看个例子
设X={x1,…,xn,…}，T={F,→}，其中ar(F)=0,ar(→)=2， 令： 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}
随着n的增大Pn将更为复杂。 令P(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)] 并且是自由T-代数 这个T-代数就是以后要讨论的命题代数.
(2)存在性 采用递归构造方法 ⅰG0=T0∪X. 这里假定T0∩X= ⅱ假设Gr(0r<n)已经确定，则： ⅲ
ⅳ定义G中运算tG:Gar(t)→G ⅴ对任何xX,(x)=x 构造 称X中的元素为生成元 Gn是T-表达式集，其复杂程度随着n的增大而增加。 推论17.1:设G是可列集X={x1,…,xn,…}上的自由T-代数。则G中每个元素都是某个有限子集Xn={x1,…,xn}所生成的自由T-代数中的元素。
设A是任一T-代数，(G,)是按定理17.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唯一确定。
定义函数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-代数的自由生成集的元素。
第十八章 命题逻辑
§1 命题代数 定义18.1:设T={F,→}，这里ar(F)=0，ar(→)=2。称任何这样的T-代数为命题代数。 例:对于Z2={0,1}，构造T-代数。 令FZ2:Z20={}→Z2, FZ2()=0, →Z2:Z22→Z2, →Z2(m,n)=1+m·(1+n) “+,·”是模2加法和乘法运算. 构成了一个命题代数。a·b简写为ab。
由可列集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)= 按类型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)],即命题代数 自由代数
定义18.2:设X是可列集，X上的自由T-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。
在任何命题代数中，可利用F和→定义一元运算和其它二元运算,,，定义为：
(p)(q)可简写为pq。 运算的优先次序排列为： > > > → > 在相同优先级的运算之间，先左后右。
作业: P229 :1,3,5,6