《离散数学 教学课件 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,
