[离散数学]命题逻辑P

#[离散数学]命题逻辑P| 来源: 网络整理| 查看: 265

[离散数学]命题逻辑P_6：命题等价公式及应用前言1. 基本等价关系定理 2. 判断公式类型例1：证明公式类型例2：证明复杂公式间的等价关系 3. 开关电路化简4. 逻辑电路化简5. 智力游戏总结

前言

第六讲：命题公式等价公式及应用

数理逻辑，就是用数学的方法研究逻辑推理的规律。

命题公式( p r o p o s i t i o n a l f o r m u l a propositional formula propositionalformula)亦称合式公式，是数理逻辑术语，它是按照一定规律形成的符号序列，在命题演算中，公式通常用归纳定义给出。

根据两个公式等价的定义或判定定理，可以利用真值表来证明任意两个公式之间的等价关系，由此得到一组基本等价公式。

本文命题等价公式及应用是命题逻辑的第六部分。

1. 基本等价关系定理

设 G , H , S G,H,S G,H,S为任意的命题公式。

幂等律 E 1 : G ∨ G = G E_1:G\lor G=G E1:G∨G=G； E 2 : G ∧ G = G E_2:G\land G=G E2:G∧G=G.

同真 - 析取或合取 - 为真同假 - 析取或合取 - 为假

交换律 E 3 : G ∨ H = H ∨ G E_3:G\lor H=H \lor G E3:G∨H=H∨G； E 4 : G ∧ H = H ∧ G E_4:G\land H=H \land G E4:G∧H=H∧G.

析取或合取的对称性

结合律 E 5 : G ∨ ( H ∨ S ) = ( G ∨ H ) ∨ S E_5:G\lor (H \lor S)=(G \lor H) \lor S E5:G∨(H∨S)=(G∨H)∨S； E 6 : G ∧ ( H ∧ S ) = ( G ∧ H ) ∨ S E_6:G\land (H \land S)=(G \land H) \lor S E6:G∧(H∧S)=(G∧H)∨S.

三个公式析取或合取，先算前两个和先算后两个等价。

同一律 E 7 : G ∨ 0 = G E_7:G\lor 0=G E7:G∨0=G； E 8 : G ∧ 1 = G E_8:G\land 1=G E8:G∧1=G.

1析取0为1；0析取0为0 1合取1为1；0合取0为0

此处运算律与集合相似，可以通过对比的方式进行记忆。析取对应集合的并运算，合取对应集合的交运算。 0对应空集；1对应全集。

零律 E 9 : G ∨ 1 = 1 E_9:G\lor 1=1 E9:G∨1=1； E 10 : G ∧ 0 = 0 E_{10}:G\land 0=0 E10:G∧0=0.

析取有一个为1，则为1 合取有一个为0，则为0

分配律 E 11 : G ∨ ( H ∧ S ) = ( G ∨ H ) ∧ ( G ∨ S ) E_{11}:G\lor (H \land S)=(G \lor H)\land (G\lor S) E11:G∨(H∧S)=(G∨H)∧(G∨S)； E 12 : G ∧ ( H ∨ S ) = ( G ∧ H ) ∨ ( G ∧ S ) E_{12}:G\land (H \lor S)=(G \land H)\lor (G\land S) E12:G∧(H∨S)=(G∧H)∨(G∧S).

吸收律 E 13 : G ∨ ( G ∧ H ) = G E_{13}:G\lor (G \land H)=G E13:G∨(G∧H)=G； E 14 : G ∧ ( G ∨ H ) = G E_{14}:G\land (G \lor H)=G E14:G∧(G∨H)=G.

外层析取，内层合取；外层合取，内层析取。 H H H就被吸收掉了，用于化简公式，可用于证明中。

