离散数学命题与联接词

离散数学命题与联接词第1页，共44页，2023年，2月20日，星期一目录数理逻辑集合论图论抽象代数形式语言与自动机第2页，共44页，2023年，2月20日，星期一数理逻辑命题演算命题与联结词重言式范式命题演算形式系统谓词演算个体、谓词和量词谓词演算永真式谓词公式的前束范式一阶谓词演算形式系统第3页，共44页，2023年，2月20日，星期一数理逻辑逻辑学是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创建的。亚里士多德在逻辑学上最重要的工作是提出三段论学说。一个三段论就是一个包括有大前提、小前提和结论三个部分的论证。三段论有许多不同的种类，其中最著名的例子：凡是人都会死（大前提）苏格拉底是人（小前提）所以：苏格拉底会死（结论）第4页，共44页，2023年，2月20日，星期一数理逻辑用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑。数理逻辑的萌芽利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。莱布尼茨（Leibniz）就曾经设想能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是他的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨的思想可以说是数理逻辑的先驱。第5页，共44页，2023年，2月20日，星期一数理逻辑数理逻辑的开创1847年，英国数学家布尔G.Boole发表了《逻辑的数学分析》，建立了“布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。数理逻辑的大发展1884年，德国数学家弗雷格Frege出版了《数论的基础》一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。美国人皮尔斯Peirce，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。第6页，共44页，2023年，2月20日，星期一数理逻辑数学危机和解决在集合论的研究过程中，出现了一次称作数学史上的第三次大危机。这次危机是由于发现了集合论的悖论引起。集合论本来是论证很严格的一个分支，被公认为是数学的基础。1903年，英国哲学家、逻辑学家、数学家罗素Russell对集合论提出了以他名字命名的“罗素悖论”，这个悖论的提出几乎动摇了整个数学基础。罗素提出类型论，策梅罗Zermelo提出公理化集合论来对康托尔Contour的朴素集合论进行限制，解决悖论问题。第7页，共44页，2023年，2月20日，星期一数理逻辑对数学进行形式化的努力第三次数学危机解决以后，整个数学界非常乐观希尔伯特Hilbert的形式化思想占统治地位数学建立在集合论和数理逻辑两块基石之上康托尔的朴素集合论已经被公理化集合论代替，消除了悖论整个数学的基本理论是自然数的算术和实数理论，它们都已经公理化如果能够证明这些形式系统的一致性和完全性，整个数学基础就比较牢靠了1928年，希尔伯特提出四个问题，希望能够把整个数学理论系统形式化，并通过有限多步证明它们没有矛盾。第8页，共44页，2023年，2月20日，星期一数理逻辑数理逻辑的转折1930年，哥德尔Godel宣布了不完全性定理一个包括初等数论的形式系统，如果是一致的，那就是不完全的。而且如果初等算术系统是一致的，则一致性在算术系统内不可证明。数理逻辑最重大的成就之一，是数理逻辑发展的一个里程碑和转折点。哥德尔在研究过程中直接考虑悖论及解决悖论的方法，从而把第三次数学危机引导至另一个方向上。人们认识到对整个数学形式化的努力是注定要失败的。数学基础的危机不那么突出了，绝大部分数学家仍然把自己的研究建立在朴素集合论或ZF公理集合论的基础上。第9页，共44页，2023年，2月20日，星期一数理逻辑数理逻辑的四大分支悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理逻辑的一个重要分支—公理集合论。为了研究数学系统的无矛盾性问题，需要以数学理论体系的概念、命题、证明等作为研究对象，研究数学系统的逻辑结构和证明的规律，这样又产生了数理逻辑的另一个分支—证明论。数理逻辑新近还发展了许多新的分支，如递归论、模型论等。递归论主要研究可计算性的理论，它和计算机的发展和应用有密切的关系。模型论主要是研究形式系统和数学模型之间的关系。第10页，共44页，2023年，2月20日，星期一命题演算：命题与联结词命题（proposition/statements）对确定的对象作出判断的陈述句命题的真值（truthvalue）判断正确，称该命题真（true）否则，称该命题假（false）基本假设：排中律非真即假排中律有问题？第11页，共44页，2023年，2月20日，星期一命题演算：命题与联结词直觉主义对排中律的否定直觉主义学派认为，数学的基础和出发点是自然数的理论，而自然数则是由人的原始直觉（按时间顺序出现的感觉）构造出来的。数学理论可靠性的唯一标准就是心智上的可构造性。他们有一句名言：“存在必须等于被构造。”按照直觉主义的观点，要判定一个命题p为真，就必须给出p的构造性证明。要判定一个否定命题非p为真，就必须有一个构造，这一构造将任何一个假定原命题p为真的构造导致谬误，例如推出一对矛盾的命题q和非q。第12页，共44页，2023年，2月20日，星期一命题演算：命题与联结词直觉主义对排中律的否定在经典逻辑和经典数学中，人们经常使用间接证明的方法：欲证一个命题为p真，不是直接去证明，而是先假定p不真，即非p真，然后推出逻辑矛盾，以此来证明命题为p真。这种方法直觉主义者是不能接受的，因为由非p推出逻辑矛盾并不意味着可以肯定命题p找到一个构造性证明。直觉主义者否定排中律的普遍有效性。他们认为，排中律是从有穷事物中概括出来的，任何一个涉及有穷事物全体的命题，如“我们班所有的同学都戴眼镜”，总可以通过对这些事物逐一加以验证，来判明该命题的真假，这时，排中律是有效的。第13页，共44页，2023年，2月20日，星期一命题演算：命题与联结词直觉主义对排中律的否定但是，如果人们忘记了排中律的有穷来源，把它看成普遍适用的原则，并把它用于无穷的场合，就会犯错误。这是因为，对于无穷的事物，我们不可能对它们一一加以鉴别。例如，设命题p为著名的哥德巴赫猜想：“每一个大于4的偶数都可以表示为两个素数之和”（素数为只能被1和本身整除的数），这是一个涉及无穷的命题（因为偶数和素数都是无穷的），至今还无法证明这一猜想，即不能断定p真；但我们也无法论证这一猜想是错的，因此，也不能断定非p真。这样，命题p既不能证实，也不能否定，排中律失效。第14页，共44页，2023年，2月20日，星期一命题演算：命题与联结词考虑下面的语句雪是白的2+2=52是偶数且3也是偶数袁世凯称帝那天北京下雨大于2的偶数均可分解为两个素数之和您贵姓？x+y<10第15页，共44页，2023年，2月20日，星期一命题演算：命题与联结词注意前面第三个命题由两个命题和一个“且”连接而成逻辑联结词（logicalconnectives）连接命题对真值进行运算的词原子命题（atoms）不含有逻辑联结词的命题复合命题（compoundproposition）包含原子命题和逻辑联结词的命题第16页，共44页，2023年，2月20日，星期一命题演算：命题与联结词复合命题的例子雪不是白的今晚我去看书或者去看电影你去了学校，我去了工厂（省略了“且”）如果天气好，那么我去接你偶数a是素数，当且仅当a=2第17页，共44页，2023年，2月20日，星期一命题演算：命题与联结词命题和联结词的符号化真命题用t表示，假命题用f表示原子命题常用p,q,r,s或者pi,qi,ri,si表示联结词用特殊符号表示否定词（negation）”并非”（not）：¬合取词（conjunction）”并且”（and）：∧析取词（disjunction）”或”（or）：∨蕴涵词（implication）”如果…那么…”（if…then…）：→双向蕴含词（two-wayimplication）”当且仅当”（ifandonlyif）：↔真值中的真（true）用1表示，假（false）用0表示第18页，共44页，2023年，2月20日，星期一命题演算：命题与联结词逻辑联结词和真值表列出原子命题和联结词作用于原子命题后的真值否定词（negation）”并非”（not）：¬p¬p0110第19页，共44页，2023年，2月20日，星期一命题演算：命题与联结词否定词（negation）”并非”（not）：¬¬p的逻辑关系为p不成立如果p表示命题“雪是白的”，那么“雪不是白的”应该表示为¬p注意在包含多个对象命题的否定时，其意义的变化“天鹅都是白的”，其否定并不是“天鹅都不是白的”，而是“天鹅不都是白的”或“并非所有天鹅都是白的”第20页，共44页，2023年，2月20日，星期一命题演算：命题与联结词合取词（conjunction）”并且”（and）：∧p∧q的逻辑关系为p和q同时成立pqp∧q000010100111第21页，共44页，2023年，2月20日，星期一命题演算：命题与联结词合取词（conjunction）”并且”（and）：∧自然语言中许多表示并列的连接词都可以符号化为“∧”“既…又…”，“不但…而且…”，“虽然…但是…”p：张三聪明；q：张三用功张三既聪明又用功：p∧q张三不仅聪明，而且用功：p∧q张三虽然不太聪明，但他很用功：¬p∧q张三不是不聪明，而是不用功：p∧¬q张三和李四是好朋友：简单命题第22页，共44页，2023年，2月20日，星期一命题演算：命题与联结词析取词（disjunction）”或”（or）：∨p∨q的逻辑关系为p和q中至少一个成立pqp∨q000011101111第23页，共44页，2023年，2月20日，星期一命题演算：命题与联结词析取词（disjunction）”或”（or）：∨自然语言中的“或”可以符号化为∨，但有时要注意原命题中的“或”可能表示排斥性选择李四学过德语或法语（相容或）：p∨qp:李四学过德语，q:李四学过法语张三生于1972年或1973年（排斥或）：p∨qp:张三生于1972年，q:张三生于1973年人固有一死，或重于泰山，或轻于鸿毛（排斥或）(p∧¬q)∨(¬p∧q)：异或p:人死重于泰山，q:人死轻于鸿毛第24页，共44页，2023年，2月20日，星期一命题演算：命题与联结词蕴涵词（implication）”如果…那么…”（if…then…）：→p→q的逻辑关系是，p是q的充分条件，或者说q是p的必要条件pqp→q001011100111第25页，共44页，2023年，2月20日，星期一命题演算：命题与联结词蕴涵词（implication）：→p→q中的p称作蕴涵前件，q称作蕴涵后件自然语言中的许多条件连接词都可以符号化为→，但是要注意条件的顺序“只要…就…”，“如果…那么…”，“只有…才…”自然语言中，条件语句一般都具有内在的联系，而数理逻辑中的蕴涵则仅是命题的一种连接，不一定具有什么内在联系在蕴涵式中，只有p为真q为假时，p→q才为假和(¬p∨q)真值表相同第26页，共44页，2023年，2月20日，星期一命题演算：命题与联结词蕴涵词（implication）：→如果天气好，那么我去接你：p→qp:天气好，q:我去接你只有p真q假算是食言只要2是偶数，雪就是黑的：p→qp:2是偶数，q:雪是黑的p为真，q为假，本命题为假只有天黑了，夜猫子才出来活动：p→q注意：p:夜猫子出来活动，q:天黑了第27页，共44页，2023年，2月20日，星期一命题演算：命题与联结词双向蕴含词（two-wayimplication）”当且仅当”（ifandonlyif）：↔p↔q的逻辑关系是p与q互为充分必要条件，在pq真值相同的情况下，p↔q为真pqp↔q001010100111第28页，共44页，2023年，2月20日，星期一命题演算：命题与联结词双向蕴含词（two-wayimplication）：↔圆1和圆2面积相等当且仅当它们的半径相等：p↔qp:圆1和圆2面积相等，q:圆1和圆2半径相等不管p和q的真值如何，p↔q为真2＋3＝5当且仅当5是有理数除非网断了，否则他一定在qq上：p↔¬qp:网断了，q:他在qq上第29页，共44页，2023年，2月20日，星期一命题演算：命题与联结词组合例子：如果3是合数，则4是素数，并且如果4是素数，则它不能被2整除p:3是合数，q:4是素数，r:4能被2整除(p→q)∧(q→¬r)如果2+3>5当且仅当5是合数，则2和3都是有理数p:2+3>5，q:5是合数，r:2是有理数，s:3是有理数(p↔q)→(r∧s)第30页，共44页，2023年，2月20日，星期一命题演算：命题与联结词命题常元（propositionconstants）表示具体命题及表示常命题的p,q,r,s等和t,f命题变元（propositionvariables）以“真，假”或者“1，0”为取值范围的变量仍用p,q,r,s等表示命题公式（propositionformula）由命题常元、变元和联结词组成的形式更为复杂的命题第31页，共44页，2023年，2月20日，星期一命题演算：命题与联结词命题公式（propositionformula）定义命题常元和命题变元是命题公式，特别的称作原子公式或原子如果A,B是命题公式，那么(¬A),(A∧B),(A∨B),(A→B),(A↔B)也是命题公式只有有限步引用上述两条所组成的符号串是命题公式命题公式简称做公式，采用大写A,B,C等表示命题公式的这种定义方法称作归纳定义，在集合论中将会详细讨论归纳定义第32页，共44页，2023年，2月20日，星期一命题演算：命题与联结词命题公式例子(¬(p→(q∧r)))是命题公式(qp),p→r,(p1∧(p2∧…都不是命题公式简化公式的约定公式最外层的括号一律可以省略约定逻辑联结词的优先级第33页，共44页，2023年，2月20日，星期一命题演算：命题与联结词逻辑联结词优先级联结词{¬,∧,∨,→,↔}中，¬是一元联结词，其它都是连接两个命题的二元联结词我们定义优先级为：¬,(∧,∨),→,↔除非有括号，否则按照优先级从高到低，从左到右的次序结合p→q∧r→s等同于(p→(q∧r))→s第34页，共44页，2023年，2月20日，星期一命题演算：命题与联结词真值函数（truthfunction）如果将联结词看作逻辑运算符，那么包含命题变元p1,p2,…pn的公式A可以看作是p1,p2,…pn的真值函数指派（赋值assignments）对任意给定的p1,p2,…pn的一种取值状况，称为指派或者赋值用希腊字母α,β等表示对于每个赋值，公式A均有一个确定的真值第35页，共44页，2023年，2月20日，星期一命题演算：命题与联结词成真赋值和成假赋值当公式A对赋值α为真时，称α是A的成真赋值，或者α弄真A，记做α(A)=1反之，称α是A的成假赋值，或者α弄假A，记做α(A)=0真值表对于所有可能的赋值，公式A的真值可以用真值表来描述当A(p1,p2,…pn)中有k个联结词时，公式A的真值表应为2n行、k+n列。第36页，共44页，2023年，2月20日，星期一命题演算：命题与联结词公式¬(p→(q∧r))的真值表pqrq∧rp→(q∧r)¬(p→(q∧r))000010001010010010011110100001101001110001111110第37页，共44页，2023年，2月20日，星期一命题演算：命题与联结词语句的形式化我和他既是兄弟又是同学：p∧qp:我和他是兄弟，q:我和他是同学狗急跳墙：p→qp:狗急了，q:狗跳墙如果他不来那么是生病了或者不在本地：¬p→(q∨¬r)p:他来，q:他生病，r:他在本地无论是否下雨，我都去上学(p→q)∧(¬p→q)或者(p∧q)∨(¬p∧q)或者qp:天下雨，q:我去上学第38页，共44页，2023年，2月20日，星期一命题演算：命题与联结词语句的形式化要善于确定原子命题，如兄弟这个概念就无需进一步拆分；要善于识别自然语言中的联结词；对于涉及多个对象进行否定的否定词位置要准确；不能省略必要的括号，另外，为了提高公式的可读性，要保留一些括号；有时候语句的形式化结果不是唯一的，可能具有不同形式，但是逻辑上是等价的。第3