东大20春学期《离散数学X》在线平时作业1参考资料

东大20春学期《离散数学X》在线平时作业1参考资料引言这份参考资料旨在为正在学习《离散数学X》课程并准备完成20春学期在线平时作业1的同学们提供一些学习上的指引与帮助。离散数学作为计算机科学与技术等相关专业的核心基础课程，其概念抽象、逻辑性强，对后续课程的学习至关重要。平时作业是检验学习效果、巩固知识理解的重要环节。本资料将围绕作业可能涉及的核心知识点进行梳理，并结合课程特点给出一些解题思路与学习建议，希望能助同学们一臂之力。请注意，本资料仅为辅助学习之用，鼓励同学们独立思考、自主完成作业，以真正掌握课程内容。一、核心知识点梳理本次平时作业1的考察范围，根据课程进度和《离散数学X》的通常教学安排，大概率集中在课程的开篇部分，主要包括命题逻辑和集合论基础两大块。这两部分是离散数学的基石，也是后续学习谓词逻辑、关系、图论等内容的前提。1.1命题逻辑(PropositionalLogic)命题逻辑是研究以命题为基本单位构成的前提和结论之间的可推导关系。*1.1.1命题与联结词(PropositionsandConnectives)*命题：能够判断真假的陈述句。它必须具有唯一的真值（真或假）。需要注意区分哪些语句是命题，哪些不是（如祈使句、疑问句、悖论等）。*原子命题与复合命题：不能再分解为更简单命题的命题称为原子命题或简单命题；由原子命题通过联结词组合而成的命题称为复合命题。*常用逻辑联结词：*否定(Negation)：通常用符号“¬”表示。若P为命题，则¬P表示“非P”，其真值与P相反。*合取(Conjunction)：通常用符号“∧”表示。P∧Q表示“P并且Q”，当且仅当P和Q都为真时，P∧Q为真。*析取(Disjunction)：通常用符号“∨”表示。P∨Q表示“P或者Q”，当且仅当P和Q至少有一个为真时，P∨Q为真。这里的“或”是“可兼或”。*蕴含(Implication)：通常用符号“→”表示。P→Q表示“如果P，那么Q”。当前件P为真，后件Q为假时，P→Q为假；其余情况均为真。理解蕴含的逻辑意义是难点，需注意与自然语言中“如果…那么…”的区别。*等价/双条件(Biconditional)：通常用符号“↔”表示。P↔Q表示“P当且仅当Q”，当P和Q的真值相同时，P↔Q为真；否则为假。*命题符号化：将自然语言描述的语句抽象为用命题变元和联结词表示的符号串。这是运用命题逻辑解决实际问题的第一步，需要准确理解自然语言的语义，并选择合适的联结词。*1.1.2命题公式及其赋值(PropositionalFormulasandAssignments)*命题公式（合式公式）：由命题变元、联结词和括号按照一定的语法规则组成的符号串。*公式的赋值：给公式中的所有命题变元指定一组真值（0或1），从而确定公式的真值。*重言式（永真式,Tautology）：无论对命题变元作何种赋值，公式的真值总为真。*矛盾式（永假式,Contradiction）：无论对命题变元作何种赋值，公式的真值总为假。*可满足式（Satisfiable）：存在至少一种赋值使公式的真值为真。重言式是特殊的可满足式。*判断公式类型的方法：真值表法是最基本也是最直接的方法，通过列出公式所有可能的赋值及其对应的真值来判断。*1.1.3等值演算(EquivalentCalculus)*等值式：如果两个公式A和B在任何赋值下都具有相同的真值，则称A与B等值，记作A⇔B。*基本等值式：如双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、零律、同一律、排中律、矛盾律、蕴含等值式（P→Q⇔¬P∨Q）、等价等值式（P↔Q⇔(P→Q)∧(Q→P)）、假言易位（P→Q⇔¬Q→¬P）、等价否定等值式（P↔Q⇔¬P↔¬Q）等。这些基本等值式是进行等值演算的基础，需要熟练掌握和记忆。*等值演算：利用已知的等值式，推演出其他等值式的过程。等值演算可以用来化简公式、判断公式类型（如证明某公式为重言式或矛盾式）、证明两个公式等值等。*1.1.4范式(NormalForms)*简单析取式与简单合取式：由有限个命题变元或其否定构成的析取式称为简单析取式；由有限个命题变元或其否定构成的合取式称为简单合取式。*析取范式(DisjunctiveNormalForm,DNF)：由有限个简单合取式构成的析取式。*合取范式(ConjunctiveNormalForm,CNF)：由有限个简单析取式构成的合取式。*主析取范式与主合取范式：在析取范式中，每个简单合取式都是极小项，则称该析取范式为主析取范式；在合取范式中，每个简单析取式都是极大项，则称该合取范式为主合取范式。任何一个非矛盾式都存在唯一的主析取范式；任何一个非重言式都存在唯一的主合取范式。主范式是命题公式的标准形式，在逻辑推理和电路设计等领域有重要应用。*求主范式的方法：通常可以通过等值演算将公式化为析取范式（或合取范式），然后通过添加缺少的变元、合并相同项等步骤得到主析取范式（或主合取范式）；也可以利用真值表法，根据使得公式为真的赋值（极小项）或为假的赋值（极大项）直接写出。*1.1.5命题逻辑的推理理论(InferenceTheoryinPropositionalLogic)*推理的形式结构：设A₁,A₂,...,Aₖ,B都是命题公式，如果对于A₁∧A₂∧...∧Aₖ→B是重言式，则称由前提A₁,A₂,...,Aₖ推出结论B的推理是有效的或正确的，记作A₁∧A₂∧...∧Aₖ⇒B。*推理规则：如前提引入规则、结论引入规则、置换规则，以及常用的推理定律对应的规则，如假言推理（ModusPonens,MP）、拒取式（ModusTollens,MT）、析取三段论、假言三段论、等价三段论、构造性二难等。*构造证明法：利用推理规则，从前提一步步推出结论的过程。常用的证明方法有直接证明法、附加前提证明法（CP规则，用于结论是蕴含式的情况）和归谬法（反证法，假设结论的否定为真，推出矛盾）。1.2集合论基础(FundamentalsofSetTheory)集合论是现代数学的基础，离散数学中的许多概念都建立在集合论之上。*1.2.1集合的基本概念与表示*集合：具有某种特定性质的对象的总体。集合中的对象称为元素。*集合的表示方法：常用的有列举法（将元素一一列出）和描述法（用谓词描述元素的共同属性）。*集合与元素的关系：属于（∈）或不属于（∉）。*集合的特性：确定性、互异性、无序性。*常用集合：自然数集N、整数集Z、有理数集Q、实数集R等，以及空集∅、全集E（或U）。*集合间的关系：包含（子集，⊆）、真包含（真子集，⊂）、相等（=）。注意区分元素与集合的关系（∈）和集合与集合的关系（⊆,⊂,=）。*幂集(PowerSet)：设A为集合，由A的所有子集组成的集合称为A的幂集，记作P(A)或℘(A)。若A有n个元素，则P(A)有2ⁿ个元素。*1.2.2集合的基本运算*并集(Union)：A∪B={x|x∈A∨x∈B}*交集(Intersection)：A∩B={x|x∈A∧x∈B}*对称差集(SymmetricDifference)：A⊕B=(A-B)∪(B-A)={x|(x∈A∧x∉B)∨(x∈B∧x∉A)}*文氏图(VennDiagram)：是表示集合及其运算的直观工具，有助于理解和解决集合问题。*1.2.3集合恒等式*基本集合恒等式：如幂等律、交换律、结合律、分配律、德摩根律（对于集合运算的）、同一律、零律、排中律、矛盾律、吸收律、双重否定律（对绝对补集而言）、补交转换律（A-B=A∩~B）等。这些恒等式对于集合的等价变形和证明非常重要。*证明集合恒等式的方法：通常可以通过证明等式两边的集合互相包含（即证左边⊆右边且右边⊆左边）；也可以利用已知的集合恒等式进行推演。二、解题思路与学习建议2.1解题思路1.仔细审题，明确题意：拿到题目后，首先要仔细阅读，理解题目要求。是判断命题、进行符号化、求公式真值、证明等值式、求范式，还是进行推理，或是关于集合的基本运算与证明？明确题目类型是正确解题的第一步。2.回归定义，夯实基础：很多题目考察的是对基本概念和定义的理解。当遇到问题时，不要急于求成，先回顾相关的定义、定理和公式。例如，判断一个语句是否为命题，就要回到命题的定义——“能判断真假的陈述句”。3.灵活运用方法，注重技巧：*命题逻辑中：真值表法是一种万能但有时略显繁琐的方法，对于变元个数较少的公式非常有效。等值演算是化简公式和证明等值的核心方法，需要熟练掌握基本等值式。对于推理证明题，要熟练运用推理规则，选择合适的证明方法（直接证法、CP规则、归谬法）。*集合论中：文氏图可以帮助直观理解集合间的关系和运算，但它不能作为严格的证明。证明集合相等或包含关系，最基本的方法是元素属于法。集合恒等式的证明则需要对各种运算律熟练于心。4.步骤清晰，书写规范：解题过程中，尤其是证明题，要写出关键步骤，逻辑清晰，论据充分。这不仅有助于自己检查，也方便老师批改。2.2学习建议1.重视基本概念：离散数学的概念繁多且抽象，务必吃透每个概念的内涵与外延，不能似是而非。2.多做练习，勤于思考：离散数学的学习离不开练习。通过做题可以检验对知识的掌握程度，加深理解，培养解题技巧和逻辑思维能力。遇到难题要多思考，不要轻易放弃，可以查阅教材、笔记或与同学讨论。3.梳理知识脉络，构建知识体系：命题逻辑和集合论基础各自有其内在的逻辑结构，学习时要注意知识点之间的联系与区别，形成系统的知识框架，而不是孤立地记忆零散的知识点。4.注意逻辑表达的准确性：无论是符号化命题，还是进行推理证明，都要力求逻辑严谨，表达准确无误。这是离散数学的基本要求。5.结合实际，理解应用：思考所学知识在计算机科学等领域的应用背景，如逻辑在电路设计、程序正确性验证中的作用，集合在数据库、数据结构中的应用等，这能提高