离散数学教程ppt

离散数学数学与信息科学学院第一部分数理逻辑第二部分集合论第三部分图论第四部分抽象代数离散数学第一部分数理逻辑数理逻辑是用数学方法研究推理中前提和结论之间的形式关系的学科。推理是由一个或几个判断推出一个新判断的思维形式。数学方法是指建立一套表意符号体系，对具体事物进行抽象的形式研究的方法。第一章命题逻辑第二章一阶谓词逻辑第一部分数理逻辑1.1命题和命题联结词1.2命题公式及其赋值1.3等值演算与联结词完备集1.4析取范式与合取范式1.5推理的形式结构1.6自然推理系统P第一章命题逻辑1.命题：能判断真假的陈述句。包含两层意思：（1）必须是陈述句。（2）能够确定（分辨）其真值。不等式等式自然语言中的陈述句万根。如：张校长的头发有一。是否知道真假是不同的注意：能否分辨真假与1.1命题和命题联结词）我正在说谎。）啊，我的天哪！）我们要努力学习。）你喜欢数学吗？。）三角形的内角和等于87658014）火星上有生命。。）面积大。）海洋的面积比陆地的例：3962211.1命题和命题联结词2.命题的真值：判断结果表示。或一般用命题,,,,,:iiqprqp注意：此处不纠缠具体命题的真假问题，只是将其作为数学概念来处理。假命题—假真命题—真真值：真用T或1表示，假用F或0表示。3.命题和真值的符号化1.1命题和命题联结词1.1命题和命题联结词火星上有生命。。积大。海洋的面积比陆地的面例：:962::rqp）我正在说谎。）啊，我的天哪！）我们要努力学习。）你喜欢数学吗？。三角形的内角和等于8765801:s）火星上有生命。。）面积大。）海洋的面积比陆地的例：396221）我正在说谎。）啊，我的天哪！）我们要努力学习。）你喜欢数学吗？。）三角形的内角和等于87658014原子命题：不能被分解为更简单的陈述句复合命题：原子命题通过联结词联结而成例：2是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。p：2是有理数，q：2是偶数，r：2是素数，s：3是素数，t：4是素数。1.1命题和命题联结词4、命题联结词”。读作“非的否命题，记作称作复合命题，没有”等否定词组成的和“非”、“不”、“用命题否定词pppp,).1不是质数。：是质数。如：的逻辑抽象。、“不”和“没有”等是自然语言中的“非”44:ppppTFFT1.1命题和命题联结词”。合取”或“与读作“组成的复合命题，记作和、是命题，由、合取词qpqpqpqpqp,).2一面”等的逻辑抽象。、“一面但是”而且”、“虽然”、“不但又“既”、是自然语言中的“并且pqpqFFFFTFTFFTTT：王化的品德很好。：王化的成绩很好。qp王化不但成绩好而且品德好。p∧q：1.1命题和命题联结词”。或读作“组成的复合命题记作和、命题析取词qpqpqp,).3的逻辑抽象。、“或者”中的可兼或是自然语言中的“或”pqpqFFFFTTTFTTTT：灯泡坏了。：开关坏了。qp1.1命题和命题联结词开关坏了或灯泡坏了。p∨q：例：1.张晓婧爱唱歌或爱听音乐。2.张晓婧是内蒙人或是陕西人。3.张晓婧只能挑选202或203房间。1.1命题和命题联结词注意：当排斥或两边的情况实际根本不可能同时发生的时候，排斥或也可抽象为∨。但为了方便起见一般不这样抽象。称作后件（结论）。，”。称为前件（前提）条件或“”则读作“如果组成的复合命题记作和、由命题蕴涵词qqpqppqp,,q).4的逻辑抽象。”，则”，“若，则是自然语言中的“如果pqpqFFTFTTTFFTTT有位父亲对儿子说：“如果我去书店，就一定给你买电脑报“。问：在什么情况下，父亲算失信呢？1.1命题和命题联结词注意：①“只要p，就q‘，’因为p，所以q”，“p仅当q”，‘只有q，才p“，”除非q才p“，”除非q，否则非p“都可抽象为p→q。②p，q可以没有任何内在联系。例：1.如果3＋3＝6，那么雪是白的。2.除非我能工作完成了，我才去看电影。3.只要天下雨，我就回家。4.我回家仅当天下雨。p→q的逻辑关系为q是p的必要条件或p是q的充分条件。1.1命题和命题联结词的逻辑抽象。条件”，“当且仅当”是自然语言中的“充要”。当且仅当读作“组成的复合命题记作和、由命题等价词qp,).5qpqppqpqFFTFTFTFFTTT1.1命题和命题联结词pq的逻辑关系为p与q互为充要条件例：1.3是有理数当且仅当加拿大位于亚洲。2.两圆的面积相等，则他们的半径相等，反之亦然。6.q异或联结词指的是排斥或，当且仅当p、q的真值相异时，p为真。pqpqFFFFTTTFTTTF)()()2(qp1qpqpqppq等价于等价于）（有如下性质：由定义知1.1命题和命题联结词例：今天第一节课上离散数学或数据结构。左往右的次序运算。）同级的联结词，按从（省略不必要的括号。）按优先级书写，可以（。，，，，）由强到弱依次是：（联结词的优先次序：32,1例：p：北京比天津人口多q：2＋2＝4r：乌鸦是黑色的pqpqrrqqp)2(1）（求以下命题的真值1.1命题和命题联结词5、语句形式化）选择命题联结词。（命题）；）确定原子命题（简单（形式化的步骤：211.1命题和命题联结词例：2是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。p：2是有理数，q：2是偶数，r：2是素数，s：3是素数，t：4是素数。p不对；q且r；r或t；如果r，则s；r当且仅当s。跳墙。中的联结词，如：狗急）要善于识别自然语言（，如：我和他是同学。）给定句子是否是命题（注意：21去郊游，否则就不去。如果明天天气好，我们表。选小陈或小周一人为代践经验。他虽有理论知识但无实。么你一定会成为近视眼如果你走路时看书，那自讨没趣。，那么你们俩都不会去如果你和他不都是傻子例.5.4.3.2.11.1命题和命题联结词命题常元：表示具体确定内容的命题。命题变元：表示不确定具体内容的命题。题公式。）得到的符号串都是命）、（）有限次的使用（（也是命题公式；是命题公式，则、）若（公式；公式，称其为原子命题）单个命题变元是命题（命题公式的递归定义：定义213,qp,,,,q21.1qpqpqpqppp1.2命题公式及其赋值rpprqppqpqrrqqp)5()4())3()2(1）例（1.2命题公式及其赋值同时约定：（1）最外层的括号可以省去。（2）不影响运算次序的括号也可以省去。。层公式，＋是，则公式＝或＝或＝或＝或＝层公式，且，分别是，）若公式（层公式；＋是，则＝层公式且是）若公式（层公式；其为为单个命题变元，则称）公式（命题公式的层次：定义),max(1nACBACBACBACBACBAjiCB31nABAnB20A1.2jin1.2命题公式及其赋值pqpqrrqp)2(1）例（1.2命题公式及其赋值rqp)(是有理数：是偶数，：是素数，：232rqp是无理数：是偶数，：是素数，：232rqp称为成假赋值。的成真赋值，否则，则称其为的真值为若指定的一组值使的一组赋值或解释。对一组确定的取值，称为给的命题公式，为含有命题变元设定义A1Ap,,,p,,,.32121AppppAnn的真值表。称为情况列成表，在其全部赋值下的真值将公式定义AA.41.2命题公式及其赋值1n1)1223FnFnnnn真值表的构造步骤：（）若公式共有（个变元，则真值表第一行写出个变元，公式F写在第列。（）写出个变元的所有可能取值（种）,按从低到高的顺序写出公式的各层次。（）在不同赋值下求出各层次的真值及的真值。为可满足式。的值为真，则称）若至少有一组赋值使为永假式；为假，则称在所有赋值下的取值均）若为永真式；为真，则称在所有赋值下的取值均若，公式定义AA3AA2AA)1.5A1.2命题公式及其赋值pqpqrrqp)2(1）例（也是重言式。为重言式，则和若定理BABABA,.11.2命题公式及其赋值1.,ABABABAB定义设和是两个命题公式，若为重言式，则称公式是等值的公式，记作。1.p)();.qqpppp例证明（.qpq注意：和的区别是公式间的关系符号，如：p是命题联结词1.3命题公式的等值式,,ABABABBAABCABCABCABCABCABACABCABAC交换律：结合律：分配律：)(),(),()pqpqpqrpqrpqr例：（与基本等值式（A，B，C为任意命题公式）1.3命题公式的等值式0,110A,,1,,,1.11,00(),,AAAAAAAAAAAAAAAAAAAAAAAAAAAABAAABAABABABAB同一律：互补律：，重补律：等幂律：零一律：A吸收律：德摩根律：1.3命题公式的等值式,BABABBABABBAABABBAABABABABAB蕴含等值式：A假言易位：等价等值式：A等价否定等值式：归谬论：(AB)(AB)A因A，B，C可以代入任意的命题公式，故以上等值式称为等值式模式。由已知的等值式推演出另外一些等值式的过程为等值演算。1.3命题公式的等值式()()()ABA(B)(A)AABBA置换规则：设是含公式的命题公式，是用公式置换了中所有的后得到的命题公式。若，则等值演算的应用：1.验证等值式2.判定公式的类型3.解决工作生活中的判断问题2.qpqqp例等值等价式p1.3命题公式的等值式()()()pqprpqr(),(()),((()))pqpqppqrppqpq甲、已、丙3人根据口音对王教授是哪人进行了判断：甲说：王教授不是苏州人，是上海人已说：王教授不是上海人，是苏州人丙说：王教授既不是上海人，也不是杭州人结果3人中有一人全对，一人对一半，一人全错。问王教授是哪人？联结词的完备集.{0,1}{0,1}n.nF定义称：为元真值函数{0,1}01nn中的元素为由，组成的长为的符号串n个命题变元可以形成22n个不同的真值函数对于每个真值函数，都可以找到许多与之等值的命题公式，而每个命题公式对应唯一的与之等值的真值函数。定义.设S是一个联结词集合，如果任何n（n≥1）元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。.{,,}ThS是联结词完备集.345S{,,,,}{,}{,}{,}SSS12推论：以下联结词集都是完备集＝{,,,}S.,pqpq定义设为两个命题，复合命题“与（或）的否定式”称作p,q的与（或）非式，记作pq(pq)..{},{}Th也是联结词完备集.联结词的完备集1.4析取范式与合取范式定义：命题变元及其否定统称为文字。仅由有限个文字构成的析取式称为简单（质）析取式。仅由有限个文字构成的合取式称为简单（质）合取式。,,,pppqpq例：注意：单个文字既是简单析取式又是简单合取式。讨论：设A为含n个文字的简单析取式若A中同时含pi和﹁pi，则？若A为永真式，则？若A为永真式，则A中必同时含有pi和﹁pi，反之亦然。同理有，若A为简单合取式，A为永假式的充要条件是A中同时含有pi和﹁pi。定理1.①一个简单析取式是重言式当且仅当它同时含有