离散数学笔记(特级教师精心整理)

离散数学教案 1 离散数学笔记（特级教师精心整理） 第一章 命题逻辑 内容： 命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法 教学目的： 1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 2．熟练掌握常用的基本等价式及其应用。 3．熟练掌握（主）析/合取范式的求法及其应用。 4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 5．熟练掌握形式演绎的方法。 教学重点： 1．命题的概念及判断 2．联结词，命题的翻译 3．主析（合）取范式的求法 4．逻辑推理 教学难点： 1．主析（合）取范式的求法 2．逻辑推理 1.1 命题及其表示法 1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称作命题。 1.1.2 命题的表示 命题通常使用大写字母A，B，…，Z 或带下标的大写字母或数字表示，如 Ai，[10]，R 等，例如 A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。 1.2 命题联结词 1.2.1 否定联结词﹁P P P 0 1 1 0 1.2.2 合取联结词∧ P Q QP  0 0 0 0 1 0 离散数学教案 2 1 0 0 1 1 1 1.2.3 析取联结词∨ P Q QP  0 0 0 0 1 1 1 0 1 1 1 1 1.2.4 条件联结词→ P Q QP  0 0 1 0 1 1 1 0 0 1 1 1 1.2.5 双条件联结词 P Q QP  0 0 1 0 1 0 1 0 0 1 1 1 1.2.6 与非联结词↑ P Q QP  0 0 1 0 1 1 1 0 1 1 1 0 性质： （1） P↑P ﹁（P∧P） ﹁P； （2）（P↑Q）↑（P↑Q） ﹁（P↑Q） P∧Q； （3）（P↑P）↑（Q↑Q） ﹁P↑﹁Q P∨Q。 1.2.7 或非联结词↓ P Q QP  0 0 1 0 1 0 1 0 0 1 1 0 性质： （1）P↓P ﹁（P∨Q） ﹁P； 离散数学教案 3 （2）（P↓Q）↓（P↓Q） ﹁（P↓Q） P∨Q； （3）（P↓P）↓（Q↓Q） ﹁P↓﹁Q ﹁（﹁P∨﹁Q） P∧Q。 1.3 命题公式、翻译与解释 1.3.1 命题公式 定义 命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P 是公式；（3）如果P、Q 是公式，则P∧Q、P∨Q、P Q、 P Q都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如，下面的...