第二章命题推理(离散数学)详解

命题逻辑等值演算等值式定理：设A，B两个命题公式（即前面的合式公式），若A，B构成的等价式A↔B为重言式，则A与B是等值的，记作A⇔B(可以说该式子为等值式模式)常用的16组等值式模式：双重否定律：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∨1⇔1,A∧0⇔0同一律:A∨0⇔A,A∧1⇔1排中律:A∨﹁A⇔1矛盾律:A∧﹁A⇔0蕴涵等值式: A→B⇔﹁A∨B等价等值式: A↔B⇔(A→B)∧(B→A)假言易位:A→B⇔﹁B→﹁A(这里可以用逆否命题的概念证明)等价否定等值式:A↔B⇔﹁A↔﹁B(或写成﹁B↔﹁A，这里可以用逆否命题的概念证明)归谬(miu)论：(A→B)∧(A→﹁B)⇔﹁A(此处可以通过蕴涵等值式，交换律以及结合律进行结合证明)上述等值式模式可以通过真值表证明等值式的验证1.等值演算法（即通过等值式模式对原式进行变形）举例:(p∨q)→r⇔(p→r)∧(q→r)证明时可以从左边开始演算也可以从右边开始演算，无硬性要求，这里我们从右边开始演算。

(p→r)∧(q→r)⇔(﹁p∨r)∧(﹁q∨r) //蕴涵等值式⇔(﹁p∧﹁q)∨r //分配律⇔﹁(p∨q)∨r //德摩根律⇔(p∨q)→r //蕴涵等值式2.真值表法（我在第一章的最后有叙述，这里不再重述）3.观察法（也可称为带入法，此处适合用以证明两式不等值的情况）关于等值演算法的补充：等值演算法可以用以证明公式的类型。

1.当最后结果为1时为重言式（永真式）2.当最后结果为0时为矛盾式（永假式）3.当最后结果只能化成某个命题变项或公式时为可满足式析取范式与合取范式简单析取式：p,﹁p,p∨q,﹁p∨q,p∨﹁q,,﹁p∨﹁q,﹁p∨﹁q∨r等（这里可以发现的是里面都只含有析取联结词，简单析取式结构就是由析取联结词和命题变项组成的一个公式）简单合取式：p,﹁p,p∧q,﹁p∧q,p∧﹁q,,﹁p∧﹁q,﹁p∧﹁q∧r等（这里可以发现的是里面都只含有合取联结词，简单合取式结构就是由合取联结词和命题变项组成的一个公式）课本中的定理：命题变项及其否定统称为文字。

离散数学命题逻辑
离散数学是一门研究离散结构和逻辑推理的学科。

在这门学科中，命题逻辑是其中最基础的一部分。

命题逻辑是一种符号系统，用于表示和推理关于命题的真值。

命题是可以判断为真或假的陈述句。

命题逻辑的目标是通过推理规则和运算符来确定一个复合命题的真值。

命题逻辑中的符号包括命题变量、命题常量、逻辑连接词和逻辑运算符。

命题变量是用字母表示的可以代表任意命题的符号，命题常量是具体的命题，例如“今天是晴天”。

逻辑连接词包括“与”、“或”、“非”等。

逻辑运算符包括合取、析取、否定等。

命题逻辑有一些重要的推理规则，例如蕴含规则、假言推理、逆否命题等。

这些推理规则可以用来证明一个复合命题的真值。

在命题逻辑中，还可以使用真值表来确定一个复合命题的真值。

真值表是一种列出所有可能的真值组合并计算复合命题真值的表格。

除了命题逻辑，离散数学中还有谓词逻辑、谓词演算等其他逻辑系统。

这些逻辑系统在表示和推理复杂问题时更为强大和灵活。

离散数学中的命题逻辑在计算机科学、人工智能、密码学等领域有着广泛的应用。

例如，在计算机程序设计中，命题逻辑被用来表示和推理程序的正确性。

在人工智能中，命题逻辑被用来表示和推理关于世界的知识。

在密码学中，命题逻辑被用来分析和构造安全的密码算法。

总而言之，离散数学中的命题逻辑是一种重要的逻辑系统，用于表示和推理关于命题的真值。

它在各个领域都有广泛的应用，是理解和应用离散数学的基础。

离散数学命题逻辑公式1. 命题逻辑的基本概念命题逻辑是离散数学的一个重要分支，主要研究命题之间的关系以及命题的推理规则。

