定义函数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字(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上的一个T-字。定义19.9:一个T-代数变量(T-algebravariable)是一个自由T-代数的自由生成集的元素。研究真假值和形式证明之间的关系构造一个简单的数学推理模型——命题逻辑构造较为精细的模型——一阶谓词逻辑§2命题代数由可列集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X}P2={(→,ai,aj)|aiP0,ajP1}∪{(→,ai,aj)|aiP1,ajP0}P(X)为：P(X)=定义20.2:设X是可列集，X上的自由T（=({F,→},ar)）-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。在任何命题代数中，可利用F和→定义一元运算和其它二元运算,,，定义为：(p)(q)可简写为pq。运算的优先次序排列为：>>>→>在相同优先级的运算之间，先左后右。§3命题演算的语义定义20.4:设v0为X→Z2的映射，称v0为命题变元的一个指派。v(p→q)=v(p)→v(q)=1+v(p)(1+v(q))=1+v(p)+v(p)v(q)；v(p)=v(p→F)=v(p)→v(F)=1+v(p)(1+v(F))=1+v(p)(1+0)=1+v(p)；v(pq)=v(p→q)=v(p)→v(q)=1+(1+v(p))(1+v(q))=v(p)+v(q)+v(p)v(q)；v(pq)=v((pq))=1+v(pq)=v(p)v(q);v(pq)=v((p→q)(q→p))=1+v(p)+v(q)二、P(X)中元素的解释和真值表把P(X)中的每个元素(即命题演算的合式公式)解释为可判断真假的语句原子公式集中的每个原子公式(命题变元x)表示任意的简单命题(即原子命题)P(X)中的其它元素表示复合命题。对任意pP(X)和给定的赋值v:P(X)→Z2，若v(p)=1，则说p所表示的命题为真，简称p为真；若v(p)=0，则说p所表示的命题为假，简称p为假。在P(X)上所定义的一元和二元运算,,,→,,可分别解释为命题联结词“非”，“合取”，“析取”，“蕴含”和“等价”。列出下述表格(在表中p表示v(p))：对任意的v1,v2,vnZ2,将v1,v2,vn分别指派给x1,x2,xn由定理20.1知此指派可唯一扩张为赋值v:P(Xn)→Z2,此时对任意pP(Xn),都有确定的真值v(p)Z2由此定义n元真值函数fp:Z2n→Z2,使得fp(v1,v2,vn)=v(p).定义20.5:函数f:Z2n→Z2称为n元真值函数定义20.6:设pP(X)，定义p的n元真值函数fp:Z2n→Z2为：fp=v(p)，称fp为p的真值函数。由p的真值函数所建立的函数值表称为p的真值表。例:写出合式公式(x1x2)→(x3→x1)真值表以后可简写为:三、语言蕴含定义20.7：设AP(X),qP(X)，若对所有使得v(p)=1(对一切pA)的赋值v，都有v(q)=1，则称q是假设集A的后件，或称A语义蕴含q，记为A╞q，用Con(A)表示A的后件全体，即Con(A)={pP(X)|A╞p}。注意：A是P(X)的子集，但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)，有{F}╞q。定义20.8:设pP(X)，若对P(X)的任意赋值v都有v(p)=1，则称p是有效的，也称为重言式。若对P(X)的任意赋值v都有v(p)=0，则称