离散数学数理逻辑部分

Outline命题逻辑非形式命题演算(Informalstatementcalculus)形式命题演算(Formalstatementcalculus)谓词逻辑(一阶逻辑)非形式谓词演算(Informalpredicatecalculus)形式谓词演算(Formalpredicatecalculus)Ch1.非形式命题演算1.1命题和连接词Example1.1IfSocratesisamanthenSocratesismortalSocratesisaman∴SocratesismortalAB,A,∴BCh1.非形式命题演算1.2真值函数和真值表NOT:~p(Negation)AND:p∧q(Conjunction)OR:p∨q(Disjunction)Imply:pq(Conditional)Ifandonlyif:p<->q(Biconditional)Definition1.2:命题形式((p∧q)r)(p(~((pq)∨r)))pqpqTTTTFFFTTFFTCh1.非形式命题演算Definition1.5重言式(tautology):恒真的命题形式矛盾式(contradition):恒假的命题形式Example1.6(p∨(~p))是重言式(p∧(~p))是矛盾式Ch1.非形式命题演算Definition1.7若(AB)是重言式，则称A逻辑蕴涵B(logicallyimply)若(A<->B)是重言式，则称A逻辑等价于B(logicallyequivalent)Example1.8(p∧q)逻辑蕴涵p(~(p∧q))逻辑等价于((~p)∨(~q))Proposition1.9若A和(AB)都是重言式，则B也是重言式Ch1.非形式命题演算Proposition1.17(DeMorgan’sLaw)((~A1)∨(~A2)∨…∨(~An))逻辑等价于(~(A1∧A2∧…∧An))((~A1)∧(~A2)∧…∧(~An))逻辑等价于(~(A1∨A2∨…∨An))严格证明略Ch1.非形式命题演算1.4范式(SGU182:OpentheBrackets)Proposition1.20(disjunctivenormalform)任何一个命题形式A都可以等价为如下形式的析取范式:(Qij如同p或~p的形式)证明：选取A的真值表中使A为真的的那些真值赋值，如(pq)∧(qp)中的p=T,q=T和p=F,q=F，然后写为：

((p∧q)∨((~p)∧(~q)))Ch1.非形式命题演算Proposition1.21(conjunctivenormalform)任何一个命题形式A都可以等价为如下形式的合取范式:(Qij如同p或~p的形式)证明：设~A的析取范式为B，如((p∧q)∨(p∧(~q))),则A逻辑等价于~B，如~((p∧q)∨(p∧(~q)))，逻辑等价于(((~p)∨(~q))∧((~p)∨q))为A的合取范式。

