离散数学-经典必看.pptVIP

2023/7/17 计算机软件 离散数学 Discrete Mathematics主讲教师：任美睿 2023/7/17　　离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。 2023/7/17　　离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、代数系统和图论。本课程主要讲授以上四个方面的内容。 2023/7/17数理逻辑简介 2023/7/17　　数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，这里所指的数学方法就是引进一套符号体系的方法，所以数理逻辑又称符号逻辑。它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。 2023/7/17数理逻辑的研究内容现代数理逻辑：逻辑演算、证明论、公理集合论、递归论和模型论。逻辑演算是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的，本门课研究命题逻辑与谓词逻辑。 2023/7/17第一章 命题逻辑Proposition Logic第1.1节 命题及联结词 2023/7/17内容：命题，逻辑联结词，命题符号化 (1)掌握命题概念 (2)掌握联结词含义及真值表 (3)掌握命题符号化方法 重点： 2023/7/17一、命题的概念 命题：能判断真假的陈述句。 命题真值：命题所表达的判断结果。真命题：真值为真的命题。 假命题：真值为假的命题。 说明：一切没有判断内容的句子，无所谓是非的 句子，如感叹句、疑问句、祈使句等都不是命题。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。 2023/7/17例1、判断下列句子中哪些是命题。 (1) 重庆是直辖市。 (2) 4是素数。 (4) 请把门关上！ (6) 地球外的星球上也有人。 (3) 。 √T √F √T × × √？(5)大于 2023/7/17例1、判断下列句子中哪些是命题。 (7) 明天有课吗？ (9) 我正在说假话。 (8) 小明和小林都是三好生。 × ×悖论,无法判断真值 √?(10) 2020年春节是晴天。 √? 2023/7/17命题的判断判断一个语句是否为命题，关键： ①首先看是否为陈述句； ②再看其真值是否唯一。要注意两点： ①一个陈述句在客观上能判断真假，而不受人的知识范围的限制； ②一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。 结论:1、命题一定是陈述句，陈述句未必是命题。2、命题的真值有时可以明确给出，但有时还需要依靠环境、条件和实际环境时间才能确定其真值。 2023/7/17命题的记法命题的符号化：P,Q,R,…,Pi, ,Qi ,Ri,…真值的符号化：1/T表真，0/F表假例：P: 2是素数，Q:雪是黑色的 2023/7/17命题的分类例：4是合数。原子命题例：4是合数，并且3是素数。复合命题例：4是合数，并且3是素数，但1既不是素数也不是合数。复合命题 2023/7/17例： 是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。解： 2023/7/17二、逻辑联结词。 这五种常用的联结词有 2023/7/17真值表 1、“非”称为的否定式，记作例如：：11是素数；：11不是素数取值1，取值0。0110 2023/7/17真值表 2、“并且”称为的合取式，记作。例1.1，小刚和小明都是大学生0 00 1001 01 101：小刚是大学生，：小明是大学生解：命题符号化为： 2023/7/17注意：①自然语言中的“既…，又…”, “不但…，而且…”, “虽然…，但是…”, “一面…，一面…”,等都可符号化为 ，在逻辑电路中表示“与门”，在开关电路中表示“串联”联结方式。② 但不要见到“与”或“和”就使用联结词 2023/7/17(1)小丽既聪明又用功。 (2)小丽聪明，但不用功。 (3)小丽不但聪明，而且用功。 (4) 小丽不是不聪明，是不用功。 例2、将下面命题符号化。(5)小刚与小丽都是三好学生。 (6)小刚与王丽是同学。 ：小丽用功。：小丽聪明，R:小刚是三好学生， S :小丽是三好学生。 T:小刚与王丽是同学解：设 2023/7/17真值表 3、“或者”称的析取式，记作。0 00 1011 01