离散数学1-命题与联接词.ppt

《离散数学1-命题与联接词.ppt》由会员分享，可在线阅读，更多相关《离散数学1-命题与联接词.ppt（44页珍藏版）》请在三一办公上搜索。

1、离散数学(1),陈斌,目录,数理逻辑集合论图论抽象代数形式语言与自动机,数理逻辑,命题演算命题与联结词重言式范式命题演算形式系统谓词演算个体、谓词和量词谓词演算永真式谓词公式的前束范式一阶谓词演算形式系统,数理逻辑,逻辑学是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创建的。亚里士多德在逻辑学上最重要的工作是提出三段论学说。一个三段论就是一个包括有大前提、小前提和结论三个部分的论证。三段论有许多不同的种类，其中最著名的例子：凡是人都会死（大前提）苏格拉底是人（小前提）所以：苏格拉底会死（结论）,数理逻辑,用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑

2、。数理逻辑的萌芽利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。莱布尼茨（Leibniz）就曾经设想能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是他的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨的思想可以说是数理逻辑的先驱。,数理逻辑,数理逻辑的开创1847年，英国数学家布尔G.Boole发表了逻辑的数学分析，建立了“布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻

3、辑的基础。数理逻辑的大发展1884年，德国数学家弗雷格Frege出版了数论的基础一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。美国人皮尔斯Peirce，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。,数理逻辑,数学危机和解决在集合论的研究过程中，出现了一次称作数学史上的第三次大危机。这次危机是由于发现了集合论的悖论引起。集合论本来是论证很严格的一个分支，被公认为是数学的基础。1903年，英国哲学家、逻辑学家、数学家罗素Russell对集合论提出了以他名字命名的“罗素悖论”，这个悖论的提出几乎动摇了整个数学基础。罗素提出类型论，策梅罗Z

4、ermelo提出公理化集合论来对康托尔Contour的朴素集合论进行限制，解决悖论问题。,数理逻辑,对数学进行形式化的努力第三次数学危机解决以后，整个数学界非常乐观希尔伯特Hilbert的形式化思想占统治地位数学建立在集合论和数理逻辑两块基石之上康托尔的朴素集合论已经被公理化集合论代替，消除了悖论整个数学的基本理论是自然数的算术和实数理论，它们都已经公理化如果能够证明这些形式系统的一致性和完全性，整个数学基础就比较牢靠了1928年，希尔伯特提出四个问题，希望能够把整个数学理论系统形式化，并通过有限多步证明它们没有矛盾。,数理逻辑,数理逻辑的转折1930年，哥德尔Godel宣布了不完全性定理一个

5、包括初等数论的形式系统，如果是一致的，那就是不完全的。而且如果初等算术系统是一致的，则一致性在算术系统内不可证明。数理逻辑最重大的成就之一，是数理逻辑发展的一个里程碑和转折点。哥德尔在研究过程中直接考虑悖论及解决悖论的方法，从而把第三次数学危机引导至另一个方向上。人们认识到对整个数学形式化的努力是注定要失败的。数学基础的危机不那么突出了，绝大部分数学家仍然把自己的研究建立在朴素集合论或ZF公理集合论的基础上。,数理逻辑,数理逻辑的四大分支悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理逻辑的一个重要分支公理集合论。为了研究数学系统的无矛盾性问题，需要以数学理论体系的概念、命

6、题、证明等作为研究对象，研究数学系统的逻辑结构和证明的规律，这样又产生了数理逻辑的另一个分支证明论。数理逻辑新近还发展了许多新的分支，如递归论、模型论等。递归论主要研究可计算性的理论，它和计算机的发展和应用有密切的关系。模型论主要是研究形式系统和数学模型之间的关系。,命题演算：命题与联结词,命题（proposition/statements）对确定的对象作出判断的陈述句命题的真值（truth value）判断正确，称该命题真（true）否则，称该命题假（false）基本假设：排中律非真即假排中律有问题？,命题演算：命题与联结词,直觉主义对排中律的否定直觉主义学派认为，数学的基础和出发点是自然数

7、的理论，而自然数则是由人的原始直觉（按时间顺序出现的感觉）构造出来的。数学理论可靠性的唯一标准就是心智上的可构造性。他们有一句名言：“存在必须等于被构造。”按照直觉主义的观点，要判定一个命题p为真，就必须给出p的构造性证明。要判定一个否定命题非p为真，就必须有一个构造，这一构造将任何一个假定原命题p为真的构造导致谬误，例如推出一对矛盾的命题q和非q。,命题演算：命题与联结词,直觉主义对排中律的否定在经典逻辑和经典数学中，人们经常使用间接证明的方法：欲证一个命题为p真，不是直接去证明，而是先假定p不真，即非p真，然后推出逻辑矛盾，以此来证明命题为p真。这种方法直觉主义者是不能接受的，因为由非p推

