【精华】离散数学(高教)概念整理.docx

精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -- 学习资料收集于网络，仅供参考 数理规律 命题规律 命题 p,q,r,s 非真即假的陈述句 命题的真值 0 1 命题的陈述句所表达的判定结果 原子命题（简洁命题） 不能被分解成更简洁的命题 简洁命题通过联结词联结而成的命题，称为复合命题 命题的符号化 p: 4 是素数 用小写英文字母（如 p:4 是素数）表示命题； 用小写英文字母（如 p:4 是素数）表示原子命题，用联结词联结原子命题表示复合命题； 联结词 否定连接词 ￢ 否 p 为真当且仅当 p 为假 合取联结词 ∧ p 合取 q 为真当且仅当 p， q 同时为真（复合命题“ p 并且 q”称为 p 与 q 的合取式） 析取联结词 ∨ p 析取 q 为假当且仅当学习资料 p， q 同时为假（复合命题“ p 或 q”称为 p 与 q 的析取式） - - -细心整理 - - - 欢迎下载 - - - 第 1 页，共 39 页 精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -- 学习资料收集于网络，仅供参考 包蕴连接词→ p 包蕴 q 为假当且仅当 p 为真， q 为假；（复合命题“假如 p,就 q”（由于 p 所以 q，除非 q 才 p）称为 p 与 q 的包蕴式， p 是包蕴式的前件， q 是包蕴式的后件） q 是 p 的必要条件； 等价联结词 . p 等价 q 当且仅当，同时为真或假； （复合命题“ p 当且仅当 q”称作 p 与 q 的等价式） 真值表 命题公式及其赋值命题常项 原子命题（简洁命题）的另一称呼，由于其真值确定 命题变项 真值可以变化的陈述句 合式公式（命题公式） A， B 命题变项用联结词和圆括号用肯定规律关系连接起来的符号串，简称公式 赋值（说明） 给公式 A 中的每个命题变项各指定一个真值；这组值使 A 为 1，就称为成真赋值； 学习资料 - - -细心整理 - - - 欢迎下载 - - - 第 2 页，共 39 页 精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -- 学习资料收集于网络，仅供参考 含 n 个命题变项的公式有 2 的 n 次方个不同赋值； 含 n 个命题变项的公式有 2 的 2 的 n 次方个不同真值表情形； 重言式（永真式） 命题公式 A 在各种赋值下取值均为真 冲突式（永假式） 命题公式 A 在各种赋值下取值均为假 可满意式 命题公式 A 至少存在一个成真赋值 哑元 对公式 A 和 B 进行比较争论，可知 A 和 B 共含有 n 个命题变项，其中 A 不含有的命题变项称为 A 的哑元，其取值不影响 A 的值 命题规律等值演算等值式 . 假如命题 A 和 B 有相同的真值表， 就有命题 A. B 为重言式， 这种情形下称 A 与 B 是等值的， 记作 A. B （重要）等值式模式 常用的 16 条命题间的等值模式，书 p18 学习资料 - - -细心整理 - - - 欢迎下载 - - - 第 3 页，共 39 页 精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -- 学习资料收集于网络，仅供参考 析取范式与合取范式 文字 命题变项及其否定的统称 简洁析取式，简洁合取式 由有限个文字构成的析取式，合取式 析取范式，合取范式 由有限个简洁合取式的析取构成的命题公式，称为析取范式；同理为合取范式； 命题公式的析取或合取范式一般不唯独 微小项，极大项 简洁合取式中的命题变项及它的否定式恰好显现一次， 并根据下标拍好， 这样的简洁合取式叫做微小项；同理为极大项； n 个命题变项可以产生 2 的 n 次方个微小项， 每个微小项都有且仅有一个成真赋值， 这一组成真赋值（ 01 组成）转化为对应的十进制数 i，将这个微小项表示为 类似的，极大项为 主析取范式 主合取范式 全部简洁合取式都是微小项的析取式，这是唯独的主析取范式；同理； 联结词的完备集 n 元真值函数 F 函数 F 的自变量为 n 个命题变项， 值域为 {0,1},这样的函数叫 n 元真值函数； n 个命题变项一共可以构成 2 的 2 的 n 次方个不同的真值函数； 每个真值函数与唯独的一个主析取范式 （主合取范式） 等值， 同时它们都等值于无穷多个等值的命题公式； 学习资料 - - -细心整理 - - - 欢迎下载 - - - 第 4 页，共 39 页 精品word学习资料 可编辑资料 - - - - - - - - - - - - - - - -- 学习资料收集于网络，仅供参考 联结词完备集 S={￢