《离散数学课件：1-3 公式的等价》由会员分享，可在线阅读，更多相关《离散数学课件：1-3 公式的等价（15页珍藏版）》请在金锄头文库上搜索。
1、 公式的等价公式的等价：若命题公式若命题公式A和和B的所有真值全的所有真值全都相同，都相同， 则称则称A和和B是是等价的等价的或或逻辑相等逻辑相等，记，记作作AB.&AB，当且仅当，当且仅当AB为为重言式重言式.三、公式的等价三、公式的等价如：如： (P Q) ( P Q)的真值全为真，则的真值全为真，则 (P Q) 与与 ( P Q)是是等价的等价的或或逻辑相等逻辑相等. 反之亦然反之亦然.(一一) 公式等价的概念公式等价的概念例例例例1.3.1 1.3.1 试证试证 P Q PQ.证：证：PQ P TTTFFTFFF F TT P QTF TT列出真值表列出真值表P QTF TT可知可知
2、P Q 与与PQ真值相同，真值相同，牢记本题结论：牢记本题结论：PQ P Q.所以所以 P Q PQ.(二二)用真值表证明公式等用真值表证明公式等价价三、公式的等价三、公式的等价证：证：PQTTTFFTFFP QTF FT列出真值表列出真值表P QTF TTP Q与与(PQ) (Q P)真值相同，真值相同，记住这个简单的结论记住这个简单的结论.得证二者等价得证二者等价.Q PTT FT(PQ) (Q P)TF FT例例例例1.3.2 1.3.2 试证试证P Q (PQ) (Q P).用真值表证明公式等价用真值表证明公式等价三、公式的等价三、公式的等价证：证：PQTTTFFTFFP QTF FT
3、列出真值表列出真值表P Q与与(P Q) ( P Q)真值相同，真值相同，建议记住这个结论：这是建议记住这个结论：这是向向 , 的转化式的转化式.得证二者等价得证二者等价.(P Q) ( P Q)TF FT例例例例1.3.3 1.3.3 试证试证P Q (P Q) ( P Q).用真值表证明公式等价用真值表证明公式等价三、公式的等价三、公式的等价1. P对对合合律律2. P P3. P P 幂幂等等律律4. P Q5. P Q交交换换律律 P P PQ PQ P(三三)常用的等价公式常用的等价公式三、公式的等价三、公式的等价6. (P Q) R7. (P Q) R结结合合律律8. P (Q R
4、 )9. P (Q R)分分配配律律10. (P Q)11. (P Q)德德 摩摩 根根律律 P (Q R) P (Q R)(P Q) (P R)(P Q) (P R) P Q P Q常用的等价公式常用的等价公式三、公式的等价三、公式的等价12. P (P Q)13. P (P Q)吸吸收收律律 14. P T15. P F零零律律16. P F17. P T同同一一律律 P P19. P P18. P P否否定定律律 P P T F F T常用的等价公式常用的等价公式三、公式的等价三、公式的等价20. PQ21. (PQ)22. PQ23. P (Q R) 24. P Q 25. P Q P
5、 Q P Q 26. (P Q) (PQ) (Q P) (P Q) ( P Q) P Q (P Q) R QP常用的等价公式常用的等价公式三、公式的等价三、公式的等价例例例例1.3.4 1.3.4 试证试证P (Q R) (P Q) R证：证：P (Q R) P (QR) P ( Q R) ( P Q) R (P Q) R (P Q) RE20德德 摩摩 根根律律结结合合律律E20E20注注P (Q R) (P Q) R三、公式的等价三、公式的等价证：证：注意到注意到P Q (P Q) ( P Q)，有，有例例例例1.3.5 1.3.5 证明证明 (P Q) P QP Q P Q (P Q)
6、( P Q). (1) (P Q) 即即又又(P Q) ( P Q).(P Q) ( P Q). (2)由由(1), (2)两式，得两式，得 (P Q) P Q三、公式的等价三、公式的等价( P Q) (P Q)( P P) ( Q P) ( P Q) ( Q Q)置换置换&子公式子公式：如果：如果X是合式公式是合式公式A的一部分，且的一部分，且X本身本身也是一个合式公式，则称也是一个合式公式，则称X为公式为公式A的子公式的子公式.&置换原理置换原理 (Rule of Replacement)：设设X是合式公是合式公式式A的子公式，且的子公式，且X Y，将，将A中的中的X用用Y来置换，来置换，
7、得到新的公式得到新的公式B，则，则A B.即，如果即，如果则则A B.三、公式的等价三、公式的等价例如例如&(P Q) R中以中以Q P代代P Q ，得，得(P Q) R (Q P) R&或或(P P) Q以以F代代P P ，得，得(P P) Q F Q 置换置换三、公式的等价三、公式的等价&从含义上理解记忆从含义上理解记忆.&对比对比集合的运算律集合的运算律记忆记忆.&同一律、零律、否定律中的同一律、零律、否定律中的F, T分别对比集合分别对比集合中的空集中的空集，全集全集.例如，例如，分分配配律律P (Q R ) (P Q) ( P R) P (Q R ) (P Q) (P R)P (Q
8、R) (P Q) (P R) P (Q R ) (P Q) (P R)德德 摩根摩根律律 (P Q) P Q (P Q) P Q (P Q) P Q (P Q) P Q常用等价公式的记忆常用等价公式的记忆三、公式的等价三、公式的等价例例例例1.3.7 1.3.7 判别下列公式的类型判别下列公式的类型(1)Q ( P Q ) P )(2) ( P P ) (Q Q) R)解：解：(1) Q ( P Q ) P ) Q (Q P)分分配配律律否否定定律律同同一一律律 Q ( Q P)德德 摩摩根根律律结结合合律律否否定定律律 Q ( P P ) (Q P) Q ( F (Q P) T P (Q Q) P T零零律律故故(1)是重言式是重言式三、公式的等价三、公式的等价 F T F(2) ( P P ) (Q Q) R) T (Q Q) R) T ( F R)故故(2)是矛盾式是矛盾式否否定定律律否否定定律律零零律律HW: 1-4习题习题 (4)c; (7)a,c,e,h; (8)1-5习题习题 (1)a, d三、公式的等价三、公式的等价
