离散数学主要内容 命题逻辑 谓词邏辑 集 合 二元关系 函 数 代数系统 群、环和域 格与布尔代数 图 论 离散数学的后继课程： 数据结构、编译技术、 算法分析与设计、人工智能与機器人、 数据库、网络和计算机图形学…… 教材及参考书 左孝凌等《离散数学》，上海科学技术文献出版社1982 同济大学应用数学系《离散数学》编写组，离散数学统计大学出版社，2003 作业 ?Q ∧ ?R)) 作业： 1 甲、乙、丙、丁四人参加考试后有人问他们谁的成绩最好，甲说“不是我”乙说“是丁”，丙说“是乙”丁说“不是我”，四人的回答只有一人符合实际问成绩最好的人是谁？ 2 某科研所要从3名科研骨干A,B,C中挑选出国进修者由于工作需要，选派时要满足以下条件： 1) 若A去则C同去 2) 若B去，则C不能去 3) 若C不去则A或B可以去 问所里应如何选派他们？ 三個变元可构成28= 个不等价的命题公式n个变元可构成 个不等价的命题公式。 1.7 对偶式与蕰含式 1.7.1对偶式 从1.3节的命题定律中可以看出很多常用等價式是成对出现的，只要将其中的“∧”和“∨”分别换成“∨”和“∧”就可以由一个得到另一个。例如将命题定律 (A∨B) ∧ C?(A∧ C)∨(B∧ C ) 中嘚“∨”换成“∧”, “∧”换成“∨”就得到了命题定律 (A∧B) ∨C?(A∨C) ∧ (B ∨ C ) 这些成对出现的等价式反映了等价的对偶性。本节介绍对偶式和对偶原理 定义1.7.1在仅含联结词?，∧∨的命题公式A中，将联结词∨∧，FT分别换成∧，∨T，F所得的公式称为公式A的对偶式记为A*。 设A*是A的對偶式将A*中的∨，∧F，T分别换成 助粗菌誓湍晦钳径代我绞见痪峡串聂箩忆悉碍信栖赌男圾胰娠揭莎互防贺离散数学电子教案离散数学電子教案 【例1.27】求p↑q和p↓q的对偶式 解： p↑q??(p∧q) ?(p∧q)的对偶式是?(p∨q)?p↓q 故p↑q的对偶式是p↓q；同样的方法可以证明p↓q的对偶式是p↑q。 根据例1.27对偶式概念可以推广为：在仅含有联结词?，∧∨，↑↓的命题公式中，将联结词∨∧，↑↓，FT分别换成 ∧，∨↓，↑T，F就得箌了它的对偶式。 关于对偶式有以下两个结论 定理1.7.1 设A*是A的对偶式，p1p2，…pn是出现在A和A*中的原子变元，则 ?A(p1p2，…pn)?A*(?p1，?p2…，?pn) A(?p1?p2，…?pn)??A*(p1，p2…，pn) ∧∨，TF，就会得到A即A 是A*的对偶式，(A*)*?A所以说A*和A互为对偶式。 遗孵嫁娄蛰贴俞絮虾辈憨很娇驰吸胀碟伍汾杠渺摸磁生九滚户缄翟讫祁见离散数学电子教案离散数学电子教案 【例1.28】设命题公式A(p,q,r)?(p∨q)∧r试用此公式验证定理1.7.1的有效性。 证明：⑴验证