北语直属15春《离散数学》作业1

北语直属15春《离散数学》作业1离散数学作为计算机科学与技术领域的基础学科，其严谨的逻辑体系和抽象思维方式是构建后续专业知识的重要基石。本次作业1作为课程开篇的检验，主要聚焦于命题逻辑的核心内容，包括命题与联结词、真值表、等值演算、范式以及命题逻辑的推理理论。本文旨在为同学们提供一份针对性的复习指南与解题思路梳理，助力大家更好地理解并掌握这些基础概念与方法。一、命题与联结词：逻辑的基石命题逻辑研究的基本单位是命题。理解命题的定义及其分类是入门的关键。1.命题的界定：命题是指具有唯一真值的陈述句。这里有两个核心要素：“陈述句”和“唯一真值”。感叹句、疑问句、祈使句通常不构成命题。真值可以是真（用T或1表示）或假（用F或0表示），但一个命题的真值必须是确定的，不能模棱两可。例如，“雪是白色的”是一个真命题，而“这个语句是假的”则因产生自指矛盾，不成为命题。2.原子命题与复合命题：不能再分解为更简单命题的命题称为原子命题或简单命题。由原子命题通过联结词组合而成的命题则为复合命题。识别原子命题是进行逻辑分析的第一步。3.逻辑联结词：这是将原子命题组合成复合命题的基本工具，务必准确理解每种联结词的逻辑含义、真值表定义以及自然语言中的表达方式。*否定（¬）：对原命题的真值取反。*合取（∧）：只有当所有支命题都为真时，复合命题才为真。*析取（∨）：至少有一个支命题为真时，复合命题为真（注意区分“相容或”与“排斥或”，后者在自然语言中常见，需用∨和¬的组合来精确表达）。*蕴含（→）：这是最容易产生混淆的联结词。P→Q表示“如果P，则Q”。其真值表中，只有当P为真且Q为假时，P→Q才为假。要特别注意理解“善意的推定”，即当前件P为假时，无论后件Q真假，整个蕴含式都为真。*等价（↔）：当两个支命题的真值完全相同时，等价式为真。解题要点：在面对具体问题时，首先要准确地将自然语言描述的命题符号化，这需要对上述联结词的深刻理解。例如，“只有A，才B”应符号化为B→A，而非A→B。二、命题公式与真值表：形式化与语义由命题变元、逻辑联结词和括号按照一定规则组成的符号串称为命题公式。真值表则是研究命题公式语义的重要工具，它清晰地展示了公式在所有可能的命题变元真值组合下的取值情况。1.命题公式的定义与层次：理解公式的递归定义方式，能够判断一个符号串是否为合法的命题公式，并分析其层次结构。2.真值表的构造：构造真值表时，需先确定命题变元的个数，列出所有可能的真值组合（若有n个变元，则有2^n种组合），然后按照公式的层次结构由内向外逐步计算各子公式的真值，最终得到整个公式的真值。3.公式的分类：根据真值表，可将命题公式分为重言式（永真式）、矛盾式（永假式）和可满足式。重言式在任何解释下都为真，矛盾式则相反，可满足式至少存在一种解释使其为真。解题要点：真值表法是一种直观且万能的方法，可用于判断公式类型、验证等值式、判断公式间的蕴含关系等。在作业中，对于一些不太复杂的公式，构造真值表是解决问题的有效途径。例如，验证两个公式是否等值，只需构造它们的真值表，看其最后一列是否完全相同。三、等值演算与范式：公式的变形与标准化等值演算是命题逻辑中的核心方法，它基于已知的等值式（如双重否定律、幂等律、交换律、结合律、分配律、德摩根律、吸收律、蕴含等值式、等价等值式等）对命题公式进行等价变换。1.基本等值式：务必牢记并熟练运用这些基本的“逻辑代数”法则。例如，德摩根律¬(A∨B)⇔¬A∧¬B和¬(A∧B)⇔¬A∨¬B在化简公式时非常有用。蕴含等值式A→B⇔¬A∨B则揭示了蕴含联结词与否定、析取联结词之间的联系。2.等值演算的应用：通过等值演算，可以实现公式的化简、判断公式的类型（如证明某公式为重言式，可尝试将其等值演算为“1”）、证明两个公式等值等。演算过程中，要注意每一步变换的依据，确保推理的正确性。3.范式：范式是命题公式的标准形式，具有唯一性（主范式），为我们提供了一种统一的方法来比较和研究公式。*析取范式与合取范式：析取范式是由有限个简单合取式组成的析取式；合取范式是由有限个简单析取式组成的合取式。任何命题公式都存在与之等值的析取范式和合取范式，但它们不唯一。*主析取范式与主合取范式：这是更为精细的范式。主析取范式由极小项的析取组成，每个极小项对应着使得公式为真的一组命题变元真值组合（成真赋值）；主合取范式由极大项的合取组成，每个极大项对应着使得公式为假的一组命题变元真值组合（成假赋值）。它们具有唯一性，因此是判断公式等值、求解公式类型、解决实际逻辑问题的有力工具。解题要点：等值演算是核心技能，需要大量练习才能熟练掌握。在求范式时，通常的步骤是：消去→和↔，内移否定号（德摩根律），然后使用分配律将公式化为所需的范式形式。求主范式时，可以通过真值表法（找出所有成真/成假赋值对应的极小项/极大项）或等值演算法（添加缺少的变元，再用分配律展开）。四、命题逻辑的推理理论：由前提到结论的过渡推理是从给定的前提集合出发，应用推理规则得出结论的过程。这部分内容直接关系到逻辑思维能力的培养。1.推理的形式结构：将推理符号化为“H₁∧H₂∧...∧Hₖ→C”的形式，其中H₁...Hₖ是前提，C是结论。若该蕴含式为重言式，则称推理有效或正确。2.推理规则：常用的推理规则包括：前提引入规则、结论引入规则、置换规则，以及假言推理（肯定前件）、附加、化简、拒取式（否定后件）、假言三段论、析取三段论、构造性二难等。这些规则是进行有效推理的依据，必须准确理解其含义和使用条件。3.判断推理有效性的方法：*真值表法：判断蕴含式是否为重言式。*等值演算法：将蕴含式化简，看是否能得到“1”。*主范式法：检查主析取范式是否包含所有极小项（或主合取范式是否为空）。*自然推理系统P中的形式证明：这是作业和考试中重点考察的内容。从前提出发，严格按照推理规则，逐步推导出结论。常用的技巧包括直接证明法、附加前提证明法（适用于结论为蕴含式）和归谬法（反证法，假设结论的否定为真，推出矛盾）。解题要点：形式证明是难点。在进行证明时，要明确每一步推理所依据的前提和规则，保持清晰的思路。对于复杂的推理，可以尝试从结论入手进行反向思考，或者利用归谬法将问题转化。五、学习建议与常见误区1.深刻理解基本概念：离散数学的特点是概念性强，务必不要死记硬背，要理解概念的内涵和外延。2.多做练习：只有通过大量不同类型的习题练习，才能真正掌握各种解题方法和技巧，熟悉各种联结词和推理规则的应用场景。3.注重逻辑思维的培养：学习离散数学的过程本身就是逻辑思维训练的过程，要养成严谨、清晰的思维习惯。4.常见误区提醒：*对“蕴含”联结词的理解不准确，特别是P为假时P→Q为真的情况。*自然语言符号化时，对联结词的选择不当，如混淆“如果...则...”与“只有...才...”。*在等值演算中，随意使用“自创”的等值式，而不是基于基本等值式进行推导