设A是任一T-代数，(G,)是按定理19.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唯一确定。

定义函数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-algebra variable)是一个自由T-代数的自由生成集的元素。

研究真假值和形式证明之间的关系 构造一个简单的数学推理模型——命题逻辑 构造较为精细的模型—— 一阶谓词逻辑

§2 命题代数 定义20.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,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)= 按类型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)],即命题代数 自由代数

定义20.2:设X是可列集，X上的自由T（ =({F,→},ar) ）-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。

在任何命题代数中，可利用F和→定义一元运算和其它二元运算,,，定义为：

(p)(q)可简写为pq。 运算的优先次序排列为：  >  >  > → >  在相同优先级的运算之间，先左后右。

§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为X→A的映射，则v0可唯一扩张为P(X)→A的同态映射v。

定义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))： 通过对P(X)的解释,命题代数P(X)所建立的形式系统就可以表示我们所熟悉的命题.

对任意的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，则称p是永假式。 因此若╞p，则p就是重言式，简记为╞p 注意A╞p是命题逻辑元语言中的陈述句，但它本身不是P(X)中的元素。

例：{p}╞p→q 例：{x1→(x2→x3),x2}╞x1→x3

引理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.2:下述结论是等价的。 (1)p,q等值。 (2)╞pq。 (3)p,q有相同的真值函数和真值表。 定理20.3:对任意p,q,rP(X)有下述结论： (1)╞pp； (2)╞(pq)pq； (3)╞(pq)pq； (4)╞(p1p2…pn)p1p2…pn (5)╞(p1p2…pn)p1p2…pn

四、析取范式和合取范式 定义20.10:形式为 的合式公式称为 析取范式，形式为 的合式公式称 为合取范式，这里yij为某个命题变元xk或其否定xk。 例：(x1x2)(x1x2)(x1x2x3)是析取范式，而 (x1x2)  (x1 x3)是合取范式。

定理20.4:任何命题合式公式(即P(X)中的元素)都有只含命题变元及,,这三种运算的合式公式与该命题合式公式等值 证明:对任意p=p(x1,x2,…xn)P(Xn) 1.对P(Xn)中任一赋值v恒有v(p(x1,x2,…xn)) =0 2.存在P(Xn)中的赋值v使得v(p(x1,x2,…xn)) =1 构造与该指派所对应的合式公式y1y2… yn, 使得: 目标是v(yi)=1

定义20.11:一个合式公式若不是永假式，则用定理20.4的证明方法得到的等值析取范式称为该合式公式的标准析取范式。 推论20.1:每个非重言式必等值于一个合取范式。 定义20.12:一个合式公式若不是重言式，则用推论20.1的证明方法得到的等值合取范式称为该合式公式的标准合取范式。

例：求与(x1→x2)→(x3)等值的标准析取范式和标准合取范式。

作业: P400 5,6,7