天津大学：《离散数学》课程教学资源（PPT课件讲稿）数理逻辑讲义（第一章 命题逻辑、第二章 谓词逻辑）

1-4真值表与等价公式 基本的命题逻辑等价关系 幂等律:PvP<>P,P^P令→P 结合律:(PQ)VR→P(QVR) (PQ)∧R<→P∧(Q∧R) 交换律:PvQ→QP,P入Q<QP 分配律: PV(QAR分>(PQ)入(PVR) P(QR)冷(P∧Q)(P∧R) 27

27 1-4真值表与等价公式 ◼ 基本的命题逻辑等价关系 幂等律： PPP, PPP 结合律：（PQ）RP（QR） （PQ）RP（Q R） 交换律： PQ QP， PQQP 分配律： P(QR)(PQ)(PR）, P(QR)(PQ)(PR）

1-4真值表与等价公式 基本命题逻辑等价关系(续) 吸收律:Pv(P^Q)◇→>P,P∧(P√QP 德摩根律:η(P√Q)分-P^TQ 1(PAQ) Pv1Q 同一律:PF→P,P∧T→P 零律:PT<→T,PAF<F 否定律:PηP台→T,P∧ηP→F 28

28 1-4真值表与等价公式 ◼ 基本命题逻辑等价关系（续） 吸收律： P(PQ)P, P(PQ)P 德摩根律： ┐（PQ）┐P┐Q ┐（PQ）┐P┐Q 同一律： PFP， PTP 零律： PTT， PFF 否定律： P ┐PT， P ┐PF

1-4真值表与等价公式 ■定义4:如果Ⅹ是命题公式A的一部分,且X也是 命题公式,则称X是A的子公式 定理1:设Ⅹ是命题公式A的子公式,若X→Y,则 若将A中的X的每一次出现用Y来置换,所得公式 B与A等价,即AB 证明:因为对变元的任一组指派,Ⅹ与Y真值相 同,故以Y取代X后,公式B与公式A相对于变元 的任一指派的真值也必相同,所以AB ■定义:称满足定理1的置换为等价置换 29

29 1-4真值表与等价公式 ◼ 定义4：如果X是命题公式A的一部分，且X也是 命题公式，则称X是A的子公式 ◼ 定理1：设X是命题公式A的子公式，若XY，则 若将A中的X的每一次出现用Y来置换，所得公式 B与A等价，即AB 证明： 因为对变元的任一组指派，X与Y真值相 同，故以Y取代X后，公式B与公式A相对于变元 的任一指派的真值也必相同，所以AB ◼ 定义：称满足定理1的置换为等价置换

1-4真值表与等价公式 ■例子:证明下列命题公式(可以利用基本的命 题逻辑等价关系) Q→(P(P∧Q))<>Q→P (P∧Q)v(P^1Q)<>P P→Q-PvQ (P→Q)→(QVR)<→ PVQVR P∧_QQ<→PQ

30 1-4真值表与等价公式 ◼ 例子：证明下列命题公式（ 可以利用基本的命 题逻辑等价关系） Q→（P（PQ））Q→P （PQ)（P┐Q)P P→Q┐PQ （P→Q）→（QR）PQR P┐QQPQ

1-5重言式与蕴含式 重言式即永真式;矛盾式即永假式 ■定理1:任何两个重言式的合取或析取,仍然是重言式 证明:设A、B为两个重言式,则AAB和AVB的真值分别 等于T∧T和TT ■定理2:对一个重言式的同一分量都用任何一个命题公 式置换,所得命题公式仍为一个重言式 证明:由于重言式的真值与分量的真值指派无关,故 对同一分量以任何一个命题公式置换后,重言式的真 值不变 ■问题:上述定理对于子公式替换的情形是否仍成立? 31

31 1-5重言式与蕴含式 ◼ 重言式即永真式；矛盾式即永假式 ◼ 定理1：任何两个重言式的合取或析取，仍然是重言式 证明：设A、B为两个重言式，则AB和AB的真值分别 等于TT和TT ◼ 定理2：对一个重言式的同一分量都用任何一个命题公 式置换，所得命题公式仍为一个重言式 证明：由于重言式的真值与分量的真值指派无关，故 对同一分量以任何一个命题公式置换后，重言式的真 值不变 ◼ 问题：上述定理对于子公式替换的情形是否仍成立？