离散数学第1章 命题演算.ppt

《离散数学第1章 命题演算.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本课程的知识范围及相关课程的关系：绪论离散数学涉及的数学领域非常广，同时与计算机科学和相关学科关系非常密切，是很多计算机有关课程的基础．离散数学是《算法分析》、《数据结构》、《数据库理论》、《编译原理》、《操作系统》、《可计算性理论》、《人工智能》、《形式语言与自动机》、《信息管理与检索》以及《开关理论》等课程的先修课，也是研究自动控制、管理科学、电子工程等的重要工具。1引言数理逻辑是用数学上的形式化的方法研究形式逻辑中推理规律的一种理论，它通过引进一套符号化形式体系，进行逻辑推理，所以数理逻辑也称为符号逻辑。自然语言是

2、极其丰富多彩的，然而也有模棱两可、含糊多义的特性，因此，对于严格的逻辑推理，使用自然语言是极不方便的，需要引入一种形式化语言，它具有单一、明确的含义，这种形式化语言在数理逻辑中称为目标语言（或称对象语言），由目标语言和一些规定的公式与符号构成了数理逻辑的形式符号体系。2第一章命题演算3§1-1命题与联结词1.1命题数理逻辑研究的中心问题是推理,而推理的前提和结论都是表达判断的陈述句。因而表达判断的陈述句就成了推理的基本要素。4§1-1命题与联结词在数理逻辑中，能判断真假但不能既真又假的陈述句称为命题。即，做为命题的陈述句

3、所表达的判断只有两种结果：正确的或错误的，称这种判断结果为命题的真值。真值只能取两个值：真(Ｔ或1）或假（Ｆ或０）。称真值为真的命题为真命题，真值为假的命题为假命题。5例:判断下列语句是否是命题（1）上海是个大城市。（2）所有素数都是奇数。（3）3是奇数。（4）雪是黑色的。（5）地球外的星球上也有生物。（６）a是大于1的数。（７）你去哪里？（８）全体立正！（９）请进来！（10）x+y>106注意事项1、命题一定是陈述句，但陈述句不一定是命题。2、真值是否唯一与我们是否知道它是两回事。总之:命题是具有唯一真值的陈述句(它只

4、有T和F两种)。7思考题：这句话是否为命题：我正在说假话。1.若这句话为T，则说明我此时正在说真话，那句子的取值应该为F2.若这句话为F，则说明我此时正在说假话，那句子的取值应该为T所以这句话没有办法判断真假，所以不是命题！8命题符号化为了能用数学方法来研究命题之间的逻辑关系和推理，需要将命题符号化。一个任意的没有赋予具体内容的命题是一个命题变元。定义：以“真”、“假”为其变域的变元称为命题变元。常用大写的英文字母A，B，C，…P，Q，R，…等来表示一个命题或命题变元。9命题符号化由于命题变元是表示任意的命题，所以它的真

5、值没有被确定，只有当命题变元用一个具体的命题“代入”时，它才有确定的真值。例如，用P表示任意的命题，则P是命题变元，P没有确定的真值。当P用具体命题如“所有素数都是奇数”代入后，P就表示命题“所有素数都是奇数”，这时P有确定的真值为F。用一个具体的命题“代入”命题变元，也称为对命题变元进行指派。10原子命题通常把不含任何联结词的命题称为原子命题或简单命题。例:(1)5不是素数。(2)2和3都是素数。(3)2或3是素数。(4)若数a是4的倍数，则它一定是2的倍数。(5)数a是偶数当且仅当它能被2整除。易知:以上都不是简单命

6、题。11复合命题联结词可以把一些简单命题组合成复杂命题，由简单命题和联结词组合成的复杂命题称为复合命题。在自然语言中，各类语句的联结词“与”、“并且”、“或”等，往往没确定、惟一的含义，是多义性的。在数理逻辑中，命题的联结词都有严格的定义，并且予以符号化。12联结词1.否定定义设P是命题，P的否定“非P”也是一个命题，记作﹁P。﹁称为否定联结词。当P的真值为T时，﹁P的真值为F。当P的真值为F时，﹁P的真值为T例设P：张三是上海人。则﹁P：张三不是上海人。P﹁PTFFT13联结词2.合取定义设P,Q是命题，复合命题“P并

7、且Q”称为Ｐ与Ｑ的合取式,记作P∧Q，∧称为合取联结词。当且仅当P，Q的真值同为T时，P∧Q的真值才为T，在其他情况下，P∧Q真值都为F。PQP∧QTTFFTFTFTFFF14联结词例如设P：张绍昆是个男人。Q：张绍昆是个教师。则复合命题“张绍昆是个男人并且是个教师”可符号化为：P∧Q。即P∧Q：张绍昆是个男教师。15注意事项:1、自然语言中的“既…又…”、“不但…而且”、“虽然…但是”等都可以符号化为∧2、联结词合取∧的概念和自然语言中的“与”、“并且”、“和”的意义相似，但并不完全相同。16注意事项:例1：小王是三好

8、学生，小张是三好学生。这两个命题的合取可写作：小王和小张都是三好学生。但是对于命题：小王和小张是好朋友。它不是两个命题的合取，只能看做是一个命题。17注意事项:例2：设P：我去泰山看日出。Q：教室里有两台彩电。这两个命题的合取为：P∧Q：我去泰山看日出与教室里有两台彩电。在自然语言中，上述命题的合取是没有意义的，因为