离散数学笔记（3）——谓词逻辑

wzf2000
2019年9月26日

离散数学笔记（3）——谓词逻辑

基本概念

个体与个体变元

能够独立存在的事物，称之为个体，也称之为客体。它可以是具体的，也可以是抽象的。

通常用小写英文字母 $a,b,c,\cdots$ 表示。

用小写英文字母 $x,y,z\cdots$ 表示任何个体，则称这些字母为个体变元。

谓词

用以刻画个体的性质或者个体之间关系的即是谓词。

用一个大写英文字母后边有括号，括号内是若干个客体变元表示谓词，如果括号内有 $n$ 个客体变元，称该谓词为 $n$ 元谓词。

一般地：$P(x_1,x_2,\cdots,x_n)$ 是 $n$ 元谓词。

谓词性质

1. 它包含一个或多个个体变元，并且
2. 它不是一个命题，但是
3. 一旦在特定的允许选择范围内，将其中所有个体变元都进行替换，那么它就成为一个命题。

命题函数

谓词相当于一个函数，称之为命题函数。

简单命题函数定义：$n$ 元谓词 $P(x_1,x_2,\cdots,x_n)$ 称之为简单命题函数。

规定：当命题函数 $P(x_1,x_2,\cdots,x_n)$ 中 $n=0$ 时，即 $0$ 元谓词，表示不含有客体变元的谓词，它本身就是一个命题变元。

复合命题函数定义：将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。

简单命题函数与复合命题函数统称为命题函数。

论域

定义：在命题函数中命题变元的取值范围，称之为论域，也称之为个体域。

定义：由所有论域构成的论域，称之为全总个体域。

约定：对于一个命题函数，如果没有给定个体域，则假定该个体域是全总个体域。

个体函数

例：张华的父亲是教师。

设 $P(x)$：表示 $x$ 是教师。

$a$ ：表示张华的父亲。

设 $f(x)$:表示 $x$ 的父亲。

$a$：表示张华。

则原命题符号化为：$P(f(a))$

$f(x)$ 称为个体函数（或函词）。

个体函数与谓词的区别

个体函数是论域到论域的映射，$g:\mathbb{N} \rightarrow \mathbb{N}$，如果指定的个体 $a \in \mathbb{N}$，则 $g(a)\in \mathbb{N}$。

谓词是从个体域到 $\{T,F\}$ 的映射，即谓词 $E(x)$ 可以看成映射 $E:\mathbb{N} \rightarrow \{T,F\}$，如果指定个体 $a \in \mathbb{N}$，则 $E(a)$ 的真值 $\in \{T,F\}$。

量词

定义：在命题中表示对个体数量化的词，称之为量词。

存在量词：记作 $\exists$，表示“有些”、 “有一个”、“某些”、“至少一个“等。

$\exists x F(x)$：表示存在着个体域中的个体具有性质 $F$。

全称量词：记作 $\forall$，表示“每个”、 “任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。

$\forall x F(x)$：表示个体域里所有的个体都有性质 $F$。

谓词公式及命题符号化

原子谓词公式

定义：称 $n$ 元谓词 $P(x_1,x_2,\cdots,x_n)$ 为原子谓词公式。

谓词合式公式

递归定义如下：

1. 原子谓词公式是合式公式。
2. 如果 $A$ 是合式公式，则 $\lnot A$ 也是合式公式。
3. 如果 $A$、$B$ 是合式公式，则 $(A \land B)$、$(A \lor B)$、 $(A \rightarrow B)$、$(A \leftrightarrow B)$ 都是合式公式。
4. 如果 $A$ 是合式公式，$x$ 是 $Ａ$ 中的任何个体变元， 则 $\exists x Ａ$和 $\forall x Ａ$ 也是合式公式。
5. 只有有限次地按规则 1 至 4 求得的公式才是合式公式。

谓词合式公式也叫谓词公式，简称公式。

为了方便，最外层括号可以省略，但是若量词后边有括号，则此括号不能省。

量词的作用域

定义：在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。

自由变元与约束变元

定义：如果个体变元 $x$ 在 $\exists x$ 或者 $\forall x$ 的作用域内，则称 $x$ 在此作用域内约束出现，并称 $x$ 在此作用域内是约束变元。否则 $x$ 是自由出现，并称 $x$ 是自由变元。

对约束变元和自由变元有如下几点说明：

1. 对约束变元用什么符号表示无关紧要。
2. 一个谓词公式如果无自由变元，它就表示一个命题。

约束变元的改名规则：

1. 对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的作用域内此个体变元出现的各处同时换名。
2. 改名后用的个体变元名称，不能与该量词的作用域内的其它变元名称相同。

对自由变元的代入规则：

1. 对谓词公式中的自由变元可以作代入。代入时需要对公式中出现该变元的每一处，同时作代入。
2. 代入后的变元名称要与公式中的其它变元名称不同。

命题符号化

在谓词演算中，命题的符号表达式与论域有关系。

表明 $x$ 的特性的谓词，如 $\mathbb{N}(x)$，称为特性谓词。

唯一性表示示例

有限论域下公式 $\exists xP(x)$、$\forall xP(x)$ 的表示法

设论域为 $\{a_1,a_2,\cdots,a_n\}$，则有：

1. $\exists xP(x) = P(a_1) \lor P(a_2) \lor \cdots \lor P(a_n)$
2. $\forall xP(x) = P(a_1) \land P(a_2) \land \cdots \land P(a_n)$

