离散数学笔记——01数理逻辑

Share

参考教材：屈婉玲, 耿素云, 张立昂. 离散数学[M]. 第二版. 北京: 高等教育出版社, 2015:3-87.

1 命题逻辑的基本概念

1.1 命题与联结词

数理逻辑是研究推理的数学分支。推理由一系列的陈述句组成。

非真即假的陈述句称作命题。

作为命题的陈述句所表达的判断结果称作命题的真值，真值只取两个值：真或假。

真值为真的命题称作真命题，真值为假的命题称作假命题。

任何命题的真值都是唯一的。

不能被分解成更简单的命题称作简单命题或原子命题。

由简单命题通过联结词联结而成的命题称作复合命题。

判断给定句子是否为命题的步骤：

  1. 判断是否为陈述句
  2. 判断是否有唯一的真值

由真能退费出假、又由假能推出真，从而既不能为真，也不能为假的陈述句称作悖论。悖论不是命题。

用小写字母表示命题称为命题的符号化。

$p$ : $4$ 是素数

完全由符号构成的语言称为形式语言。

联结词：“非”、“并且”、“或”、“如果……，则……”

  1. 设 $p$ 为命题，复合命题“非 $p$”（或 “$p$ 的否定”）称作 $p$ 的否定式，记作 $\neg p$ 。符号 $\neg$ 称作否定联结词。规定 $\neg p$ 为真当且仅当 $p$ 为假。
  2. 设 $p$, $q$ 为两个命题，复合命题“ $p$ 并且 $q$ ”（或 “ $p$ 与 $q$ ”）称为 $p$ 与 $q$ 的合取式，记作 $p\land q$ 。 $\land$ 称为合取联结词。规定 $p\land q$ 为真当且仅当 $p$ 与 $q$ 同时为真。
  3. 设 $p$, $q$ 为两个命题，复合命题“ $p$ 或 $q$ ”称为 $p$ 与 $q$ 的析取式，记作 $p\lor q$ 。 $\lor$ 称为析取联结词。规定 $p\lor q$ 为假当且仅当 $p$ 与 $q$ 同时为假。
  4. 自然语言的“或”具有二义性，用它有时具有相容性（即它联结的两个词可以同时为真），有时具有排斥性（即只有当一个为真、另一个为假时，才为真），对应的分别称作相容或和排斥或
  5. 设 $p$, $q$ 为两个命题，复合命题“如果 $p$ ，则 $q$ ”称为 $p$ 与 $q$ 的蕴涵式，记作 $p\to q$ ，并称 $p$ 是蕴含式的前件， $q$ 为蕴含式的后件。 $\to$ 称为蕴涵联结词。规定 $p\to q$ 为假当且仅当 $p$ 为真 $q$ 为假。 $p\to q$ 的逻辑关系为 $q$ 是 $p$ 的必要条件。
  6. 设 $p$, $q$ 为两个命题，复合命题“ $p$ 当且仅当 $q$ ”称作 $p$ 与 $q$ 的等价式，记作 $p\leftrightarrow q$ ， $\leftrightarrow$ 称为等价联结词。规定 $p\leftrightarrow q$ 为真当且仅当 $p$ 与 $q$ 同时为真或同时为假。 $p\to q$ 的逻辑关系为 $p$ 与 $q$ 互为充分必要条件。

命题公式及赋值

简单命题是命题逻辑中最基本的研究单位，其真值是确定的，又称作命题常项或命题常元。

命题常项相当于初等数学中的常数。初等数学中还有变量，对应地，这里有命题变项。取值真或假的变元称作命题变项或命题变元。可以用命题变项表示真值可以变化的陈述句。

命题变项不是命题，命题变项与命题常项的关系如同初等数学中变量与常量的关系，今后也用小写字母表示命题变项。这样一来，小写字母既可以表示命题常项，也可以表示命题变项，通常可以由上下文确定。

将命题变项用联结词和圆括号按照一定的逻辑关系联结起来的符号串称作合式公式。当使用联结词集 $\{\neg, \land, \lor, \to, \leftrightarrow\}$ 时，合式公式定义如下

  1. 单个命题变项和命题常项是合式公式，并称为原子命题公式
  2. 若 $A$ 是合式公式，则 $\neg A$ 是合式公式
  3. 若 $A, B$ 是合式公式，则 $A\land B, A\lor B, A\to B, A\leftrightarrow B$ 是合式公式
  4. 有限次地应用 1~3 形成的符号串是合式公式