矛盾律 E 15 : ¬ G ∧ G = 0 E_{15}:\lnot G\land G = 0 E15:¬G∧G=0.排中律 E 16 : ¬ G ∨ G = 1 E_{16}:\lnot G\lor G = 1 E16:¬G∨G=1.双重否定律 E 17 : ¬ ( ¬ G ) = G E_{17}:\lnot (\lnot G) = G E17:¬(¬G)=G.德摩根律 E 18 : ¬ ( G ∨ H ) = ¬ G ∧ ¬ H E_{18}:\lnot (G \lor H) = \lnot G \land \lnot H E18:¬(G∨H)=¬G∧¬H; E 19 : ¬ ( G ∧ H ) = ¬ G ∨ ¬ H E_{19}:\lnot (G \land H) = \lnot G \lor \lnot H E19:¬(G∧H)=¬G∨¬H.

析取的否定=否定的合取；合取的否定=否定的析取。主要用于公式的变形

蕴涵式 E 20 : G → H ) = ¬ G ∨ H E_{20}:G \rightarrow H) = \lnot G \lor H E20:G→H)=¬G∨H.

将蕴涵联结词转化为否定联结词和析取联结词常用，用于消除或添加蕴涵联结词。

假言易位 E 21 : G → H = ¬ H → ¬ G E_{21}:G \rightarrow H = \lnot H \rightarrow \lnot G E21:G→H=¬H→¬G.

如果 G G G则 H H H，等价于如果 ¬ H \lnot H ¬H则 ¬ G \lnot G ¬G。即逆否命题，原命题为真，则逆否命题为真；原命题为假，则逆否命题为假。

等价式 E 22 : G ↔ H = ( G → H ) ∧ ( H → G ) = ( ¬ G ∨ H ) ∧ ( ¬ H ∨ G ) E_{22}:G \leftrightarrow H = (G \rightarrow H) \land (H \rightarrow G) = (\lnot G \lor H) \land (\lnot H \lor G) E22:G↔H=(G→H)∧(H→G)=(¬G∨H)∧(¬H∨G).

等价联结词 - 转化为蕴涵联结词 - 转化为否定联结词和析取联结词。可用于消去或添加等价联结词。

等价否定等式 E 23 : G ↔ H = ¬ G ↔ ¬ H E_{23}:G \leftrightarrow H = \lnot G \leftrightarrow \lnot H E23:G↔H=¬G↔¬H.

G G G等价 H H H， ¬ G \lnot G ¬G也等价 ¬ H \lnot H ¬H

归谬论 E 24 : ( G → H ) ∧ ( G → ¬ H ) = ¬ G E_{24}:(G \rightarrow H) \land (G \rightarrow \lnot H) = \lnot G E24:(G→H)∧(G→¬H)=¬G.

即反证法，假设结论不成立，找出矛盾，说明假设不正确，证明原结论成立。如果 G G G，则 H H H，且如果 G G G，则 ¬ H \lnot H ¬H，存在矛盾 - 说明 G G G不成立，即 ¬ G \lnot G ¬G。

2. 判断公式类型例1：证明公式类型

利用命题公式的基本等价关系，证明 ( P → Q ) ∧ P → Q (P→Q)\land P→Q (P→Q)∧P→Q是重言式。

证明

通常第一步 - 通过蕴含式消去蕴涵联结词 - 蕴涵联结词不方便进行变换和化简。

( P → Q ) ∧ P → Q \left( P\rightarrow Q \right) \land P\rightarrow Q (P→Q)∧P→Q = ( ¬ P ∨ Q ) ∧ P → Q = ¬ ( ( ¬ P ∨ Q ) ∧ P ) ∨ Q =(\lnot P \lor Q) \land P \rightarrow Q = \lnot (( \lnot P \lor Q) \land P) \lor Q =(¬P∨Q)∧P→Q=¬((¬P∨Q)∧P)∨Q （蕴含式）

