离散数学

命题公式与命题公式的分类2

---

djr7208 2026年9月5日 1

0 评论

根据真值表，我们可以总结出以下24个基本等价关系

1. E1：G∨G=G                                              （幂等律）

          E2：G∧G=G

通过列真值表，两者显然成立。

• E3：G∨H=H∨G                                              （交换律）

   E4：G∧H=H∧G

• E5：G∨（H∨S）=（G∨H）∨S                                 (结合律)

E6: G∧(H∧S)=(G∧H)∧S

通过列出真值表可以证明

• E7：G∨1=1                                               （零律）

   E8：G∧0=0

• E9：G∧1=G                                              （同一律）

   E10：G∨0=G

• E11：G∨（H∧S）=（G∨H）∧（G∨S）                        （分配律）

   E12：G∧（H∨S）=（G∧H）∨（G∧S）             

• E13：G∨（G∧H）=G                                        （吸收律）

   E14：G∧（G∨H）=G

列出真值表证明：

G	H	G∨（H∧G）	G∧（G∨H）
0	0	0  0	0  0
0	1	0  0	0  1
1	0	1  0	1  1
1	1	1  1	1  1

• E15：G∧¬G=0                                                （矛盾律）

   E16：G∨¬G=1

• E17：¬（¬G）=G                                              （排中律）
• E18：¬（G∨H）=¬G∧¬H                                   （德摩根律）

E19：¬（G∧H）=¬G∨¬H

1. E20:G→H=¬G∨H                                            （蕴含式）

蕴含式利用真值表证明如下：

G	H	G→H	¬G∨H
0	0	1	1 1
0	1	1	1 1
1	0	0	0 0
1	1	1	0 1

1. E21：G→H=¬H→¬G                                         （假言易位）
2. E22：G⟷ H=（G→H）∧（H→G）（双条件的定义）              （等价式）

               =（¬G∨H）∧（¬H∨G）

1. E23：G⟷ H=¬G⟷ ¬H                                  （等价否定等式）

E23证明：G⟷ H=（G→H）∧（H→G）

                =（¬H→¬G）∧（¬G→¬H）

                =¬G⟷ ¬H

使用假言易位证明

1. E24:（G→H）∧（G→¬H）=¬G                               （归谬论）

E24证明：     （G→H）∧（G→¬H）=¬G  

   （¬H→¬G）∧（H→¬G）

随便令H为0或1，都可发现真正取决 （¬H→¬G）和（H→¬G）的真值的其实是¬G

验证等价关系还能通过文氏图的方式验证，在总体论域中，∧与∩等价，∨与∪等价

代入定理：设G（P1，P2，P3….Pn）是一个命题公式，其中P1，P2，P3，Pn是G的n个命题变元，G1（P1，P2，P3….Pn），G2（P1，P2，P3….Pn）….Gn（P1，P2，P3….Pn）是任意的命题公式，若G为永真公式或永假公式，则可用G1取代P1，以此类推，则

                G（G1，G2，G3…Gn）=G’(P1,P2,P3…Pn)

代表着，永真公式的永真在于连接词带来的永真，与命题变元如何取并无关系，所以可以替换来创造新的永真公式

如：

设G（P，Q）=（P∧（P→Q））→Q为永真公式，另有两任意公式H（P，Q）=P∨¬Q，S（P，Q）=P⟷ Q

G（H，S）=（H∧（H→S））→S=（（P∨¬Q）∧（（P∨¬Q）→（P⟷ Q）））→（P⟷ Q）

则G（H，S）为永真公式成立，下列给出真值表证明

以上证明，其仍然是永真公式

替换定理：设G１是G的子公式，H１是任意的命题公式，在G中凡是出现G１处都以H１替换，由此得到新的命题公式H，

若G１＝H１，则G＝H

即大公式中的小公式与其等价的公式相替换，最终形成的大公式不变

例如，证明（（P∨Q）∧¬（¬P∧（¬Q∨¬R）））∨（¬P∧¬Q）∨（¬P∧¬R）是一个永真公式

（（P∨Q）∧¬（¬P∧（¬Q∨¬R）））∨（¬P∧¬Q）∨（¬P∧¬R）

＝（（P∨Q）∧（P∨（Q∧R）））∨（¬P∧¬Q）∨（¬P∧¬R）

＝（（P∨Q）∧（（P∨Q）∧（P∨R）））∨（¬P∧¬Q）∨（¬P∧¬R）

＝（（P∨Q）∧（（P∨Q）∧（P∨R）））∨¬（P∨Q）∨¬（P∨R）

＝（（P∨Q）∧（（P∨Q）∧（P∨R）））∨¬（（P∨Q）∧（P∨R））

为方便演示，令P∨Q为A，P∨R为B，则上式表示为

（A∧（A∧B））∨¬（A∧B）

＝（（A∧A）∧B）∨¬（Ａ∧Ｂ）

＝（Ａ∧Ｂ）∨¬（Ａ∧Ｂ）

＝１

证毕