《离散数学》课程PPT教学课件讲稿（数理逻辑）第二章 命题逻辑的等值和推理演算

第二章命题逻辑的等值和推理演算 ●内容:推理形式和推理演算是数理逻辑研 究的基本内容。 ●推理演算要用正确的推理:推理形式由前 提和结论经蕴涵词联接而成。我们关注正 确的推理形式。正确的推理形式可由逻辑 关系符表达。 ●非形式描述:本章对命题等值和推理演算 进行的讨论,是以语义的观点进行的排形 式的描述

第二章命题逻辑的等值和推理演算 ⚫内容：推理形式和推理演算是数理逻辑研 究的基本内容。 ⚫推理演算要用正确的推理：推理形式由前 提和结论经蕴涵词联接而成。我们关注正 确的推理形式 。正确的推理形式可由逻辑 关系符表达。 ⚫非形式描述：本章对命题等值和推理演算 进行的讨论，是以语义的观点进行的非形 式的描述

等值演算考察逻辑关系符◇>) 1)等值定理、公式 2)由真值表写命题公式(由T写、由F写) 3)联结词的完备集(由个别联结词表示所 有联结词的问题) 4对偶式命题公式的对偶性) 5范式命题公式的统一标准

⚫等值演算(考察逻辑关系符 )： 1)等值定理、公式 2)由真值表写命题公式(由T写、由F写) 3)联结词的完备集(由个别联结词表示所 有联结词的问题) 4)对偶式(命题公式的对偶性) 5)范式(命题公式的统一标准) 

*推理演算(考察逻辑关系符→) 1)推理形式正确推理形式的表示) 2)基本推理公式各种三段论及五种证明 方法) 3推理演算〔明推理公式的第六种方法, 使用推理规则) 4)归结推理法证明推理公式的第七种方 法,常用反证法)

 推理演算(考察逻辑关系符 ) ： 1)推理形式(正确推理形式的表示) 2)基本推理公式(各种三段论及五种证明 方法) 3)推理演算(证明推理公式的第六种方法， 使用推理规则) 4)归结推理法(证明推理公式的第七种方 法，常用反证法) 

21等值定理 21.1等值的定义 等值的定义:给定两个命题公式A和B, 而P1P是出现于A和B中的所有命题 变项那么公式A和B共有2个解释,若 对其中的任一解释,公式A和B的真值都 相等,就称A和B是等值的(叵等价的) 记作A=B或A分→B。注意逻辑关系词

2.1.1 等值的定义 ⚫等值的定义：给定两个命题公式A和B, 而P1…Pn是出现于A和B中的所有命题 变项, 那么公式A和B共有2n个解释, 若 对其中的任一解释, 公式A和B的真值都 相等, 就称A和B是等值的(或等价的)。 记作A = B或A  B。注意逻辑关系词  2.1 等值定理

例1:证明PA_PvQ=Q 证明画出(PA-PQ与Q的真值表可看出等 式是成立的。 PQP∧PP∧P)∨Q FFTT FTFT FFFF图 FTFT 2.1.1

例1: 证明(P∧P)∨Q = Q 证明: 画出(P∧P)∨Q与Q的真值表可看出等 式是成立的

例2:证明Pv_P=Qv_Q 证明:画出PPQv_Q的真值表可看出 它们是等值的而且它们都是重言式

例2: 证明P∨P = Q∨Q 证明: 画出P∨P, Q∨Q的真值表, 可看出 它们是等值的, 而且它们都是重言式

等值定义补充说明:两个公式等值并不要 求它们一定含有相同的命题变项。若仅在 等式一端的公式里有变项P出现那么等式 两端的公式其真值均与P无关。例1中公式 (P-P)vQ与Q的真值都同P无关例2中 Py_PQvQ都是重言式它们的真值也都 与P、Q无关

⚫等值定义补充说明：两个公式等值并不要 求它们一定含有相同的命题变项。若仅在 等式一端的公式里有变项P出现, 那么等式 两端的公式其真值均与P无关。例1中公式 (P∨P) ∨Q与Q的真值都同P无关, 例2中 P∨P, Q∨Q都是重言式, 它们的真值也都 与P、Q无关

2.1.2等值定理 定理211对公式A和B,A=B的充分必要 条件是AB是重言式 扣任意解释下,A和B都有相同的真值。 证明:定理中的两部分都与上一行等同

2.1.2 等值定理 ⚫定理2.1.1 对公式A和B, A = B的充分必要 条件是A  B是重言式。 即任意解释下，A和B都有相同的真值。 证明：定理中的两部分都与上一行等同

令“=”作为逻辑关系符是一种 等价关系 A=B是表示公式A与B的一种关系。这种关 系具有三个性质: 1.自反性A=A。 2.对称性若A=B则B=A。 3.传递性若A=B,B=C则A=C。 这三条性质体现了“=”的实质含义

❖ “ ＝ ”作为逻辑关系符是一种 等价关系 A = B是表示公式A与B的一种关系。这种关 系具有三个性质: 1. 自反性 A = A。 2. 对称性 若A = B则B = A。 3. 传递性 若A = B, B = C则A = C。 这三条性质体现了“ ＝ ”的实质含义

22等值公式 (真值表验证,Venn图理解) 221基本的等值公式特别注意蓝色字) 1.双重否定律 P= P 2.结合律 PQ)∨R=P(QVR) (P∧Q)∧R=P∧Q∧R) (PHQ)4>R=PR

2.2 等值公式 (真值表验证，Venn图理解) 2.2.1 基本的等值公式(特别注意蓝色字) 1. 双重否定律 P = P 2. 结合律 (P∨Q) ∨R = P∨(Q∨R) (P∧Q) ∧R = P∧(Q∧R) (P  Q)  R = P  (Q  R)