离散数学教案 第1章命题逻辑 命题逻辑，也称命题演算，记为L5。它与谓词逻辑构成数理逻辑的基础，而命 题逻辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的 学问。因此，数理逻辑又名为符号逻辑。 命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。 1.1命题与联结词 1,命题的概念 所谓命题，是指具有非真必假的陈述句。而疑问句、析使句和感叹句等因都不能 判断其真假，故都不是命题。命题仅有两种可能的真值一真和假，且二者只能居其一。 真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值 逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。 如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。 原子命题是命题逻辑的基本单位。 命题分为两类： 第一类是原子命题，原子命题用大写英文字母P,Q,R.及其带下标的Pi,Qi, Ri,.表示。 第二类是复合命题，它由原子命题、命题联结词和圆括号组成。 2,命题联结词 定义1.1.1设P表示一个命题，由命题联结词和命题P连接成幻P,称P 为P的否定式复合命题，一P读“非P”。称幻为否定联结词。P是真，当且仅当 P为假：7P是假，当且仅当P为真。否定联结词“”的定义可由表1.1.1表示之。 由于否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。 定义1.1.2设P和Q为两个命题，由命题联结词八将P和Q连接成P∧Q,称P 八Q为命题P和Q的合取式复合命题，P人Q读做“P与Q”,或“P且Q”。称∧为合 取联结词。 当且仅当P和Q的真值同为真，命题PAQ的真值才为真：否则，PAQ的真值为 假。合取联结词八的定义由表1.1.2表示之。 定义1.1.3设P和Q为两个命题，由命题联结词V把P和Q连接成PVQ,称P VQ为命题P和Q的析取式复合命题，PVQ读做“P或Q”。称V为析取联结词。 6
离散数学教案 6 第 1 章 命题逻辑 命题逻辑，也称命题演算，记为 Ls。它与谓词逻辑构成数理逻辑的基础，而命 题逻辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的 学问。因此，数理逻辑又名为符号逻辑。 命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。 1.1 命题与联结词 １. 命题的概念 所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能 判断其真假，故都不是命题。命题仅有两种可能的真值—真和假，且二者只能居其一。 真用 1 或 T 表示，假用 0 或 F 表示。由于命题只有两种真值，所以称这种逻辑为二值 逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。 如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。 原子命题是命题逻辑的基本单位。 命题分为两类： 第一类是原子命题，原子命题用大写英文字母 P，Q，R.及其带下标的 Pi，Qi， Ri，.表示。 第二类是复合命题，它由原子命题、命题联结词和圆括号组成。 ２. 命题联结词 定义 1.1.1 设 P 表示一个命题，由命题联结词┐和命题 P 连接成┐P，称┐P 为 P 的否定式复合命题， ┐P 读“非 P”。称┐为否定联结词。┐P 是真，当且仅当 P 为假；┐P 是假，当且仅当 P 为真。否定联结词“┐”的定义可由表 1.1.1 表示之。 由于否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。 定义 1.1.2 设 P 和 Q 为两个命题，由命题联结词∧将 P 和 Q 连接成 P∧Q，称 P ∧Q 为命题 P 和 Q 的合取式复合命题，P∧Q 读做“P 与 Q”，或“P 且 Q”。称∧为合 取联结词。 当且仅当 P 和 Q 的真值同为真，命题 P∧Q 的真值才为真；否则，P∧Q 的真值为 假。合取联结词∧的定义由表 1.1.2 表示之。 定义 1.1.3 设 P 和 Q 为两个命题，由命题联结词∨把 P 和 Q 连接成 P∨Q，称 P ∨Q 为命题 P 和 Q 的析取式复合命题，P∨Q 读做“P 或 Q”。称∨为析取联结词
离散数学教案 当且仅当P和Q的真值同为假，PVQ的真值为假：否则，PVQ的真值为真。析取联 结词V的定义由表1.1.3表示之。 由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别的联结词定义之。 与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系，有 关例子就不再给出了。 定义1.1.4设P和Q为两个命题，由命题联结词→把P和Q连接成P→Q,称P →Q为命题P和Q的条件式复合命题，简称条件命题。P→Q读做“P条件Q”或者“若 P则Q”。称一为条件联结词。 当P的真值为真而Q的真值为假时，命题P→Q的真值为假：否则，P一Q的真值 为真。条件联结词一的定义由表1.1.4表示之。 在条件命题P→Q中，命题P称为P→Q的前件或前提，命题Q称为P→Q的后件 或结论。条件命题P一Q有多种方式陈述：“如果P,那么Q”:“P仅当Q”:“Q 每当P”:“P是Q的充分条件”：“Q是P的必要条件”等。 在日常生活中，用条件式表示前提和结论之间的因果或实质关系，如例1.1.4中 的①，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要 求与结论有任何关系，这种条件式称为实质条件命题。采用实质条件式作定义，不单 是出于“善意推断”，主要是因为前提与结论间有无因果和实质关系难以区分，而且 实质条件式己包含了形式条件式，更便于应用。 定义1.1.5令P、Q是两个命题，由命题联结词把P和Q连接成P)Q,称 P一Q为命题P和Q的双条件式复合命题，简称双条件命题，P行Q读做“P当且 仅当Q”,或“P等价Q”。称→为双条件联结词。 当P和Q的真值相同时，P:Q的真值为真：否则，PQ的真值为假。双条 件联结词的定义由表1.1.5表示之。 在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值， 而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是 至关重要的，请读者认真去领会。 1.2命题变元和合式公式 1.命题变元
离散数学教案 7 当且仅当 P 和 Q 的真值同为假，P∨Q 的真值为假；否则，P∨Q 的真值为真。析取联 结词∨的定义由表 1.1.3 表示之。 由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别的联结词定义之。 与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系，有 关例子就不再给出了。 定义 1.1.4 设 P 和 Q 为两个命题，由命题联结词→把 P 和 Q 连接成 P→Q，称 P →Q 为命题 P 和 Q 的条件式复合命题，简称条件命题。P→Q 读做“P 条件 Q”或者“若 P 则 Q”。称→为条件联结词。 当 P 的真值为真而 Q 的真值为假时，命题 P→Q 的真值为假；否则，P→Q 的真值 为真。条件联结词→的定义由表 1.1.4 表示之。 在条件命题 P→Q 中，命题 P 称为 P→Q 的前件或前提，命题 Q 称为 P→Q 的后件 或结论。条件命题 P→Q 有多种方式陈述：“如果 P，那么 Q”；“P 仅当 Q”；“Q 每当 P”；“P 是 Q 的充分条件”；“Q 是 P 的必要条件”等。 在日常生活中，用条件式表示前提和结论之间的因果或实质关系，如例 1.1.4 中 的①，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要 求与结论有任何关系，这种条件式称为实质条件命题。采用实质条件式作定义，不单 是出于“善意推断”，主要是因为前提与结论间有无因果和实质关系难以区分，而且 实质条件式已包含了形式条件式，更便于应用。 定义 1.1.5 令 P、Q 是两个命题，由命题联结词把 P 和 Q 连接成 P Q，称 P Q 为命题 P 和 Q 的双条件式复合命题，简称双条件命题，P Q 读做“P 当且 仅当 Q”，或“P 等价 Q”。称为双条件联结词。 当 P 和 Q 的真值相同时，P Q 的真值为真；否则，P Q 的真值为假。双条 件联结词的定义由表 1.1.5 表示之。 在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值， 而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是 至关重要的，请读者认真去领会。 1.2 命题变元和合式公式 １. 命题变元
离散数学教案 在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称 为命题常元：一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命 题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元 指派真值。 命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题 的涵义，只关心其真值，因此，可以形式地定义它们如下： 定义1.2.1以真或1、假或0为其变域的变元，称为命题变元：真或1、假或 0称为命题常元。 2.合式公式 通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为 不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用 归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公 式。 定义1.2.2单个命题变元和命题常元称为原子命题公式，简称原子公式。 定义1.2.3合式公式是由下列规则生成的公式： ①单个原子公式是合式公式。 ②若A是一个合式公式，则(IA)也是一个合式公式。 ③若A、B是合式公式，则(AAB)、(AVB)、(A→B)和(AB)都是合式公式 ④只有有限次使用①、②和③生成的公式才是合式公式。 当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作 以下约定： ①规定联结词的优先级由高到低的次序为：一、八、V、→、→ ②相同的联结词按从左至右次序计算时，圆括号可省略。 ③最外层的圆括号可以省略。 为了方便计，合式公式也简称公式。 3.公式真值表 定义1.2.4对于公式中命题变元的每一种可能的真值指派，以及由它们确定出 的公式真值所列成的表，称为该公式的真值表。 定义1.2.5如果B是公式A中的一部分，且B为公式，则称B是公式A的子公
离散数学教案 8 在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称 为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命 题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元 指派真值。 命题常元和命题变元均可用字母 P 等表示。由于在命题逻辑中并不关心具体命题 的涵义，只关心其真值，因此，可以形式地定义它们如下： 定义 1.2.1 以真或 1、假或 0 为其变域的变元，称为命题变元；真或 1、假或 0 称为命题常元。 2. 合式公式 通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为 不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用 归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公 式。 定义 1.2.2 单个命题变元和命题常元称为原子命题公式，简称原子公式。 定义 1.2.3 合式公式是由下列规则生成的公式： ①单个原子公式是合式公式。 ②若 A 是一个合式公式，则(lA)也是一个合式公式。 ③若 A、B 是合式公式，则(A∧B)、(A∨B)、(A→B)和(A B)都是合式公式。 ④只有有限次使用①、②和③生成的公式才是合式公式。 当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作 以下约定： ①规定联结词的优先级由高到低的次序为：┐、∧、∨、→、 ②相同的联结词按从左至右次序计算时，圆括号可省略。 ③最外层的圆括号可以省略。 为了方便计，合式公式也简称公式。 ３. 公式真值表 定义 1.2.4 对于公式中命题变元的每一种可能的真值指派，以及由它们确定出 的公式真值所列成的表，称为该公式的真值表。 定义 1.2.5 如果 B 是公式 A 中的一部分，且 B 为公式，则称 B 是公式 A 的子公