离散数学(逻辑)课件

离散数学（逻辑）欢迎来到离散数学（逻辑）课程！课程目标：掌握逻辑基础，为计算机科学应用打下基础核心目标深入理解逻辑的基本概念和理论。应用目标能够将逻辑知识应用于计算机科学领域，例如程序验证、人工智能等。课程大纲：命题逻辑、谓词逻辑、证明方法1命题逻辑命题、联结词、真值表、逻辑等价、推理规则等。2谓词逻辑谓词、量词、量词辖域、量词的否定等。3证明方法直接证明、反证法、数学归纳法、结构归纳法等。逻辑的意义：形式化思维，精确表达清晰、准确地表达思想。避免歧义和错误。进行严谨的推理和论证。命题与联结词命题一个能够判断真假的陈述句。联结词用于连接命题的符号，例如否定、合取、析取等。命题的定义：能判断真假的陈述句例如："今天是星期一"是一个命题，因为它可以判断真假。"你吃饭了吗？"则不是一个命题，因为它是一个疑问句，无法判断真假。真值：真命题与假命题真命题一个为真的陈述句。假命题一个为假的陈述句。联结词：否定（¬）、合取（∧）、析取（∨）、蕴含（→）、等价（↔）否定（¬）对命题的真值取反。1合取（∧）两个命题都为真时才为真。2析取（∨）两个命题至少一个为真时才为真。3蕴含（→）前件为真且后件为假时才为假。4等价（↔）两个命题的真值相同时才为真。5联结词的真值表真假假真真真真假真真假假假真假真真假假真假假真真复合命题的真值表构建列出所有可能的命题组合。根据联结词的真值表，计算每个联结词的结果。最终得到复合命题的真值表。命题公式与真值表命题公式由命题和联结词组成的表达式，例如：(P∧Q)→¬R。真值表用于表示命题公式在不同命题取值下的真值结果。命题公式的类型：永真式、永假式、可满足式永真式在所有命题取值下都为真的命题公式，例如：P∨¬P。永假式在所有命题取值下都为假的命题公式，例如：P∧¬P。可满足式至少存在一种命题取值组合使命题公式为真的命题公式，例如：P→Q。等价公式1定义两个命题公式在所有命题取值下都有相同的真值。2表示用符号"≡"表示，例如：¬(P∧Q)≡¬P∨¬Q。3应用简化命题公式，方便推理和证明。逻辑等价的定义如果两个命题公式在所有可能的命题取值组合下都具有相同的真值，则它们是逻辑等价的。例如，¬(P∧Q)和¬P∨¬Q是逻辑等价的，因为它们在真值表中具有相同的真值结果。常见的逻辑等价公式：德摩根律、分配律等1德摩根律¬(P∧Q)≡¬P∨¬Q¬(P∨Q)≡¬P∧¬Q2分配律P∧(Q∨R)≡(P∧Q)∨(P∧R)P∨(Q∧R)≡(P∨Q)∧(P∨R)3其他等价公式P→Q≡¬P∨QP↔Q≡(P→Q)∧(Q→P)等价公式的应用：化简命题公式1利用逻辑等价公式可以将复杂的命题公式简化为更简单的形式。2例如，¬(P∧Q)∨(P∧R)可以化简为¬P∨¬Q∨(P∧R)。3简化后的公式更容易理解和推理。蕴含式定义表示一个命题推导出另一个命题的逻辑关系，符号为"→"。理解如果前件为真，则后件必须为真；如果前件为假，则后件可以为真也可以为假。蕴含式的定义与理解真真真真假假假真真假假真蕴含式的真值表逆、否、逆否命题1原命题如果P则Q2逆命题如果Q则P3否命题P且非Q4逆否命题如果非Q则非P蕴含式的推理规则：肯定前件、否定后件肯定前件如果P为真，则Q为真。否定后件如果Q为假，则P为假。量词与谓词谓词一个带变量的命题函数，例如："x是偶数"。量词用于指定谓词的变量范围，例如：全称量词"∀"和存在量词"∃"。谓词的定义：带变量的命题函数谓词是一个带变量的命题函数，它在不同的变量取值下可能为真，也可能为假。例如，谓词"P(x):x是偶数"，当x取值为2时，P(2)为真；当x取值为3时，P(3)为假。谓词可以表示各种概念和关系，是谓词逻辑的基础。全称量词（∀）与存在量词（∃）全称量词(∀)表示对某个集合中的所有元素都成立，例如：∀x∈R,x²≥0。存在量词(∃)表示至少存在一个元素满足条件，例如：∃x∈R,x²=1。量词辖域1定义量词的辖域是指量词作用范围内的部分。2作用确定量词所修饰的变量的范围。3示例∀x(P(x)∧Q(x))中，量词∀x的辖域是整个公式。带有量词的命题的真值判断全称量词如果对所有变量取值都成立，则命题为真。存在量词如果至少存在一个变量取值使得命题成立，则命题为真。量词的否定¬∀xP(x)≡∃x¬P(x)¬∃xP(x)≡∀x¬P(x)多个量词的使用多个量词可以同时出现在一个命题中。例如：∀x∃yP(x,y)表示对于所有x，都存在一个y使得P(x,y)成立。量词的顺序会影响命题的意义。逻辑推理从已知的前提推导出新的结论的过程。推理需要遵循一定的逻辑规则，以保证结论的正确性。逻辑推理是计算机科学、数学、哲学等领域的重要基础。推理的定义：从前提推出结论的过程前提已知的真命题。1推理规则用于推导出新结论的逻辑规则。2结论从前提和推理规则推导出的新命题。3推理的形式结构1前提P1,P2,...,Pn2推理规则R3结论Q有效推理与无效推理有效推理前提为真时，结论一定为真的推理。无效推理前提为真时，结论不一定为真的推理。推理规则：肯定前件、否定后件、假言推理、拒取式等1肯定前件如果P→Q，且P为真，则Q为真。2否定后件如果P→Q，且Q为假，则P为假。3假言推理如果P→Q，且Q→R，则P→R。4拒取式如果P→Q，且¬Q为真，则¬P为真。自然演绎系统一套完整的推理规则，可以用来推导出任何有效的结论。自然演绎系统通常采用树状结构，每个节点表示一个命题，连接线表示推理规则。自然演绎系统是现代逻辑推理的重要工具。推理证明定义利用推理规则，从已知的前提推出结论的过程。目的证明结论的正确性，并展现推理过程。命题逻辑的推理证明方法步骤1.列出前提。2.利用推理规则推导出新的命题。3.重复步骤2，直到推出结论。示例已知：P→Q，Q→R证明：P→R前提引入规则1可以将前提直接引入证明。2前提可以作为推导其他结论的依据。3前提的引入是证明的第一步。结论证明规则利用推理规则，从已知的前提推导出结论。结论的证明是证明的最终目标。结论的证明必须遵循逻辑规则，确保结论的正确性。证明题实例分析证明题已知：P→Q，¬Q证明：¬P证明过程1.P→Q(前提)2.¬Q(前提)3.¬P(否定后件规则，由1和2推出)谓词逻辑的推理证明方法1全称特指规则如果∀xP(x)为真，则对于任意的个体常数a，P(a)为真。2存在例示规则如果∃xP(x)为真，则存在一个个体常数a使得P(a)为真。证明题实例分析已知：∀x(P(x)→Q(x)),P(a)证明：Q(a)1.∀x(P(x)→Q(x))(前提)2.P(a)→Q(a)(全称特指规则，由1推出)3.P(a)(前提)4.Q(a)(肯定前件规则，由2和3推出)证明方法直接证明从前提出发，利用推理规则直接推导出结论。1反证法假设结论不成立，推导出矛盾，从而证明结论成立。2数学归纳法证明一个关于自然数的命题时，先证明基础情况，然后假设命题对于某个自然数成立，推导出命题对于下一个自然数也成立。3结构归纳法证明关于递归定义的结构的命题，先证明基础情况，然后假设命题对于所有子结构成立，推导出命题对于整个结构也成立。4直接证明从前提出发，利用推理规则直接推导出结论。直接证明通常采用演绎推理，即从一般到特殊的推理方式。直接证明是一种常用的证明方法，适用于许多简单的命题。反证法定义假设结论不成立，推导出矛盾，从而证明结论成立。步骤1.假设结论不成立。2.从假设出发，推导出矛盾。3.由于假设导致矛盾，因此假设不成立，结论成立。数学归纳法证明一个关于自然数的命题时，先证明基础情况，然后假设命题对于某个自然数成立，推导出命题对于下一个自然数也成立。数学归纳法是一种强大的证明方法，适用于许多关于自然数的命题。数学归纳法的核心是递推关系。结构归纳法证明关于递归定义的结构的命题，先证明基础情况，然后假设命题对于所有子结构成立，推导出命题对于整个结构也成立。结构归纳法类似于数学归纳法，但适用于更一般的结构，例如树、链表等。结构归纳法的核心是递归关系。证明题实例分析1证明题证明：对于任意自然数n，1+2+...+n=n(n+1)/22基础情况当n=1时，命题成立，因为1=1(1+1)/23归纳假设假设命题对于某个自然数k成立，即1+2+...+k=k(k+1)/24归纳步骤需要证明命题对于k+1也成立，即1+2+...+(k+1)=(k+1)(k+2)/21+2+...+(k+1)=(1+2+...+k)+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2因此，命题对于k+1也成立。应用实例：逻辑电路设计应用场景逻辑电路设计中，可以使用逻辑运算符来构建各种电路。示例可以使用AND门、OR门、NOT门等逻辑门实现各种逻辑运算。应用实例：程序验证目的验证程序的正确性，确保程序按照预期执行。方法使用逻辑推理来证明程序满足特定规范。应用实例：数据库查询优化逻辑推理可以用于优化数据库查询语句。通过逻辑化简和等价变换，可以得到效率更高的查询语句。逻辑推理在数据库管理系统中发挥着重要作用。常见谬误1肯定后件谬误如果P→Q，且Q为真，则P为真。2否定前件谬误如果P→Q，且P为假，则Q为假。3循环论证谬误使用结论本身作为证明结论的依据。肯定后件谬误例如："如果下雨，则地面湿。现在地面湿，所以下雨了。"这种推理是错误的，因为地面湿可能由其他原因引起，例如洒水。肯定后件谬误错误地将"P→Q且Q为真"推导出"P为真"。否定前件谬误定义错误地将"P→Q且P为假"推导出"Q为假"。示例例如："如果考试及格，则可以参加晚会。现在考试不及格，所以不能参加晚会。"这种推理是错误的，因为考试不及格并不意味着不能参加晚会。循环论证谬误使用结论本身作为证明结论的依据。例如："神存在，因为圣经说神存在。圣经是神的话，所以神存在。"这种推理是错误的，因为它假设了神存在，然后用神存在来证明神存在。逻辑的应用：人工智能逻辑推理是人工智能领域的核心技术之一。专家系统、知识表示、机器学习等都依赖于逻辑推理。逻辑推理可以帮助人工智能系统进行决策、学习和问题解决。逻辑的应用：形式化方法定义使用数学方法来描述和分析系统，例如程序、硬件等。应用逻辑推理在形式化方法中起着重要作用，可以用来验