定理20.6代换定型设X,Y是两个集合, φ是P(X)→>P(Y)的同态映射,这里P(X)和 P(Y分别是XY上的自由)命题代数。设 W=W(X1,n是PX)的元素,A是P(X) 的子集,令qp(xq∈PY), (1)如果Aw,则(A)qw)(=w(q1,m) (2)如果AFw,则 φ(A)Fp(w)=w(q1,qm)
定理20.6(代换定理):设X,Y是两个集合， 是P(X)→P(Y)的同态映射，这里P(X)和 P(Y)分别是X,Y上的(自由)命题代数。设 w=w(x1 ,,xn )是P(X)的元素，A是P(X) 的子集，令qi=(xi ),qiP(Y)， (1)如果A┝w，则(A)┝(w)(=w(q1 ,,qn )) (2)如果A╞w，则 (A)╞(w)(=w(q1 ,,qn ))
证明:(1)设p1…,pn为由A证明w的序列 ①p∈A,则q(p)∈Q(A) p∈A ③p是由p和p=(→)得到0,k< (2)设Aw,是PY的赋值即为P到Z2 的同态映射,并使vA){1} 关键证明v(ow)是否为1
证明:(1)设p1 ,,pm为由A证明w的序列. ①piA,则(pi )(A) ②piA ③pi是由pj和pk=(pj→pi )得到(j,k<I)。 (2)设A╞w,v是P(Y)的赋值,即为P(Y)到Z2 的同态映射,并使v((A)){1} 关键证明v((w))是否为1
推论202设P(Xn)为Xn上的命题代数 p∈PQXn)(i=1,,n W=W(x1,x)∈P(Xn,则有: (1)如果w,则卜w(p1…,Pn) a(2)如果Hw,则w(p1,…,pnl 定义2016:设p,WEP(X),若p在w中出现, 则称p为w的子公式
推论20.2:设P(Xn )为Xn上的命题代数， piP(Xn )(i=1, ,n), w=w(x1 ,,xn )P(Xn )，则有： (1)如果┝w，则┝w(p1 ,,pn )。 (2)如果╞w，则╞w(p1 ,,pn )。 定义20.16:设p,wP(X)，若p在w中出现， 则称p为w的子公式
定理20.7(子公式替换定理):设 W,p,p'∈P(X),p为w的子公式,把p在W 中的某些出现替换为p得到的公式记为 (1)若hp>p,则有Mww (2)若卜>p,则有Hwwo
定 理 20.7( 子 公 式 替 换 定 理 ): 设 w,p,p'P(X)，p为w的子公式，把p在w 中的某些出现替换为p'得到的公式记为 w'。 (1)若┝pp'，则有┝ww'。 (2)若╞pp'，则有╞ww
o∞5-般逻辑系统 定义2017:一个逻L是由下述集合 所组成的系统:元素(称为命题)集P; 函数集v这些函数都是从P到某个值 集W的,称为赋值特别若W>2则称 L为多值逻辑系统);以及对应于P的每 个子集A导出P中元素的有限序列集 (称为由前提A得到的证明)
§5一般逻辑系统 定义20.17:一个逻辑L是由下述集合 所组成的系统：元素(称为命题)集P； 函数集V(这些函数都是从P到某个值 集W的，称为赋值.特别若|W|>2则称 L为多值逻辑系统);以及对应于P的每 个子集A导出P中元素的有限序列集 (称为由前提A得到的证明)
■例如:X上命题演算的逻辑,记为 Prop(X),它是由集合P=P(xX)(X上自由命 题代数),所有的P(X)到Z2同态映射集v 以及满足定义20.13的证明集组成,后者 包含从P(X的每个子集A导出P(X中元素 的有限序列(称为由假设A得到的证明)集
例如： X 上 命 题 演 算 的 逻 辑 ， 记 为 Prop(X)，它是由集合P=P(X)(X上自由命 题代数)，所有的P(X)到Z2同态映射集V， 以及满足定义20.13的证明集组成，后者 包含从P(X)的每个子集A导出P(X)中元素 的有限序列(称为由假设A得到的证明)集
在逻辑L中,语义蕴含由赋值所定义,记 号APp读成“A语义蕴含p”或称“p是A 的后件”,语法蕴含由证明所定义,记 号Ah读成“A语法蕴含p”或称“p是A的 推导”。若⑦卜p,则称p是的重言式; 若b,则称p是L的定理 定义20.18:如果Ah必有AHp,则称逻辑 工是可靠的( sound)。 定义20.19:如果F不是工的定理,则称逻 辑工是协调的( consistent)
在逻辑L中，语义蕴含由赋值所定义，记 号A╞p读成“A语义蕴含p”或称“ p是A 的后件” ，语法蕴含由证明所定义，记 号A┣p读成“A语法蕴含p”或称“ p是A的 推导” 。若╞p，则称p是L的重言式； 若┣p，则称p是L的定理。 定义20.18:如果A┣p必有A╞p，则称逻辑 L是可靠的(sound)。 定义20.19:如果F不是L的定理，则称逻 辑L是协调的(consistent)
定义20.20:如果AF必有AFp,则称逻辑L 是完备的( complete 可缮性和完备性把真值和证明联系起来, 而协调性则是纯语法性质,即任何逻辑都 不会导致矛盾。 ■定义20.21:如果存在一个算法,对逻辑L 的每个命题p,能在有限步内确定p是否为 重言式,则称逻辑L是有效性可判定的。 定义20.22:如果存在一个算法,对逻辑L 的每个命题p,能在有限步内确定p是否为定 理,则称逻辑L是可证明性可判定的
定义20.20:如果A╞p必有A┣p，则称逻辑L 是完备的(complete)。 可靠性和完备性把真值和证明联系起来， 而协调性则是纯语法性质，即任何逻辑都 不会导致矛盾。 定义20.21:如果存在一个算法，对逻辑L 的每个命题p，能在有限步内确定p是否为 重言式，则称逻辑L是有效性可判定的。 定义20.22:如果存在一个算法，对逻辑L 的每个命题p,能在有限步内确定p是否为定 理，则称逻辑L是可证明性可判定的
o96命题演算的性质 定理20.8(可箬性定理):设 ACP(X),PEP(X)。若AFp,则有AFp 简言之:Ded(A)∈con(A)。 证明:设p1pnp是从A推导p的证 明序列,要证明的是p为A的后件。 设v是PX)到2的赋值,且v(A={1}, 施归纳于证明序列长度n n=1,则p=p1,故p∈A∪A,由习题 206知每个公理都是重言式,且 V(A)={1},所以vp)=1
§6 命题演算的性质 定 理 20.8( 可靠性定理 ): 设 AP(X),pP(X)。若A┣p，则有A╞p。 简言之：Ded(A) Con(A)。 证明：设p1 ,…,pn=p是从A推导p的证 明序列，要证明的是p为A的后件。 设v是P(X)到Z2的赋值，且v(A){1}， 施归纳于证明序列长度n。 n=1，则p=p1，故pA∪A，由习题 20.6 知每个公理都是重言式 ， 且 v(A){1}，所以v(p)=1
现假设n>1,且对任何n≤k,若p可从A 用n≤k步证明序列推出,必有AFp 下面就是证明对n=k+1也成立。 pn=p有下述两种情况 n(i)pn∈AUA,因此有v(pn)=1, (对某个jn,有p=P→>Pn,此时 v(p/=v(p1→>pn),由v的同态性质知 v(p=v9)→v(pn),故v(p)=1
现假设n>1，且对任何nk，若p可从A 用 nk步证明序列推出，必有A╞p。 下面就是证明对n=k+1也成立。 pn=p有下述两种情况: (i)pnA∪A，因此有v(pn )=1， (ii)对某个i,j<n，有pi=pj→pn，此时 v(pi )=v(pj→pn )，由v的同态性质知： v(pi )=v(pj )→v(pn )，故v(pn )=1