8、出逻辑矛盾并不意味着可以肯定命题p找到一个构造性证明。直觉主义者否定排中律的普遍有效性。他们认为，排中律是从有穷事物中概括出来的，任何一个涉及有穷事物全体的命题，如“我们班所有的同学都戴眼镜”，总可以通过对这些事物逐一加以验证，来判明该命题的真假，这时，排中律是有效的。,命题演算：命题与联结词,直觉主义对排中律的否定但是，如果人们忘记了排中律的有穷来源，把它看成普遍适用的原则，并把它用于无穷的场合，就会犯错误。这是因为，对于无穷的事物，我们不可能对它们一一加以鉴别。例如，设命题p为著名的哥德巴赫猜想：“每一个大于4的偶数都可以表示为两个素数之和”（素数为只能被1和本身整除的数），这是一个涉及无

9、穷的命题（因为偶数和素数都是无穷的），至今还无法证明这一猜想，即不能断定p真；但我们也无法论证这一猜想是错的，因此，也不能断定非p真。这样，命题p既不能证实，也不能否定，排中律失效。,命题演算：命题与联结词,考虑下面的语句雪是白的2+2=52是偶数且3也是偶数袁世凯称帝那天北京下雨大于2的偶数均可分解为两个素数之和您贵姓？x+y10,命题演算：命题与联结词,注意前面第三个命题由两个命题和一个“且”连接而成逻辑联结词（logical connectives）连接命题对真值进行运算的词原子命题（atoms）不含有逻辑联结词的命题复合命题（compound proposition）包含原子命题和逻辑

10、联结词的命题,命题演算：命题与联结词,复合命题的例子雪不是白的今晚我去看书或者去看电影你去了学校，我去了工厂（省略了“且”）如果天气好，那么我去接你偶数a是素数，当且仅当a=2,命题演算：命题与联结词,命题和联结词的符号化真命题用t表示，假命题用f表示原子命题常用p,q,r,s或者pi,qi,ri,si表示联结词用特殊符号表示否定词（negation）”并非”（not）：合取词（conjunction）”并且”（and）：析取词（disjunction）”或”（or）：蕴涵词（implication）”如果那么”（ifthen）：双向蕴含词（two-way implication）”当且仅当”

11、（if and only if）：真值中的真（true）用1表示，假（false）用0表示,命题演算：命题与联结词,逻辑联结词和真值表列出原子命题和联结词作用于原子命题后的真值否定词（negation）”并非”（not）：,命题演算：命题与联结词,否定词（negation）”并非”（not）：p的逻辑关系为p不成立如果p表示命题“雪是白的”，那么“雪不是白的”应该表示为p注意在包含多个对象命题的否定时，其意义的变化“天鹅都是白的”，其否定并不是“天鹅都不是白的”，而是“天鹅不都是白的”或“并非所有天鹅都是白的”,命题演算：命题与联结词,合取词（conjunction）”并且”（and）：pq的

12、逻辑关系为p和q同时成立,命题演算：命题与联结词,合取词（conjunction）”并且”（and）：自然语言中许多表示并列的连接词都可以符号化为“”“既又”，“不但而且”，“虽然但是”p：张三聪明；q：张三用功张三既聪明又用功：pq张三不仅聪明，而且用功：pq张三虽然不太聪明，但他很用功：pq张三不是不聪明，而是不用功：pq张三和李四是好朋友：简单命题,命题演算：命题与联结词,析取词（disjunction）”或”（or）：pq的逻辑关系为p和q中至少一个成立,命题演算：命题与联结词,析取词（disjunction）”或”（or）：自然语言中的“或”可以符号化为，但有时要注意原命题中的“或”

13、可能表示排斥性选择李四学过德语或法语（相容或）：pqp:李四学过德语，q:李四学过法语张三生于1972年或1973年（排斥或）：pqp:张三生于1972年，q:张三生于1973年人固有一死，或重于泰山，或轻于鸿毛（排斥或）(pq)(pq)：异或p:人死重于泰山，q:人死轻于鸿毛,命题演算：命题与联结词,蕴涵词（implication）”如果那么”（ifthen）：pq的逻辑关系是，p是q的充分条件，或者说q是p的必要条件,命题演算：命题与联结词,蕴涵词（implication）：pq中的p称作蕴涵前件，q称作蕴涵后件自然语言中的许多条件连接词都可以符号化为，但是要注意条件的顺序“只要就”，“如

14、果那么”，“只有才”自然语言中，条件语句一般都具有内在的联系，而数理逻辑中的蕴涵则仅是命题的一种连接，不一定具有什么内在联系在蕴涵式中，只有p为真q为假时，pq才为假和(pq)真值表相同,命题演算：命题与联结词,蕴涵词（implication）：如果天气好，那么我去接你：pqp:天气好，q:我去接你只有p真q假算是食言只要2是偶数，雪就是黑的：pqp:2是偶数，q:雪是黑的p为真，q为假，本命题为假只有天黑了，夜猫子才出来活动：pq注意：p:夜猫子出来活动，q:天黑了,命题演算：命题与联结词,双向蕴含词（two-way implication）”当且仅当”（if and only if）：pq

