《离散数学课件第一章(第3讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第一章(第3讲).ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4 等价式与蕴涵式等价式与蕴涵式1等价公式等价公式定义定义：如果对两个公式，不论作何种指：如果对两个公式，不论作何种指派，它们真值均相同，则称，是逻辑等价派，它们真值均相同，则称，是逻辑等价的的.并记作：并记作：例：可以证明：例：可以证明：Q P P 原命题原命题 逆反命题逆反命题 列出真值表列出真值表,由真值表得：由真值表得：原命题原命题逆反命题逆反命题P Q PQ QP P F F TTTTF T TTFFT F FFTTT T TTTT由等价定义可知：由等价定义可知：若若，则，则 若若，C，则则下面列出下面列出13组等价公式组等价公式（1）双重否定律）双重否定律：（2）幂等律：）幂等律：
2、；（3）结合律：）结合律：（）（）；）；（）（）；）；（）（）（4）交换律）交换律：；（5）分配律：）分配律：（）（）（）；）；（）（）（）（6）摩根律：）摩根律：（）；（）（7）吸收律：）吸收律：（）；（）（8）蕴含律：）蕴含律：（9）等价律：）等价律：（）（）（10）零律：）零律：；（11）同一律：）同一律：；（12）否定律：）否定律：；（13）逆反律：）逆反律：说明：说明：（1）证明上述）证明上述3组等价公式的方法可用真值表法。组等价公式的方法可用真值表法。（2）、均满足结合律，则在单一用均满足结合律，则在单一用、联结词组成的命题公式中，括号可以省去联结词组成的命题公式中，括号可以省去。
3、2置换规则置换规则定义定义：给定一命题公式：给定一命题公式A，其中，其中P1、P2Pn 是是A中中的原子命题变元，若的原子命题变元，若 （1）用某些命题公式代换）用某些命题公式代换A中的一些原子命题变元中的一些原子命题变元Pi （2）用命题公式）用命题公式Bi代换代换Pi，则必须用，则必须用Bi代换代换A中的所有中的所有Pi 由此而得到的新的命题公式由此而得到的新的命题公式B称为命题公式称为命题公式A的的代换实例代换实例。讨论定义：讨论定义：（1）用命题公式只能代换）用命题公式只能代换原子命题变元原子命题变元，而不能去，而不能去代换分子命题公式代换分子命题公式。（2）要用命题公式）要用命题公式
4、同时代换同时代换同一个原子命题变元同一个原子命题变元。（3）一个命题公式的代换实例有许多个，但不一定）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式都等价于原来的命题公式。例例设设A：（Q）若用（）若用（）代换）代换A中的中的，得得B：（：（）（Q（）是）是A的代换实例的代换实例.而而B：（：（）（Q）不是）不是A的代换实例。的代换实例。例例的代换实例有：（的代换实例有：（），（，（），（）等）等所以，一个命题公式的代换实例有无限个。所以，一个命题公式的代换实例有无限个。3.等价置换等价置换定义定义：给定一命题公式，给定一命题公式，是的任何部分，若是的任何部分，若也是一命题公式
5、，则称也是一命题公式，则称是的子命题公式。是的子命题公式。例：例：（：（）（）的子命题公式有：的子命题公式有：、（、（）、（）、（）、）、（）、（）、（）（）等。等。定理定理：给定一命题公式，：给定一命题公式，是的子公式。是的子公式。设设B是一命题公式，若是一命题公式，若 B，并用，并用B取代取代中的中的，从而生成一新的命题公式，从而生成一新的命题公式B，则，则B。从定理可见：一个命题公式从定理可见：一个命题公式A，经多次取代，所得，经多次取代，所得到的新公式与原公式等价。到的新公式与原公式等价。例：证明：例：证明：（）（）PPPPPPFTTFTFTF定义定义：设公式中有设公式中有n个不同的原
6、子变元个不同的原子变元p1,pn,(n为为正整数正整数)。该变元组的任意一组确定的值（。该变元组的任意一组确定的值（u1,un）称为）称为关于关于p1,pn的一个的一个完全指派完全指派，其中，其中ui或为，或为。或为，或为。4命题公式的永真式、永假式和可满足式命题公式的永真式、永假式和可满足式例：例：定义定义：如果一个命题公式的所有完全指派均使该公：如果一个命题公式的所有完全指派均使该公式取真值，则该公式称为式取真值，则该公式称为永真式或重言式永真式或重言式。如果一个。如果一个命题公式的所有完全指派均使该公式取假值，则该公命题公式的所有完全指派均使该公式取假值，则该公式称为式称为永假式永假式。
7、既不是永真式，又不是永假式，则称。既不是永真式，又不是永假式，则称此命题公式是此命题公式是可满足式可满足式。讨论：讨论：二个永真式的析取、合取、蕴含、等价均为永真式。二个永真式的析取、合取、蕴含、等价均为永真式。5 重言式与蕴含式重言式与蕴含式定义定义：当且仅当：当且仅当是一个永真式，我们称是一个永真式，我们称永真蕴含，永真蕴含，记作：记作：说明：说明：(1)“”读作读作“永真蕴含永真蕴含”，“蕴含蕴含”(2)“”是关系符，是关系符，不为命题公式。不为命题公式。例：例：证明：证明：；P 分析：要证明这两个永真蕴含关系成立，按照永分析：要证明这两个永真蕴含关系成立，按照永真蕴含关系的定义，只需要
8、证明真蕴含关系的定义，只需要证明（）和）和（）为永真式。为永真式。(1)列出真值表证明列出真值表证明 P Q（）（）F F T TF T T TT F T TT T T T（2）用等价公式证明）用等价公式证明 （）（）（）T（）（）（）（）T定理定理 命题公式命题公式的充要条件是的充要条件是为永真式。为永真式。证明：证明：（）充分性：（）充分性：为永真式，即、有相同的真为永真式，即、有相同的真值，所以值，所以。（）必要性：（）必要性：，即、有相同的真值表，所，即、有相同的真值表，所以以为永真式。为永真式。定理定理：设、是二个命题公式：设、是二个命题公式,的充分必要的充分必要条件是条件是 且且。
9、证明：证明：(1)若若，则，则为一永真式为一永真式 由定律：由定律：（）（）（）（）且（）且（）也为一永真式）也为一永真式 即：即：且且成立成立(2)若若 且且，则（，则（）和（）和（）为）为一永真式一永真式.所以所以为一永真式，则为一永真式，则也成立。也成立。此定理把此定理把“”和和“”之间建立了相应的关系。之间建立了相应的关系。下面给出常用的永真蕴含式下面给出常用的永真蕴含式 I1 （）I2 （）I3（）I4 （）I5 （）I6 （）（）（）I7 （）（）（）I8 （）（）（）I9 P I10 I11 （）I12（）I13 （）（）（）注：证明上述永真蕴含式的方法为：把注：证明上述永真蕴含
10、式的方法为：把“”关系符改关系符改为为“”联结词，证明所得的公式为永真式。而证明联结词，证明所得的公式为永真式。而证明永真式又有四种具体方法：永真式又有四种具体方法：(1)真值表法真值表法(2)等价公式法等价公式法（3）假设单条件命题前件为）假设单条件命题前件为 ，若能推导出后件也，若能推导出后件也一定为一定为，则永真蕴含关系成立。，则永真蕴含关系成立。PQPQFFTFTTTFFTTT例：证明例：证明（）证明：在命题公式证明：在命题公式（）中，设前件为中，设前件为 ，则、（，则、（）均为）均为 。为为 ，为为 ，也应为也应为 ，命题公式命题公式（）为为T（）成立成立（4）假设单条件命题后件为）
11、假设单条件命题后件为 F ，若能推导出前件也，若能推导出前件也一定为一定为F，则永真蕴含关系成立。，则永真蕴含关系成立。PQPQFFTFTTTFFTTT 例：证明例：证明（）证明：在命题公式证明：在命题公式（）中，设后件中，设后件为为 ，则为，则为 ，代入前件得代入前件得 (1)若为，则若为，则（）为）为 ；(2)若为，则若为，则（）为）为 ；命题公式命题公式（）为为T（）成立成立 若后件简单则可选用若后件简单则可选用(4)证明；若前件简单则可选用证明；若前件简单则可选用(3)证明。证明。定理定理：给定命题公式、，若：给定命题公式、，若，且，且，则，则。证明：证明：，且，且，（）（）为永真式，）为永真式，由由I6：（：（）（）（），），（）也为永真式；即，）也为永真式；即，成立成立 定理定理：给定一个命题公式、，若：给定一个命题公式、，若,，则，则（）证明：证明：，（）（）为永真式，）为永真式，由条件，若一定为由条件，若一定为 ，则、均为，则、均为 ，（）也为）也为 ，（）为）为 。