合式公式也称作命题公式或命题形式，简称公式。

设 $A$ 为合式公式， $B$ 为 $A$ 中一部分，若 $B$ 也是合式公式，则称 $B$ 为 $A$ 的子公式。

对于这个定义，要做以下说明：

  1. 定义给出的合式公式的定义方式称作归纳定义或递归定义方式，下文中还将多次出现这种定义方式
  2. 定义中引进了 $A,B$ 等符号，用它们表示任意的合式公式，称作元语言符号。而某个具体的公式，如 $p,p\land q,(p\land q)\to r$ 等称作对象语言符号。所谓对象语言是指用来描述研究对象的语言，而元语言是指用来描述对象语言的语言，这两种语言是不同层次的语言。

在命题公式中，由于有命题变项的出现，因而真值是不确定的。用命题常项替换公式中的命题变项称作解释。在将公式中出现的全部命题变项都解释成具体的命题常项后，公式就成了真值确定的命题。

设 $p_1,p_2,\cdots,p_n$ 是出现在公式 $A$ 中的全部命题变项，给 $p_1, p_2, \cdots, p_n$ 各指定一个真值，称为对 $A$ 的一个赋值或解释。若指定的一组值使 $A$ 为 $1$ ，则称这组值为 $A$ 的成真赋值。若使 $A$ 为 $0$ ，则称这组值为 $A$ 的成假赋值。

对含 $n$ 个命题变项的公式 $A$ 的赋值采用下述记法

  1. 若 $A$ 中出现的命题变项为 $p_1, p_2, \cdots, p_n$ ， $A$ 的赋值 $\alpha_1,\alpha_2,\cdots,\alpha_n$ 是指 $p_1=\alpha_1,p_2=\alpha_2,\cdots,p_n=\alpha_n$

不难看出，含 $n(n\ge1)$ 个命题变项的公式共有 $2^n$ 个不同的赋值。

将命题公式 $A$ 在所有赋值下取值情况列成表，称作 $A$ 的真值表。

构造真值表的具体步骤如下：

  1. 找出公式中所含的全体命题变项 $p_1,p_2,\cdots,p_n$ ，列出 $2^n$ 个赋值。赋值从 $00\cdots0$开始，然后按照二进制加法每次加 $1$ ，依次写出每个赋值，直到 $11\cdots1$ 为止。
  2. 按照从低到高的顺序写出公式的各个层次
  3. 对应各个赋值计算出各层次的真值，直到最后计算出公式的真值

如果两个公式 $A$ 与 $B$ 的真值表对所有赋值最后一列都相同，即最后结果都相同，则称两个真值表相同，而不考虑构造真值表的中间过程

设 $A$ 为任一命题公式

  1. 若 $A$ 在它的各种赋值下取值均为真，则称 $A$ 为重言式或永真式
  2. 若 $A$ 在它的各种赋值下取值均为假，则称 $A$ 为矛盾式或永假式
  3. 若 $A$ 不是矛盾式，则称 $A$ 为可满足式

2 命题逻辑等值演算

2.1 等值式

设 $A,B$ 是两个命题公式，若 $A,B$ 构成的等价式 $A\leftrightarrow B$ 为重言式，则称 $A$ 与 $B$ 是等值的，记作 $A\Leftrightarrow B$ 。

若 $A$ 与 $B$ 的真值表相同，则 $A\Leftrightarrow B$ ；否则， $A\nLeftrightarrow B$ 。

16 组常用的等值式模式：

  1. 双重否定律 $A\Leftrightarrow \neg\neg A$
  2. 幂等律 $A\Leftrightarrow A\lor A,A\Leftrightarrow A\land A$
  3. 交换律 $A\lor B\Leftrightarrow B\lor A, A\land B\Leftrightarrow B\land A$
  4. 结合律 $(A\lor B)\lor C\Leftrightarrow A\lor (B\lor C), (A\land B)\land C\Leftrightarrow A\land (B\land C)$
  5. 分配律 $A\lor(B\land C)\Leftrightarrow (A\lor B)\land (A\lor C), A\land(B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)$
  6. 德摩根律 $\neg(A\lor B)\Leftrightarrow \neg A\land\neg B, \neg(A\land B)\Leftrightarrow \neg A\lor\neg B$
  7. 吸收律 $A\lor (A\land B)\Leftrightarrow A, A\land(A\lor B)\Leftrightarrow A$
  8. 零律 $A\lor 1\Leftrightarrow1, A\land0\Leftrightarrow0$
  9. 同一律 $A\lor0\Leftrightarrow A,A\land1\Leftrightarrow A$
  10. 排中律 $A\lor\neg A\Leftrightarrow1$
  11. 矛盾律 $A\land\neg A\Leftrightarrow0$
  12. 蕴涵等值式 $A\to B\Leftrightarrow \neg A\lor B$
  13. 等价等值式 $A\leftrightarrow B\Leftrightarrow(A\to B)\land(B\to A)$
  14. 假言易位 $A\to B\Leftrightarrow\neg B\to\neg A$
  15. 等价否定等值式 $A\leftrightarrow B\Leftrightarrow\neg A\leftrightarrow\neg B$
  16. 归谬论 $(A\to B)\land(A\to\neg B)\Leftrightarrow\neg A$

