离散数学课件.pdf

Discrete Math 离 散 数 学 第一章 命题逻辑 1 1 命题符号化及联结词 1 2 命题公式及分类 1 3 等值演算 1 4 联结词全功能集 1 5 对偶与范式 1 6 推理理论 1 7 题例分析 例 1 1 1 0 0 1 1 1 0 1 0 0 p q q p 0 0 1 1 p 1 1 1 0 0 1 1 1 0 1 0 0 p q q p 2个命题变项 p q 2 2 4组赋值 解释 2 2 2 16个真值不同的 命题公式 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 P Q P Q P Q P Q P Q 1 1 0 0 C 1 1 1 1 F 1 1 1 0 E 0 1 0 1 5 1 0 0 0 8 1 0 1 0 A 1 1 0 1 D 1 0 1 1 B 1 0 0 1 9 0 1 1 1 7 0 1 1 0 6 0 1 0 0 4 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 3 2 1 0 P Q 真值表 0 1 1 1 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 命题公式 p n p 2 p 1 2 n 行行 n个命题变项 2 n n 组赋值 解释 2 2 n2 n 个真值不同的命题公式 1 3 等值演算 n个命题变元只能生成2 2 n 个真值不同的命题公式 而命题公式集合是无限集 所以 必存在命题公式 的等值问题和同型问题 Def 设A B为两命题公式 若等价式A B是重言 式 则称A与B是等值的 记为A B 或称A逻辑等 价于B A等值于B 若公式A和B的真值表是相同的 则A和B等值 验证两公式是否等值 只需做出它们的真值表 比较最后一列 即可 注 两公式等值 不一定是含相同的命题变项 vs 区别 是逻辑联结词 属于目标语言中的符号 它 出现在命题公式中 不是逻辑联结词 属于元语言中的符号 表 示两个命题公式的一种关系 不属于这两个公 式的任何一个公式中的符号 联系 A B 1 当且仅当 A B 又称A B是永真双条件式 等值 等值关系性质 自反性 对任意A 有A A 对称性 对任意A和B 若A B 则B A 传递性 对任意A B和C 若A B B C 则A C 基本等价式 命题定律 在判定公式间是否等价 有一些简单而又经常使用 的等价式 称为基本等价式或称命题定律 提示 1 将A B C看作集合 2 建立如下对应关系 补 0 空集 1 全集S 重要的等值式 1 双重否定律 A A 运算顺序 右 左 2 等幂律 A A A A A A 3 交换律 A B B A A B B A A B B A 4 结合律 A B C A B C A B C A B C A B C A B C 重要的等值式 5 分配律 A B C A B A C A B C A B A C 6 德 摩根律 A B A B A B A B 7 吸收律 A A B A A A B A 8 零律 A 0 0 A 1 1 0 A 0 1 A 1 提示 1 将A B C看作集合 2 建立如下对应关系 补 0 空集 1 全集S 重要的等值式 9 同一律 A 1 A A 0 A 10 排中律 A A 1 11 矛盾律 A A 0 12 蕴涵等值式 A B A B 13 等价等值式 A B A B B A 14 假言易位 A B B A 15 等价否定等值式 A B A B 16 归谬论 A B A B A 德 摩根律的推广 A 1 A 2 A n A 1 A 2 A n A 1 A 2 A n A 1 A 2 A n 补充 A B A B A B A B A B 判断A B C 与 A B C是否等值 A B C A B C 0 0 0 0 0 0 如果A C B C 或A C B C 是否A B 代入规则vs置换规则 在定义命题公式时 联结词可把已知公式联结成新 的公式 可把逻辑联结词看成运算 除逻辑联结词外 代入 和 置换 从已知公式得 到新的公式 也可将它们看成运算 1 代入规则 Th 在永真式A中 任一原子命题变元R出现的每一 处 用另一公式S代入 所得公式B仍是永真式 注 R与S可能没有任何逻辑关系 2 置换规则 Th 设A 1 是合式公式A的子公式 若A 1 B 1 并且将 A中的A 1 用B 1 替换 得到公式B 则A B 例 求证 P Q P Q 为永真式 证 由排中律知 R R 1 即R R为永真式 用公式 P Q 代入原式中的命题变元R 则得 P Q P Q 由代入规则知 原式是永真式 注 若仅仅把 P Q 代入到永真式的一个析取项 R 得到 P Q R 显然它不是永真式 因为这不符合代入规则所 要求的处处代入 例 验证等值式p q r p q r p q r p q r p q r p q r p q r p q r 例 验证等值式p p q p q P p 1 p q q 代入规则vs置换规则 部分 全部 处处代入 代入 置换方式 A B 永真式 B A 1 B 1 S任意公式 S A 1 A 1 子公式 R原子命题变项 R A 1 命题公式 永真式 A 置换 代入 代入是对原子命题变项而言的 而置换可对命题公 式实行 代入必须是处处代入 而置换可部分替换 也可全 部替换 代入R与S可能没有任何逻辑关系 而置换要求替 换时满足A 1 B 1 判断下列公式的类型 1 q p q p 2 p p q q r 3 p q p 解 1 q p q p q p q p p q p q 1 永真式 例 用等值演算解决下面问题 A B C D4人做百米竞赛 观众甲 乙 丙预报比 赛的名次为 甲 C第一 B第二 乙 C第二 D第三 丙 A第二 D第四 比赛结束后发现甲 乙 丙每人报告的情况都是 各对一半 试问实际名次如何 假设无并列者 解 设a i b i c i d i 分别表示A第i名 B第i名 C第i名 D第i名 i 1 2 3 4 显然a i b i c i d i 中各有一个真命题 c 1 b 2 c 1 b 2 1 c 2 d 3 c 2 d 3 1 a 2 d 4 a 2 d 4 1 因真命题的合取式仍为真命题 1 1 1 1 c 1 b 2 c 1 b 2 c 2 d 3 c 2 d 3 c 1 b 2 c 2 d 3 c 1 b 2 c 2 d 3 c 1 b 2 c 2 d 3 c 1 b 2 c 2 d 3 c 1 b 2 c 2 d 3 c 1 b 2 c 2 d 3 又1 1 a 2 d 4 c 1 b 2 c 2 d 3 a 2 b 2 c 1 c 2 d 3 d 4 C第一 A第二 D第三 B第四 否定中的肯定 老师为了测试甲乙丙丁四名学生的分析推理能力 拿 了五顶式样相同的帽子给他们看 并强调说 这里有 两顶白帽 一顶红帽 一顶黄帽 一顶蓝帽 接着他 让四人依序坐在四级台阶上 然后叫他们闭上眼睛 又替每人戴上一顶帽子 最后 他让学生们张开眼 睛 并判断自己头上戴的帽子是什么颜色 结果是出人意外的 虽说坐在后面的人看见前面的人 所戴帽子的颜色 但甲 乙 丙三人看了看并想了 想 都摇头说猜不出来 某丁坐在最前面 他看不到 别人的帽色 但此时却发话了 说他业已猜到自己所 戴的帽子颜色 某丁是如何断定自己的帽色呢 否定中的肯定 某丁是这样思考的 某甲得天独厚坐得最高 能看到其余三人的帽子 他为什么说猜不出来呢 肯定他看到了前面有人戴 着白帽 因为假如前面的人都戴杂色帽的话 那么 他就能猜出自己所戴的是非白帽而莫属了 再说某乙 她可是个聪明人 某甲的想法 她自然 了如指掌 那么她为什么也说猜不到呢 一定是她 也看到了前面有人戴着白帽 不然的话 她就会从 某甲的态度和其他人的帽色 判断自己戴着白帽 最后说某丙 她的智商绝不比某乙底 可她为什么 也说猜不到呢 理由只能是一个 就是她看到了我 头上戴着白帽 第一章 命题逻辑 1 1 命题符号化及联结词 1 2 命题公式及分类 1 3 等值演算 1 4 联结词全功能集 1 5 对偶与范式 1 6 推理理论 1 7 题例分析 1 4 联结词全功能集 1 联结词的扩充 5个联结词 还不能广泛地做到简洁而直接地表达命题间的 联系 可以根据需要定义更多的联结词 如排 斥或 与非 或非 Def 设P和Q是两命题 复合命题 P Q之中恰有恰有一个成立 称为P与Q的排 斥或 异或 记作 P Q P Q P Q P Q 复合命题 P与Q的否定 称为P与Q的与非式 记作 P Q P Q P Q P Q的真值 P Q为F 当且仅当 P和Q均为T 与非的性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q 复合命题 P或Q的否定 称为P与Q的或非式 记作 P Q P Q P Q P Q的真值 P Q为T 当且仅当 P和Q均为F 或非的性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q 和 都不满足结合律 2 n元真值函数 Def 0 1 上的n元函数f 0 1 n 0 1 就称为一 个n元真值函数 联结词 实际上是一个一元真值函数 f 0 1 f 1 0 而联结词 和 是二元真值函数 f 0 0 0 f 0 1 0 f 1 0 0 f 1 1 1 f 0 0 0 f 0 1 1 f 1 0 1 f 1 1 1 f 0 0 1 f 0 1 1 f 1 0 0 f 1 1 1 f 0 0 1 f 0 1 0 f 1 0 0 f 1 1 1 问题 是否所有的真值函数都可使用常用的5个真 值联结词来表示呢 3 联结词全功能集 已知有8个联结词就够用了 能不能少呢 若能少 表明有些联结词的逻辑功能可由其他联 结词替代 事实上 因为有下列等价式 P Q P Q P Q P Q P Q P Q P Q P Q Q P 常用的5个联结词 和 能由联结词组 或 取代 表示 究竟最少需要几个联结词 联结词全功能集 用最少的几个联结词就能等价表示所有的命题公 式 或者说 用最少的几个联结词就能替代所有联结 词的功能 这便是所要定义的联结词全功能集 Def 称G为联结词极小全功能集 若G满足下列两条件 由G中联结词构成的公式能等价表示任意命题公 式 G中的任一联结词不能用其余联结词等价表示 和 都是联结词极小全功能 集 而 和 都不是 联结词极小全功能集 但为了表示方便 经常使用联结词组 证明 和 都是联结词的完全集 证 1 要证 是联结