离散数学(第12-13)陈瑜

1、2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1 1陈瑜陈瑜Email：2022-2-142022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2 2主要内容主要内容n 命题合适公式与真值表命题合适公式与真值表 1 1）命题常项与命题变项）命题常项与命题变项 2 2）命题公式与赋值）命题公式与赋值 3 3）永真式）永真式 4 4）矛盾式）矛盾式n 命题公式的等价命题公式的等价 1 1）基本等价式）基本等价式 2 2）等价式的判断）等价式的判断 2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3 31.2 1.2 命

2、题合适公式与真值表命题合适公式与真值表n 一个特定的命题是一个一个特定的命题是一个常值命题常值命题，它不是具有它不是具有值值“T”(“1”)“T”(“1”)，就是具有值，就是具有值“F”(“0”)“F”(“0”)。n 而一个任意的没有赋予具体内容的原子命题是而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量一个变量命题，常称它为命题变量( (或命题变或命题变元元) )，该命题变量无具体的真值，该命题变量无具体的真值，它的它的值域是值域是集合集合 T T，F(F(或或00，1)1)。n 当原子命题是命题变元时，当原子命题是命题变元时，其其复合命题也即为复合命题也即为命题变元的

3、命题变元的“函数函数”，且该，且该“函数函数”的值仍为的值仍为“真真”或或“假假”值，这样的函数可形象地称为值，这样的函数可形象地称为“真值函数真值函数”,”,或称为命题公式或称为命题公式, ,此命题公式没此命题公式没有确切真值。有确切真值。2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院4 41.2 1.2 命题合适公式与真值表命题合适公式与真值表n 一个特定的命题是一个常值命题一个特定的命题是一个常值命题，它不是具有它不是具有值值“T”(“1”)“T”(“1”)，就是具有值，就是具有值“F”(“0”)“F”(“0”)。n 而一个任意的没有赋予具体内容的原子命题是

4、而一个任意的没有赋予具体内容的原子命题是一个一个变量命题变量命题，常称它为，常称它为命题变量命题变量( (或或命题变命题变元元) )，该命题变量，该命题变量无具体无具体的真值，的真值，它的它的值域是值域是集合集合 T T，F(F(或或00，1)1)。n 当原子命题是命题变元时，当原子命题是命题变元时，其其复合命题也即为复合命题也即为命题变元的命题变元的“函数函数”，且该，且该“函数函数”的值仍为的值仍为“真真”或或“假假”值，这样的函数可形象地称为值，这样的函数可形象地称为“真值函数真值函数”,”,或称为命题公式或称为命题公式, ,此命题公式没此命题公式没有确切真值。有确切真值。2022-2-

5、142022-2-14计算机科学与工程学院计算机科学与工程学院5 51.2 1.2 命题合适公式与真值表命题合适公式与真值表n 一个特定的命题是一个常值命题一个特定的命题是一个常值命题，它不是具有它不是具有值值“T”(“1”)“T”(“1”)，就是具有值，就是具有值“F”(“0”)“F”(“0”)。n 而一个任意的没有赋予具体内容的原子命题是而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量一个变量命题，常称它为命题变量( (或命题变或命题变元元) )，该命题变量无具体的真值，该命题变量无具体的真值，它的它的值域是值域是集合集合 T T，F(F(或或00，1)1)。n 当原

6、子命题是命题变元时，当原子命题是命题变元时，其其复合命题也即为复合命题也即为命题变元的命题变元的“函数函数”，且该，且该“函数函数”的值仍为的值仍为“真真”或或“假假”值，这样的函数可形象地称为值，这样的函数可形象地称为“真值函数真值函数”,”,或称为或称为命题公式命题公式, ,此命题公式此命题公式没没有确切真值有确切真值。2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院6 6命题公式（合适公式）命题公式（合适公式）n定义定义1-2.1(1-2.1(命题公式命题公式, ,简称简称公式公式) ) 1 1）命题命题变元变元（原子命题变元原子命题变元）本身是一个公式；）本

