西安电子科技大学离散数学软件学院办第一篇数理逻辑第1章命题逻辑1.1命题第1课时V第2课时1.2命题公式一第3课时1.3逻辑等价式与永真蕴含式第4课时之1.4主范式第5课时1.5命题逻辑的推理与证明方法1第6课时之1.6命题逻辑的应用
西安电子科技大学 离散数学 软件学院 第一篇 数理逻辑 第1课时 1.1 命题 第1章 命题逻辑 1.3 逻辑等价式与永真蕴含式 1.2 命题公式 1.4 主范式 1.5 命题逻辑的推理与证明方法 第2课时 第3课时 第4课时 第5课时 第6课时 1.6 命题逻辑的应用
西安电子科技大学逻辑等价式$1.3.1 j软件学院教家设A和B是两个含有相同命题变元P1,P2，Pn的逻辑等价：命题公式，若对于Pi,P....,P,的每-种真值指派，A和B的真值均相同，则称A和B是逻辑等价公式，记为A台B。若A为重言式，记为A台T例如：PΛQQ ΛPP-Q-PV Q与联结词“一”不同，等价符“台”是一个关系符，它表示命题公式A与B在相同的赋值下总是等值的
西安电子科技大学 逻辑等价式 软件学院 逻辑等价: §1.3.1 与联结词“↔”不同，等价符“⇔”是一个 关系符，它表示命题公式A与B在相同的赋值 下总是等值的。 例如： P ∧ Q ⇔Q ∧ P P→Q ⇔¬P ∨ Q
西安电子科技大学$1.3.1 j逻辑等价式软件学院「定理】设A，B为两个命题公式，AB当且仅当AB为重言式。证明：(i）充分条件若A一B为重言式，则A，B在相同的赋值下的真值均相同，所以A和B是逻辑等价的公式，即A台B.ii）必要条件若A台B，则有A,B在相同的赋值下的真值均相同，所以AB为重言式
西安电子科技大学 §1.3.1 逻辑等价式 软件学院 证明： （i）充分条件 若A↔ B为重言式，则A,B在相同的赋值下的真值 均相同，所以 A和B是逻辑等价的公式，即A⇔B. （ii ）必要条件 若A⇔B ，则有A,B在相同的赋值下的真值均相 同，所以 A ↔ B为重言式
西安电子科技大学S1.3.1逻辑等价式软件学院茶家家家教家【例题】证明命题公式P→Q与一PVQ等价，解答：首先给出(P→Q)+(-PVQ)的真值表，如表1.2-1所示。表1.2-1PQP→Q-PVQ(P→Q)+(-PYQ)0011111101001011111可以看出(P→Q)+(一PVQ)是重言式，因此有P→+Q与-PVQ等价
西安电子科技大学 §1.3.1 逻辑等价式 软件学院
西安电子科技大学逻辑等价式$1.3.1软件学院家24个基本的逻辑等价式Ei对合律--PPE,PVPP等幂律E,PAP-PE4PVQ-QVP交换律EsPAQ-QAPE(PVQ) YR-PV(QVR)结合律Ef(PAQ)A R-PA(QAR)EsPA(QVR)PAQVPAR分配律E,PV (QAR)-(PVQ) A(PVR)
西安电子科技大学 §1.3.1 逻辑等价式 软件学院
西安电子科技大学逻辑等价式$1.3.1软件学院家家E1o-(PVQ)- -PA-Q德，摩根定律En-(PAQ)- -PV -QE?PV (PAQ)-P吸收律ErP A(PVQ) PEut蕴含表达式(P-→Q) ±-PVQEt;等值表达式(P→Q) =(P-Q) A(Q-P)Er.PVT-T零一律E17PAF-FEisPVF-P同一律E1gPAT-PE20排中律PV-P-T矛盾律EnPA-P-F输出律Es(PAQ-R)-(P-(Q-R)归谬律E(P→Q) A(P→-Q))--P逆反律E(P+Q)=(-0+-P)
西安电子科技大学 §1.3.1 逻辑等价式 软件学院
西安电子科技大学$1.3.1逻辑等价式软件学院【定理】将命题式A中的某个子公式B用与B等替换规则价的另一个命题公式C置换，所得命题公式A与A逻辑等价。例如: R^(P→Q)台RΛ(-P V Q)应用替换规则、代入规则和基本的逻辑等价式，可以将一个公式变换为另一个与之等价的公式
西安电子科技大学 软件学院 应用替换规则、代入规则和基本的逻 辑等价式，可以将一个公式变换为另 一个与之等价的公式 。 替换规则 【定理】将命题式A中的某个子公式B用与B等 价的另一个命题公式C置换，所得命题公式A′ 与A逻辑等价。 例如： R ∧ ( P → Q ) ⇔ R ∧ (¬ P ∨ Q) §1.3.1 逻辑等价式
西安电子科技大学S1.3.2永真蕴含式软件学院茶家家家若A一B是一个重言式，则称“A永真蕴含B”永真蕴含：记为A→B。例如：P^QP永真蕴含符“”也是一个关系符。A→B当且仅当A为T时，B一定为T，即“由A成立可以逻辑推出B也成立
西安电子科技大学 §1.3.2 永真蕴含式 软件学院 永真蕴含： 永真蕴含符“⇒”也是一个关系符。 A⇒B当且仅当A为T时，B一定为T， 即“由A成立可以逻辑推出B也成立” 例如： P ∧ Q ⇒ P
西安电子科技大学$1.3.2永真蕴含式软件学院【例题】证明：-QAP→Q)→P方法一：（真值表法）PP→QQ-Q-QA(P-Q)-QA(P-Q)--P0111010011001110011
西安电子科技大学 §1.3.2 永真蕴含式 软件学院
西安电子科技大学S1.3.2永真蕴含式软件学院【例题】］证明： -QA(P→Q)→ -P方法二：（假定前件为真，推出后件也为真）假定-Q^(P→Q)为T，则有-Q为T且P→Q为T由P-→Q为T，可得-Q→-P为T文-Q为T，可得-P为T故有-Q ^(P-→Q)=-P
西安电子科技大学 软件学院 假定¬Q∧(P→Q)为T，则有¬Q为T且P→Q为T. 由P→Q为T，可得¬Q→¬P为T. 又¬Q为T，可得¬P为T. 故有¬Q ∧(P→Q)⇒¬P. §1.3.2 永真蕴含式