周源【信息技术】 看-.pptx

离散数学数理逻辑部分ZhouYuan

Ch1.非形式命题演算1.2真值函数和真值表(Negation)(Conjunction)(Disjunction)NOT:~pAND:p∧qOR:p∨qImply:pq(Conditional)Ifandonlyif:p-q(Biconditional)Definition1.2:命题形式((p∧q) r)(p (~((p q)∨r)))pqp qTTTTFFFTTFFT

Ch1.非形式命题演算–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和(A B)都是重言式，则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为真的的那些真值赋值，如(p q)∧(q p)中的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(A∨B)逻辑等价于((~A)(~B)))B)因而任何仅包含{~,∧,∨}的命题形式都可以表示为仅含{~, }的命题形式

Ch2.形式命题演算问题起源：当命题形式的连接词过多时，我们的直觉并不一定很准确，希望建立一个简单的系统来对应直觉。这也符合我们计算机的思维。“如果A不正确蕴涵A正确那么A一定正确”这句话对吗？“如果当对任意的B均有A蕴涵B成立时，A一定成立，那么A一定成立”很容易理解吗？

Ch2.形式命题演算2.1形式系统L(Definition2.1)–定义命题逻辑的形式推演系统L包含如下内容：–1.字母表：~, ,(,),p1,p2,p3,…–2.合式公式:由连接词~,–公理模式构成的有限长公式(L1)(L2)(L3)((A B) (A C))(B A))(((~A)(A (B A))((A (B C))(~B))–推演规则(MP):从(A的结论BB)和A可以得到一个直接

Ch2.形式命题演算–Definition2.2(证明的定义)–L中的一个证明是一个有限合式公式的序列：A1,A2,…,An，对任何1≤i≤n,Ai要么是一个公理，要么有证明序列中靠前的两个合适公式Aj和Ak由MP推演而来(j,ki)。–称之为L中An的一个证明，称An为L的一个定理，记为┣An–Remark2.3:可见Aj和Ak一定为如同B和(BA)的形式

Ch2.形式命题演算–Definition2.5(从公式集Г出发的推演)–类似于Definition2.2，只不过证明序列中的公式还可以是Г的一员。–Example2.6{A,(B (A C))}┣(B C)(1)Aassu