离散数学_命题逻辑_11

1、离散数学离散数学 东北石油大学软件学院东北石油大学软件学院王永安王永安离散数学(Discrete Mathematics)n研究离散量的关系离散量的关系的一门科学n研究离散结构离散结构的数学分科（辞海）n用一组基本的指令来编制一个计算机程序，非常类似于从一组公理来构造一个从一组公理来构造一个数学证明数学证明。(D.E.Knuth 1974 图灵奖得主)怎样理解离散n什么是离散？离散就是不连续。离散就是不连续。线与点。人的说话声，鸟叫声等；计算机里储存声音。 生活中，人眼见到的图像(非计算机里的)；计算机里用灰度值(从0到255)表示的图像。计算机不能处理连续信息的，这是由计算机的本质：0和1，

2、决定的。因此，如果要用计算机来处理连续信息，必须经过离散化。离散数学的地位离散数学的构成计算机与离散数学n电子数字计算机是一个离散结构，只能处理离散的数量关系n电子数字计算机是数理逻辑与电子学结合的产数理逻辑与电子学结合的产物物n离散数学是计算机编程的内在思维逻辑的表象内在思维逻辑的表象离散数学的特点n提高抽象思维、严格推理以及综合归纳分析能力n以研究离散量的结构和相互关系为主要目标n显著特征是符号化和形式化符号化和形式化离散数学的用途n又称“计算机数学计算机数学”，因为离散数学的主要应用领域是计算机。数理逻辑数字逻辑电路、密码学图论(包括树)数据结构、操作系统 、编译原理、计算机网络集合论和

3、关系代数软件工程和数据库原理考核方式与成绩评定期末采用闭卷考试形式。 总评成绩： 作业、平时考勤及学习态度占 15%，旷课一次扣2分，迟到一次扣1分。 期末考试占 85%。qq群:173410467博客: http:/ 第一部分数理逻辑什么是数理逻辑n数理逻辑(Mathematical Logic) 是研究演绎推理的一门学科。用数学方法数学方法来研究推理的规律推理的规律统称为数理逻辑。例1n请看下面两段文字请看下面两段文字(1)你的钱在你的钱包里，你的钱包在你的口袋里，那么你的钱一定在你的口袋里。(2) 人必然会死，苏拉格底是人，因此苏拉格底会死。什么是数理逻辑主要研究内容：推理 着重于推理过

4、程是否正确 着重于语句间的关系主要研究方法：数学方法 就是引进一套符号体系的方法,故数理逻辑也称为符号逻辑(Symbolic Logic)。例2n已知1+1=2，1+2=3，请问你的推理结果是什么？ A. 2-1=1 B. 3-2=1 C. 3-1=2 D. 1+1+1=3误区：条件中没有给出“-”“-”-”是常识性臆断是常识性臆断结论：推理结果只有一个（推理表象松散、结论：推理结果只有一个（推理表象松散、 实质严谨）实质严谨）正确答案 D数理逻辑的组成命题逻辑命题逻辑命题的基本概念命题逻辑等值演算命题逻辑推理谓词逻辑谓词逻辑 ( (一阶逻辑一阶逻辑) )谓词逻辑基本概念谓词逻辑等值演算谓词逻

5、辑推理总结什么是数理逻辑？用数学方法来研究推理的规律统称为数理逻辑。用数学方法来研究推理的规律统称为数理逻辑。数理逻辑的组成？命题逻辑和谓词逻辑命题逻辑和谓词逻辑为什么要研究数理逻辑？ 程序算法数据程序算法数据 算法逻辑控制算法逻辑控制 第一章命题逻辑基本概念命题逻辑基本概念n1.1 1.1 命题与联结词命题与联结词n1.2 命题公式及其赋值1.1命题与联结词n一、命题一、命题1.1.命题的概念命题的概念定义定义.1 非真即假非真即假 的陈述句称作命题。命题的判断结果判断结果称为命题的真值。真值只能取两个值：真或假(0或1) 真判断正确 假判断错误n2.2.命题的特点命题的特点

6、任何命题的真值都是唯一的。只有具有确定真值确定真值的陈述句陈述句才是命题。真值是否唯一与我们是否知道它的真值是两回事。1.1命题与联结词1.1命题与联结词例例1.1 1.1 判断下列语句是否是命题判断下列语句是否是命题(1)北京是中国的首都。 (2)所有的树木都是植物。(3)昨天大庆下雨。 (4) 请勿吸烟!(5) 这朵花多好看呀!(6)我正在说假话。悖论，不是命题悖论，不是命题真命题真命题命题命题不是命题不是命题不是命题不是命题真命题真命题1.1命题与联结词例例1.1 1.1 判断下列语句是否是命题判断下列语句是否是命题(7) x+80。(8)你出去么？(9)5或6是素数。(10)如果行列式