命题逻辑中的基本概念包括：命题：命题是描述客观事实真假的句子。

命题的真假值只有两个：真和假。

命题联结词：命题联结词用于将两个或多个命题连接起来，形成新的命题。

常见的命题联结词有：否定（¬）、合取（∧）、析取（∨）、蕴含（→）和等价（↔）。

命题公式：命题公式是由命题和命题联结词组成的表达式。

命题公式的真假值取决于其组成命题的真假值。

2. 命题逻辑的推理规则命题逻辑的推理规则是用于从给定的命题公式推导出新命题公式的规则。

常见的推理规则有：三段论：三段论是一种由两个前提和一个结论组成的推理形式。

如果两个前提都是真的，那么结论也一定是真的。

例如：所有哺乳动物都是恒温动物。

猫是哺乳动物。

所以，猫是恒温动物。

假言推理：假言推理是一种由一个条件句和一个结论组成的推理形式。

如果条件句是真的，那么结论也一定是真的。

例如：如果今天下雨，那么我就不出门。

今天下雨。

所以，我不出门。

选言推理：选言推理是一种由两个或多个分支组成的推理形式。

如果其中一个分支是真的，那么结论也一定是真的。

例如：要么今天下雨，要么明天下雨。

今天下雨。

所以，明天不会下雨。

3. 命题逻辑的应用命题逻辑在计算机科学、人工智能、哲学等领域有着广泛的应用。

在计算机科学中，命题逻辑用于设计和分析逻辑电路、编译器和操作系统等。

在人工智能中，命题逻辑用于知识表示和推理。

在哲学中，命题逻辑用于研究逻辑的本质和推理的有效性。

4. 结语命题逻辑是离散数学的一个重要分支，主要研究命题之间的关系以及命题的推理规则。

命题逻辑的应用非常广泛，包括计算机科学、人工智能、哲学等领域。

第二章命题逻辑---学习指导一、内容提要1.命题逻辑基本概念（1）命题与连接词命题与真值：命题、命题的真值、真命题、假命题、简单命题（或原子命题）复合命题；命题与真值的符号化：用p、q、r等命题，用数字1表示命题真，用0表示假；连接词及其符号化：记S={￢、∧、Ｖ、-→、←→}，称S为常用联结词集。

（2）基本复合命题复合命题：基本复合命题以及多次使用联结词集S中的联结词复合而成的命题。

排斥或可以看成非基本复合命题的复合命题。

（3）命题合成及其赋值：命题常项与命题变项：命题常项是命题，命题变项是取值为0或1的变量，也用p、q、r等表示。

命题公式：由命题变项或常项以及联结词按一定规则形成的公式，也称合成公式或公式。

公式的赋值:给公式中变项指定真值，成真赋值、成假赋值、公式的真值表。

命题公式的类型：重言式（永真式）、矛盾式（永假式）、可满足式。

2.命题逻辑等值演算（1）等值式与基本等值式等值式：若A←→B为重言式，记为A<=>B，并称A<=>B为等值式。

（2）基本的等值式（教材P49-P50）等值演算：由已知的等值式推演出新的等值式的过程。

置换规则：若A<=>B,则Φ（A）<=>Φ(B)（3）联结词完备集真值函数：n元真值函数F：{0，1}n-→{0,1}.任何含n个命题变项的公式A,都与唯一的一个真值函数等值，若公式A与B与同一个真值函数等值，则A<=>B。

联结词完备集：{￢、∧、Ｖ、-→、←→}，{￢、∧、Ｖ}，{￢、∧}，{￢，-→}，{↓}，{↑}。

（4）真值表：主要用于验证两个公式是否相等。

3.范式（1）主要定义：文字，简单析取式，简单合取式，极小项，极大项，析取范式，公式的析取范式，合取范式，公式的合取范式，主析取范式，公式的主析取范式，主合取范式。

定理2.1：在真命题逻辑中，任何公式都存在着唯一的与之等值的主析取范式与合取范式（2）求公式A的主析取范式的方法与步骤：方法1等值演算法消去A中联结词-→、←→（若存在）；否定号￢内移（德摩根定律）或消去（双重否定律）；使用∧对Ｖ的分配律；将不是极小项的简单合取式等值地化成若干个极小项的析取式；表示，使用冥等律，最后排序。