15、的逻辑关系是p与q互为充分必要条件，在pq真值相同的情况下，pq为真,命题演算：命题与联结词,双向蕴含词（two-way implication）：圆1和圆2面积相等当且仅当它们的半径相等：pqp:圆1和圆2面积相等，q:圆1和圆2半径相等不管p和q的真值如何，pq为真235当且仅当5是有理数除非网断了，否则他一定在qq上：pqp:网断了，q:他在qq上,命题演算：命题与联结词,组合例子：如果3是合数，则4是素数，并且如果4是素数，则它不能被2整除p:3是合数，q:4是素数，r:4能被2整除(pq)(qr)如果2+35当且仅当5是合数，则2和3都是有理数p:2+35，q:5是合数，r:2是有理

16、数，s:3是有理数(pq)(rs),命题演算：命题与联结词,命题常元（proposition constants）表示具体命题及表示常命题的p,q,r,s等和t,f命题变元（proposition variables）以“真，假”或者“1，0”为取值范围的变量仍用p,q,r,s等表示命题公式（proposition formula）由命题常元、变元和联结词组成的形式更为复杂的命题,命题演算：命题与联结词,命题公式（proposition formula）定义命题常元和命题变元是命题公式，特别的称作原子公式或原子如果A,B是命题公式，那么(A),(AB),(AB),(AB),(AB)也是命题公式

17、只有有限步引用上述两条所组成的符号串是命题公式命题公式简称做公式，采用大写A,B,C等表示命题公式的这种定义方法称作归纳定义，在集合论中将会详细讨论归纳定义,命题演算：命题与联结词,命题公式例子(p(qr)是命题公式(qp),pr,(p1(p2都不是命题公式简化公式的约定公式最外层的括号一律可以省略约定逻辑联结词的优先级,命题演算：命题与联结词,逻辑联结词优先级联结词,中，是一元联结词，其它都是连接两个命题的二元联结词我们定义优先级为：,(,),除非有括号，否则按照优先级从高到低，从左到右的次序结合pqrs等同于(p(qr)s,命题演算：命题与联结词,真值函数（truth function）如

18、果将联结词看作逻辑运算符，那么包含命题变元p1,p2,pn的公式A可以看作是p1,p2,pn的真值函数指派（赋值assignments）对任意给定的p1,p2,pn的一种取值状况，称为指派或者赋值用希腊字母,等表示对于每个赋值，公式A均有一个确定的真值,命题演算：命题与联结词,成真赋值和成假赋值当公式A对赋值为真时，称是A的成真赋值，或者弄真A，记做(A)=1反之，称是A的成假赋值，或者弄假A，记做(A)=0真值表对于所有可能的赋值，公式A的真值可以用真值表来描述当A(p1,p2,pn)中有k个联结词时，公式A的真值表应为2n行、k+n列。,命题演算：命题与联结词,公式(p(qr)的真值表,命

19、题演算：命题与联结词,语句的形式化我和他既是兄弟又是同学：pqp:我和他是兄弟，q:我和他是同学狗急跳墙：pqp:狗急了，q:狗跳墙如果他不来那么是生病了或者不在本地：p(qr)p:他来，q:他生病，r:他在本地无论是否下雨，我都去上学(pq)(pq)或者(pq)(pq)或者qp:天下雨，q:我去上学,命题演算：命题与联结词,语句的形式化要善于确定原子命题，如兄弟这个概念就无需进一步拆分；要善于识别自然语言中的联结词；对于涉及多个对象进行否定的否定词位置要准确；不能省略必要的括号，另外，为了提高公式的可读性，要保留一些括号；有时候语句的形式化结果不是唯一的，可能具有不同形式，但是逻辑上是等价的

20、。,作业,选作你手头上的离散数学章节后习题关于排中律的报告搜集一些你认为难以形式化的命题，并分析其规律。,关于课程教材,O158/75计算机科学中的离散结构王元元,张桂芸编著，机械工业出版社 2004O158/60离散数学导论王元元,张桂芸编著，科学出版社 2002O158/36离散数学王元元,李尚奋编著，科学出版社 1994,END,特殊符号表,PC,英国数学家德摩根,德摩根，A（Augustus De Morgan 18061871）英国数学家、逻辑学家他认为：代数学实际上是一系列“运算”，这种“运算”能在任何符号（不一定是数字）的集合上，根据一定的公设进行这一新的数学思想使代数得以脱离算术的束缚,英国数学家德摩根,在逻辑学方面，德摩根首创了关系逻辑的研究他提出了论域概念，并用代数方法来研究逻辑演算，建立了著名的德摩根律他还分析了关系的种类和性质，研究了关系命题和关系推理，得到了一些逻辑规律和定理，从而突破了古典的主谓逻辑的局限性，这对其后数理逻辑的发展有一定的影响德摩根撰写了不少算术、代数、三角等方面的教材，他在分析学和逻辑学方面的主要著作有微积分学（1842）、形式逻辑（1847）等摘自中国大百科全书数学卷,