离散数学课件第一章(第3讲).ppt

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