消去第二个蕴涵联结词时，【 ( ¬ P ∨ Q ) ∧ P (\lnot P \lor Q) \land P (¬P∨Q)∧P】整体为蕴涵的前件，对整体取否定。公式【 ¬ ( ( ¬ P ∨ Q ) ∧ P ) \lnot((\lnot P \lor Q) \land P) ¬((¬P∨Q)∧P)】结构为合取后取否定，符合德摩根律。公式【 ¬ ( ¬ P ∨ Q ) \lnot (\lnot P \lor Q) ¬(¬P∨Q)】结构为合取后取否定，符合德摩根律。

= ( ¬ ( ¬ P ∨ Q ) ∨ ¬ P ) ∨ Q = ( ( P ∧ ¬ Q ) ∨ ¬ P ) ∨ Q =(\lnot (\lnot P \lor Q) \lor \lnot P) \lor Q = ((P \land \lnot Q) \lor \lnot P)\lor Q =(¬(¬P∨Q)∨¬P)∨Q=((P∧¬Q)∨¬P)∨Q （德摩根律）

公式【 ( P ∧ ¬ Q ) ∨ ¬ P (P \land \lnot Q) \lor \lnot P (P∧¬Q)∨¬P】，内层为合取，外层为析取，符合分配律，将其展开。

= ( ( P ∨ ¬ P ) ∧ ( ¬ Q ∨ ¬ P ) ) ∨ Q =((P \lor \lnot P) \land (\lnot Q \lor \lnot P)) \lor Q =((P∨¬P)∧(¬Q∨¬P))∨Q （分配律）

公式【 P ∨ ¬ P P \lor \lnot P P∨¬P】符合排中律，结果为1。

= ( 1 ∧ ( ¬ Q ∨ ¬ P ) ) ∨ Q =(1 \land (\lnot Q \lor \lnot P)) \lor Q =(1∧(¬Q∨¬P))∨Q （排中律）

公式【 1 ∧ ( ¬ Q ∨ ¬ P ) 1 \land (\lnot Q \lor \lnot P) 1∧(¬Q∨¬P)】符合同一律。

= ( ¬ Q ∨ ¬ P ) ∨ Q =(\lnot Q \lor \lnot P) \lor Q =(¬Q∨¬P)∨Q （同一律）

公式【 ( ¬ Q ∨ ¬ P ) ∨ Q (\lnot Q \lor \lnot P) \lor Q (¬Q∨¬P)∨Q】中三个部分间都是析取，可使用结合律和交换律。

= ( ¬ Q ∨ Q ) ∨ ¬ P =(\lnot Q \lor Q)\lor \lnot P =(¬Q∨Q)∨¬P （结合律，交换律）

公式【 ¬ Q ∨ Q \lnot Q \lor Q ¬Q∨Q】符合排中律，结果为1。

= 1 ∨ ¬ P =1\lor \lnot P =1∨¬P （排中律）

根据零律，1析取任何一个值都为1

= 1 = 1 =1 （零律）

此类问题主要是变形和化简的过程，先对蕴涵或等价联结词进行消去，然后运用德摩根律、分配律、结合律、交换律等，将相同的命题变元放在一起进行化简，直到可以确定公式的类型为止。

例2：证明复杂公式间的等价关系

利用命题公式的基本等价关系，证明 P → ( Q → R ) = ( P ∧ Q ) → R P→(Q→R)=(P\land Q)→R P→(Q→R)=(P∧Q)→R。

证明 P → ( Q → R ) P→(Q→R) P→(Q→R) = ¬ P ∨ ( Q → R ) =\lnot P \lor (Q\rightarrow R) =¬P∨(Q→R) （蕴含式） = ¬ P ∨ ( ¬ Q ∨ R ) =\lnot P \lor (\lnot Q\lor R) =¬P∨(¬Q∨R) （蕴含式） = ( ¬ P ∨ ¬ Q ) ∨ R =(\lnot P \lor \lnot Q) \lor R =(¬P∨¬Q)∨R （结合律） = ¬ ( P ∧ Q ) ∨ R =\lnot ( P \land Q) \lor R =¬(P∧Q)∨R （德摩根律） = ( P ∧ Q ) → R =( P \land Q) \rightarrow R =(P∧Q)→R （蕴含式）