(注意多次使用DeMorgan’sLaw)Ch1.非形式命题演算1.5连接词的完备集(Adequateset)Definition1.23若任何真值函数都可以表示为仅含一个集合中的连接词的命题形式，则称为连接词的完备集Proposition1.24:{~,}是连接词的完备集证明:{~,∧,∨}是完备集(A∧B)逻辑等价于(~(A(~B)))(A∨B)逻辑等价于((~A)B)因而任何仅包含{~,∧,∨}的命题形式都可以表示为仅含{~,}的命题形式Ch2.形式命题演算问题起源：当命题形式的连接词过多时，我们的直觉并不一定很准确，希望建立一个简单的系统来对应直觉。这也符合我们计算机的思维。“如果A不正确蕴涵A正确那么A一定正确”这句话对吗？“如果当对任意的B均有A蕴涵B成立时，A一定成立，那么A一定成立”很容易理解吗？Ch2.形式命题演算2.1形式系统L(Definition2.1)定义命题逻辑的形式推演系统L包含如下内容：1.字母表：~,,(,),p1,p2,p3,…2.合式公式:由连接词~,构成的有限长公式公理模式(L1)(A(BA))(L2)((A(BC))((AB)(AC))(L3)(((~A)(~B))(BA))推演规则(MP):从(AB)和A可以得到一个直接的结论BCh2.形式命题演算Definition2.2(证明的定义)L中的一个证明是一个有限合式公式的序列：A1,A2,…,An，对任何1≤i≤n,Ai要么是一个公理，要么有证明序列中靠前的两个合适公式Aj和Ak由MP推演而来(j,k<i)。称之为L中An的一个证明，称An为L的一个定理，记为┣

AnRemark2.3:可见Aj和Ak一定为如同B和(BA)的形式Ch2.形式命题演算Definition2.5(从公式集Г出发的推演)类似于Definition2.2，只不过证明序列中的公式还可以是Г的一员。Example2.6{A,(B(AC))}┣(BC)(1)Aassumption(2)(B(AC))assumption(A(BA))(L1)(BA)(1),(3)MP((B(AC))((BA)(BC))(L2)((BA)(BC))(2),(5)MP(BC)(4),(6)MPCh2.形式命题演算Example2.7:┣(AA)(1)(A((AA)A))((A(AA))(AA))(L2)(2)(A((AA)A))(L1)(3)((A(AA))(AA))(1),(2)MP(4)(A(AA))(L1)(5)(AA)(3),(4)MP思考：上述过程的证明可不可以转化为A┣A呢？这样就容易多了。Ch2.形式命题演算Proposition2.8(演绎定理,TheDeductionTheorem)设Г∪{A}┣B则Г┣A

B[证明]施归纳法于Г∪{A}┣B的证明长度n归纳奠基:(n=1)B是公理，则如下可证明Г┣A

B(1)B(公理)(2)(B(AB))(L1)(3)(AB)(1),(2)MPB是Г的一员，类似于上面的证明B就是A，那么由Example2.7有┣(A

A)，可得Г┣A

BCh2.形式命题演算归纳阶段:设n>1,定理对一切长度小于n的证明序列成立,现证明对长度为n的证明亦正确:如归纳奠基，亦有B为公理,Г的一员,和B为A三种情况情况4:B由前方两个公式MP得来，这两个公式一定形如C和(CB)，由归纳假设:Г┣(AC)且Г┣(A(CB))，如下证明Г┣(AB)(1)…(q)(AC)(q+1)…(k)(A(CB))(k+1)(A(CB))((AC)(AB))(L2)(k+2)(AC)(AB)(k),(k+1)MP(k+3)(AB)(q),(k+2)MPCh2.形式命题演算Remark:演绎定理的逆定理是平凡的:若有Г┣A

B则一定有Г∪{A}┣A

B同时显然有Г∪{A}┣A使用一次MP就可以得到Г∪{A}┣BCh2.形式命题演算Corollary2.10{(AB),(BC)}┣(AC)(HS,HypotheticalSyllogism,假言三段论)(1)(AB)assumption(2)(BC)assumption(3)Aassumption(4)B(1),(3)MP(5)C(2),(4)MP这就证明了{(A

B),(B

C),A}┣C由演绎定理不难得{(A

B),(B

C)}┣(A

C)Ch2.形式命题演算Proposition2.11┣(~AA)A(1)(~AA)assumption(2)(~A(~~(~AA)~A))(L1)(3)(~~(~AA)~A)(A~(~AA))(L3)(4)(~A(A~(~AA)))(2),(3)HS(5)(~A(A~(~AA)))((~AA)(~A~(~AA)))(L2)(6)(~AA)(~A~(~AA))(4),(5)MP(7)(~A~(~AA))(1),(6)MP(8)(~A~(~AA))((~AA)A)(L3)(9)(~AA)A(7),(8)MP(10)A(1),(9)MPCh2.形式命题演算这就证明了(~AA)┣A，由演绎定理：

┣((~AA)A)几个Exercises见后页Remark:可见在命题逻辑的公理系统内推演并不是一件容易的事情，是否可以证明这个系统的一些性质，如系统的定理一定是直觉上正确的(可靠性定理)直觉上正确的公式一定可以在系统内证明

(完备性定理)Ch2.形式命题演算Ex.1┣(~~AA)Ch2.形式命题演算Ex.2┣(A~~A)Ch2.形式命题演算Ex.3┣(AB)(~B~A)Ch2.形式命题演算Ex.4{B,~C}┣~(BC)Ch2.形式命题演算Ex.5┣~B(BC)Ch2.形式命题演算Ex.6{AB,~AB}┣BCh2.形式命题演算2.2完备性定理

(TheAdequacyTheoremforL)Proposition2.14可靠性定理(TheSoundnessTheorem):L的定理都是重言式证明思路：L的三条公理可靠推演规则(三段论)可靠由归纳法可知，L的所有定理可靠Ch2.形式命题演算Proposition(Extra):弱完备性定理,即若A是重言式，则A是L的定理(可以在系统内证明)。Remark:联想我们靠真值表来确定A是否为重言式，如果可以将真值表的思想对应为系统内的一个证明序列，问题就迎刃而解了。Ch2.形式命题演算Definition2.12真值赋值真值赋值为一个函数v:{p1,p2,p3,…}{T,F}任何一个真值赋值v可以将定义域扩张至整个合式公式集合，只要按照如下规则：v(~A)=Tiff.v(A)=FV(AB)=Tiff.v(A)=F或v(B)=T方便起见，扩张后的真值赋值v通常仍记为vCh2.形式命题演算Lemma:设Σ是命题变元或其否定形式的集合，对于任何一个真值赋值v，令其对应的Σ为：若v(pi)=T则令pi∈∑,否则~pi∈∑v(A)=T则∑┣A,v(A)=F则∑┣(~A)证明:施归纳法于A的结构归纳奠基:若A为命题变元pi,则显然正确归纳证明:根据A的构成方法分两种情况:A为(~B)A为(BC)Ch2.形式命题演算若A为(BC),若v(A)=F,则v(B)=T,v(C)=F,由归纳假设∑┣B和∑┣(~C)

由Ex.4有{B,~C}┣~(BC)=~A

即∑┣~A若v(A)=T,则v(B)=F或v(C)=T,即∑┣(~B)或∑┣C

显然有┣C(BC)及┣~B(BC)(Ex.5)

因而一定有∑┣(BC)即∑┣ACh2.形式命题演算有了这样一个引理,则可以较容易的证明弱完备性定理:由于A是重言式,那么对任意真值赋值A都为真,再由演绎定理不难得到下述事实(假设A中仅出现p1和p2)┣p1(p2A)┣~p1(p2A)┣p1(~p2A)┣~p1(~p2A)由Ex.6的结论:{~AB,AB}┣B知┣p2A┣~p2A再合并一次就得到┣A由这个思路很容易得到定理的严格证明Ch2.形式命题演算Remark:可以看出,弱完备性定理的证明是构造性的,因此我们可以通过编写一个程序完成系统内的证明,希望同学们在上机时实践一下。Remark:事实上我们还有另外一种更强大的证明这一命题的方法，且这种方法对于一阶谓词逻辑中的完备性定理的证明有很大的帮助。Ch2.形式命题演算强完备性定理的证明Definition2.15形式系统L的一个扩充(extension)L*是指在L中修改或添加公理,而L的定理仍然是L*的定理Remark:显然L是L的扩充

Ch2.形式命题演算Definition2.16L的一个扩充L*是协调的(consistent)若不存在公式A使得A和(~A)都是L*的定理Proposition2.17L是协调的反设L不协调,即存在A和(~A)都是L的定理,则由可靠性定理知A和(~A)都是重言式，这显然是不可能的,因而L协调Ch2.形式命题演算Proposition2.18L*是协调的当且仅当存在一个公式A不是L*的定理若L*协调,则任意A和(~A)总有一个不是L*的定理若L*不协调,则存在~A和A同时是L*的定理,由Ex.5:┣~A(AB)对任意B成立，因而对任意B使用两次MP可知B是L*的定理，即不存在A不是L*的定理Ch2.形式命题演算Proposition2.19设L*是L的一个协调扩充,若A不是L*的定理,则将(~A)作为新公理扩充入L*得到L**仍然是协调的反设L**不协调,即任何公式都是L**的定理,如A这等价于从{~A}出发在L*中可以推演出A由演绎定理,(~AA)是L*的定理而由Proposition2.11:┣(~AA)A由一次MP得A是L*的定理,矛盾因此L**协调Ch2.形式命题演算Definition2.20设L*是L的一个扩充,若对任意A和(~A),至少有一个是L*的定理,则称L*是极大的(complete)Remark:显然L不是极大的Ch2.形式命题演算Proposition2.21(Lindenbaum定理)若L*是L的一个协调扩充,则一定存在L*的一个极大协调的扩充首先合式公式集合是可数集,因此可以将所有合式公式排成一列A0,A1,A2,…按如下方式得到L*的扩充序列J0,J1,J2,…令J0=L*,对n>0,若An-1是Jn-1的定理,则令Jn=Jn-1否则将(~An-1)作为一条新公理扩充如Jn-1得到JnCh2.形式命题演算首先J0协调,若Jn-1协调若An-1是Jn-1的定理,那么Jn=Jn-1亦协调若An-1不是Jn-1的定理,由Proposition2.19,将(~An-1)作为一条新公理扩充入Jn-1得到Jn仍然协调由归纳原理:对有限的n都有Jn协调令J为L的一个扩充,其公理集为所有Ji集合的并反若J不协调,在J中可推演出A和(~A),由于证明长度有限,因而使用到的公理有限,存在有限n使得Jn包含了所有需要的公理,进而A和(~A)都是Jn的定理，这和Jn的协调