离散数学形考任务3数理逻辑部分概念及性质

离散数学形考任务3数理逻辑部分概念及性质引言数理逻辑作为离散数学的核心组成部分，旨在通过数学化的形式语言研究推理的有效性与逻辑规律。它为计算机科学、人工智能、语言学等多个领域提供了坚实的理论基础。在形考任务3中，对数理逻辑部分的考察重点在于对基本概念的准确理解和对核心性质的灵活运用。本文将系统梳理该部分的核心概念与关键性质，以期为学习者提供清晰的知识脉络和实用的复习指引。一、命题与联结词1.1命题的概念命题是数理逻辑研究的基本单位，指的是能判断真假的陈述句。一个命题必须满足两个基本条件：首先，它必须是一个陈述句；其次，它必须具有唯一的真值，即要么为真（用T或1表示），要么为假（用F或0表示）。真值是命题的固有属性，不随环境或主观判断而改变。性质：*二值性：任一命题的真值仅为真或假，二者必居其一且只居其一。*确定性：命题的真值是明确的，不存在模糊或歧义。例如，“雪是白色的”是一个真命题；“2加3等于7”是一个假命题。而“请把门关上”（祈使句）、“今天天气真好啊！”（感叹句）、“x大于5”（真值不确定的陈述句）均不是命题。1.2命题联结词原子命题是不能再分解为更简单命题的命题。复合命题则是由原子命题通过命题联结词组合而成。常用的命题联结词包括：*否定联结词（¬）：表示“非”。设P为命题，复合命题¬P（读作“非P”）的真值与P的真值相反。*性质：双重否定律成立，即¬¬P与P真值相同。*合取联结词（∧）：表示“并且”。设P、Q为命题，复合命题P∧Q（读作“P合取Q”或“P并且Q”）的真值为真，当且仅当P和Q的真值均为真。*性质：交换律（P∧Q≡Q∧P）、结合律（(P∧Q)∧R≡P∧(Q∧R)）、幂等律（P∧P≡P）。*析取联结词（∨）：表示“或者”（相容或）。设P、Q为命题，复合命题P∨Q（读作“P析取Q”或“P或者Q”）的真值为假，当且仅当P和Q的真值均为假。*性质：交换律（P∨Q≡Q∨P）、结合律（(P∨Q)∨R≡P∨(Q∨R)）、幂等律（P∨P≡P）、分配律（P∨(Q∧R)≡(P∨Q)∧(P∨R)；P∧(Q∨R)≡(P∧Q)∨(P∧R)）。*蕴含联结词（→）：表示“如果…那么…”。设P、Q为命题，复合命题P→Q（读作“P蕴含Q”或“如果P，那么Q”）的真值为假，当且仅当P的真值为真而Q的真值为假。P称为前件，Q称为后件。*性质：*P→Q与¬P∨Q等值。*逆否命题¬Q→¬P与原命题P→Q等值。*反之，逆命题Q→P与反命题¬P→¬Q等值，但与原命题不等值（除非构成等价）。*当P为假时，无论Q真假，P→Q恒为真（善意的推定）。*等价联结词（↔）：表示“当且仅当”。设P、Q为命题，复合命题P↔Q（读作“P等价于Q”或“P当且仅当Q”）的真值为真，当且仅当P和Q的真值相同。*性质：*P↔Q与(P→Q)∧(Q→P)等值。*交换律（P↔Q≡Q↔P）。*P↔Q与(P∧Q)∨(¬P∧¬Q)等值。真值表是表示命题联结词作用的有效工具，它清晰地列出了在命题变元所有可能的真值组合下，复合命题的对应真值。理解并熟练构造真值表，是掌握命题逻辑的基础。二、命题公式与赋值2.1命题公式的定义命题公式，亦称合式公式，是由命题变元、命题常元（T和F）以及命题联结词按一定规则组成的符号串。其递归定义如下：1.单个命题变元或命题常元是命题公式。2.若A是命题公式，则¬A也是命题公式。3.若A和B是命题公式，则(A∧B)、(A∨B)、(A→B)、(A↔B)也是命题公式。4.只有有限次应用上述规则所得到的符号串才是命题公式。命题公式的层次反映了其构造的复杂性。理解公式的层次有助于掌握其结构。2.2公式的赋值与类型赋值（解释）：给命题公式中的所有命题变元指定一组确定的真值（0或1），称为对该公式的一个赋值或解释。若指定的一组值使公式的真值为1，则称该赋值为成真赋值；若使公式的真值为0，则称该赋值为成假赋值。根据公式在所有可能赋值下的真值情况，可将命题公式分为以下类型：*重言式（永真式）：在任何赋值下，公式的真值都为1。*矛盾式（永假式）：在任何赋值下，公式的真值都为0。*可满足式：至少存在一个赋值使公式的真值为1。性质：*重言式一定是可满足式，但反之不然。*矛盾式一定不是可满足式。*设A为重言式，则A的否定为矛盾式；反之亦然。*若A和B均为重言式，则A∧B、A∨B、A→B、A↔B也都是重言式。判断一个公式的类型，是命题逻辑中的基本问题，常用方法有真值表法、等值演算法和主范式法。三、等值演算3.1等值式的概念设A、B是两个命题公式，若A↔B是重言式，则称A与B是等值的，记作A≡B。这里的“≡”不是联结词，而是表示两个公式逻辑等价的元语言符号。3.2基本等值式掌握一些基本的等值式，是进行等值演算的基础。常见的基本等值式包括：*双重否定律：A≡¬¬A*幂等律：A≡A∨A，A≡A∧A*交换律：A∨B≡B∨A，A∧B≡B∧A*结合律：(A∨B)∨C≡A∨(B∨C)，(A∧B)∧C≡A∧(B∧C)*分配律：A∨(B∧C)≡(A∨B)∧(A∨C)，A∧(B∨C)≡(A∧B)∨(A∧C)*德摩根律：¬(A∨B)≡¬A∧¬B，¬(A∧B)≡¬A∨¬B*吸收律：A∨(A∧B)≡A，A∧(A∨B)≡A*零律：A∨T≡T，A∧F≡F*同一律：A∨F≡A，A∧T≡A*排中律：A∨¬A≡T*矛盾律：A∧¬A≡F*蕴含等值式：A→B≡¬A∨B*等价等值式：A↔B≡(A→B)∧(B→A)*假言易位：A→B≡¬B→¬A*等价否定等值式：A↔B≡¬A↔¬B*归谬论：(A→B)∧(A→¬B)≡¬A3.3等值演算与置换规则等值演算是指利用已知的等值式，通过逐步置换命题公式中的子公式，将一个公式变换为另一个与之等值的公式的过程。置换规则：设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式。若A≡B，则Φ(A)≡Φ(B)。等值演算的主要应用包括：判断公式的类型（重言式、矛盾式、可满足式）、证明等值式、化简命题公式、解决实际逻辑问题等。四、范式范式是命题公式的标准形式，它为我们提供了一种统一的方法来研究和比较公式的性质。4.1析取范式与合取范式*文字：命题变元及其否定统称为文字。*简单析取式：由有限个文字组成的析取式。一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定。*简单合取式：由有限个文字组成的合取式。一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定。*析取范式：由有限个简单合取式组成的析取式。*合取范式：由有限个简单析取式组成的合取式。性质：*任何命题公式都存在与之等值的析取范式和合取范式（范式存在定理）。*析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。*合取范式是重言式当且仅当它的每个简单析取式都是重言式。4.2主析取范式与主合取范式为了使范式具有唯一性，需要引入主范式的概念。*极小项：在含有n个命题变元的简单合取式中，若每个命题变元及其否定不同时出现，而二者之一必出现且仅出现一次，则称该简单合取式为极小项。n个命题变元共有2ⁿ个不同的极小项。每个极小项都有且仅有一个成真赋值，对应二进制数可转换为一个十进制数，以此作为极小项的编码（通常用mₖ表示）。*主析取范式：由有限个极小项组成的析取式。*极大项：在含有n个命题变元的简单析取式中，若每个命题变元及其否定不同时出现，而二者之一必出现且仅出现一次，则称该简单析取式为极大项。n个命题变元共有2ⁿ个不同的极大项。每个极大项都有且仅有一个成假赋值，对应二进制数可转换为一个十进制数，以此作为极大项的编码（通常用Mₖ表示）。*主合取范式：由有限个极大项组成的合取式。性质：*任何命题公式（非永假式）都存在唯一的与之等值的主析取范式。*任何命题公式（非永真式）都存在唯一的与之等值的主合取范式。*矛盾式的主析取范式为空范式（不含有任何极小项），记为F；其主合取范式包含所有极大项。*重言式的主合取范式为空范式（不含有任何极大项），记为T；其主析取范式包含所有极小项。*主析取范式中的极小项对应公式的所有成真赋值；主合取范式中的极大项对应公式的所有成假赋值。*若已知公式的主析取范式，则可直接写出其主合取范式，反之亦然（利用极小项与极大项的互补关系）。求主析取范式和主合取范式的方法主要有：真值表法和等值演算法。主范式在逻辑电路设计、自动推理等领域有重要应用。五、命题逻辑的推理理论推理是从已知的命题（前提）出发，按照一定的规则推出新命题（结论）的思维过程。数理逻辑的核心任务之一就是研究推理的有效性。5.1推理的形式结构设A₁,A₂,...,Aₖ和B都是命题公式。若对于A₁∧A₂∧...∧Aₖ→B是重言式，则称从前提A₁,A₂,...,Aₖ推出结论B的推理是有效的或正确的，并称B是A₁,A₂,...,Aₖ的逻辑结论或有效结论，记作A₁∧A₂∧...∧Aₖ⇒B（或A₁,A₂,...,Aₖ⇒B）。推理的有效性仅与推理的形式结构有关，而与前提和结论的具体内容无关。即使前提为假，但只要推理形式正确，推理就是有效的。5.2推理定律推理定律是指一些常用的、重要的重言蕴涵式，它们是进行有效推理的依据。主要的推理定律包括：*附加律：A⇒(A∨B)*化简律：(A∧B)⇒A，(A∧B)⇒B*假言推理（肯定前件式）：(A→B)∧A⇒B*拒取式（否定后件式）：(A→B)∧¬B⇒¬A*析取三段论（否定肯定式）：(A∨B)∧¬A⇒B，(A∨B)∧¬B⇒A*假言三段论（传递律）：(A→B)∧(B→C)⇒(A→C)*等价三段论：(A↔B)∧(B↔C)⇒(A↔C)*构造性二难：(A→B)∧(C→D)∧(A∨C)⇒(B∨D)（特殊形式：(A→B)∧(¬A→B)∧(A∨¬A)⇒B，即(A→B)∧(¬A→B)⇒B）*破坏性二难：(A→B)∧(C→D)∧(¬B∨¬D)⇒(¬A∨¬C)5.3自然推理系统P自然推理系统是一种形式化的推理系统，它从给定的前提出发，应用系统中的推理规则进行推理演算，得到结论。自然推理系统P的构成：1.字母表：命题变元、联结词、括号与逗号。2.合式公式：同命题公式的定义。3.推理规则：*前提引入规则（P规则）：在证明的任何步骤上都可以引入前提。*结论引入规则（T规则）：在证明的任何步骤上所得到的结论都可以作为后续证明的前提。*置换规则：在证明的任何步骤上，命题公式中的