7、身是一个公式； 2 2）如如P P，Q Q是公式，则是公式，则( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命题公式命题公式仅由仅由有限步有限步使用规则使用规则1-21-2后产生的结果。后产生的结果。 该公式常用符号该公式常用符号G G、H H、等表示。等表示。 注：为简单期间，以后称合适公式为公式。注：为简单期间，以后称合适公式为公式。n为书写和输入计算机及计算方便起见，约定：为书写和输入计算机及计算方便起见，约定： 1 1）最外层括号可以省略）最外层括号可以省略 2 2）按联结词的优先级的括号可以省略）按联结词的优先级

8、的括号可以省略2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院7 7命题公式（合适公式）命题公式（合适公式）n定义定义1-2.1(1-2.1(命题公式命题公式) ) 1 1）命题变元（）命题变元（原子命题变元原子命题变元）本身是一个公式；）本身是一个公式； 2 2）如）如P P，Q Q是公式，则是公式，则( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命题公式仅由有限步使用规则）命题公式仅由有限步使用规则1-21-2后产生的结果。后产生的结果。 该公式常用符号该公式常用符号G G、H H、等表示。

9、等表示。 注：为简单期间，以后称合适公式为公式。注：为简单期间，以后称合适公式为公式。n为书写和输入计算机及计算方便起见，约定：为书写和输入计算机及计算方便起见，约定： 1 1）最外层括号可以省略）最外层括号可以省略 2 2）按联结词的优先级的括号可以省略）按联结词的优先级的括号可以省略2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院8 8命题公式（合适公式）命题公式（合适公式）n定义定义1-2.1(1-2.1(命题公式命题公式) ) 1 1）命题变元（）命题变元（原子命题变元原子命题变元）本身是一个公式；）本身是一个公式； 2 2）如）如P P，Q Q是公式，则是

10、公式，则( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命题公式仅由有限步使用规则）命题公式仅由有限步使用规则1-21-2后产生的结果。后产生的结果。 该公式常用符号该公式常用符号G G、H H、等表示。等表示。 注：为简单期间，以后称合适公式为公式。注：为简单期间，以后称合适公式为公式。n为书写和输入计算机及计算方便起见，为书写和输入计算机及计算方便起见，约定约定： 1 1）最外层括号可以省略）最外层括号可以省略 2 2）按联结词的优先级的括号可以省略）按联结词的优先级的括号可以省略2022-2-142022-2-14计算

11、机科学与工程学院计算机科学与工程学院9 9命题公式（合适公式）命题公式（合适公式）n定义定义1-2.1(1-2.1(命题公式命题公式) ) 1 1）命题变元（）命题变元（原子命题变元原子命题变元）本身是一个公式；）本身是一个公式； 2 2）如）如P P，Q Q是公式，则是公式，则( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命题公式仅由有限步使用规则）命题公式仅由有限步使用规则1-21-2后产生的结果。后产生的结果。 该公式常用符号该公式常用符号G G、H H、等表示。等表示。 注：为简单期间，以后称合适公式为公式。注：为

12、简单期间，以后称合适公式为公式。n为书写和输入计算机及计算方便起见，为书写和输入计算机及计算方便起见，约定约定： 1 1）最外层括号可以省略）最外层括号可以省略 2 2）按联结词的优先级的括号可以省略）按联结词的优先级的括号可以省略 2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1010n 符号串：符号串：(P(QR)(Q(P(QR)(Q(SR)SR)； ( (PQ)PQ)； (P( (P(PQ)(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是等都是命题公式命题公式。 符号串：符号串：(PQ)(PQ)Q)Q)；(PQ(PQ；( (PQ(RP

13、Q(R； PQ PQ。等都不是合法的命题公式。等都不是合法的命题公式。例例2.12.1：定义定义1-2.21-2.2：如公式：如公式A A是公式是公式B B的一部分，则称的一部分，则称A A是是B B的子公式。的子公式。2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1111n 符号串：符号串：(P(QR)(Q(P(QR)(Q(SR)SR)； ( (PQ)PQ)； (P( (P(PQ)(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是命题公式。等都是命题公式。 符号串：符号串：(PQ)(PQ)Q)Q)； (PQ (PQ；( (PQ(RPQ(R；

14、 PQ PQ。等等都不是合法的命题公式都不是合法的命题公式。例例2.12.1：定义定义1-2.21-2.2：如公式：如公式A A是公式是公式B B的一部分，则称的一部分，则称A A是是B B的子公式。的子公式。2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1212n 符号串：符号串：(P(QR)(Q(P(QR)(Q(SR)SR)； ( (PQ)PQ)； (P( (P(PQ)(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是命题公式。等都是命题公式。 符号串：符号串：(PQ)(PQ)Q)Q)；(PQ(PQ；( (PQ(RPQ(R； PQ PQ。

15、等都不是合法的命题公式。等都不是合法的命题公式。例例2.12.1：n定义定义1-2.21-2.2：如公式：如公式A A是公式是公式B B的一部分，则称的一部分，则称A A是是B B的的子公式子公式。2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1313公式的解释与真值表：公式的解释与真值表：n 定义定义1-2.31-2.3 设设P P1 1、P P2 2、P Pn n是出现在公式是出现在公式G G中的所有命题变元中的所有命题变元，指定指定P P1 1、P P2 2、P Pn n的的一组一组真值（如真值（如1 1，0 0，1 1，0 0，1 1），），则则这组真值这

16、组真值称称为为G G的的一个解释一个解释, ,常记为常记为。一般来说，若有个命题变元，则应有一般来说，若有个命题变元，则应有2 2n n个个不同的解释。不同的解释。n 定义定义1-2.4 1-2.4 如果公式如果公式G G在解释下是真的，则在解释下是真的，则称满足称满足G G；如果；如果G G在解释下是假的，则称在解释下是假的，则称弄假弄假G G。将公式。将公式G G在其所有可能解释下在其所有可能解释下的的真值情真值情况列成况列成的表，称为的表，称为G G的真值表的真值表。n个个2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1414公式的解释与真值表：公式的解释与

17、真值表：n 定义定义1-2.3 1-2.3 设设P P1 1、P P2 2、P Pn n是出现在公式是出现在公式G G中的所有命题变元中的所有命题变元，指定指定P P1 1、P P2 2、P Pn n的的一组一组真值（如真值（如1 1，0 0，1 1，0 0，1 1），），则则这组真值这组真值称称为为G G的一个解释的一个解释, ,常记为。常记为。一般来说，若有个命题变元，则应有一般来说，若有个命题变元，则应有2 2n n个个不同的解释。不同的解释。n 定义定义1-2.4 1-2.4 如果公式如果公式G G在解释下是真的，则在解释下是真的，则称满足称满足G G；如果；如果G G在解释下是假的，

18、则称在解释下是假的，则称弄假弄假G G。将公式。将公式G G在其所有可能解释下在其所有可能解释下的的真值情真值情况列成况列成的表，称为的表，称为G G的真值表的真值表。n个个2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1515公式的解释与真值表：公式的解释与真值表：n 定义定义1-2.3 1-2.3 设设P P1 1、P P2 2、P Pn n是出现在公式是出现在公式G G中的所有命题变元中的所有命题变元，指定指定P P1 1、P P2 2、P Pn n的的一组一组真值（如真值（如1 1，0 0，1 1，0 0，1 1），），则则这组真值这组真值称称为为G G的

19、一个解释的一个解释, ,常记为。常记为。一般来说，若有个命题变元，则应有一般来说，若有个命题变元，则应有2 2n n个个不同的解释。不同的解释。n 定义定义1-2.41-2.4 如果公式如果公式G G在解释下是真的，则在解释下是真的，则称称满足满足G G；如果；如果G G在解释下是假的，则称在解释下是假的，则称弄假弄假G G。将。将公式公式G G在其所有可能解释下在其所有可能解释下的的真值情真值情况列成况列成的表，称为的表，称为G G的真值表的真值表。n个个2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1616构造构造公式公式G G1 1：P PQ Q的的真值表如

20、下：真值表如下：P PQ QP PPQPQ0 00 01 11 10 01 11 11 11 10 00 00 01 11 10 01 1例例2.22.2 P PQ Q和和PQPQ的的真值表完全一致真值表完全一致2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1717构造构造公式公式G G1 1：P PQ Q的的真值表如下：真值表如下：P PQ QP PPQPQ0 00 01 11 10 01 11 11 11 10 00 00 01 11 10 01 1例例2.22.2 P PQ Q和和PQPQ的的真值表完全一致真值表完全一致2022-2-142022-2-14计

21、算机科学与工程学院计算机科学与工程学院1818构造构造公式公式G G2 2：( (PQPQ) () () )的真值表的真值表P PQ QPQPQ( (PQPQ) () () )0 00 01 10 0 0 00 01 11 10 0 0 01 10 00 01 1 0 01 11 11 10 0 0 0例例2.32.3该公式对所有可能的解释取值均为该公式对所有可能的解释取值均为0 02022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院1919P PQ QPQPQ( (PQPQ)0 00 01 11 10 01 11 11 11 10 00 01 11 11 11 11

22、1例例2.42.4构造构造公式公式G G3 3 ：( (PQPQ)的真值表的真值表该公式对所有可能的解释取值均为该公式对所有可能的解释取值均为1 12022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2020从这三个真值表可以看到一个非常有趣的从这三个真值表可以看到一个非常有趣的事实：事实： 公式公式G G3 3对所有可能的解释具有对所有可能的解释具有“真真”值值 公式公式G G2 2对所有可能的解释均具有对所有可能的解释均具有“假假”值值 公式公式G G1 1则具有则具有“真真”和和“假假”值值结论：结论：G1：PQG2：(PQ) ()G3 ：(PQ)2022-2-1

23、42022-2-14计算机科学与工程学院计算机科学与工程学院2121定义定义1-2.51-2.5：1 1）公式公式G G3 3称为称为永真公式永真公式( (重言式重言式) )，如果在如果在它的所有解释之下都为它的所有解释之下都为“真真”。2 2）公式）公式G G2 2称为永假公式称为永假公式( (矛盾式，不可满矛盾式，不可满足公式足公式),),如果在它的所有解释之下都为如果在它的所有解释之下都为“假假”。3 3）公式）公式G G1 1称为可满足的，如果它不是永假称为可满足的，如果它不是永假的（即存在解释使公式取值的（即存在解释使公式取值1 1）。）。2022-2-142022-2-14计算机科

24、学与工程学院计算机科学与工程学院2222定义定义1-2.51-2.5：1 1）公式公式G G3 3称为永真公式称为永真公式( (重言式重言式) )，如果在，如果在它的所有解释之下都为它的所有解释之下都为“真真”。2 2）公式公式G G2 2称为称为永假公式永假公式( (矛盾式，不可满矛盾式，不可满足公式足公式),),如果在它的所有解释之下都为如果在它的所有解释之下都为“假假”。3 3）公式）公式G G1 1称为可满足的，如果它不是永假称为可满足的，如果它不是永假的（即存在解释使公式取值的（即存在解释使公式取值1 1）。）。2022-2-142022-2-14计算机科学与工程学院计算机科学与工程

25、学院2323定义定义1-2.51-2.5：1 1）公式公式G G3 3称为永真公式称为永真公式( (重言式重言式) )，如果在，如果在它的所有解释之下都为它的所有解释之下都为“真真”。2 2）公式公式G G2 2称为永假公式称为永假公式( (矛盾式，不可满矛盾式，不可满足公式足公式),),如果在它的所有解释之下都为如果在它的所有解释之下都为“假假”。3 3）公式公式G G1 1称为称为可满足的可满足的，如果它不是永假如果它不是永假的的（即存在解释使公式取值（即存在解释使公式取值1 1）。）。2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2424n1 1）永真式永真

26、式G G的否定的否定G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定G G是永真式。是永真式。 2 2）永真式一定是可满足式永真式一定是可满足式, ,可满足式不一定是永真式。可满足式不一定是永真式。3 3）两个永真式的合取、析取、条件、双条件均为永两个永真式的合取、析取、条件、双条件均为永真式。真式。n这样由简单的重言式，可以推出无数个复杂的重言式。这样由简单的重言式，可以推出无数个复杂的重言式。判定给定公式是否为永真式，永假式或可满足式的问判定给定公式是否为永真式，永假式或可满足式的问题，称为给定公式的判定问题。题，称为给定公式的判定问题。n在逻辑研究和计算机推理以及决策判断时，人们

27、对于在逻辑研究和计算机推理以及决策判断时，人们对于所研究的命题，最关心的莫过于所研究的命题，最关心的莫过于“真真”、“假假”问题，问题，所以永真公式在数理逻辑的研究中占有特殊且重要的所以永真公式在数理逻辑的研究中占有特殊且重要的地位。地位。 永真式的特点：永真式的特点：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2525n1 1）永真式）永真式G G的否定的否定G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定G G是永真式。是永真式。 2 2）永真式一定是可满足式）永真式一定是可满足式, ,可满足式不一定是永真式。可满足式不一定是永真式。3 3）两个永真

28、式的合取、析取、条件、双条件均为永）两个永真式的合取、析取、条件、双条件均为永真式。真式。n这样由简单的重言式，可以推出无数个复杂的重言式。这样由简单的重言式，可以推出无数个复杂的重言式。判定给定公式是否为永真式、永假式或可满足式的问判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的题，称为给定公式的判定问题判定问题。n在逻辑研究和计算机推理以及决策判断时，人们对于在逻辑研究和计算机推理以及决策判断时，人们对于所研究的命题，最关心的莫过于所研究的命题，最关心的莫过于“真真”、“假假”问题，问题，所以永真公式在数理逻辑的研究中占有特殊且重要的所以永真公式在数理逻辑的研究中占有特殊且

29、重要的地位。地位。 永真式的特点：永真式的特点：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2626n1 1）永真式）永真式G G的否定的否定G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定G G是永真式。是永真式。 2 2）永真式一定是可满足式）永真式一定是可满足式, ,可满足式不一定是永真式。可满足式不一定是永真式。3 3）两个永真式的合取、析取、条件、双条件均为永）两个永真式的合取、析取、条件、双条件均为永真式。真式。n这样由简单的重言式，可以推出无数个复杂的重言式。这样由简单的重言式，可以推出无数个复杂的重言式。判定给定公式是否为永真式，永假式或

30、可满足式的问判定给定公式是否为永真式，永假式或可满足式的问题，称为给定公式的判定问题。题，称为给定公式的判定问题。n在逻辑研究和计算机推理以及决策判断时，人们对于在逻辑研究和计算机推理以及决策判断时，人们对于所研究的命题，最关心的莫过于所研究的命题，最关心的莫过于“真真”、“假假”问题，问题，所以永真公式在数理逻辑的研究中占有特殊且重要的所以永真公式在数理逻辑的研究中占有特殊且重要的地位。地位。 永真式的特点：永真式的特点：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2727 命题逻辑的命题逻辑的基本任务基本任务之一，就是找出那些之一，就是找出那些属于永真式的命

31、题公式。属于永真式的命题公式。（1 1）真值表法（简单、直观）真值表法（简单、直观）（2 2）置换（代换，代入）法则）置换（代换，代入）法则 如果公式如果公式A A中的一些变元，用一些公式代入，中的一些变元，用一些公式代入，而且每次出现同一变元时，总用同一公式代入，而且每次出现同一变元时，总用同一公式代入，就可从公式就可从公式A A得到公式得到公式B B，则称公式，则称公式B B为公式为公式A A的的置换（代入）实例（例式）。置换（代入）实例（例式）。置换定理：永真式的任何置换（代入）实例仍是置换定理：永真式的任何置换（代入）实例仍是一个永真式。一个永真式。永真式的判断：永真式的判断：2022

32、-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2828 命题逻辑的基本任务之一，就是找出那些命题逻辑的基本任务之一，就是找出那些属于永真式的命题公式。属于永真式的命题公式。（1 1）真值表法）真值表法（简单、直观）（简单、直观）（2 2）置换（代换，代入）法则）置换（代换，代入）法则 如果公式如果公式A A中的一些变元，用一些公式代入，中的一些变元，用一些公式代入，而且每次出现同一变元时，总用同一公式代入，而且每次出现同一变元时，总用同一公式代入，就可从公式就可从公式A A得到公式得到公式B B，则称公式，则称公式B B为公式为公式A A的的置换（代入）实例（例式）。置换

33、（代入）实例（例式）。置换定理：永真式的任何置换（代入）实例仍是置换定理：永真式的任何置换（代入）实例仍是一个永真式。一个永真式。永真式的判断：永真式的判断：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院2929 命题逻辑的基本任务之一，就是找出那些命题逻辑的基本任务之一，就是找出那些属于永真式的命题公式。属于永真式的命题公式。（1 1）真值表法（简单、直观）真值表法（简单、直观）（2 2）置换（代换，代入）法则）置换（代换，代入）法则 如果公式如果公式A A中的一些变元，用一些公式代入，中的一些变元，用一些公式代入，而且每次出现同一变元时，总用同一公式代入，而且

34、每次出现同一变元时，总用同一公式代入，就可从公式就可从公式A A得到公式得到公式B B，则称公式，则称公式B B为公式为公式A A的的置换置换（代入）（代入）实例实例（例式）。（例式）。置换定理：永真式的任何置换（代入）实例仍是置换定理：永真式的任何置换（代入）实例仍是一个永真式。一个永真式。永真式的判断：永真式的判断：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3030 命题逻辑的基本任务之一，就是找出那些命题逻辑的基本任务之一，就是找出那些属于永真式的命题公式。属于永真式的命题公式。（1 1）真值表法（简单、直观）真值表法（简单、直观）（2 2）置换（代换，

35、代入）法则置换（代换，代入）法则 如果公式如果公式A A中的一些变元，用一些公式代入，中的一些变元，用一些公式代入，而且每次出现同一变元时，总用同一公式代入，而且每次出现同一变元时，总用同一公式代入，就可从公式就可从公式A A得到公式得到公式B B，则称公式，则称公式B B为公式为公式A A的的置换（代入）实例（例式）。置换（代入）实例（例式）。n 置换定理置换定理：永真式的任何置换（代入）实例仍：永真式的任何置换（代入）实例仍是一个永真式。是一个永真式。永真式的判断：永真式的判断：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3131 例如：例如： PQPQ P

36、 P（永真式永真式） 对上式中的对上式中的P P，用（，用（RSRS）代入，）代入， 对对Q Q，用（，用（M M N N）代入后得到：）代入后得到： （RSRS）（M M N N）（RSRS） 该公式也是一个永真式该公式也是一个永真式（3 3）公式推演法（等价变换、替换（取代）规）公式推演法（等价变换、替换（取代）规（范）则）（范）则） 具体方法在下节中介绍具体方法在下节中介绍永真式的判断：永真式的判断：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3232 例如：例如： PQPQ P P（永真式）（永真式） 对上式中的对上式中的P P，用（，用（RSRS）代入

37、，）代入， 对对Q Q，用（，用（M M N N）代入后得到：）代入后得到： （RSRS）（M M N N）（RSRS） 该公式也是一个永真式该公式也是一个永真式（3 3）公式推演法）公式推演法（等价变换、替换（取代）规（等价变换、替换（取代）规（范）则）。（范）则）。 具体方法在下节中介绍具体方法在下节中介绍永真式的判断：永真式的判断：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3333n 定义定义1-3.11-3.1设设G G、H H是是公式，公式，如果在如果在任意解释任意解释下，下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是是

38、等价等价的的 ，记记作作G GH H。n 定理定理1-3.21-3.2公式公式G G、H H等价的充分必要条件是公式等价的充分必要条件是公式 G GH H是永真公式。是永真公式。 此定理是从另一角度来看待等价性此定理是从另一角度来看待等价性n 等价式的性质:1 1）自反性：）自反性：A A A A2 2）对称性：若）对称性：若 A A B B，则，则 B B A A3 3）可传递性）可传递性: :若若 A A B B，B B C C，则，则A A C C1.3 1.3 命题公式的等价命题公式的等价2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3434n 定义定义1

39、-3.11-3.1设设G G、H H是是公式，公式，如果在任意解释下，如果在任意解释下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是等价的是等价的 ，记记作作G GH H。n 定理定理1-3.21-3.2公式公式G G、H H等价的等价的充分必要条件充分必要条件是公式是公式 G GH H是永真公式。是永真公式。 此定理是从另一角度来看待等价性此定理是从另一角度来看待等价性n 等价式的性质:1 1）自反性：）自反性：A A A A2 2）对称性：若）对称性：若 A A B B，则，则 B B A A3 3）可传递性）可传递性: :若若 A A B B，B B C C，

40、则，则A A C C1.3 1.3 命题公式的等价命题公式的等价2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3535n 定理定理1-3.21-3.2公式公式G G、H H等价的充分必要条件是公式等价的充分必要条件是公式 G GH H是永真公式。是永真公式。 证明：证明： 如果如果G GH H，根据定义对任何解释公式根据定义对任何解释公式G G和和H H取相同的真值，因此取相同的真值，因此G GH H恒取真值恒取真值1 1，即，即G GH H是是永真式。永真式。 反过来，如果反过来，如果G GH H是永真式，根据联结词是永真式，根据联结词的定义，对任何解释的定义，

41、对任何解释G G和和H H必取相同的真值，必取相同的真值，从而从而G GH H成立。成立。 1.3 1.3 命题公式的等价命题公式的等价2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3636n 定理定理1-3.21-3.2公式公式G G、H H等价的充分必要条件是公式等价的充分必要条件是公式 G GH H是永真公式。是永真公式。 证明：证明： 如果如果G GH H，根据定义对任何解释公式根据定义对任何解释公式G G和和H H取相同的真值，因此取相同的真值，因此G GH H恒取真值恒取真值1 1，即，即G GH H是是永真式。永真式。 反过来，如果反过来，如果G G

42、H H是永真式，根据联结词是永真式，根据联结词的定义，对任何解释的定义，对任何解释G G和和H H必取相同的真值，必取相同的真值，从而从而G GH H成立。成立。 1.3 1.3 命题公式的等价命题公式的等价2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3737n 定理定理1-3.21-3.2公式公式G G、H H等价的充分必要条件是公式等价的充分必要条件是公式 G GH H是永真公式。是永真公式。 证明：证明： 如果如果G GH H，根据定义对任何解释公式根据定义对任何解释公式G G和和H H取相同的真值，因此取相同的真值，因此G GH H恒取真值恒取真值1 1

43、，即，即G GH H是是永真式。永真式。 反过来，如果反过来，如果G GH H是永真式，根据联结词是永真式，根据联结词的定义，对任何解释的定义，对任何解释G G和和H H必取相同的真值，必取相同的真值，从而从而G GH H成立。成立。 1.3 1.3 命题公式的等价命题公式的等价 这个定理建立了这个定理建立了和和之间转换的关之间转换的关系系。 然而，如果直接用这个定理来证明两然而，如果直接用这个定理来证明两个公式等价，常常会使得证明变得更加繁个公式等价，常常会使得证明变得更加繁琐！琐！2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3838n 定义定义1-3.11-

44、3.1设设G G、H H是是公式，公式，如果在任意解释下，如果在任意解释下，G G与与H H的的真值相同，则称公式真值相同，则称公式G G、H H是等价的是等价的 ，记记作作G GH H。n 定理定理1-3.21-3.2公式公式G G、H H等价的充分必要条件是公式等价的充分必要条件是公式 G GH H是永真公式。是永真公式。 此定理是从另一角度来看待等价性此定理是从另一角度来看待等价性n 等价式的性质等价式的性质: :1 1）自反性：）自反性：A A A A2 2）对称性：若）对称性：若 A A B B，则，则 B B A A3 3）可传递性）可传递性: :若若 A A B B，B B C

45、C，则，则A A C C1.3 1.3 命题公式的等价命题公式的等价2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院3939n 首先首先，双条件词，双条件词“”是一种逻辑联结词，公式是一种逻辑联结词，公式G GH H是命题公式，其中是命题公式，其中“”是一种逻辑运算，是一种逻辑运算，G GH H的结果仍是一个命题公式的结果仍是一个命题公式。n 而逻辑等价而逻辑等价“”则是描述了两个公式则是描述了两个公式G G与与H H之间之间的一种逻辑等价关系，的一种逻辑等价关系，G GH H表示表示“命题公式命题公式G G等等价价于命题公式于命题公式H H”，G GH H 的结果

46、不是命题公式。的结果不是命题公式。n 其次，如果要求用计算机来判断命题公式其次，如果要求用计算机来判断命题公式G G、H H是是否逻辑等价，即否逻辑等价，即G GH H那是办不到的那是办不到的，然而计算机然而计算机却可却可“计算计算”公式公式G GH H是否是永真公式。是否是永真公式。 “” ” 与与“”的区别的区别2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院4040n 首先，双条件词首先，双条件词“”是一种逻辑联结词，公式是一种逻辑联结词，公式G GH H是命题公式，其中是命题公式，其中“”是一种逻辑运算，是一种逻辑运算，G GH H的结果仍是一个命题公式的结

47、果仍是一个命题公式。n 而逻辑等价而逻辑等价“”则是描述了两个公式则是描述了两个公式G G与与H H之间之间的一种逻辑等价关系，的一种逻辑等价关系，G GH H表示表示“命题公式命题公式G G等等价价于命题公式于命题公式H H”，G GH H 的结果不是命题公式的结果不是命题公式。n 其次，如果要求用计算机来判断命题公式其次，如果要求用计算机来判断命题公式G G、H H是是否逻辑等价，即否逻辑等价，即G GH H那是办不到的那是办不到的，然而计算机然而计算机却可却可“计算计算”公式公式G GH H是否是永真公式。是否是永真公式。 “” ” 与与“”的区别的区别2022-2-142022-2-1

48、4计算机科学与工程学院计算机科学与工程学院4141n 首先，双条件词首先，双条件词“”是一种逻辑联结词，公式是一种逻辑联结词，公式G GH H是命题公式，其中是命题公式，其中“”是一种逻辑运算，是一种逻辑运算，G GH H的结果仍是一个命题公式的结果仍是一个命题公式。n 而逻辑等价而逻辑等价“”则是描述了两个公式则是描述了两个公式G G与与H H之间之间的一种逻辑等价关系，的一种逻辑等价关系，G GH H表示表示“命题公式命题公式G G等等价价于命题公式于命题公式H H”，G GH H 的结果不是命题公式。的结果不是命题公式。n 其次其次，如果要求用计算机来判断命题公式，如果要求用计算机来判断

49、命题公式G G、H H是是否逻辑等价，即否逻辑等价，即G GH H那是办不到的那是办不到的，然而计算机然而计算机却可却可“计算计算”公式公式G GH H是否是永真公式。是否是永真公式。 “” ” 与与“”的区别：的区别：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院4242基本等价式基本等价式命题定律命题定律 EquivalenceEquivalence： 设设G G，H H，S S是任何的公式，则：是任何的公式，则：1 1: :(G(G H)H)(GH)(HG)(GH)(HG)( (等价等价) ) 2 2：(GH) (GH) ( (GH) GH) ( (蕴涵蕴涵

50、) ) 3 3：GG GG G (G (幂等律幂等律) )4 4：GG GG G G5 5：GH GH HG (HG (交换律交换律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (结合律结合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院4343基本等价式基本等价式命题定律命题定律 EquivalenceEquivalence： 设设G G，H H，

51、S S是任何的公式，则：是任何的公式，则：1 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等价等价) )2 2：(GH) (GH) ( (GH) GH) ( (蕴涵蕴涵) )3 3：GG GG G G ( (幂等律幂等律) )4 4：GG GG G G5 5：GH GH HG (HG (交换律交换律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (结合律结合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 20

52、22-2-142022-2-14计算机科学与工程学院计算机科学与工程学院4444基本等价式基本等价式命题定律命题定律 EquivalenceEquivalence： 设设G G，H H，S S是任何的公式，则：是任何的公式，则：1 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等价等价) )2 2：(GH) (GH) ( (GH) GH) ( (蕴涵蕴涵) )3 3：GG GG G (G (幂等律幂等律) )4 4：GG GG G G5 5：GH GH HG HG ( (交换律交换律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (结

53、合律结合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院4545基本等价式基本等价式命题定律命题定律 EquivalenceEquivalence： 设设G G，H H，S S是任何的公式，则：是任何的公式，则：1 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等价等价) )2 2：(GH) (GH) ( (GH) GH) ( (蕴涵蕴涵) )3 3：GG GG G (G (幂等

54、律幂等律) )4 4：GG GG G G5 5：GH GH HG (HG (交换律交换律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (结合律结合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院4646基本等价式基本等价式命题定律命题定律 EquivalenceEquivalence： 设设G G，H H，S S是任何的公式，则：是任何的公式，则：1

55、 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等价等价) )2 2：(GH) (GH) ( (GH) GH) ( (蕴涵蕴涵) )3 3：GG GG G (G (幂等律幂等律) )4 4：GG GG G G5 5：GH GH HG (HG (交换律交换律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (结合律结合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G G ( (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14计算机科学与工

56、程学院计算机科学与工程学院47471111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G( (同一律同一律) )1414：GTGT G G 1515：GTGT T T( (零律零律) )1616：GFGF F F 1717：GGG G T (T (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (双重否定律双重否定律) )2020：（：（GH)S GH)S G G（HSHS） （输出律）（输出律）2121：（：（G G H

57、H）( (GH)(GGH)(GH) (H) (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) )2424： (GH) (GH) GGH H。基本等价式（续）：基本等价式（续）：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院48481111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G( (同一律同一律) )1414：

58、GTGT G G 1515：GTGT T T( (零律零律) )1616：GFGF F F 1717：GGG G T (T (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (双重否定律双重否定律) )2020：（：（GH)S GH)S G G（HSHS） （输出律）（输出律）2121：（：（G G H H）( (GH)(GGH)(GH) (H) (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) )2424： (GH) (GH) GGH

59、 H。基本等价式（续）：基本等价式（续）：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院49491111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G( (同一律同一律) )1414：GTGT G G 1515：GTGT T T( (零律零律) )1616：GFGF F F 1717：GGG G T (T (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (双重否定律双重否定律) )2020：（

60、：（GH)S GH)S G G（HSHS） （输出律）（输出律）2121：（：（G G H H）( (GH)(GGH)(GH) (H) (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) )2424： (GH) (GH) GGH H。基本等价式（续）：基本等价式（续）：2022-2-142022-2-14计算机科学与工程学院计算机科学与工程学院50501111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (