本文共 2368 字，大约阅读时间需要 7 分钟。
离散数学
数理逻辑
命题逻辑
基本概念
命题：具有确切真值的陈述句称为命题。 真值：一个命题总有一个值，一般来讲，命题是正确的则真值为真，命题为错误的真值为假。 原子（简单）命题：不能再分解为更简单命题的命题。 复合命题：可以分解的命题。 命题变量：一个表示确定命题的命题标识符。 命题变元：表示任一命题的命题标识符。（命题变元不是命题） 指派/解释：当命题变元P用一个特定的命题取代时，P才能确定真值，称为对P进行指派。若公式G在解释I下是真，则称I满足G，I是G的成真赋值。反之称I弄假于G。 命题公式：由命题变量、命题变元、联结词和括号等组成的复合命题形式，这些符号不能任意组合，必须按下列定义： - 命题变元本身是一个公式。
- 若P是公式，┐P也是公式。
- 若PQ是公式，则P∧Q、P∨Q、P→Q、P↔Q也是公式。
- 仅由有限步骤使用规则1-3后产生的结果。
真值表：公式G在其所有可能的解释下所取真值的表。 等价公式：给定两个命题公式A和B，P1，P2，…Pn为所有于出现、并A和B中的原子变元，若给所有命题变元任一组真值指派，A和B的真值相同，则称A和B是等价的或者逻辑相等。充分必要条件是，G↔H。 基本等价公式。 子公式：如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。 等价置换：设X是合式公式A的子公式，若X↔Y，如果将A中的X用Y来置换，所得公式B和公式A等价。 合取范式：一个命题公式称为合取范式，当且仅当它具有形式：A1∧A2∧⋯∧An (n≥1)。 析取范式：一个命题公式称为析取范式，当且仅当它具有形式：A1∨A2∨⋯An (n≥1)。 命题公式的析取范式可以指出公式何时为真，而合取范式可以指出公式何时为假，从而代替真值表。 小项：n个命题变元的合取式，称为布尔合取或小项，但是每个变元和和他的否定不能同时存在，但两者必须出现且仅出现一次。 - 每个小项当其真值指派与编码相同时，其真值为T，其余情况都是F。
- 两个不同小项的合取永假。
- 全体小项的析取式永真。
- 主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价公式称作原式的主析取范式。在真值表中，是真值为1的指派所对应小项的析取。
- 大项：n个命题变元的析取式，称作布尔析取或大项，其中每个变元和他的否定不能同时存在，但两者必须出现且仅出现一次。
- 每个大项当其真值指派与编码相同时，其真值是F，其余均为T。
- 任何两个不同大项的析取式永真。
- 全体大项的合取式永假。
- 主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取组成，则该等价式称为原式的主合取范式。在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。
- 命题公式永真但且仅当它的主析取范式包含所有的小项，主合取范式为空。永假公式反之。
- 两个命题公式相等当且仅当它们的主析取范式、主合取范式相等。
- 永真公式（重言式）：所有解释之下都是真。
- 永假公式（矛盾式）：在所有的解释之下都是假。
联结词
以下是常见联结词及其true值结果：
| 联结词 | 记号 | 表达式 | 真值结果 |
| 否定 | �4718 | �4718P | P为假时为真，P为真时为假 |
| 合取 | ∧ | P∧Q | P与Q都为真时为真，否则为假 |
| 析取 | ∨ | P∨Q | P或Q中至少一个为真时为真，否则为假 |
| 条件 向 | → | P→Q | 当且仅当P为真且Q为假时为假，其他情况为真 |
| 双条件 | ↔ | P↔Q | 当P与Q真值相同时为真，将其他情况为假 |
联结词的优先级从高到低依次为：非、合取、析取、条件、双条件。
命题符号化
- 确定给定句子是否为命题。
- 列出原子命题。
- 句子中连词是否为命题联结词。
- 根据命题含义，正确表示原子和适当选择命题联结词。
基本等价公式
基本等价公式主要包括：
- logically equivalent expressions based on De Morgan's laws, distributing, and combining.
判断命题公式逻辑等价的方法
- 真值表
- 基本等价公式
- 等值置换
- 等值关系的传递性
求合取范式和析取范式的方法
- 简化联结词：将公式中的联结词化归成合取，析取以及非。
- 否定深入：利用德摩根律将“非”直接移到各个命题变元之前。
- 归约：利用分配律、结合律归约成合取范式或析取范式。
求出主析取范式的方法
- 真值表
- 基本等价公式
- 化归为析取范式
- 除去析取范式中所有永假的析取项
- 将析取式中重复出现的析取项和相同的变元合并
- 对析取项补入没有出现的命题变元，添加（P析取非P），然后，用分配律展开。
求主合取范式的方法
- 真值表
- 基本等价公式
- 划归为合取范式
- 除去合取范式中永真的合取项
- 合并相同的合取项和相同的变元
- 对合取项补入没有出现的命题变元，即添加（P合取非P）式，然后，分配律展开。
主范式间的转换
通过德摩根定律、分配律可以将一个主范式转换另一主范式。
证明永真（假）的方法
- 真值表
- 证明和T（F）等价
证明蕴含的方法
- 指定前件真值为T，若由此推出Q的真值也是T，得证。
- 指定后件Q的真值是F，若由此推出P的真值也是F，得证。
常用的蕴含式
常见的蕴含式包括：
- P→(Q∨¬P)
- (P∨¬P)→Q
推理的方法
- 真值表法
- 在所有行中，只要有一行的前提是真，结论是真，则得证。
- 在所有行中，只要有一行的结论是假，且前提也是假，则得证。
- 直接证法
- 推理规则：
- 规则P（前提引入规则）：前提在推到过程中随时引入。
- 规则T（逻辑结果引入规则）：在推导过程中，如果有一个、多个公式蕴含着公式S，则公式S可以引入推导之中。
- 规则CP（附加前提规则）：如果能从给定的前提集合T和公式P推导出S，则能从此T推导出P→S（使用场景是结论公式是蕴含式或者析取式）。
- 间接证法
转载地址：http://ddwqz.baihongyu.com/