离散数学--命题逻辑分析课件

高等学校高等学校21世纪教材世纪教材7/8/20241高等学校21世纪教材离散数学8/13/20231第一章第一章 命题逻辑命题逻辑命命命命题题题题逻逻逻逻辑辑辑辑，也也也也称称称称命命命命题题题题演演演演算算算算，记记记记为为为为LsLsLsLs。它它它它与与与与谓谓谓谓词词词词逻逻逻逻辑辑辑辑构构构构成成成成数数数数理理理理逻逻逻逻辑辑辑辑的的的的基基基基础础础础，而而而而命命命命题题题题逻逻逻逻辑辑辑辑又又又又是是是是谓谓谓谓词词词词逻逻逻逻辑辑辑辑的的的的基基基基础础础础。数数数数理理理理逻逻逻逻辑辑辑辑是是是是用用用用数数数数学学学学方方方方法法法法即即即即通通通通过过过过引引引引入入入入表表表表意意意意符符符符号号号号研研研研究究究究推推推推理理理理的的的的学学学学问问问问。因因因因此此此此，数数数数理理理理逻逻逻逻辑辑辑辑又又又又名为符号逻辑。名为符号逻辑。名为符号逻辑。名为符号逻辑。命命命命题题题题逻逻逻逻辑辑辑辑是是是是研研研研究究究究由由由由命命命命题题题题为为为为基基基基本本本本单单单单位位位位构构构构成成成成的的的的前前前前提和结论之间的可推导关系。提和结论之间的可推导关系。提和结论之间的可推导关系。提和结论之间的可推导关系。退出退出第一章命题逻辑命题逻辑，也称命题演算，记为Ls。它与谓词逻1.1 1.1 命题与联结词命题与联结词命题与联结词命题与联结词1.2 1.2 命题变元和合式公式命题变元和合式公式命题变元和合式公式命题变元和合式公式1.3 1.3 公式分类与等价公式公式分类与等价公式公式分类与等价公式公式分类与等价公式1.4 1.4 对偶式与蕴涵式对偶式与蕴涵式对偶式与蕴涵式对偶式与蕴涵式1.5 1.5 联结词的扩充与功能完全组联结词的扩充与功能完全组联结词的扩充与功能完全组联结词的扩充与功能完全组1.6 1.6 公式标准型公式标准型公式标准型公式标准型范式范式范式范式1.7 1.7 公式的主范式公式的主范式公式的主范式公式的主范式1.8 1.8 命题逻辑的推理理论命题逻辑的推理理论命题逻辑的推理理论命题逻辑的推理理论1.1 命题与联结词1.1 命题与联结词命题与联结词.命题的概念命题的概念命题的概念命题的概念所所所所谓谓谓谓命命命命题题题题，是是是是指指指指具具具具有有有有非非非非真真真真必必必必假假假假的的的的陈陈陈陈述述述述句句句句。而而而而疑疑疑疑问问问问句句句句、祈祈祈祈使使使使句句句句和和和和感感感感叹叹叹叹句句句句等等等等因因因因都都都都不不不不能能能能判判判判断断断断其其其其真真真真假假假假，故故故故都都都都不不不不是是是是命命命命题题题题。命命命命题题题题仅仅仅仅有有有有两两两两种种种种可可可可能能能能的的的的真真真真值值值值真真真真和和和和假假假假，且且且且二二二二者者者者只只只只能能能能居居居居其其其其一一一一。真真真真用用用用1 1 1 1或或或或T T T T表表表表示示示示，假假假假用用用用0 0 0 0或或或或F F F F表表表表示示示示。由由由由于于于于命命命命题题题题只只只只有有有有两两两两种种种种真真真真值值值值，所所所所以以以以称称称称这这这这种种种种逻逻逻逻辑辑辑辑为为为为二二二二值值值值逻逻逻逻辑辑辑辑。命命命命题题题题的的的的真真真真值值值值是是是是具具具具有有有有客客客客观观观观性性性性质的，而不是由人的主观决定的。质的，而不是由人的主观决定的。质的，而不是由人的主观决定的。质的，而不是由人的主观决定的。1.1 命题与联结词.命题的概念如果一陈述句再也不能分解成更为简单的语句，由如果一陈述句再也不能分解成更为简单的语句，由如果一陈述句再也不能分解成更为简单的语句，由如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基它构成的命题称为原子命题。原子命题是命题逻辑的基它构成的命题称为原子命题。原子命题是命题逻辑的基它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。本单位。本单位。本单位。命命命命题题题题分分分分为为为为两两两两类类类类，第第第第一一一一类类类类是是是是原原原原子子子子命命命命题题题题，原原原原子子子子命命命命题题题题用用用用大大大大写英文字母写英文字母写英文字母写英文字母P P，Q Q，R R及其带下标的及其带下标的及其带下标的及其带下标的P Pi i，Q Qi i，R Ri i，表示。表示。表示。表示。第第第第二二二二类类类类是是是是复复复复合合合合命命命命题题题题，它它它它由由由由原原原原子子子子命命命命题题题题、命命命命题题题题联联联联结结结结词词词词和和和和圆括号组成。圆括号组成。圆括号组成。圆括号组成。如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为.命题联结词命题联结词定义定义定义定义1.1.11.1.1 设设设设P P表表表表示示示示一一一一个个个个命命命命题题题题，由由由由命命命命题题题题联联联联结结结结词词词词和和和和命命命命题题题题P P连连连连接接接接成成成成P P，称称称称P P为为为为P P的的的的否否否否定定定定式式式式复复复复合合合合命命命命题题题题，P P读读读读“非非非非P”P”。称称称称为为为为否否否否定定定定联联联联结结结结词词词词。P P是是是是真真真真，当当当当且且且且仅仅仅仅当当当当P P为为为为假假假假；P P是是是是假假假假，当当当当且且且且仅仅仅仅当当当当P P为为为为真真真真。否否否否定定定定联联联联结结结结词词词词“”的的的的定定定定义义义义可可可可由表由表由表由表1.1.11.1.1表示之。表示之。表示之。表示之。.命题联结词离散数学-命题逻辑分析课件由由于于“否否定定”修修改改了了命命题题，它它是是对对单单个个命命题题进进行行操操作作，称称它它为为一一元元联联结词结词。由于“否定”修改了命题，它是对单个命题进行操作，称它为一元定义定义定义定义1.1.21.1.2设设设设P P和和和和QQ为为为为两两两两个个个个命命命命题题题题，由由由由命命命命题题题题联联联联结结结结词词词词将将将将P P和和和和QQ连连连连接接接接成成成成P PQQ，称称称称P PQQ为为为为命命命命题题题题P P和和和和QQ的的的的合合合合取取取取式式式式复复复复合合合合命命命命题题题题，P PQQ读读读读做做做做“P“P与与与与Q”Q”，或或或或“P“P且且且且Q”Q”。称称称称为合取联结词。为合取联结词。为合取联结词。为合取联结词。当当当当且且且且仅仅仅仅当当当当P P和和和和QQ的的的的真真真真值值值值同同同同为为为为真真真真，命命命命题题题题P PQQ的的的的真真真真值值值值才才才才为为为为真真真真；否否否否则则则则，P PQQ的的的的真真真真值值值值为为为为假假假假。合合合合取取取取联联联联结结结结词词词词的的的的定定定定义由表义由表义由表义由表1.1.21.1.2表示之。表示之。表示之。表示之。定义1.1.2设P和Q为两个命题，由命题联结词将P和Q离散数学-命题逻辑分析课件定义定义定义定义1.1.31.1.3 设设设设P P和和和和QQ为为为为两两两两个个个个命命命命题题题题，由由由由命命命命题题题题联联联联结结结结词词词词把把把把P P和和和和QQ连连连连接接接接成成成成P PQQ，称称称称P PQQ为为为为命命命命题题题题P P和和和和QQ的的的的析析析析取取取取式式式式复复复复合合合合命命命命题题题题，P PQQ读读读读做做做做“P“P或或或或Q”Q”。称称称称为为为为析析析析取取取取联联联联结结结结词词词词。当当当当且且且且仅仅仅仅当当当当P P和和和和QQ的的的的真真真真值值值值同同同同为为为为假假假假，P PQQ的的的的真真真真值值值值为为为为假假假假；否否否否则则则则，P PQQ的的的的真真真真值值值值为为为为真真真真。析析析析取取取取联联联联结结结结词词词词的的的的定定定定义义义义由由由由表表表表1.1.31.1.3表示之。表示之。表示之。表示之。定义1.1.3设P和Q为两个命题，由命题联结词把P和Q连离散数学-命题逻辑分析课件由由由由定定定定义义义义可可可可知知知知，析析析析取取取取联联联联结结结结词词词词表表表表示示示示“可可可可兼兼兼兼或或或或”，“不不不不可可可可兼或兼或兼或兼或”另有别的联结词定义之。另有别的联结词定义之。另有别的联结词定义之。另有别的联结词定义之。与与与与合合合合取取取取联联联联结结结结词词词词一一一一样样样样，使使使使用用用用析析析析取取取取联联联联结结结结词词词词时时时时，也也也也不不不不要要要要求求求求两命题间一定有任何关系，有关例子就不再给出了。两命题间一定有任何关系，有关例子就不再给出了。两命题间一定有任何关系，有关例子就不再给出了。两命题间一定有任何关系，有关例子就不再给出了。由定义可知，析取联结词表示“可兼或”，“不可兼或”另有别的联定义定义定义定义1.1.41.1.4 设设设设P P和和和和QQ为为为为两两两两个个个个命命命命题题题题，由由由由命命命命题题题题联联联联结结结结词词词词把把把把P P和和和和QQ连连连连接接接接成成成成PQPQ，称称称称PQPQ为为为为命命命命题题题题P P和和和和QQ的的的的条条条条件件件件式式式式复复复复合合合合命命命命题题题题，简简简简称称称称条条条条件件件件命命命命题题题题。PQPQ读读读读做做做做“P“P条条条条件件件件Q”Q”或或或或者者者者“若若若若P P则则则则Q”Q”。称。称。称。称为条件联结词。为条件联结词。为条件联结词。为条件联结词。当当当当P P的的的的真真真真值值值值为为为为真真真真而而而而QQ的的的的真真真真值值值值为为为为假假假假时时时时，命命命命题题题题PQPQ的的的的真真真真值值值值为为为为假假假假；否否否否则则则则，PQPQ的的的的真真真真值值值值为为为为真真真真。条件联结词条件联结词条件联结词条件联结词的定义由表的定义由表的定义由表的定义由表1.1.41.1.4表示之。表示之。表示之。表示之。定义1.1.4设P和Q为两个命题，由命题联结词把P和Q连离散数学-命题逻辑分析课件在在在在条条条条件件件件命命命命题题题题PQPQ中中中中，命命命命题题题题P P称称称称为为为为PQPQ的的的的前前前前件件件件或或或或前前前前提提提提，命命命命题题题题QQ称称称称为为为为PQPQ的的的的后后后后件件件件或或或或结结结结论论论论。条条条条件件件件命命命命题题题题PQPQ有有有有多多多多种种种种方方方方式陈述：式陈述：式陈述：式陈述：“如如如如果果果果P P，那那那那么么么么Q”Q”；“P“P仅仅仅仅当当当当Q”Q”；“Q“Q每每每每当当当当P”P”；“P“P是是是是QQ的充分条件的充分条件的充分条件的充分条件”；“Q“Q是是是是P P的必要条件的必要条件的必要条件的必要条件”等。等。等。等。在条件命题PQ中，命题P称为PQ的前件或前提，命题Q称为在在在在日日日日常常常常生生生生活活活活中中中中，用用用用条条条条件件件件式式式式表表表表示示示示前前前前提提提提和和和和结结结结论论论论之之之之间间间间的的的的因因因因果果果果或或或或实实实实质质质质关关关关系系系系，如如如如例例例例1.1.41.1.4中中中中的的的的，这这这这种种种种条条条条件件件件式式式式称称称称为为为为形形形形式式式式条条条条件件件件命命命命题题题题。然然然然而而而而在在在在命命命命题题题题逻逻逻逻辑辑辑辑中中中中，一一一一个个个个条条条条件件件件式式式式的的的的前前前前提提提提并并并并不不不不要要要要求求求求与与与与结结结结论论论论有有有有任任任任何何何何关关关关系系系系，这这这这种种种种条条条条件件件件式式式式称称称称为为为为实实实实质质质质条条条条件件件件命命命命题题题题。采采采采用用用用实实实实质质质质条条条条件件件件式式式式作作作作定定定定义义义义，不不不不单单单单是是是是出出出出于于于于“善善善善意意意意推推推推断断断断”，主主主主要要要要是是是是因因因因为为为为前前前前提提提提与与与与结结结结论论论论间间间间有有有有无无无无因因因因果果果果和和和和实实实实质质质质关关关关系系系系难难难难以以以以区区区区分分分分，而且实质条件式已包含了形式条件式，更便于应用。而且实质条件式已包含了形式条件式，更便于应用。而且实质条件式已包含了形式条件式，更便于应用。而且实质条件式已包含了形式条件式，更便于应用。在日常生活中，用条件式表示前提和结论之间的因果或实质关系，如定义定义定义定义1.1.51.1.5 令令令令P P、QQ是是是是两两两两个个个个命命命命题题题题，由由由由命命命命题题题题联联联联结结结结词词词词把把把把P P和和和和QQ连连连连接接接接成成成成P P QQ，称称称称P P QQ为为为为命命命命题题题题P P和和和和QQ的的的的双双双双条条条条件件件件式式式式复复复复合合合合命命命命题题题题，简简简简称称称称双双双双条条条条件件件件命命命命题题题题，P P QQ读读读读做做做做“P“P当当当当且且且且仅仅仅仅当当当当Q”Q”，或或或或“P“P等价等价等价等价Q”Q”。称。称。称。称为双条件联结词。为双条件联结词。为双条件联结词。为双条件联结词。当当当当P P和和和和QQ的的的的真真真真值值值值相相相相同同同同时时时时，P P QQ的的的的真真真真值值值值为为为为真真真真；否否否否则则则则，P P QQ的的的的真真真真值值值值为为为为假假假假。双双双双条条条条件件件件联联联联结结结结词词词词的的的的定定定定义义义义由由由由表表表表1.1.51.1.5表表表表示之。示之。示之。示之。定义1.1.5令P、Q是两个命题，由命题联结词把P和Q连离散数学-命题逻辑分析课件在在在在本本本本节节节节结结结结束束束束时时时时，应应应应强强强强调调调调指指指指出出出出的的的的是是是是：复复复复合合合合命命命命题题题题的的的的真真真真值值值值只只只只取取取取决决决决于于于于各各各各原原原原子子子子命命命命题题题题的的的的真真真真值值值值，而而而而与与与与它它它它们们们们的的的的内内内内容容容容、含含含含义义义义无无无无关关关关，与与与与原原原原子子子子命命命命题题题题之之之之间间间间是是是是否否否否有有有有关关关关系系系系无无无无关关关关。理理理理解解解解和和和和掌掌掌掌握握握握这这这这一一一一点是至关重要的，请读者认真去领会。点是至关重要的，请读者认真去领会。点是至关重要的，请读者认真去领会。点是至关重要的，请读者认真去领会。在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命1.2 命题变元和合式公式命题变元和合式公式.命题变元命题变元在在在在命命命命题题题题逻逻逻逻辑辑辑辑中中中中，命命命命题题题题又又又又有有有有命命命命题题题题常常常常元元元元和和和和命命命命题题题题变变变变元元元元之之之之分分分分。一一一一个个个个确确确确定定定定的的的的具具具具体体体体的的的的命命命命题题题题，称称称称为为为为命命命命题题题题常常常常元元元元；一一一一个个个个不不不不确确确确定定定定的的的的泛泛泛泛指指指指的的的的任任任任意意意意命命命命题题题题，称称称称为为为为命命命命题题题题变变变变元元元元。显显显显然然然然，命命命命题题题题变变变变元元元元不不不不是是是是命命命命题题题题，只只只只有有有有用用用用一一一一个个个个特特特特定定定定的的的的命命命命题题题题取取取取代代代代才才才才能能能能确确确确定定定定它它它它的的的的真真真真值值值值：真或假。这时也说对该命题变元指派真值。真或假。这时也说对该命题变元指派真值。真或假。这时也说对该命题变元指派真值。真或假。这时也说对该命题变元指派真值。1.2 命题变元和合式公式.命题变元命题常元和命题变元均可用字母命题常元和命题变元均可用字母命题常元和命题变元均可用字母命题常元和命题变元均可用字母P P等表示。由于在等表示。由于在等表示。由于在等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，命题逻辑中并不关心具体命题的涵义，只关心其真值，命题逻辑中并不关心具体命题的涵义，只关心其真值，命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下：因此，可以形式地定义它们如下：因此，可以形式地定义它们如下：因此，可以形式地定义它们如下：定义定义定义定义1.2.11.2.1 以真或以真或以真或以真或1 1、假或、假或、假或、假或0 0为其变域的变元，称为为其变域的变元，称为为其变域的变元，称为为其变域的变元，称为命题变元；真或命题变元；真或命题变元；真或命题变元；真或1 1、假或、假或、假或、假或0 0称为命题常元。称为命题常元。称为命题常元。称为命题常元。命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关2.2.合式公式合式公式合式公式合式公式通通通通常常常常把把把把含含含含有有有有命命命命题题题题变变变变元元元元的的的的断断断断言言言言称称称称为为为为命命命命题题题题公公公公式式式式。但但但但这这这这没没没没能能能能指指指指出出出出命命命命题题题题公公公公式式式式的的的的结结结结构构构构，因因因因为为为为不不不不是是是是所所所所有有有有由由由由命命命命题题题题变变变变元元元元、联联联联结结结结词词词词和和和和括括括括号号号号所所所所组组组组成成成成的的的的字字字字符符符符串串串串都都都都能能能能成成成成为为为为命命命命题题题题公公公公式式式式。为为为为此此此此常常常常使使使使用用用用归归归归纳纳纳纳定定定定义义义义命命命命题题题题公公公公式式式式，以以以以便便便便构构构构成成成成的的的的公公公公式式式式有有有有规规规规则则则则可可可可循循循循。由这种定义产生的公式称为合式公式。由这种定义产生的公式称为合式公式。由这种定义产生的公式称为合式公式。由这种定义产生的公式称为合式公式。定义定义定义定义1.2.21.2.2 单单单单个个个个命命命命题题题题变变变变元元元元和和和和命命命命题题题题常常常常元元元元称称称称为为为为原原原原子子子子命命命命题题题题公式，简称原子公式。公式，简称原子公式。公式，简称原子公式。公式，简称原子公式。2.合式公式定义定义定义定义1.2.31.2.3 合式公式是由下列规则生成的公式：合式公式是由下列规则生成的公式：合式公式是由下列规则生成的公式：合式公式是由下列规则生成的公式：单个原子公式是合式公式。单个原子公式是合式公式。单个原子公式是合式公式。单个原子公式是合式公式。若若若若A A是是是是一一一一个个个个合合合合式式式式公公公公式式式式，则则则则(A)A)也也也也是是是是一一一一个个个个合合合合式式式式公公公公式式式式。若若若若A A、B B是是是是合合合合式式式式公公公公式式式式，则则则则(A(AB)B)、(A(AB)B)、(AB)(AB)和和和和(A(A B)B)都是合式公式。都是合式公式。都是合式公式。都是合式公式。只只只只有有有有有有有有限限限限次次次次使使使使用用用用、和和和和生生生生成成成成的的的的公公公公式式式式才才才才是是是是合合合合式式式式公式。公式。公式。公式。定义1.2.3合式公式是由下列规则生成的公式：当当当当合合合合式式式式公公公公式式式式比比比比较较较较复复复复杂杂杂杂时时时时，常常常常常常常常使使使使用用用用很很很很多多多多圆圆圆圆括括括括号号号号，为为为为了了了了减减减减少少少少圆圆圆圆括号的使用量，可作以下约定：括号的使用量，可作以下约定：括号的使用量，可作以下约定：括号的使用量，可作以下约定：规定联结词的优先级由高到低的次序为：规定联结词的优先级由高到低的次序为：规定联结词的优先级由高到低的次序为：规定联结词的优先级由高到低的次序为：l l、相同的联结词按从左至右次序计算时，圆括号可省略。相同的联结词按从左至右次序计算时，圆括号可省略。相同的联结词按从左至右次序计算时，圆括号可省略。相同的联结词按从左至右次序计算时，圆括号可省略。最外层的圆括号可以省略。最外层的圆括号可以省略。最外层的圆括号可以省略。最外层的圆括号可以省略。为了方便计，合式公式也简称公式。为了方便计，合式公式也简称公式。为了方便计，合式公式也简称公式。为了方便计，合式公式也简称公式。当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使.公式真值表公式真值表公式真值表公式真值表定义定义定义定义1.2.41.2.4 对对对对于于于于公公公公式式式式中中中中命命命命题题题题变变变变元元元元的的的的每每每每一一一一种种种种可可可可能能能能的的的的真真真真值值值值指指指指派派派派，以以以以及及及及由由由由它它它它们们们们确确确确定定定定出出出出的的的的公公公公式式式式真真真真值值值值所所所所列列列列成成成成的的的的表表表表，称称称称为该公式的真值表。为该公式的真值表。为该公式的真值表。为该公式的真值表。定义定义定义定义1.2.51.2.5 如如如如果果果果B B是是是是公公公公式式式式A A中中中中的的的的一一一一部部部部分分分分，且且且且B B为为为为公公公公式式式式，则称则称则称则称B B是公式是公式是公式是公式A A的子公式。的子公式。的子公式。的子公式。.公式真值表用用用用归归归归纳纳纳纳法法法法不不不不难难难难证证证证明明明明，对对对对于于于于含含含含有有有有n n个个个个命命命命题题题题变变变变元元元元的的的的公公公公式式式式，有有有有2n2n个真值指派，即在该公式的真值表中有个真值指派，即在该公式的真值表中有个真值指派，即在该公式的真值表中有个真值指派，即在该公式的真值表中有2n2n行。行。行。行。为方便构造真值表，为方便构造真值表，为方便构造真值表，为方便构造真值表，特约定如下：特约定如下：特约定如下：特约定如下：命题变元按字典序排列。命题变元按字典序排列。命题变元按字典序排列。命题变元按字典序排列。对对对对每每每每个个个个指指指指派派派派，以以以以二二二二进进进进制制制制数数数数从从从从小小小小到到到到大大大大或或或或从从从从大大大大到到到到小小小小顺顺顺顺序列出。序列出。序列出。序列出。若若若若公公公公式式式式较较较较复复复复杂杂杂杂，可可可可先先先先列列列列出出出出各各各各子子子子公公公公式式式式的的的的真真真真值值值值(若若若若有有有有括括括括号号号号，则则则则应应应应从从从从里里里里层层层层向向向向外外外外层层层层展展展展开开开开)，最最最最后后后后列列列列出出出出所所所所求求求求公公公公式式式式的的的的真真真真值。值。值。值。用归纳法不难证明，对于含有n个命题变元的公式，有2n个真值指4.4.命题的符号化命题的符号化命题的符号化命题的符号化把把把把一一一一个个个个用用用用文文文文字字字字叙叙叙叙述述述述的的的的命命命命题题题题相相相相应应应应地地地地写写写写成成成成由由由由命命命命题题题题标标标标识识识识符符符符、联结词和圆括号表示的合式公式，称为联结词和圆括号表示的合式公式，称为联结词和圆括号表示的合式公式，称为联结词和圆括号表示的合式公式，称为命题的符号化。符号化应该注意下列事项命题的符号化。符号化应该注意下列事项命题的符号化。符号化应该注意下列事项命题的符号化。符号化应该注意下列事项:确定给定句子是否为命题。确定给定句子是否为命题。确定给定句子是否为命题。确定给定句子是否为命题。句子中连词是否为命题联结词。句子中连词是否为命题联结词。句子中连词是否为命题联结词。句子中连词是否为命题联结词。要要要要正正正正确确确确地地地地表表表表示示示示原原原原子子子子命命命命题题题题和和和和适适适适当当当当选选选选择择择择命命命命题题题题联联联联结结结结词词词词。4.命题的符号化 命命题题符符号号化化是是很很重重要要的的，一一定定要要掌掌握握好好，在在命命题题推推理理中中常常常常最最先先遇遇到到的的就就是是符符号号化化一一个个问问题题，解解决决不不好好，等等于于说说推推理理的的首要前提没有了。首要前提没有了。命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇1.3 公式分类与等价公式公式分类与等价公式.公式分类公式分类定义定义定义定义1.3.11.3.1设设设设 A A 为任意公式，则为任意公式，则为任意公式，则为任意公式，则 对对对对应应应应每每每每一一一一个个个个指指指指派派派派，公公公公式式式式 A A 均均均均相相相相应应应应确确确确定定定定真真真真值为真，称值为真，称值为真，称值为真，称 A A 为重言式，或永真式。为重言式，或永真式。为重言式，或永真式。为重言式，或永真式。对对对对应应应应每每每每一一一一个个个个指指指指派派派派，公公公公式式式式 A A 均均均均相相相相应应应应确确确确定定定定真真真真值为假，称值为假，称值为假，称值为假，称 A A 为矛盾式，或永假式。为矛盾式，或永假式。为矛盾式，或永假式。为矛盾式，或永假式。至至至至少少少少存存存存在在在在一一一一个个个个指指指指派派派派，公公公公式式式式 A A 相相相相应应应应确确确确定定定定真真真真值为真，称值为真，称值为真，称值为真，称 A A 为可满足式。为可满足式。为可满足式。为可满足式。1.3 公式分类与等价公式.公式分类由定义可知，重言式必是可满足式，反之一般不真。由定义可知，重言式必是可满足式，反之一般不真。由定义可知，重言式必是可满足式，反之一般不真。由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：重点将研究重言式，它最有用，因为它有以下特点：重点将研究重言式，它最有用，因为它有以下特点：重点将研究重言式，它最有用，因为它有以下特点：重言式的否定是矛盾式，矛盾式的否定是重言式，重言式的否定是矛盾式，矛盾式的否定是重言式，重言式的否定是矛盾式，矛盾式的否定是重言式，重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。这样只研究其一就可以了。这样只研究其一就可以了。这样只研究其一就可以了。两重言式的合取式、析取式、条件式和双条件式两重言式的合取式、析取式、条件式和双条件式两重言式的合取式、析取式、条件式和双条件式两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂等都仍是重言式。于是，由简单的重言式可构造出复杂等都仍是重言式。于是，由简单的重言式可构造出复杂等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。的重言式。的重言式。的重言式。由重言式使用公认的规则可以产生许多有用等价由重言式使用公认的规则可以产生许多有用等价由重言式使用公认的规则可以产生许多有用等价由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。式和蕴涵式。式和蕴涵式。式和蕴涵式。由定义可知，重言式必是可满足式，反之一般不真。判定给定公式是否为永真式、永假式或可满足式的判定给定公式是否为永真式、永假式或可满足式的判定给定公式是否为永真式、永假式或可满足式的判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。问题，称为给定公式的判定问题。问题，称为给定公式的判定问题。问题，称为给定公式的判定问题。在在在在LsLs中，由于任何一个命题公式的指派数目总是有中，由于任何一个命题公式的指派数目总是有中，由于任何一个命题公式的指派数目总是有中，由于任何一个命题公式的指派数目总是有限的，所以限的，所以限的，所以限的，所以LsLs的判定问题是可解的。其判定方法有真值的判定问题是可解的。其判定方法有真值的判定问题是可解的。其判定方法有真值的判定问题是可解的。其判定方法有真值表法和公式推演法。表法和公式推演法。表法和公式推演法。表法和公式推演法。判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公.等价公式等价公式等价公式等价公式定义定义定义定义1.3.21.3.2 设设设设A A和和和和B B是是是是两两两两个个个个命命命命题题题题公公公公式式式式，如如如如果果果果A A、B B在在在在其其其其任任任任意意意意指指指指派派派派下下下下，其其其其真真真真值值值值都都都都是是是是相相相相同同同同的的的的，则则则则称称称称A A和和和和B B是是是是等等等等价价价价的的的的，或或或或逻逻逻逻辑辑辑辑相相相相等等等等，记记记记作作作作A AB B，读读读读作作作作A A等等等等价价价价B B，称称称称A AB B为为为为等等等等价价价价式。式。式。式。显显显显然然然然，若若若若公公公公式式式式A A和和和和B B的的的的真真真真值值值值表表表表是是是是相相相相同同同同的的的的，则则则则A A和和和和B B等等等等价价价价。因因因因此此此此，验验验验证证证证两两两两公公公公式式式式是是是是否否否否等等等等价价价价，只只只只需需需需做做做做出出出出它它它它们们们们的的的的真真真真值值值值表即可。表即可。表即可。表即可。.等价公式在这里，请读者注意在这里，请读者注意在这里，请读者注意在这里，请读者注意和和和和的区别与联系。的区别与联系。的区别与联系。的区别与联系。区区区区别别别别：是是是是逻逻逻逻辑辑辑辑联联联联结结结结词词词词，属属属属于于于于目目目目标标标标语语语语言言言言中中中中的的的的符符符符号号号号，它它它它出出出出现现现现在在在在命命命命题题题题公公公公式式式式中中中中；不不不不是是是是逻逻逻逻辑辑辑辑联联联联结结结结词词词词，属属属属于于于于元元元元语语语语言言言言中中中中的的的的符符符符号号号号，表表表表示示示示两两两两个个个个命命命命题题题题公公公公式式式式的的的的一一一一种种种种关关关关系系系系，不不不不属属属属于于于于这这这这两两两两个公式的任何一个公式中的符号。个公式的任何一个公式中的符号。个公式的任何一个公式中的符号。个公式的任何一个公式中的符号。联系：可用下面定理表明之。联系：可用下面定理表明之。联系：可用下面定理表明之。联系：可用下面定理表明之。在这里，请读者注意和的区别与联系。定理定理定理定理1.3.11.3.1A A B B当且仅当当且仅当当且仅当当且仅当A AB B是永真式。是永真式。是永真式。是永真式。有时也称有时也称有时也称有时也称A A B B是永真双条件式。是永真双条件式。是永真双条件式。是永真双条件式。等价式有下列性质：等价式有下列性质：等价式有下列性质：等价式有下列性质：自反性，即对任意公式自反性，即对任意公式自反性，即对任意公式自反性，即对任意公式A A，有，有，有，有A A A A。对称性，即对任意公式对称性，即对任意公式对称性，即对任意公式对称性，即对任意公式A A和和和和B B，若，若，若，若A A B B，则，则，则，则B B A A。传递性，即对任意公式传递性，即对任意公式传递性，即对任意公式传递性，即对任意公式A A、B B和和和和C C，若，若，若，若A A B B、B B C C，则，则，则，则A A C C。定理1.3.1A B当且仅当AB是永真式。.基本等价式基本等价式基本等价式基本等价式命题定律命题定律命题定律命题定律在在在在判判判判定定定定公公公公式式式式间间间间是是是是否否否否等等等等价价价价，有有有有一一一一些些些些简简简简单单单单而而而而又又又又经经经经常常常常使使使使用用用用的的的的等等等等价价价价式式式式，称称称称为为为为基基基基本本本本等等等等价价价价式式式式或或或或称称称称命命命命题题题题定定定定律律律律。牢牢牢牢固固固固地地地地记记记记住住住住它它它它并并并并能能能能熟熟熟熟练练练练运运运运用用用用，是是是是学学学学好好好好数数数数理理理理逻逻逻逻辑辑辑辑的的的的关关关关键键键键之之之之一一一一，读读读读者者者者应应应应该注意到这一点。现将这些命题定律列出如下：该注意到这一点。现将这些命题定律列出如下：该注意到这一点。现将这些命题定律列出如下：该注意到这一点。现将这些命题定律列出如下：(1)(1)双否定：双否定：双否定：双否定：A AA A。(2)(2)交交交交 换换换换 律律律律：A AB BB BA A，A AB BB BA A，A AB BB BA A。.基本等价式命题定律(3)(3)结合律：结合律：结合律：结合律：(A(AB)B)C CA A(B(BC)C)，(A(AB)B)C CA A(B(BC)C)，(A(AB)B)C CA A(B(BC)C)。(4)(4)分配律：分配律：分配律：分配律：A A(B(BC)C)(A(AB)B)(A(AC)C)，A A(B(BC)C)(A(AB)B)(A(AC)C)。(5)(5)德德德德 摩根律：摩根律：摩根律：摩根律：(A(AB)B)A A B B，(A(AB)B)A A B B。(6)(6)等幂律：等幂律：等幂律：等幂律：A AA AA A，A AA AA A。(3)结合律：(AB)CA(BC)，(AB)(7)(7)同一律：同一律：同一律：同一律：A AT TA A，A AF FA A。(8)(8)零零零零 律：律：律：律：A AF FF F，A AT TT T。(9)(9)吸收律：吸收律：吸收律：吸收律：A A(A(AB)B)A A，A A(A(AB)B)A A。(10)(10)互补律：互补律：互补律：互补律：A A A AF F，(矛盾律矛盾律矛盾律矛盾律)A A A AT T。(排中律排中律排中律排中律)(11)(11)条件式转化律：条件式转化律：条件式转化律：条件式转化律：ABABA AB B，ABABBB A A。(7)同一律：ATA，AFA。(12)(12)双条件式转化律：双条件式转化律：双条件式转化律：双条件式转化律：A AB B(AB)(AB)(BA)(BA)(A(AB)B)(A A B)B)A AB B(A(AB)B)(13)(13)输出律：输出律：输出律：输出律：(A(AB)CB)CA(BC)A(BC)。(14)(14)归谬律：归谬律：归谬律：归谬律：(AB)(AB)(A(A B)B)A A。上面这些定律，即是通常所说的布尔代数或逻辑代数的重要上面这些定律，即是通常所说的布尔代数或逻辑代数的重要上面这些定律，即是通常所说的布尔代数或逻辑代数的重要上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。组成部分，它们的正确性利用真值表是不难给出证明的。组成部分，它们的正确性利用真值表是不难给出证明的。组成部分，它们的正确性利用真值表是不难给出证明的。(12)双条件式转化律：AB(AB)(BA)(.代入规则和替换规则代入规则和替换规则代入规则和替换规则代入规则和替换规则在在在在定定定定义义义义合合合合成成成成公公公公式式式式时时时时，已已已已看看看看到到到到了了了了逻逻逻逻辑辑辑辑联联联联结结结结词词词词能能能能够够够够从从从从已已已已知知知知公公公公式式式式形形形形成成成成新新新新的的的的公公公公式式式式，从从从从这这这这个个个个意意意意义义义义上上上上可可可可把把把把逻逻逻逻辑辑辑辑联联联联结结结结词词词词看看看看成成成成运运运运算算算算。除除除除逻逻逻逻辑辑辑辑联联联联结结结结词词词词外外外外，还还还还要要要要介介介介绍绍绍绍“代代代代入入入入”和和和和“替替替替换换换换”，它它它它们们们们也也也也有有有有从从从从已已已已知知知知公公公公式式式式得得得得到到到到新新新新的的的的公公公公式式式式的的的的作作作作用用用用，因因因因此此此此有有有有人人人人也也也也将将将将它它它它们们们们看看看看成成成成运运运运算算算算，这这这这不不不不无无无无道道道道理理理理，而而而而且且且且在在在在今今今今后后后后讨讨讨讨论论论论中中中中，它的作用也是不容忽视的。它的作用也是不容忽视的。它的作用也是不容忽视的。它的作用也是不容忽视的。.代入规则和替换规则(1)(1)代入规则代入规则代入规则代入规则定理定理定理定理1.3.21.3.2 在一个永真式在一个永真式在一个永真式在一个永真式A A A A中，任何一个原子命题中，任何一个原子命题中，任何一个原子命题中，任何一个原子命题变元变元变元变元R R出现的每一处，出现的每一处，出现的每一处，出现的每一处，用另一个公式代入，所得公式用另一个公式代入，所得公式用另一个公式代入，所得公式用另一个公式代入，所得公式B B仍仍仍仍是永真式。本定理称为代入规则。是永真式。本定理称为代入规则。是永真式。本定理称为代入规则。是永真式。本定理称为代入规则。(2)(2)替换规则替换规则替换规则替换规则定定定定理理理理1.3.3 1.3.3 设设设设A A1 1是是是是合合合合式式式式公公公公式式式式A A的的的的子子子子公公公公式式式式，若若若若A A1 1B B1 1，并并并并且且且且将将将将A A中中中中的的的的A A1 1用用用用B B1 1 替替替替换换换换得得得得到到到到公公公公式式式式B B，则则则则A AB B。称称称称该该该该定定定定理为替换规则。理为替换规则。理为替换规则。理为替换规则。满足定理满足定理满足定理满足定理1.3.31.3.3条件的替换，称为等价替换。条件的替换，称为等价替换。条件的替换，称为等价替换。条件的替换，称为等价替换。(1)代入规则代入和替换有两点区别：代入和替换有两点区别：代入和替换有两点区别：代入和替换有两点区别：代代代代入入入入是是是是对对对对原原原原子子子子命命命命题题题题变变变变元元元元而而而而言言言言的的的的，而而而而替替替替换换换换可对命题公式实行。可对命题公式实行。可对命题公式实行。可对命题公式实行。代代代代入入入入必必必必须须须须是是是是处处处处处处处处代代代代入入入入，替替替替换换换换则则则则可可可可部部部部分分分分替替替替换，亦可全部替换。换，亦可全部替换。换，亦可全部替换。换，亦可全部替换。代入和替换有两点区别：1.4 对偶式与蕴涵式对偶式与蕴涵式.对偶式对偶式在在在在上上上上节节节节介介介介绍绍绍绍的的的的命命命命题题题题定定定定律律律律中中中中，多多多多数数数数是是是是成成成成对对对对出出出出现现现现的的的的，这这这这些些些些成成成成对对对对出出出出现现现现的的的的定定定定律律律律就就就就是是是是对对对对偶偶偶偶性性性性质质质质的的的的反反反反映映映映，即即即即对对对对偶偶偶偶式式式式。利利利利用用用用对对对对偶偶偶偶式式式式的的的的命命命命题题题题定定定定律律律律，可可可可以以以以扩扩扩扩大大大大等等等等价式的个数，也可减少证明的次数。价式的个数，也可减少证明的次数。价式的个数，也可减少证明的次数。价式的个数，也可减少证明的次数。1.4 对偶式与蕴涵式.对偶式定义定义定义定义1.4.1 1.4.1 在给定的仅使用联结词在给定的仅使用联结词在给定的仅使用联结词在给定的仅使用联结词 、和和和和的命题公式的命题公式的命题公式的命题公式A A中，若把中，若把中，若把中，若把和和和和互换，互换，互换，互换，F F和和和和T T互换而互换而互换而互换而得到一个命题公式得到一个命题公式得到一个命题公式得到一个命题公式A A*，则称，则称，则称，则称A A*为为为为A A的对偶式。的对偶式。的对偶式。的对偶式。显然，显然，显然，显然，A A也是也是也是也是A A*的对偶式。可见的对偶式。可见的对偶式。可见的对偶式。可见A A与与与与A A*互为互为互为互为对偶式。对偶式。对偶式。对偶式。定义1.4.1 在给定的仅使用联结词、和的命题公式A定定定定理理理理1.4.1(1.4.1(对对对对偶偶偶偶定定定定理理理理)设设设设A A和和和和A A*互互互互为为为为对对对对偶偶偶偶式式式式，P P1 1，P P2 2，P Pn n是出现是出现是出现是出现A A和和和和A A*中的原子命题变元，则中的原子命题变元，则中的原子命题变元，则中的原子命题变元，则 A(PA(P1 1，P P2 2，P Pn n)A A*(P P1 1，P P2 2，P Pn n)A(A(P P1 1，P P2 2，P Pn n)A A*(P(P1 1，P P2 2，P Pn n)表表表表明明明明，公公公公式式式式A A的的的的否否否否定定定定等等等等价价价价于于于于其其其其命命命命题题题题变变变变元元元元否否否否定定定定的的的的对对对对偶偶偶偶式式式式；表表表表明明明明，命命命命题题题题变变变变元元元元否否否否定定定定的的的的公公公公式式式式等等等等价价价价于于于于对对对对偶偶偶偶式式式式之之之之否否否否定。定。定。定。定理1.4.1(对偶定理)设A和A*互为对偶式，P1，P证明：令公式证明：令公式证明：令公式证明：令公式A A（P1P1，P2P2，PnPn）中含有）中含有）中含有）中含有联结词联结词联结词联结词 、和和和和 的数目为的数目为的数目为的数目为L L，对，对，对，对L L进行归纳证明之。进行归纳证明之。进行归纳证明之。进行归纳证明之。当当当当L=0L=0时时时时：A A（P1P1，P2P2，PnPn）=P1 =P1 ，因为因为因为因为 A A（P1P1，P2P2，PnPn）P1 P1 ，A*A*（P1 P1，P2 P2，Pn Pn）P1 P1 ，所以：所以：所以：所以：A A（P1P1，P2P2，PnPn）A A*（P1 P1，P2 P2，Pn Pn）成立成立成立成立当当当当L=1L=1时时时时，有三种情况：有三种情况：有三种情况：有三种情况：（1 1）A A（P1P1，P2P2，PnPn）=P1=P1 P2P2；（2 2）A A（P1P1，P2P2，PnPn）=P1=P1 P2P2；（3 3）A A（P1P1，P2P2，PnPn）=P1 P1。证明：令公式A（P1，P2，Pn）中含有联结词、和 对于（对于（对于（对于（1 1）有有有有A A（P1P1，P2P2，PnPn）=P1=P1 P2P2A*A*（P1 P1，P2 P2，Pn Pn）P1 P1 P2 P2 A A（P1 P1，P2 P2，Pn Pn）（P1 P1 P2 P2）由摩根定理有由摩根定理有由摩根定理有由摩根定理有 ，故故故故 ：A A（P1 P1，P2 P2，Pn Pn）A*A*（P1 P1，P2 P2，Pn Pn）对于（对于（对于（对于（2 2）同理可证。同理可证。同理可证。同理可证。对于（对于（对于（对于（3 3）A A（P1P1，P2P2，PnPn）=P1 P1A*A*（P1 P1，P2 P2，Pn Pn）P1 P1A*A*（P1 P1，P2 P2，Pn Pn）P1=P1 P1=P1 A A（P1P1，P2P2，PnPn）P1=P1 P1=P1 故而有故而有故而有故而有 A A（P1 P1，P2 P2，Pn Pn）A*A*（P1 P1，P2 P2，PnPn）对于（1）有A（P1，P2，Pn）=P1 P2假设假设假设假设Lk-1Lk-1时时时时,公式公式公式公式 A A（P1 P1，P2 P2，Pn Pn）=A*=A*（P1 P1，P2 P2，Pn Pn）成立，根据归纳法，只要证）成立，根据归纳法，只要证）成立，根据归纳法，只要证）成立，根据归纳法，只要证L=kL=k时公式也成立。时公式也成立。时公式也成立。时公式也成立。由于公式的最后一个联结词为由于公式的最后一个联结词为由于公式的最后一个联结词为由于公式的最后一个联结词为 、和和和和 之一，因此可以分之一，因此可以分之一，因此可以分之一，因此可以分别证明。别证明。别证明。别证明。（1 1）最后一个联结词为）最后一个联结词为）最后一个联结词为）最后一个联结词为，A A（P1 P1，P2 P2，Pn Pn）=A1=A1（P1 P1，P2 P2，Pn Pn）A2 A2（P1 P1，P2 P2，Pn Pn），A1A1，A2A2的联结词数目的联结词数目的联结词数目的联结词数目L L（A1 A1）=k-1=k-1，L L（A2 A2）=k-1=k-1。因此因此因此因此 A1 A1（P1 P1，P2 P2，Pn Pn）A1*A1*（P1 P1，P2 P2，Pn Pn A2 A2（P1 P1，P2 P2，Pn Pn）A2*A2*（P1 P1，P2 P2，Pn Pn A A（P1 P1，P2 P2，Pn Pn）（A1A1（P1 P1，P2 P2，Pn Pn）A2 A2（P1 P1，P2 P2，Pn Pn）A1A1（P1 P1，P2 P2，Pn Pn）A2A2（P1 P1，P2 P2，Pn Pn）A1*A1*（P1 P1，P2,P2,Pn Pn）A2*A2*（P1 P1，P2,P2,Pn Pn）A*A*（P1 P1，P2 P2，Pn Pn）。假设Lk-1时,公式 A（P1，P2，Pn）=（2 2）最后一个联结词为）最后一个联结词为）最后一个联结词为）最后一个联结词为同理可得。同理可得。同理可得。同理可得。（3 3）最后一个联结词为）最后一个联结词为）最后一个联结词为）最后一个联结词为 时，时，时，时，A A（P1 P1，P2 P2，PnPn）=A1 A1（P1 P1，P2 P2，Pn Pn）其中其中其中其中L L（A1 A1）=k-1=k-1。A A（P1 P1，P2 P2，Pn Pn）（A1 A1（P1 P1，P2 P2，Pn Pn）A1*A1*（P1 P1，P2 P2，Pn Pn）（A1 A1（P1 P1，P2 P2，Pn Pn）*（A A（P1 P1，P2 P2，Pn Pn）*A*A*（P1 P1，P2 P2，Pn Pn）结合（结合（结合（结合（1 1）（）（）（）（2 2）（）（）（）（3 3），当，当，当，当L=kL=k时，有：时，有：时，有：时，有：A A（P1 P1，P2 P2，Pn Pn）A*A*（P1 P1，P2 P2，PnPn）归纳法证明完毕。归纳法证明完毕。归纳法证明完毕。归纳法证明完毕。（2）最后一个联结词为同理可得。定定定定理理理理1.4.2 1.4.2 设设设设A A和和和和B B为为为为两两两两个个个个命命命命题题题题公公公公式式式式，若若若若A AB B则则则则A A*B B*。有有有有了了了了等等等等价价价价式式式式、代代代代入入入入规规规规则则则则、替替替替换换换换规规规规则则则则和和和和对对对对偶偶偶偶定定定定理理理理，便便便便可可可可以以以以得得得得到到到到更更更更多多多多的的的的永永永永真真真真式式式式，证证证证明明明明更更更更多多多多的的的的等等等等价价价价式，使化简命题公式更为方便。式，使化简命题公式更为方便。式，使化简命题公式更为方便。式，使化简命题公式更为方便。定理1.4.2 设A和B为两个命题公式，若AB则A*B.蕴涵式蕴涵式定定定定义义义义1.4.2 1.4.2 设设设设A A和和和和B B是是是是两两两两个个个个命命命命题题题题公公公公式式式式，若若若若A AB B是是是是永永永永真真真真式式式式，则则则则称称称称A A蕴蕴蕴蕴涵涵涵涵B B，记记记记作作作作A AB B，称称称称A AB B为为为为蕴蕴蕴蕴涵涵涵涵式式式式或或或或永永永永真条件式。真条件式。真条件式。真条件式。符符符符号号号号和和和和的的的的区区区区别别别别与与与与联联联联系系系系类类类类似似似似于于于于和和和和的的的的关关关关系系系系。区区区区别别别别：是是是是逻逻逻逻辑辑辑辑联联联联结结结结词词词词，属属属属于于于于对对对对象象象象语语语语言言言言中中中中的的的的符符符符号号号号，是是是是公公公公式式式式中中中中的的的的符符符符号号号号；而而而而不不不不是是是是联联联联结结结结词词词词，属属属属于于于于元元元元语语语语言言言言中中中中的的的的符符符符号号号号，表表表表示示示示两两两两个个个个公公公公式式式式之之之之间间间间的的的的关关关关系系系系，不不不不是是是是两两两两公公公公式式式式中中中中符符符符号号号号。联系：联系：联系：联系：A AB B成立，其充要条件成立，其充要条件成立，其充要条件成立，其充要条件A AB B是永真式。是永真式。是永真式。是永真式。.蕴涵式蕴涵式有下列性质：蕴涵式有下列性质：蕴涵式有下列性质：蕴涵式有下列性质：自反性，即对任意公式自反性，即对任意公式自反性，即对任意公式自反性，即对任