3. 开关电路化简

利用命题公式的基本等价关系，化简如下图所示开关电路。解 ( ( P ∧ Q ∧ R ) ∨ ( P ∧ Q ∧ S ) ) ∧ ( ( P ∧ R ) ∨ ( P ∧ S ) ) ((P\land Q \land R)\lor (P\land Q \land S)) \land ((P\land R) \lor (P \land S)) ((P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S)) = ( P ∧ Q ∧ ( R ∨ S ) ) ∧ ( P ∧ ( R ∨ S ) ) =(P\land Q \land (R\lor S)) \land (P \land (R \lor S)) =(P∧Q∧(R∨S))∧(P∧(R∨S)) = P ∧ Q ∧ ( R ∨ S ) ∧ P ∧ ( R ∨ S ) =P\land Q \land (R\lor S) \land P \land (R \lor S) =P∧Q∧(R∨S)∧P∧(R∨S) = P ∧ Q ∧ ( R ∨ S ) =P\land Q \land (R\lor S) =P∧Q∧(R∨S)

化简后的电路图：化简后电路

化简后开关电路功能与原开关电路功能完全一致。

4. 逻辑电路化简

利用命题公式的基本等价关系，化简如下左图所示逻辑电路。

逻辑电路

逻辑电路中的与门对应逻辑运算符的合取，或门对应析取。

解 ( ( P ∧ Q ∧ R ) ∨ ( P ∨ Q ∨ S ) ) ∧ ( P ∧ S ∧ T ) ((P\land Q \land R)\lor (P\lor Q \lor S)) \land (P\land S\land T) ((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)

吸收率 - ( P ∧ Q ∧ R ) ∨ P (P\land Q \land R)\lor P (P∧Q∧R)∨P = P P P

= ( P ∨ Q ∨ S ) ∧ ( P ∧ S ∧ T ) =(P\lor Q \lor S)\land (P\land S\land T) =(P∨Q∨S)∧(P∧S∧T)

吸收率 - ( P ∨ Q ∨ S ) ∧ P (P\lor Q \lor S)\land P (P∨Q∨S)∧P = P P P

= P ∧ S ∧ T =P\land S\land T =P∧S∧T

5. 智力游戏

侦探调查了罪案的四位证人。从证人的话侦探得出的结论是：如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁说的不可能都是真话;园丁和杂役不可能都在说谎；如果杂役说真话，那么厨师在说谎。侦探能判定这四位证人分别是在说谎还是在说真话吗？解释你的推理。

解令命题 P P P：男管家说的是真话； Q Q Q：厨师说的是真话； R R R：园丁说的是真话； S S S：杂役说的是真话。

则将上述已知条件符号化并列出真值表，选取真值结果为真的行如下表：

P P P Q Q Q R R R S S S P → Q P \rightarrow Q% P→Q ¬ ( Q ∧ R ) \lnot(Q \land R) ¬(Q∧R) ¬ ( ¬ R ∧ ¬ S ) \lnot(\lnot R \land \lnot S) ¬(¬R∧¬S) S → ¬ Q S \rightarrow \lnot Q S→¬Q 0 0 0 0 0 0 0 0 0 1 1 11111 0 0 0 0 0 0 1 1 1 0 0 01111 0 0 0 0 0 0 1 1 1 1 1 11111

可见，我们能确定 P , Q P,Q P,Q必然为假，但无法确定 R R R和 S S S的值，因而侦探只能判定男管家和厨师在说谎，但无法判定园丁与杂役谁在说真话。

总结

本文介绍了命题逻辑中的命题等价公式及应用部分，对命题逻辑有深入的了解。

【本文地址】

[离散数学]命题逻辑P

[离散数学]命题逻辑P

今日新闻

推荐新闻