$$
\Large \forall x \forall y F(x,y) = \forall y \forall x F(x,y) \\
\Large \exists x \exists y F(x,y) = \exists y \exists x F(x,y) \\
\Large \exists x \forall y F(x,y) \not = \forall y \exists x F(x,y)
$$

对谓词公式赋值

对谓词公式 $G$ 的赋值 $I$ 包括以下几点：

1. 指定一个个体域 $D$；
2. 对公式中出现的每个函词，指定 $D$ 上的个体函数；
3. 对公式中出现的每个谓词，指定 $D$ 上的谓词；
4. 对公式中出现的每个个体常量和自由变元，指定 $D$ 中的一个个体；
5. 对公式中出现的每个命题变元，指定一个真值（$T$ 或 $F$）。

这样可以得到一个命题 $G_1$，称 $G_1$ 的真值为 $G$ 在 $I$ 下的真值。

谓词公式的分类

定义：设 $G$ 为一个公式，如果 $G$ 在任何赋值下都是真的，则称 $G$ 为普遍有效式（或永真式）；如果 $G$ 在任何赋值下都是假的，则称 $G$ 为不可满足式（矛盾式）；若至少存在一个赋值使 $G$ 为真，则称 $G$ 是可满足式。

普遍有效式（永真式）

$\forall x F(x) \rightarrow \exists x F(x)$

$\forall x F(x) \rightarrow (\forall x \exists y G(x,y) \rightarrow \forall x F(x))$

$\forall x F(x) \rightarrow (\forall x F(x) \lor \exists y G(y))$

可满足式

$\forall x P(x)$

$\exists x P(x)$

$\forall x \exists y F(x,y) \rightarrow \exists x \forall y F(x,y)$

谓词公式的等价公式

定义：给定谓词公式 $A$、$B$，若对 $A$ 和 $B$ 的任一组变元进行赋值，所得命题的真值相同（即 $A \leftrightarrow B$ 为永真式），则称 $A$ 与 $B$ 等价，记作 $A = B$。

谓词公式的永真蕴含式

定义：给定谓词公式 $A$、$B$，如果 $A \rightarrow B$ 为永真式，则称 $A$ 永真蕴含 $B$，记作 $A \Rightarrow B$。

重要的谓词等价公式和永真蕴含式

1. 由命题公式推广出的公式
   1. $A(x) \Rightarrow A(x) \lor B(x)$
   2. $\exists (A(x) \rightarrow B(x)) = \exists (\lnot A(x) \lor B(x))$
   3. $\lnot (\exists x A(x) \land \exists x B(x)) = \lnot \exists x A(x) \lor \lnot \exists x B(x)$
2. 量词转换公式
   1. $\lnot \forall x A(x) = \exists x \lnot A(x)$
   2. $\lnot \exists x A(x) = \forall x \lnot A(x)$

3. 量词作用域的扩张公式
   1. $\forall x A(x) \lor B = \forall (A(x) \lor B)$
   2. $\forall x A(x) \land B = \forall x (A(x) \land B)$
   3. $\exists x A(x) \lor B = \exists x (A(x) \lor B)$
   4. $\exists x A(x) \land B = \exists x (A(x) \land B)$
   5. $B \rightarrow \forall x A(x) = \forall x (B \rightarrow A(x))$
   6. $B \rightarrow \exists x A(x) = \exists x (B \rightarrow A(x))$
   7. $\forall x A(x) \rightarrow B = \exists x (A(x) \rightarrow B)$
   8. $\exists x A(x) \rightarrow B = \forall x (A(x) \rightarrow B)$

   以上公式中，$A(x)$ 是含 $x$ 自由出现的任意公式，而 $B$ 中不含 $x$ 的自由出现。

   

   

4. 量词分配公式

   1. $\exists x (A(x) \lor B(x)) = \exists x A(x) \lor \exists x B(x)$
   2. $\forall x (A(x) \land B(x)) = \forall x A(x) \land \forall x B(x)$

   

5. 带有量词的蕴含式

   1. $\exists x (A(x) \land B(x)) \Rightarrow \exists x A(x) \land \exists x B(x)$
   2. $\forall x A(x) \lor \forall x B(x) \Rightarrow \forall x (A(x) \lor B(x))$

   

   3. $\forall x (A(x) \rightarrow B(x)) \Rightarrow \forall x A(x) \rightarrow \forall x B(x)$

   

6. 两个量词的公式

   1. $\forall x \forall y F(x,y) = \forall y \forall x F(x,y)$
   2. $\exists x \exists y F(x,y) = \exists y \exists x F(x,y)$
   3. $\exists x \forall y F(x,y) \Rightarrow \forall y \exists x F(x,y)$

范式

前束范式

如果一个谓词公式符合下面条件，它就是前束范式：

1. 所有量词前面都没有联接词；
2. 所有量词都在公式的左面；
3. 所有量词的辖域都延伸到公式的末尾。

结论：任意一个谓词公式均和一个前束范式等价。

前束范式的写法

1. 消去公式中的联接词 $\rightarrow $ 和 $\leftrightarrow$(为了便于量词辖域的扩充)；
2. 如果量词前有 $\lnot$，则用量词否定公式将 $\lnot$ 后移；再用摩根定律或求公式的否定公式，将 $\lnot$ 后移到原子谓词公式之前；
3. 用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备)；
4. 用量词辖域扩充公式提取量词，使之成为前束范式形式。

注意：前束范式不唯一

前束析取范式与前束合取范式

前束析取范式：前束范式中量词后的括号内是析取范式形式。
前束合取范式：前束范式中量词后的括号内是合取范式形式。

 离散数学 笔记