大学离散结构第一讲.ppt

离散结构 答疑与联系方式 讲课方式 考试方式及安排 《离散数学》 [1] 蔡之华　薛思清　吴　杰,《离散数学学》，中国地质大学出版社 2008.9 （1）计算机科学与技术专业的基础理论核心课。 （1）预习 （2）网上查找基础资料 （3）多做练习题 （4）复习 （5）多问多沟通多讨论 离散结构 主要知识点 重 点 难 点 主要知识点 重要知识点 知识难点 第1章 命题逻辑 讲课 10小时 教学目标 课时安排：6～8小时 掌握：命题、逻辑联结词的概念；命题与陈述句的关系，公式与解释的概念，公式的递归定义，用基本等价式化简其他公式；主析取范式与真值表的关系，用真值表法判断公式的类型；公式蕴涵与逻辑结果的概念；形式演绎方法。 理解：用联结词产生复合命题的方法；公式在解释下的真值；公式范式的概念；形式演绎和蕴涵的关系。 主要教学内容 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 联结词全功能集 (选讲) 1.5 对偶与范式 1.6 推理理论 1.7 例题选解 习 题 一 知识回顾 无 新课内容 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 联结词全功能集 (选讲) 1.5 对偶与范式 1.6 推理理论 1.7 例题选解 习 题 一 1.1 命题符号化及联结词 任何基于命题分析的逻辑称为命题逻辑。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。 命题是能唯一判断真假的陈述句。 这种陈述句的判断只有两种可能，一种是正确的判断，一种是错误的判断。如果某个陈述句判断为真（与人们公认的客观事实相符），则我们称其为真命题，并说此命题的真值为真，用1代表；否则称为假命题，并说此命题的真值为假，用0代表。 【例1.1.1】 下述各句均为命题： （1）4是偶数。 （2）煤是白色的。 （3）《几何原本》的作者是欧几里德。 （4）2190年人类将移居火星。 （5）地球外也有生命存在。 上述命题中（1）、（3）是真命题，（2）是假命题，其中的（3）可能有人说不出它的真假，但客观上能判断真假。（4）的结果目前谁也不知道，但到了时候则真假可辨，即其真值是客观存在的，因而是命题。同样，（5）的真值也是客观存在的，只是我们地球人尚不知道而已，随着科学技术的发展，其真值是可以知道的，因而也是命题。 【例1.1.2】 下列语句不是命题： （1）你好吗？ （2）好棒啊！ （3）请勿吸烟。 （4）x＞3。 （5）我正在说谎。 （1）、（2）、（3）均不是陈述句，因而不是命题。（4）是陈述句，但它的真假取决于变量x的取值，例如取x为4时其值为真，取x为2时其值为假，即其真值不唯一，因此不是命题。（5）也是陈述句，但它是悖论，因而也不是命题。 几个有趣的悖论 说谎者悖论：“我正在说谎。”－－他到底说没说谎？ 江湖传言悖论：没有人能避开西门吹雪的那一剑；陆小凤的灵犀指可以夹住任何兵器的来袭。－－这两个人交手的话，胜负如何？ 相对悖论：世上没有绝对的真理。－－这是绝对的吗？ 苏格拉底悖论：我现在唯一知道的事，就是我一无所知。－－知道还是不知道？ 性质悖论：一切都是可能的，不可能也是如此。－－可能还是不可能？ 麦堆悖论：一粒麦子构不成麦堆，两粒也不行，三粒也不行……所以无论多少麦粒都不能构成麦堆。－－肯定错了，但是错在哪里了？ 语言悖论：这句话包含七个字。－－对还是错？ 说明：以上不都是命题逻辑中讲的悖论，同学们可以课余自行考虑。 从上面讨论可以看出，判断一个语句是否是命题的关键是： (1)语句必须是陈述句。 (2)陈述句必须具有唯一的真值。要注意两点： ①一个陈述句在客观上能判断真假，而不受人的知识范围的限制。 ②一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。 以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有“主语+谓语”的形式，在数理逻辑中，我们将这种由简单句构成的命题称为简单命题，或称为原子命题，用p、q、r、pi、qi、ri等符号表示（必要时亦可用其它小写的英文字母表示）。如：