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

东大20春学期《离散数学X》在线平时作业2参考资料亲爱的同学们，大家好！针对《离散数学X》这门课程的在线平时作业，我为大家整理了一份参考资料。这份资料旨在帮助大家更好地理解作业中可能涉及的核心知识点，并提供一些解题思路上的指引。请注意，这并非标准答案，而是辅助学习的工具，希望大家能独立思考，真正掌握离散数学的精髓。一、命题逻辑回顾与深化命题逻辑作为数理逻辑的基础，在本次作业中仍占有重要地位。我们不仅要掌握命题的表示、联结词的运算，更要深入理解公式的等值演算、范式以及推理理论。1.1范式(NormalForms)作业中可能会涉及到将给定命题公式化为合取范式或析取范式的问题。*合取范式(CNF)：由若干简单析取式（子句）通过合取联结词连接而成。一个简单析取式是由命题变元或其否定组成的析取式。*析取范式(DNF)：由若干简单合取式（短语）通过析取联结词连接而成。一个简单合取式是由命题变元或其否定组成的合取式。*求解步骤：通常先消去蕴含词和等价词，然后利用德摩根律将否定词内移，最后通过分配律进行转换。如果题目要求主范式（主合取范式或主析取范式），则需要在上述基础上，对缺少的命题变元进行补项，并合并相同的项。主范式的好处是唯一性，便于判断公式的类型（重言式、矛盾式、可满足式）以及进行等值判断。典型问题与分析：例如，将公式¬(P→Q)∨R化为析取范式。首先，消去→：¬(¬P∨Q)∨R；然后，德摩根律内移否定：(P∧¬Q)∨R。这已经是析取范式了，因为它是两个简单合取式(P∧¬Q)和R的析取。如果进一步要求主析取范式，则需要考虑R中缺少的变元P和Q，以及(P∧¬Q)中缺少的变元R。对于R，可以写成(P∨¬P)∧(Q∨¬Q)∧R，然后展开；对于(P∧¬Q)，可以写成(P∧¬Q)∧(R∨¬R)，然后展开，最后合并相同的极小项。1.2推理理论(InferenceTheory)判断推理是否有效，构造有效推理的证明，是命题逻辑的核心应用。*推理规则：如前提引入规则、结论引入规则、置换规则，以及假言推理、拒取式、析取三段论、假言三段论、等价三段论、构造性二难等常用推理定律。这些是构造证明的“工具”。*证明方法：直接证明法、附加前提证明法（CP规则，适用于结论为蕴含式）、归谬法（反证法，假设结论的否定为真，推出矛盾）。典型问题与分析：例如，给定一组前提，如P∨Q,P→¬R,S→T,¬S→R,¬T，要求证明结论Q。我们可以从前提¬T和S→T入手，根据拒取式可得¬S；再由¬S和¬S→R可得R；由R和P→¬R可得¬P；最后由¬P和P∨Q可得Q。这个过程就需要熟练运用各种推理规则和定律。在书写证明序列时，每一步都要清晰注明所用的前提或推理规则，保证推理的严谨性。二、集合与关系(SetsandRelations)集合论是现代数学的基础，而关系是集合论中刻画事物之间联系的重要概念。本次作业可能会重点考察关系的性质、运算以及闭包等内容。2.1关系的性质(PropertiesofRelations)在集合A上的二元关系R，可能具有以下性质：*自反性(Reflexivity)：对所有a∈A，都有(a,a)∈R。*反自反性(Irreflexivity)：对所有a∈A，都有(a,a)∉R。*对称性(Symmetry)：若(a,b)∈R，则(b,a)∈R。*反对称性(Antisymmetry)：若(a,b)∈R且(b,a)∈R，则a=b。*传递性(Transitivity)：若(a,b)∈R且(b,c)∈R，则(a,c)∈R。判断关系是否具有这些性质，需要严格按照定义进行验证。特别注意，自反与反自反并非完全对立，存在既不自反也不反自反的关系；同样，对称与反对称也不是完全对立的。典型问题与分析：例如，设集合A={1,2,3}，关系R={(1,1),(1,2),(2,3),(3,2)}。判断其性质：*自反性：由于(2,2)∉R，(3,3)∉R，所以R不是自反的。*反自反性：由于(1,1)∈R，所以R不是反自反的。*对称性：(1,2)∈R，但(2,1)∉R，故R不对称。*反对称性：(2,3)∈R且(3,2)∈R，但2≠3，故R不反对称。*传递性：(1,2)∈R且(2,3)∈R，但(1,3)∉R，故R不传递。2.2关系的运算(OperationsonRelations)关系的运算包括集合运算（并、交、补、差）以及关系特有的复合运算和逆运算。*逆关系(InverseRelation)：设R是从A到B的关系，则R的逆关系R⁻¹是从B到A的关系，定义为R⁻¹={(b,a)|(a,b)∈R}。关系的逆运算具有一些良好的性质，例如(R⁻¹)⁻¹=R，(R∘S)⁻¹=S⁻¹∘R⁻¹等。典型问题与分析：例如，已知集合A={a,b,c},B={1,2,3},C={x,y,z}。关系R={(a,1),(a,2),(b,2)}，S={(1,x),(2,y),(3,z)}。则R∘S为{(a,x),(a,y),(b,y)}。而R⁻¹为{(1,a),(2,a),(2,b)}。理解复合关系的定义是关键，寻找中间元素b是进行复合的桥梁。2.3关系的闭包(ClosuresofRelations)关系的闭包是指将一个不具备某种性质的关系，通过最小的扩充（添加最少的有序对）使其具备该性质。常见的闭包有：*自反闭包(r(R))：添加所有(a,a)∉R的有序对。*对称闭包(s(R))：若(a,b)∈R且(b,a)∉R，则添加(b,a)。*传递闭包(t(R))：传递闭包的计算相对复杂，常用的方法有沃舍尔算法(Warshall'sAlgorithm)，或者通过R的幂运算的并集来计算，即t(R)=R∪R²∪R³∪...。对于有限集合上的关系，这个并集是有限的。典型问题与分析：例如，求集合A={1,2,3}上关系R={(1,2),(2,3),(3,1)}的自反闭包、对称闭包和传递闭包。*r(R)=R∪{(1,1),(2,2),(3,3)}。*s(R)=R∪{(2,1),(3,2),(1,3)}，因为原关系中(1,2)对应(2,1)缺失，(2,3)对应(3,2)缺失，(3,1)对应(1,3)缺失。*t(R)：通过计算R²,R³等。R²=R∘R={(1,3),(2,1),(3,2)}，R³=R²∘R={(1,1),(2,2),(3,3)}，R⁴=R³∘R=R。所以t(R)=R∪R²∪R³=A×A，即全关系。这说明该关系经过传递闭包运算后，任意两个元素之间都有了关系。三、函数(Functions)函数是一种特殊的二元关系，它要求对于定义域中的每一个元素，都有唯一的像与之对应。作业中可能会涉及函数的基本概念、性质（单射、满射、双射）以及函数的复合与逆函数。3.1函数的基本概念与性质*函数的定义：从集合A到集合B的函数f:A→B，是A×B的子集，且对每个a∈A，存在唯一的b∈B使得(a,b)∈f。*单射(Injective/One-to-One)：若a₁≠a₂则f(a₁)≠f(a₂)，或者等价地，若f(a₁)=f(a₂)则a₁=a₂。*满射(Surjective/On-to)：对每个b∈B，都存在a∈A使得f(a)=b。*双射(Bijective/One-to-OneCorrespondence)：既是单射又是满射的函数。典型问题与分析：判断一个给定的关系是否为函数，以及函数是否为单射、满射或双射，需要严格依据定义。例如，对于从整数集Z到Z的函数f(x)=x+1，它是单射也是满射，因此是双射。而f(x)=x²(Z→Z)则既不是单射（f(-1)=f(1)）也不是满射（负数没有原像）。总结与建议离散数学的学习，关键在于理解概念的精确定义，并能熟练运用这些概念进行推理和演算。对于本次作业：1.仔细审题：明确题目要求，是证明、计算还是判断。2.回归定义：遇到不熟悉的问题或卡壳时，多回顾相关概念的定义和基本性质。