每个等值式模式都可以给出无穷多个同类型的具体的等值式，这些具体的等值式称为等值式模式的代入实例。

由已知的等值式推演出另外一些等值式的过程称作等值演算。等值演算是布尔代数或逻辑代数的重要组成部分。

置换规则：设 $\varPhi(A)$ 是含公式 $A$ 的命题公式， $\varPhi(B)$ 是用公式 $B$ 置换 $\varPhi(A)$ 中 $A$ 的所有出现后得到的命题公式。若 $B\Leftrightarrow A$ ，则 $\varPhi(A)\Leftrightarrow\varPhi(B)$

2.2 析取范式与合取范式

命题变项及其否定统称作文字。仅由有限个文字构成的析取式称作简单析取式。仅有有限个文字的构成的合取式称为简单合取式。

一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。

一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。

由有限个简单合取式的析取构成的命题公式称作析取范式。

由有限个简单析取式的合取构成的命题公式称作合取范式。

一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。

一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

任一命题公式都存在与之等值的析取范式与合取范式。求给定公式范式的步骤为：

  1. 消去联结词 $\to, \leftrightarrow$
  2. 用双重否定律消去双重否定符，用德摩根律内移否定符。
  3. 使用分配律：求析取范式时使用 $\land$ 对 $\lor$ 的分配律，求合取范式时使用 $\lor$ 对 $\land$ 的分配律

在含有 $n$ 个命题变项的简单合取式（简单析取式） 中，若每个命题变项和它的否定式恰好出现一个且出现一次，而且命题变项或它的否定式按照下标从小到大按照字典顺序排列，则称这样的简单合取式（简单析取式）为极小项（极大项）。

极小项 $m_i$ 、极大项 $M_i$ ，则 $\neg m_i\Leftrightarrow M_i,m_i\Leftrightarrow\neg M_i$

所有简单合取式（简单析取式）都是极小项（极大项）的析取范式（合取范式）称为主析取范式（主合取范式）

任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。

2.3 联结词的完备集

称 $F:\{0,1\}^n\to\{0,1\}$ 为 $n$ 元真值函数。真值表最后一行为 $i$ 的记作 $F^{n}_i$

每个真值函数都与唯一的一个主析取范式（主合取范式）等值。

设 $S$ 是一个联结词集合，如果任何 $n(n\ge1)$ 元真值函数都可以由仅含 $S$ 中的联结词构成的公式表示，则称 $S$ 是联结词完备集

设 $p,q$ 是两个命题，复合命题“ $p$ 与 $q$ 的否定式” 称为 $p,q$ 的与非式，记作 $p\uparrow q$ 。即 $p\uparrow q\Leftrightarrow\neg(p\land q)$ 。符号 $\uparrow$ 称作与非联结词。

复合命题“ $p$ 或 $q$ 的否定式” 称为 $p,q$ 的或非式，记作 $p\downarrow q$ 。即 $p\downarrow q\Leftrightarrow\neg(p\lor q)$ 。符号 $\downarrow$ 称作或非联结词。

下面给出一些联结词完备集

  1. $\{\neg,\land,\lor\}$
  2. $\{\neg,\land,\lor,\to\}$
  3. $\{\neg,\land,\lor,\to,\leftrightarrow\}$
  4. $\{\neg,\land\}$
  5. $\{\neg,\lor\}$
  6. $\{\neg,\to\}$
  7. $\{\uparrow,\downarrow\}$
  8. $\{\uparrow\}$
  9. $\{\downarrow\}$

可满足性问题与消解法

任一公式都能化成等值的合取范式，因而一般的可满足性问题可以归结为合取范式的可满足性问题。

假设一个简单析取式中不同时出现某个命题变项和它的否定，否则它为永真式。