7、的两行对应成比例，则行列式的值为0。(11)角A与角B相等当且仅当A与角B是对顶角。不是命题不是命题不是命题不是命题不是命题不是命题真命题真命题假命题假命题n2.2.命题的特点命题的特点命题一定是陈述句,但陈述句不一定是命题。命题的真值有时明确给出，有时还要依靠环境、条件、实际情况等因素环境、条件、实际情况等因素才能确定其真值。1.1命题与联结词1.1命题与联结词注意：注意：一切没有判断内容的句子都不能一切没有判断内容的句子都不能作为命题。作为命题。如命令句、感叹句、如命令句、感叹句、祈使句、疑问句、悖论（二义性祈使句、疑问句、悖论（二义性的陈述句）等。的陈述句）等。1.1命题与联结词例例1.

8、2 1.2 判断下列语句是否是命题，判断下列语句是否是命题，并判断其真值。并判断其真值。(1) 黑龙江不是一个国家。(2) 3既是素数又是奇数。(3) 刘翔是大学生或是运动员。(4) 如果周末天气晴，则我们去郊外旅游。(5) 2+2=4当且仅当雪是白的。1.1命题与联结词3 3. .命题的分类命题的分类 命题定义定义1.1.2 1.1.2 简单命题(原子命题)：由简简单的陈述句单的陈述句构成的命题。(不能再分解为更简单命题的命题)定义定义1.1.3 1.1.3 复合命题：由简单命题简单命题用联联结词联结结词联结而成的命题。复合命题简单命题1.1命题与联结词n4.4.命题符号化命题符号化简单命题

9、用p,q,r等表示。约定：约定：在数理逻辑中像 “x x”、“y y”、“z z”等字母等字母总是表示变量。命题的真值符号化为用“1” 或“T” 表示“真”；用“0” 或“F” 表示“假”。1.1命题与联结词n4.4.命题符号化命题符号化复合命题的符号化用p，q，r，等表示简单命题（通常称p，q，r，为命题常项或命题常元），将p，q，r， 用某些联结词符联结词符按一定的逻辑关系联结起来就是复合命题的符号化形式。1.1命题与联结词n二、联结词二、联结词否定联结词 合取联结词 析取联结词 蕴涵联结词 等价联结词 1.1命题与联结词n1.1.否定联结词否定联结词否定联结词是一个一元运算一元运算。例例

10、1.31.3 将下列命题符号化将下列命题符号化 p ：上海是一个大城市。p ：上海不是不是一个大城市。 q ：5能被2整除。q ：5不能不能被2整除。1.1命题与联结词n1.1.否定联结词否定联结词定义定义.4设p为一命题，复合命题 “非p”（或“p的否定”）称为p的否定式，记作p ，称 为为否定联结词否定联结词。p为真当且仅当p为假。p的真值表为 p p 0 1 1 01.1命题与联结词n2.2.合取联结词合取联结词例例1.41.4 将下列命题符号化将下列命题符号化 (1) p：22=5， q：雪是黑的。 pq：22=5并且并且雪是黑的。(2) r：2是偶数，s：6是偶数。

11、rs：2和和6都是偶数。1.1命题与联结词n2.2.合取联结词合取联结词定义定义.5设p，q为二命题，复合命题 “p并且q”（或“p与q”）称为p与q的合取式，记作pq，称 为为合取联结词合取联结词。pq为真当且仅当p与q同时为真。合取联结词是一个二元运算。1.1命题与联结词n2.2.合取联结词合取联结词pq的真值表为 p q pq 0 0 1 1 0 1 0 1 0 0 0 11.1命题与联结词n2.2.合取联结词合取联结词自然语句中的“既又”，“不但而且”，“不仅而且”， “一边一边”，“虽然但”，等都可符号化为pq 的形式。注意注意: :并非所有的“和”“与”都可符号化为

12、1.1命题与联结词 例例1.51.5 将下列命题符号化将下列命题符号化（1）小李既既是100米冠军，又又是400米冠军。 （2）他一边一边吃饭，一边一边看电视。（3）他不仅不仅聪明，而且而且用功。（4）他虽然虽然不太聪明，但但他很用功。（5）他不是不是不聪明，而是而是不用功。解解 （1）设p ：小李是100米冠军, q ：小李是400米冠军。pq （2） s：他吃饭，t ：他看电视。 st （3）设p：他聪明， q： 他用功。 pq （4） pq （5） (p)qn3.3.析取联结词析取联结词例例1.61.6 将下列命题符号化将下列命题符号化(1)“(1)“王燕学过英语王燕学过英语或或法语法语

13、”符号化为符号化为pqpq，其中，其中p p：王燕学过英语，：王燕学过英语，q q：王燕学过法语。：王燕学过法语。但自然语言中，有时但自然语言中，有时“或或”表示排斥性或。表示排斥性或。(2)(2)派小王派小王或者或者小李中的一个人去开会小李中的一个人去开会pq正确答案正确答案 (pq)(pq)1.1命题与联结词1.1命题与联结词n3.3.析取联结词析取联结词定义定义.6设p，q为二命题，复合命题 “p或q”称为p与q的析取式，记作 pq ，称 为为析取联结词析取联结词。pq为真当且仅当p与q中至少一个为真。析取联结词是一个二元运算。注意注意: :析取式析取式pqpq表示的是一

