复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）23/32

§4命题演算的形式证明 个数学系统通常由一些描述系统特 有性质的陈述句所确定,这些陈述句 称为/没 系统的其它性质的证明,由一组陈述 句组成,其中最后的陈述句描述所期 望的性质,而中间的陈述句总是由它 前面的陈述句通过系统所允许的方法 推得

§4 命题演算的形式证明 一个数学系统通常由一些描述系统特 有性质的陈述句所确定，这些陈述句 称为假设， 系统的其它性质的证明，由一组陈述 句组成，其中最后的陈述句描述所期 望的性质，而中间的陈述句总是由它 前面的陈述句通过系统所允许的方法 推得

◆采用两个方法 些在任何数学证明中公认允许采用 的陈述句,把它们形式化地表述成若 干特殊的命题,这些命题可在证明的 任何一步引入,这些命题被称为公理; ◆另一个采用的方法是由若干规则构成, 这些规则规定:从某些陈述导出某些 特定陈述是可接受的,这些规则在形 式化之后,称为系统的推理规则

 采用两个方法：  一些在任何数学证明中公认允许采用 的陈述句，把它们形式化地表述成若 干特殊的命题，这些命题可在证明的 任何一步引入，这些命题被称为公理；  另一个采用的方法是由若干规则构成， 这些规则规定：从某些陈述导出某些 特定陈述是可接受的，这些规则在形 式化之后，称为系统的推理规则

对于集合X上的命题演算,称X上的自 由命题代数P(X)的子集A=A1UA2UA3 中的所有元素为系统的公理。其中: A1={p→(q→p)p,q∈P(X)} A2={(p→(q→r)→(p→q)→(p→r)|p,qr ∈P(X} ◆A3={-p→pp∈P(X} 系统的推理规则采用MP规则( modus ponens):由p和p>q可导出q

 对于集合X上的命题演算，称X上的自 由命题代数P(X)的子集A=A1∪A2∪A3 中的所有元素为系统的公理。其中：  A1={p→(q→p)|p,qP(X)}；  A2={(p→(q→r))→((p→q)→(p→r))|p,q,r P(X)}；  A3={p→p|pP(X)}。  系统的推理规则采用MP规则(modus ponens)：由p和p→q可导出q

定义2013:设q∈P(X),AcP(X),在集 合X上的命题演算中,由假设A导出q的 证明是一组有限序列p,Pn,这里p∈ P(X)(i=1,…,n),pn=q,并且对每个i, 或者p∈AUA,或者存在jk(kq的证明为: 证明 PIg p2=q→(p→q)A1 p3=(p-q pup2MP

 定义20.13:设qP(X)，AP(X)，在集 合X上的命题演算中，由假设A导出q的 证明是一组有限序列 p1 ,…,pn，这里pi P(X)(i=1,…,n)，pn=q，并且对每个i， 或者piA∪A，或者存在j,k(j,k<i)，有 pk=(pj →pi )。  例：A={q},由A导出p→q的证明为：  证明：p1=q A  p2=q→(p→q) A1  p3 =(p→q) p1 ,p2MP

定义2014设q∈PX),A∈P(X),如果存 在一个由A导出q的证明,则称q是A的 推导,或称q是从A可证明的,记为 Aq,且用Ded(A)表示A的推导全体。 {q}卜p→q 8定义20,15:设p∈P(X),如果存在一个由 O导出p的证明,则称p是X上的命题演 算的定理。记为②卜p,也简写为卜p

 定义20.14:设qP(X)，AP(X)，如果存 在一个由A导出q的证明，则称q是A的 推导，或称q是从A可证明的，记为 A┝q，且用Ded(A)表示A的推导全体。  {q}┝p→q  定义20.15:设pP(X)，如果存在一个由 导出p的证明，则称p是X上的命题演 算的定理。记为┝p，也简写为┝p

例:{p→(q→r),q→(r→s,p}q→s 证明:pP p2=p→(q→r) AA p3=(q pi,p2 MP p4=q→(r→s ◆p5=(q→(r→s)→(q→r)(q→s)A2 ◆p6=(q→r)( q→s) p4,P5 MP p7=(q→s) p3, P6 MP ◆所以有{p→(q→r),q→(r→s),p}g→s

 例：{p→(q→r), q→(r→s),p}┝q→s  证明：p1=p A  p2= p→(q→r) A  p3=(q→r) p1 ,p2MP  p4= q→(r→s) A  p5=(q→(r→s))→((q→r)→(q→s)) A2  p6=(q→r)→(q→s) p4 ,p5MP  p7=(q→s) p3 ,p6MP  所以有{p→(q→r), q→(r→s),p}┝q→s

令例:F→q ◆例:{p}Fp→>q ◆引理20.2: ◆()若q∈Ded(A),则必存在A的有限子 集A',使得q∈Ded(A') ◆(i)Ded在P(X)满足 A∈Ded(A) 若AcA2,则Ded(1)Ded(A2) Ded ded(a)=ded(a)

 例：┝F→q  例：{p}┝p→q  引理20.2:  (i)若qDed(A)，则必存在A的有限子 集A'，使得qDed(A')。  (ii) Ded在P(X)满足  ADed(A)  若A1A2 ,则Ded(A1 ) Ded(A2 )  Ded(Ded(A))=Ded(A)

◆定理20.5(演绎定理:设AcP(X)p2q∈P(X), 则Apq当且仅当AUIp}上q。 ◆证明:1Apq要证明AUq, ◆因为A卜p→q,故存在A导出p→q的有 限证明序列p1…,pn=p→>q, ◆则对于AU印}有证明序列p1,pn=p>q, pn+1→p,A∪{p} ◆pn+2=q,pn+1,pnMP

 定理20.5(演绎定理):设AP(X), p,qP(X)， 则A┝p→q当且仅当A∪{p}┝q。  证明：1.A┝p→q,要证明A∪{p}┝q，  因为A┝p→q,，故存在A导出p→q的有 限证明序列 p1 ,…,pn=p→q，  则对于A∪{p}有证明序列 p1 ,…,pn=p→q，  pn+1=p，A∪{p}  pn+2=q，pn+1 ,pnMP

Q+2AUmh要证明Ap ◆因为AUIp}q,故存在AU{p导出q的 有限证明序列p1,pn=q,为了证明 A卜p→>q,对AUp}卜q的证明序列长度 作归纳证明。 ◆例:证明{pq,q→r}Fpr ◆证明:先证{p→>q,q→r,p}Fr ◆然后由演绎定理即可得

 2. A∪{p}┝q要证明A┝p→q  因为A∪{p}┝q，故存在A∪{p}导出q的 有限证明序列 p1 ,…,pn=q，为了证明 A┝p→q，对A∪{p}┝q的证明序列长度 作归纳证明。  例：证明{p→q, q→r}┝p→r  证明： 先证{p→q, q→r,p}┝r  然后由演绎定理即可得

作业P4008,10,11

作业:P400 8,10,11