《离散数学：1-1 命题符号化及联结词1-2 命题公式及分类》由会员分享，可在线阅读，更多相关《离散数学：1-1 命题符号化及联结词1-2 命题公式及分类（51页珍藏版）》请在金锄头文库上搜索。
1、1离散数学离散数学2亚里士多得n 数学是研究数量的科学n 研究数和量的学科叫做数学n 研究数及其属性的学科叫做算术n 研究量及其属性的学科叫做几何3笛卡尔n数是一种离散的数量n线是一种连续的数量n数学是研究顺序和度量的科学n顺序=数n度量=量4罗素n数学=逻辑n逻辑是数学的少年时代n数学是逻辑的成年时代5科朗.罗宾斯n数学作为人类智慧的一种表达形式，反映生动活泼的意念、深入细致的思考、以及完美和谐的愿望n其基础是逻辑和直觉、分析和推理、共性和个性6丁石孙n数学的研究对象是客观世界的和逻辑可能的数量关系和结构关系7关肇直n数学是研究现实世界中量的关系的科学8离散数学(Discrete Mathe
2、matics)n研究离散量的关系的一门科学n研究离散结构的数学分科（辞海）9离散数学的由来与发展n一、古老n 历史：n 计数：自然数n 发展： n 图论：Konigsberg七桥问题n二、年青n 新生：n 计算机： 二进制运算10离散数学的研究对象n离散数学是现代数学的重要分支，它所研究的对象是离散的数量关系和离散量的结构模型n离散数学是与信息科学及其相关的现代科学领域密切相关的数学学科 11离散数学的应用背景n离散数学具有广泛的应用背景信息科学及相关领域需要对离散结构建立相应的数学模型，或对连续关系的数学模型离散化，离散数学就是适应这种需要而确立的，同时离散数学也为这些学科的发展提供了数学基
3、础12离散数学课程设置n计算机系核心课程n信息类专业必修课程n其它类专业的重要选修课程13离散数学的后继课程n 数据结构、编译技术n 算法分析与设计、人工智能n 数据库n 14主要内容主要内容n数理逻辑数理逻辑(Mathematics Logic)n集合论集合论(Sets)n代数结构代数结构(Algebraic Structure)n图论图论(Graph Theory)n组合分析初步组合分析初步(Combination)n形式语言和自动机初步形式语言和自动机初步Formal Languages and Automata 15教材与教学参考书教材与教学参考书n教材：教材：耿素云、屈婉玲、张立昂，
4、离散数学（第四版）耿素云、屈婉玲、张立昂，离散数学（第四版），清华大学出版社，清华大学出版社, 2008. n教学参考书：教学参考书：屈婉玲、耿素云、张立昂，离散数学题解（第屈婉玲、耿素云、张立昂，离散数学题解（第三版），清华大学出版社，三版），清华大学出版社，2008. 16两本有代表性的两本有代表性的离散数学离散数学英文参考书籍。英文参考书籍。n高高教教出出版版社社2001年年影影印印出出版版的的Discrete Mathematical Structures (Fourth Edition) （B Kolman, Robert C. Busby, Sharon Ross著），中文名为著）
5、，中文名为离散数学结构离散数学结构。n机机 械械 工工 业业 出出 版版 社社 2003年年 影影 印印 出出 版版 的的 Discrete Mathematics and Its Applications (英英 文文 Fifth Edition)（Kenneth H.Rosen著著），中中文文名名为为离离散散数数学学及其应用及其应用。17离散数学课程的学习方法n强调：逻辑性、抽象性n注重：概念、方法与应用n对概念的理解是学习的重中之重.一开始必须准确、全面、完整地记住并理解所有的定义和定理。具体做法是在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽
6、象能够适应，并为后续学习打下良好的基础。n花时间做课后习题解离散数学的题.注重解题方法。如果拿到一道题，立即能够看出它所属的类型及关联的知识点，就不难选用正确的方法将其解决，反之则事倍功半。 18考核方式u课堂出勤课堂出勤(10%)u课后作业课后作业(20%)u期末考试期末考试(70%)加分：加分：u回答课堂提问回答课堂提问u提出对教学有帮助的建议和意见提出对教学有帮助的建议和意见19数理逻辑部分数理逻辑部分n第第1章章 命题逻辑命题逻辑n第第2章章 一阶逻辑一阶逻辑20q 数理逻辑是研究推理的数学学科，着重于推理过程以及推理是否正确的研究。它分为辩证逻辑辩证逻辑与形式逻辑形式逻辑两种。q 数
7、理逻辑是用数学方法数学方法研究逻辑学中形式逻辑的一种分支学科。这里的数学方法其主要待点是引进了一套符号体系作为重要的手段，因此数理逻辑又称为符号逻辑符号逻辑。q 第一章主要介绍命题逻辑的基本概念、等值演算和推理理论。21引言引言v 推理是数理逻辑的主要研究内容，推理最基本的组成成分是什么呢？v 推理1：若华盛顿是美国的首都，则多伦多是加拿大的首都。华盛顿是美国的首都，所以，多伦多是加拿大的首都。v 推理2：如果今天天气晴朗，我就去公园。今天天气晴朗，所以，我就去了公园。构成推理最基本的要素，除联结词外就是陈述句了。命题。22第第1章章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联
8、结词1.2 命题公式及分类命题公式及分类1.3 等值演算等值演算1.4 联结词全功能集联结词全功能集1.5 对偶与范式对偶与范式1.6 推理理论推理理论231.1 命题符号化及联结词命题符号化及联结词 n命题与真值命题与真值n原子命题原子命题n复合命题复合命题n命题常项命题常项n命题变项命题变项n联结词联结词 24命题与真值命题与真值 命题命题: 判断结果惟一的陈述句判断结果惟一的陈述句命题的真值命题的真值: 判断的结果判断的结果真值的取值真值的取值: 真与假真与假真命题真命题: 真值为真的命题真值为真的命题假命题假命题: 真值为假的命题真值为假的命题注意注意: 感叹句、祈使句、疑问句都不是命
9、题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是陈述句中的悖论以及判断结果不惟一确定的也不是命题命题 25 例例 下列句子中那些是命题？下列句子中那些是命题？ (1) 是无理数是无理数. (2) 2 + 5 8. (3) x + 5 3. (4) 你有铅笔吗？你有铅笔吗？ (5) 这只兔子跑得真快呀！这只兔子跑得真快呀！ (6) 请不要讲话！请不要讲话！ (7) 我正在说谎话我正在说谎话.真命题真命题假命题假命题真值不确定真值不确定疑问句疑问句感叹句感叹句祈使句祈使句悖论悖论(3)(7)都不是命题都不是命题26命题的分类命题的分类 简单命题简单命题( (原子命题原
10、子命题) )： 简单陈述句构成的命题简单陈述句构成的命题 复合命题复合命题： 由简单命题与联结词按一定规则复合由简单命题与联结词按一定规则复合 而成的命题而成的命题 27简单命题符号化简单命题符号化 用小写英文字母用小写英文字母 p, q, r, , ,pi, ,qi, ,ri (i1）表示）表示简单命题简单命题用用“1”表示真，用表示真，用“0”表示假表示假例如，令例如，令 p： 是有理数，则是有理数，则 p 的真值为的真值为 0 q：2 + 5 = 7，则，则 q 的真值为的真值为 1 28联结词与复合命题联结词与复合命题 1.否定式与否定联结词否定式与否定联结词“ ” 定定义义 设设p为
11、为命命题题，复复合合命命题题 “非非p”（或或 “p的的否否定定”）称称 为为p的的否定式否定式，记作，记作 p. . 符号符号 称作称作否定联结词否定联结词，并规，并规 定定 p 为真当且仅当为真当且仅当p为假为假. .2.合取式与合取联结词合取式与合取联结词“” 定义定义 设设p, ,q为二命题为二命题, ,复合命题复合命题“p并且并且q”( (或或“p与与q”) )称称 为为p与与q的的合取式合取式，记作，记作pq. . 称作称作合取联结词合取联结词，并规，并规 定定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真注意：描述合取式的灵活性与多样性注意：描述合取式的灵活性与多样性 分
12、清简单命题与复合命题分清简单命题与复合命题 29 例例 将下列命题符号化将下列命题符号化. (1) 王晓既用功又聪明王晓既用功又聪明. (2) 王晓不仅聪明，而且用功王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生张辉与王丽都是三好生. (5) 张辉与王丽是同学张辉与王丽是同学. 解解 令令 p：王晓用功，：王晓用功，q：王晓聪明，则：王晓聪明，则 (1) pq (2) pq (3) pq.30 例例 (续续) 令令 r : 张辉是三好学生，张辉是三好学生，s :王丽是三好学生王丽是三好学生 (4) rs. (5) 令令 t : 张
13、辉与王丽是同学，张辉与王丽是同学，t 是简单命题是简单命题 .说明说明: (1)(4)说明描述合取式的灵活性与多样性说明描述合取式的灵活性与多样性. (5) 中中“与与”联联结结的的是是两两个个名名词词，整整个个句句子子是是一个简单命题一个简单命题.31联结词与复合命题联结词与复合命题( (续续) ) 定义定义 设设 p,q为二命题，复合命题为二命题，复合命题“p或或q”称作称作p与与q 的的析取式析取式，记作，记作pq. 称作称作析取联结词析取联结词，并规，并规 定定pq为假当且仅当为假当且仅当p与与q同时为假同时为假.例例 将下列命题符号化将下列命题符号化 (1) 2或或4是素数是素数.
14、(2) 2或或3是素数是素数. (3) 4或或6是素数是素数. (4) 小元元只能拿一个苹果或一个梨小元元只能拿一个苹果或一个梨. (5) 王晓红生于王晓红生于1975年或年或1976年年. 3.析取式与析取联结词析取式与析取联结词“”32解解 令令 p:2是素数是素数, q:3是素数是素数, r:4是素数是素数, s:6是素数是素数, , 则则 (1), (2), (3) 均为均为相容或相容或. . 分别符号化为分别符号化为: : pr , pq, rs, 它们的真值分别为它们的真值分别为 1, 1, 0. 而而 (4), (5) 为为排斥或排斥或. 令令 t :小元元拿一个苹果，小元元拿一
15、个苹果，u:小元元拿一个梨，小元元拿一个梨， 则则 (4) 符号化为符号化为 (t u) ( tu). 令令v :王晓红生于王晓红生于1975年年, ,w: :王晓红生于王晓红生于1976年年, ,则则 (5) 既可符号化为既可符号化为 (v w)( vw), 又可又可符号化为符号化为 vw , 为什么为什么? 33联结词与复合命题联结词与复合命题( (续续) ) 定定义义 设设 p,q为为二二命命题题，复复合合命命题题 “如如果果p,则则q” 称称作作p与与q的的蕴蕴涵涵式式，记记作作pq，并并称称p是是蕴蕴涵涵式式的的前前件件，q为为蕴蕴涵涵式式的的后后件件. 称称作作蕴蕴涵涵联联结结词词
16、，并并规定，规定，pq为假当且仅当为假当且仅当 p 为真为真 q 为假为假.4.蕴涵式与蕴涵联结词蕴涵式与蕴涵联结词“”34pq 的逻辑关系：的逻辑关系：q 为为 p 的必要条件的必要条件“如果如果 p，则，则 q ” 的不同表述法很多：的不同表述法很多： 若若 p，就，就 q 只要只要 p，就，就 q p 仅当仅当 q 只有只有 q 才才 p 除非除非 q, 才才 p 或或 除非除非 q, 否则非否则非 p. .当当 p 为假时，为假时，pq 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件联结词与复合命题联结词与复合命题( (续续) )35 例例 设设 p p: :
17、天冷，天冷，q q: :小王穿羽绒服，小王穿羽绒服， 将下列命题符号化将下列命题符号化 (1) 只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：
18、注意： pq 与与 qp 等值（真值相同）等值（真值相同） pqpqpqpqqp qpqpqp36联结词与复合命题联结词与复合命题( (续续) )定定义义 设设p，q为为二二命命题题，复复合合命命题题 “p当当且且仅仅当当q”称称作作p与与q的的等等价价式式，记记作作pq. 称称作作等等价价联联结结词词.并并规规定定pq为为真真当当且且仅仅当当p与与q同同时时为为真真或或同同时时为为假假.说明说明: (1) pq 的逻辑关系的逻辑关系:p与与q互为充分必要条件互为充分必要条件 (2) pq为真当且仅当为真当且仅当p与与q同真或同假同真或同假5.等价式与等价联结词等价式与等价联结词“”37例例
19、求下列复合命题的真值求下列复合命题的真值 (1) 2 + 2 4 当且仅当当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当当且仅当 3 是偶数是偶数. (3) 2 + 2 4 当且仅当当且仅当 太阳从东方升起太阳从东方升起. (4) 2 + 2 4 当且仅当当且仅当 美国位于非洲美国位于非洲. (5) 函数函数 f (x) 在在x0 可导的充要条件是它在可导的充要条件是它在 x0连续连续. 它们的真值分别为它们的真值分别为 1，0，1，0，0.38联结词与复合命题联结词与复合命题( (续续) )以上给出了以上给出了5个联结词：个联结词： , , , , ，组成，组成一个联结词集合一
20、个联结词集合 , , , , ， 联结词的优先顺序为：联结词的优先顺序为： , , , , ; 如果出如果出现的联结词同级，又无括号时，则按从左到右现的联结词同级，又无括号时，则按从左到右的顺序运算的顺序运算; 若遇有括号时，应该先进行括号若遇有括号时，应该先进行括号中的运算中的运算. 注意注意: : 本书中使用的本书中使用的 括号全为圆括号括号全为圆括号. 39联结词与复合命题(续)联结词优先级联结词优先级:( );:( ); ; , ; ;同级按从左到右的顺序进行同级按从左到右的顺序进行 p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0
21、 0 1 0 0 1 1 0 1 1 1 1基本复合命题的真值基本复合命题的真值401.2 命题公式及分类命题公式及分类命题变项与合式公式命题变项与合式公式公式的赋值公式的赋值真值表真值表命题的分类命题的分类 重言式重言式 矛盾式矛盾式 可满足式可满足式41命题变项与合式公式命题变项与合式公式 命题常项命题常项：简单命题：简单命题命题变项命题变项：真值不确定的陈述句：真值不确定的陈述句定义定义 合式公式合式公式 (命题公式命题公式, 公式公式) 递归定义如下：递归定义如下：(1) 单个命题常项或变项单个命题常项或变项 p,q,r, ,pi ,qi ,ri ,0,1 是是合式公式合式公式(2)
22、若若A是合式公式，则是合式公式，则 ( A)也是合式公式也是合式公式(3) 若若 A, B是是 合合 式式 公公 式式 ， 则则 (A B), (A B), (AB), (AB)也是合式公式也是合式公式(4) 只只有有有有限限次次地地应应用用(1)(3)形形成成的的符符号号串串才才是是合合式公式式公式说明说明: 元语言与对象语言元语言与对象语言, 外层括号可以省去外层括号可以省去 42合式公式的层次合式公式的层次 定义定义 (1) 若公式若公式A是单个的命题变项是单个的命题变项, 则称则称A为为0层公式层公式.(2) 称称A是是n+1(n0)层公式是指下面情况之一：层公式是指下面情况之一： (
23、a) A= B, B是是n层公式；层公式； (b) A=B C, 其中其中B,C分别为分别为i层和层和j层公式，且层公式，且 n=max(i, j)； (c) A=B C, 其中其中B,C的层次及的层次及n同同(b)； (d) A=BC, 其中其中B,C的层次及的层次及n同同(b)； (e) A=BC, 其中其中B,C的层次及的层次及n同同(b). 43合式公式的层次合式公式的层次 (续续) 例如例如 公式公式 p 0层层 p 1层层 pq 2层层 (pq)r 3层层 ( p q) r)( r s) 4层层44公式的赋值公式的赋值 定义定义 给公式给公式A中的命题变项中的命题变项 p1, p2
24、, , pn指定指定一组真值称为对一组真值称为对A的一个的一个赋值赋值或或解释解释成真赋值成真赋值: 使公式为真的赋值使公式为真的赋值成假赋值成假赋值: 使公式为假的赋值使公式为假的赋值说明说明： 赋赋值值 = 1 2 n之之间间不不加加标标点点符符号号， i=0或或1. A中中仅仅出出现现 p1, p2, , pn，给给A赋赋值值 1 2 n是是指指 p1= 1, p2= 2, , pn= n A中仅出现中仅出现 p, q, r, , 给给A赋值赋值 1 2 3是指是指p= 1,q= 2 , r= 3 含含n个变项的公式有个变项的公式有2n个赋值个赋值. 45真值表真值表 真值表真值表: 公
25、式公式A在所有赋值下的取值情况列成的表在所有赋值下的取值情况列成的表 例例 给出公式的真值表给出公式的真值表 A= (qp) qp 的的真值表真值表 p q qp (qp) q (qp) qp 0 00 11 01 1 1011 0001 111146例例 B = ( p q) q 的的真值表真值表 p q p p q ( p q) ( p q) q0 00 11 01 1 1100110100100000实例实例47例例 C= (p q) r 的的真值表真值表 p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 00111
26、11 1 1010101 0 1110101048公式的类型公式的类型 定义定义 设设A为一个命题公式为一个命题公式 (1) 若若A无成假赋值，则称无成假赋值，则称A为为重言式重言式( (也称也称永真式永真式) ) (2) 若若A无成真赋值，则称无成真赋值，则称A为为矛盾式矛盾式( (也称也称永假式永假式) ) (3) 若若A不是矛盾式，则称不是矛盾式，则称A为为可满足式可满足式注意：重言式是可满足式，但反之不真注意：重言式是可满足式，但反之不真. .上例中上例中A为重言式，为重言式，B为矛盾式，为矛盾式，C为可满足式为可满足式 A= (qp) qp，B = ( p q) q，C= (p q)
27、r49附：n罗素悖论有一个最常提及且十分有趣的例子，即所谓的“理发师悖论”：小镇里有一位理发师声称只给镇上所有不自己理发只给镇上所有不自己理发的人理发的人理发。n问题:理发师自己的头发谁理呢？n如果他自己理的话那么他就不是不自己理不是不自己理发的人发的人，所以他不能给自己理；但是如果他不给自己理那么他就是不自己理发的人是不自己理发的人，因而他又要给自己理。 50聪明的囚徒古希腊有个国王，对处死囚徒的方法作了两种规定：一种是砍头，一种是绞刑。并他自恃聪明的做出一种规定：囚徒可以说一句话，并且这句话是马上可以验证其真假。如果囚徒说的是真话，那么处以绞刑，如果囚徒说的是假话，那么处以砍头。许多囚徒或
28、者是因为说了假话而被砍头或者因为说了真话而被处以绞刑。有一位极其聪明的囚徒，当轮到他来选择处死方法时，他说出一句巧妙的话，结果使这个国王按照哪种方法处死他，都违背自己的决定，只得将他放了。请问：这囚徒说的是句什么话？趣味题趣味题趣味题趣味题51元语言与对象语言 元语言和对象语言的区分有个假设，即语言或符号系统是有层级的。我们在研究一个形式系统或者某种语言时，作为研究对象的符号和语言是对象语言，在研究中所使用的工具语言或符号就是元语言。比如我们用汉语来研究英语语法，英语就是对象语言，汉语则是元语言。 我们也可以在一种语言里区分出对象语言和元语言，并且，如果我们要研究元语言，则我们需要使用元元语言。在现代逻辑中，对象语言是符号语言，元语言可能是某种自然语言，也可能是符号语言。附：附：附：附：