14、种表示的是一种相容或相容或，即允许即允许p p与与q q同时为真。同时为真。1.1命题与联结词n3.3.析取联结词析取联结词pq的真值表为 p q pq 0 0 1 1 0 1 0 1 0 1 1 11.1命题与联结词4.4.蕴涵联结词蕴涵联结词例例1.71.7 将下列命题符号化将下列命题符号化(1)p：f(x)是可微的，q：f(x)是连续的。 pq：若f(x)是可微的，则f(x)是连续的。(2)p：经一事， q：长一智。 pq：不经一事，不长一智。1.1命题与联结词n4.4.蕴涵联结词蕴涵联结词定义定义.7设p，q是二命题，复合命题 “如果p，则q”称为p与q的蕴涵式，记作

15、pq。称p为蕴涵式的前件，q为蕴涵式的后件，称为为蕴涵蕴涵联结词联结词。 pq为假当且仅当p为真q为假。蕴涵联结词是一个二元运算。1.1命题与联结词n4.4.蕴涵联结词蕴涵联结词pq的真值表为 p q pq 0 0 1 1 0 1 0 1 1 1 0 11.1命题与联结词例例1.8 1.8 将下列命题符号化并判断其真值将下列命题符号化并判断其真值（1）若2+2=4，则地球是运动的。（2）若2+24，则地球是运动的。（3）若2+2=4，则地球是静止的。（4）若2+24，则地球是静止的。解解 p：2+2=4 ，q：地球是运动的：地球是运动的，（1）符号化为）符号化为 pq ,真值真值为为1。（2）

16、符号化为）符号化为 pq ,真值真值为为1。（3）符号化为）符号化为 pq ,真值真值为为0 。（4）符号化为）符号化为 pq ,真值真值为为1。1.1命题与联结词n使用蕴涵联结词时应注意的问题使用蕴涵联结词时应注意的问题在自然语句中“如果p ，则q”中的p与q往往有某种内在的联系，否则无意义。而在数理逻辑中p与与q不一定有什么内在联系不一定有什么内在联系。只要p，q能够分别确定真值， pq即成为命题。在自然科学中， “如果p ，则q”往往表示前件p为真， 后件q也为真的推理关系。而在数理逻辑中， 当p为真， q也为真时，命题pq为真，这与自然语言是一致的；但当当p为假时，则不为假时，则不管管

17、q是什么命题，命题是什么命题，命题 pq都是真命题都是真命题，这与自然语言是不一致的。1.1命题与联结词n4.4.蕴涵联结词蕴涵联结词自然语句中的“只要p就q”，“p仅当q”，“只有q才p”，“除非q才p”等都可符号化为pq 的形式。只要明天晴天只要明天晴天,我们就去郊游。我们就去郊游。p：明天晴天明天晴天，q：我们去郊游，我们去郊游，pq：只要明天晴天只要明天晴天,我们就去郊游。我们就去郊游。1.1命题与联结词例例1.9 1.9 将下列命题符号化将下列命题符号化(1)只有2是偶数，3才能被2整除(2)除非6能被4整除，6才能被2整除(3)只有天下雨，他才乘公共汽车上班(4)除非天下雨，否则他

18、不乘公共汽车上班解(1) p：2是偶数， q：3能被2整除， qp (2) r： 6能被4整除， s： 6能被2整除, sr (3) u：天下雨, v：他才乘公共汽车上班, vu (4) vu (uv )1.1命题与联结词例例1.10 1.10 将下列命题符号化将下列命题符号化(1) p：a2+b2=a2，q： b=0。 pq：a2+b2=a2当且仅当b=0。 (2) s：1+2=3， r： 雪是黑的。 sr：1+2=3当且仅当雪是黑的。 (3) u：燕子飞回北方， v：春天来了。 uv：燕子飞回北方，春天来了。1.1命题与联结词n5.5.等价联结词等价联结词定义定义.8 设p

19、，q为二命题，复合命题 “p当且仅当q”称为p与q的等价式，记作 pq，称为为等价联结词等价联结词。pq为真当且仅当p与q的真值相同。等价联结词是一个二元运算。1.1命题与联结词n5.5.等价联结词等价联结词pq的真值表为 p q pq 0 0 1 1 0 1 0 1 1 0 0 11.1命题与联结词例例1.11 1.11 将下列命题符号化并判断其真值将下列命题符号化并判断其真值（1）若2+2=4当且仅当3+3=6。（2）若2+24当且仅当3+3=6。（3）若2+2=4当且仅当3+36。（4）若2+2 4当且仅当3+36。解解 p：2+2=4，q： 3+3=6。（1）符号化为）符号化为 pq，真值真值为为1。 （2）符号化为）符号化为 pq，真值真值为为0。（3）符号化为）符号化为 pq，真值真值为为0。（4）符号化为）符号化为 pq，真值真值为为1。1.1命题与联结词n6.6.联结词的优先级顺序联结词的优先级顺序以上五种联结词，构成一个联结词集，