《离散数学 教学课件 ppt 作者 赵一鸣 阚海斌 吴永辉 dshu23》由会员分享,可在线阅读,更多相关《离散数学 教学课件 ppt 作者 赵一鸣 阚海斌 吴永辉 dshu23(14页珍藏版)》请在金锄头文库上搜索。
1、3 命题演算的形式证明,一个数学系统通常由一些描述系统特有性质的陈述句所确定,这些陈述句称为假设, 系统的其它性质的证明,由一组陈述句组成,其中最后的陈述句描述所期望的性质,而中间的陈述句总是由它前面的陈述句通过系统所允许的方法推得。,采用两个方法: 一些在任何数学证明中公认允许采用的陈述句,把它们形式化地表述成若干特殊的命题,这些命题可在证明的任何一步引入,这些命题被称为公理; 另一个采用的方法是由若干规则构成,这些规则规定:从某些陈述导出某些特定陈述是可接受的,这些规则在形式化之后,称为系统的推理规则。,对于集合X上的命题演算,称X上的自由命题代数P(X)的子集A=A1A2A3中的所有元素
2、为系统的公理。其中: A1=p(qp)|p,qP(X); A2=(p(qr)(pq)(pr)|p,q,rP(X); A3=pp|pP(X)。 系统的推理规则采用MP规则(modus ponens):由p和pq可导出q。,定义18.13:设qP(X),AP(X),在集合X上的命题演算中,由假设A导出q的证明是一组有限序列 p1,pn,这里pi P(X)(i=1,n),pn=q,并且对每个i,或者piAA,或者存在j,k(j,ki),有pk=(pjpi)。 例:A=q,由A导出pq的证明为: 证明:p1=q A p2=q(pq) A1 p3=(pq) p1,p2MP,定义18.14:设qP(X),
3、AP(X),如果存在一个由A导出q的证明,则称q是A的推导,或称q是从A可证明的,记为Aq,且用Ded(A)表示A的推导全体。 qpq 定义18.15:设pP(X),如果存在一个由导出p的证明,则称p是X上的命题演算的定理。记为p,也简写为p。,例:p(qr), q(rs),pqs 证明:p1=p A p2= p(qr) A p3=(qr) p1,p2 MP p4= q(rs) A p5=(q(rs)(qr)(qs) A2 p6=(qr)(qs) p4,p5 MP p7=(qs) p3,p6 MP 所以有p(qr), q(rs),pqs,例:Fq 例:ppq 引理18.2: (i)若qDed(
4、A),则必存在A的有限子集A,使得qDed(A)。 (ii) Ded在P(X)满足 ADed(A) 若A1A2,则Ded(A1) Ded(A2) Ded(Ded(A)=Ded(A),定理18.5(演绎定理):设AP(X), p,qP(X),则Apq 当且仅当Apq。 证明:1.Apq,要证明Apq, 因为Apq,,故存在A导出pq的有限证明序列 p1,pn=pq, 则对于Ap有证明序列 p1,pn=pq, pn+1=p,Ap pn+2=q,pn+1,pn MP,2. Apq要证明Apq 因为Apq,故存在Ap导出q的有限证明序列 p1,pn=q,为了证明Apq,对Apq的证明序列长度作归纳证明
5、。 例:证明pq, qrpr 证明: 先证pq, qr,pr 然后由演绎定理即可得,定理18.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)如果Aw,则(A)(w)(=w(q1,qn) (2)如果Aw,则 (A)(w)(=w(q1,qn),证明:(1)设p1,pm为由A证明w的序列. piA,则(pi)(A) piA pi是由pj和pk=(pjpi)得到(j,kI)。 (2)设Aw,v是P(Y)的赋值,即为P(Y)到Z2的同态映射,并使v(A)1 关键证明v(w)是否为1.,推论18.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)。 定义18.16:设p,wP(X),若p在w中出现,则称p为w的子公式。,定理18.7(子公式替换定理):设w,p,pP(X),p为w的子公式,把p在w中的某些出现替换为p得到的公式记为w。 (1)若pp,则有ww。 (2)若pp,则有ww。,作业:P241 8,10,11,