离散数字A.ppt

重言式命题、可满足式命题、永假式命题、命题的关系是什么？ 重言式 永假式 可满足式 1.4 重言式与代入规则 代入规则  　　 一个重言式，对其中所有相同的命 题变项都用一合式公式代换，其结果仍 为一重言式。这一规则称为代入规则。 换句话说，A是一个公式，对A使用 代入规则得到公式B，若A是重言式，则 B也是重言式。 1.4 重言式与代入规则 代入规则的具体要求为： 1.? 公式中被代换的只能是命题变项 （原子命题），而不能是复合命题。 2.? 对公式中某命题变项施以代入， 必须对该公式中出现的所有同一 命题变项施以相同的代换。 1.公式中被代换的只能是命题变元（原子命 题）而不能是复合命题。如可用(R∧S)来代换 某公式中的P, 记作 , 而不能反过来将公式中的(R∧S)以P代之。 1.4 重言式与代入规则 1.4 重言式与代入规则 这一要求可以用代数的例子来说明，如对 (a + b)2 = a2 + 2ab + b2 可以a = cd代入，仍会保持等式成立。 而若将a + b以cd代入，结果左端得(cd)2， 而右端无法代入cd，不能保持等式成立了。 , 2. 对公式中某命题变项施以代入，必须对该公 式中出现的所有同一命题变项代换同一公式。 公式A经代入规则可得任一公式, 而仅当A是 重言式时, 代入后重言式的性质方得保持。 如A = P∨?P, 作代入 得 B = ?Q∨??Q 仍是重言式。 1.4 重言式与代入规则 1.4 重言式与代入规则 若将?P以Q代之得B = P∨Q (这不是代入, 违反了规定2) 已不是重言式。 在第三章公理系统中，代入规则视作重要 的推理规则经常使用 。 1.4 重言式与代入规则 例1: 判断(R∨S) ∨?(R∨S)为重言式。 使用代入规则证明重言式。 P∨?P为重言式, 作代入 依据代入规则,便得(R∨S) ∨?(R∨S)。 这公式必是重言式。 1.4 重言式与代入规则 不难验证(A∧(A?B))?B是重言式, 例2：判断 ((R∨S)∧((R∨S)?(P∨Q)))?(P∨Q) 为重言式. 1.4 重言式与代入规则 作代入 便知 ((R∨S)∧((R∨S)?(P∨Q))?(P∨Q) 是重言式。 1.5 命题形式化 注意掌握用不同的方式表示同一命题 公式的方法 P?Q = ?P∨Q 善于以真值表为工具分析、验证、解 决命题形式化中的问题 1.5 命题形式化 思考题1 IF …THEN…ELSE 是常用的编程语句 记 A = IF P THEN Q ELSE R 试将其形式化（用所学的联接词表示） 进一步可尝试给出两种不同的表示 （彼此等值） 思考题2 给定真值表，如何写出对应的命题公式。 * 书上叫做“等值”，这个说法并不准确 * 第一章 命题逻辑的基本概念 第一章 命题逻辑的基本概念 1.1 命题 1.2 命题联结词及真值表 1.3 合式公式 (Well Formed Formula) 1.4 重言式 (Tautology) 1.5 命题形式化 1.1 命题 命题： 　　命题是一个能表达判断并具有确定 真值的陈述句。 1.1 命题 真值 　　作为命题的陈述句所表达的判断结果称为命题的真值。 真值只有真和假两种，通常记为T 和F。 真值为真的命题称为真命题，真值为假的命题称为假命题。 任何命题的真值都是唯一的。 命题举例： 雪是黑的。 56. 好美的清华园！ 请举例说明什么叫命题。 难道今天不是星期二吗？ 我正在说谎话。 1.1 命题 命题变项  　　用命题标识符（大写字母）来表示 任意命题时，该命题标识符称为命题变 项。 命题变项举例 P表示“离散数学的课在六教上”这一命题。 Q表示“北京是中国首都”这一命题 类比：初等数学中常量和变量的关系 命题 命题变项 北京是中国首都 Q 常量 变量 5 X 1.1 命题 简单命题  　　 无法继续分解的简单陈述句称为 简单命题或原子命题。(不包含任何与、 或、非一类联结