离散数学(二）之谓词逻辑（内容来自冯伟森《离散数学》教材+课件）

谓词与量词

虽然由V、Λ等连接词与原子命题结合可以完成一些命题的逻辑推理，但仅靠命题逻辑仍无法完成所有命题的推理，例如著名的苏格拉底命题“人都是要死的，苏格拉底是人，所以苏格拉底是要死的”，若按命题逻辑翻译为（PΛQ)->R的命题公式，其实并不恰当，因为这三个子命题还有内在联系，用彼此独立的简单的命题标识符无法研究命题内部的成分、结构及其逻辑特征。因此扩充引入谓词演算。

谓词

例：
5是质数 x是质数 F(x)
张明来自重庆 x来自y H(x,y)

1.客体（个体）常元：“5” “张明” “重庆”

2.客体（个体）变元： x,y,…

3.谓词： 描述个体性质或个体间关系的模式，F，G，GREATER_THAN等是谓词标识符

4.谓词命名式： 简称谓词，其格式为：谓词标识符（个体1，个体2，……）,有几个个体变元就叫几元谓词，记为P(x1,x2,…)。命题是谓词的特殊情况。注意交换个体变元的顺序可能会引起谓词值的改变！

5.个体域(论域)： 谓词中个体变元的取值范围，不能是空集！！！！至少有一个个体的非空集合D。若不指明论域，或认为包含一切个体的论域，称为全论域；若用其他谓词指明个体变元的性质，如MAN(x)，称为特性谓词。注意谓词取值是和一定论域相联系的！

6.谓词与命题的关系： 谓词命名式中，若谓词是常元，个体变元代以个体域中的某一个体，就成为一个命题。
例如： F(x)表示“x是质数”，个体域：正整数。
F(5)： 5时质数。 真
F(4)： 4是质数。 假

量词

1.全称量词 ?： ?x 读作“一切x”，“所有的x”。
(?x)P(x) 表示“对一切x，都有性质P”， 称为全称量化命题。
(?x)P(x)取值为真的充分必要条件是对个体域D中每个个体a，P(a)都为真。

2.存在量词 ： ?x 读作“存在x”，“某个x”。
(?x)P(x) 表示“有一个x，有性质P”， 称为存在量化命题。
(?x)P(x)取值为真的充分必要条件是对个体域D中至少存在一个个体a，P(a)为真。

3.量化断言与命题的关系 ：
?对于有限可数个体域D={a₀, a₁,…a_n}，有:
(?x )A(x)<=>A(a₀)∧A(a₁)∧…∧A(a_n)
(?x)A(x)<=>A(a₀)∨A(a₁)∨…∨A(a_n)
? 对于无限可数个体域D={a0, a1, a2…}，有:
(?x )A(x)<=>A(a₀)∧A(a₁)∧A(a₂)…
(?x)A(x)<=>A(a₀)∨A(a₁)∨A(a₂)…

4.全总个体域下的量化命题 ：
①人总是要死的。 ②有些人不怕死。用逻辑形式表达。
(1) 若论域D为人类：
设D(x): x是要死的。 F(x): x是不怕死的。
①人总是要死的 ?xD(x)
②有些人不怕死 ?xF(x)
(2) 若论域D为全总个体域：
设D(x): x是要死的。 F(x): x是不怕死的。 M(x)： x是人（特性谓词）。
① 人总是要死的。
语句为“对每一个x，如果x是人，那么x是要死的。”
② 有些人不怕死。
语句为“有一个x， x是人并且x不怕死。”
(?x)[M (x) → D(x)]
(?x)[M (x) ∧ F(x)]

5.量词的顺序说明 ：
? 如有多个量词，则读的顺序按从左到右的顺序，即：(?x)(?y)G(x,y)＝ (?x)((?y)(G(x,y))
? 量词对变元的约束，往往与量词的次序有关，不同的量词次序，可以产生不同的真值，此时对多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原体的含义。

谓词公式及其赋值

谓词公式

1. 基本符号
? 个体常量：一般用a,b,c,… ； a1,b1,c1,… 来表示， 它可以是D中的某个元素;
? 个体变量：一般用x,y,z,…, x1,y1,z1,… 来表示.它可以取值于D中的任意元素；
? 函数标识符（符号）：一般用f,g,h,…, f1,g1,h1,… 来表示。 n元函数符号f(x1,x2,…xn)可以是Dn→D的任意一个函数；
? 谓词标识符（符号）：一般用P,Q,R,…, P1,Q1,R1,…来表示。 n元谓词符号P(x1,x2,…xn)可以是Dn→{0,1}的任意一个谓词。

2.基本定义
定义（ 项）：在一阶谓词逻辑中， 项被递归地定义为：
① 任意的常量符号是项；
② 任意的个体变元符号是项；
③ 若f(x₁,x₂,x₃,…,x_n)是n元函数符号， t₁,t₂,t₃,…,t_n是项，则f(t₁,t₂,t₃,…,t_n)是项；
④ 只有有限次使用①~③规则生成的符号串才是项。
例如：复合函数f(g(f(a),g(a,x)))是一个项。
定义（ 原子公式）： 设P是n元谓词标识符， t₁,t₂,t₃,…,t_n是项,则P(t₁,t₂,t₃,…,t_n)是原子谓词公式，简称原子公式。
定义（谓词公式）： 满足下列条件的表达式，称为谓词合适公式,简称公式。
① 原子公式是谓词合适公式。
② 若A, B是合适公式，则 (?A), (?B), (A∧B), (A∨B),(A→B), (A?B)是谓词合适公式。
③ 若A是谓词公式， x是个体变元，则(?x)[A(x)]、(?x)[B(x)]是谓词合适公式。
④ 只有有限次应用①~③生成的符号串才是谓词合适公式（或简称“公式”）。

3. 量词辖域（作用域）
在表达式?xA(x)或?xA(x)中，变元x称为指导变元，A(x)称为相应量词的辖域。
例如：
(?x)[P(x) → Q(x)]
(?x)P(x) → Q(x)
辖域即为紧接于量词之后最小的子公式。
如果辖域不是原子公式，其两侧必须用括号将其界定。

4. 约束变元和自由变元
在量词(?x) 或 (?x)的辖域内，变元x的一切出现叫约束出现，称这样的变元为约束变元。
变元的非约束出现叫变元的自由出现，称这样的变元为自由变元。
例如： ① ???(?) → ?(?)
?(?)中的?是约束出现， ?(?)中的?是自由出现。
② ??(?(?, ?) → ?(?, ?))??(?, ?)
x是约束出现， y、 z是自由出现。

①式中，变元x约束和自由两个“身份”同时出现,容易引起概念上的混乱,故可对约束变元换名,对自由变元代入,使得一个变元在一个公式中只以一种形式出现。这就需要下面两个公式：
规则1： 约束变元的换名规则
使用在辖域中未出现过的变元标识符替换原来的指导变元和在辖域中的所有同名变元。
规则2： 自由变元的代入规则
使用在公式中未出现过的变元标识符替换原来所有同名自由变元。

公式的解释

一个定义在论域D上的公式A的每一个解释(赋值、 指派) I由如下三部分组成：
(1) A中的每个常量符号,指定D中的一个元素；
(2) A中的每个n元函数符号,指定Dn到D的一个具体的函数；
(3) A中的每个n元谓词符号,指定Dn到{0,1}的一个具体的谓词。
例：
公式A=?(x)P(x,f(x)) ∧ G(a)
给定赋值I：论域D={1,2}；
P(x,y)： x=y； G(x)： x=1；
f(1)=2, f(2)=1; a=1。
求公式的真值？
解：
? = ?(1, ?(1)) ∧ ?(2, ?(2)) ∧ ?(?)
= ?(1,2) ∧ ?(2,1) ∧ ?(1)
= 0 ∧ 0 ∧ 1
= 0

谓词公式的类型

设A是以D为论域的谓词公式，
（1） 如果在关于D的任一解释下， A的值都是真时，称A是D上的永真式（重言式）；
（2） 如果关于D的任一解释下， A的值都是假时，称A是D上的永假式(矛盾式，不可满足公式)；
（3) 如果在关于D的某一解释下， A取值为真，称A是D上可满足公式。

谓词公式的等价与范式

谓词公式的等价

定义： 设A和B是论域D上的谓词公式，如果任一解释下， A和B都取相同的真值，则称A和B在论域D上等价，记为?<=D>?, 简记为? ? ?。
设A和B是论域D上的谓词公式，则 A ? B 当且仅当 A?B是D上的永真式。

谓词演算的基本等价式

1.命题演算的基本等价式也是谓词演算的基本等价式。
例如：
P→Q ?～P?Q ; A(x)→B(x)?～A(x)?B(x)

2. 量词的否定
① ～（?x） P(x) ?（?x） [～ P(x)]
② ～（?x） P(x) ?（?x） [～ P(x)]
可以推广到多个量词

3.量词辖域的收缩与扩张
设Q是不含指导变元的谓词公式（包括命题）
①（?x） [P(x)∨Q] ?（?x） P(x)∨Q
②（?x） [P(x)∧Q] ?（?x） P(x)∧Q
③ （?x） [P(x)∨Q] ?（?x） P(x)∨Q
④ （?x） [P(x)∧Q] ?（?x） P(x)∧Q
⑤==（?x） P(x)→Q ?（?x） [P(x)→Q]==
⑥==（?x） P(x)→Q ?（?x） [P(x)→Q]==
⑦ Q→（?x） P(x) ?（?x） [Q→P(x)]
⑧ Q→（?x） P(x) ?（?x） [Q→P(x)]

4.量词的分配形式
①(?x)(P(x)∧ Q(x))?(?x)P(x)∧(?x)Q(x)
②(?x)(P(x)∨ Q(x))?(?x)P(x)∨(?x)Q(x)

5.其他等价式
(?x)(?ｙ)(P(x)∨ Q(ｙ))?(?x)P(x)∨(?x)Q(x)
(?x)(?ｙ)(P(x)∧ Q(ｙ))?(?x)P(x)∧(?x)Q(x)
(?x)(P(x)→Q(x))?(?x)P(x)→(?x)Q(x)

6.两个量词的等价式
(?x)(?y)A(x,ｙ)?(?y)(?x)A(x,ｙ)
(?x)(?y)A(x,ｙ)?(?y)(?x)A(x,ｙ)

谓词公式的范式

1. 前束范式
定义：设谓词公式 A=(Q₁x₁)(Q₂x₂)…(Q_nx_n)G，其中Q_ix_i或是?x_i或是?x_i (1≤i≤n)， G是不含有量词的公式，则称A是前束范式，称G是A的母式。
例如：(?x)(?y)P(x,y,z)∨Q(x)?(?x)(?y)[P(x,y,z)∨Q(t)]
?(所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之末)
定义: 如果在前束范式(Q₁x₁)(Q₂x₂)…(Q_nx_n)G中，母式G是合取(析取)范式时，称这个前束范式为前束合取(析取)范式。

2.斯柯林(Skolem)范式----不含存在量词的前束合取范式
定义: 设谓词公式A的等价前束合取范式是(Q₁x₁)(Q₂x₂)…(Q_nx_n)G,
1)从左到右扫描量词， 设Q_i是第一个遇到的存在量词,
① 如i=1,则选择一个在G中未使用过的常量标识符代替G中的全部x₁,然后删去(Q₁x₁);
② 如果i>1,则Q_１ ,Q₂,…Q_i-1都是全称量词,这时选择一个在G中未使用过的函数标识符(如g)， 并用g(x₁,x₂,…,x_i-1)去代替G中的全部x_i,然后删去(Q_ix_i);
2） 重复这一过程,直到公式中不含存在量词为止。
这样得到的公式称为Skolem范式,而取代存在量词时使用的常量标识符或函数,称为Skolem函数。
定理： 设谓词公式A的Skolem范式为S,则A为矛盾式当且仅当S为矛盾式。
注意： 只有当A是矛盾式时， S才与它同为矛盾式。 一般情况下， A与S并不一定等价。

谓词公式的蕴涵

1.定义

设A和B是以D为论域的谓词公式，如果在任一解释下，当公式A取值真时，公式B也取值真，则称A(永真)蕴涵B，记为A?B。A?B当且仅当A→B是永真式。
2.谓词蕴含式

（1）对已有的命题基本蕴涵式，利用永真式代入规则，形成谓词基本蕴涵式。
例如：
? ∧ (? → ?) ? ?
?(?) ∧ (?(?) → ?(?)) ? ?(?)
（2）全称指定规则（Universal Specification） US规则

（3）存在指定规则（ Existential Specification） ES规则

（4）全称推广规则（ Universal Generalization） UG规则

（5）存在推广规则（ Existential Generalization） EG规则

（6）设P(x)和Q(x)是论域D上的谓词公式，下述蕴涵式成立。

谓词逻辑的推理方法

推理规则

(1) P规则：前提引用规则。
(2) T规则：中间结果引用规则。TE为等价变换式，TI为蕴涵变换式。
(3) CP规则：如果要推导形如A?B→C的公式，则把B作为附加前提，与A一起推导出C。
(4)量词的四条重要的推理规则：US(全称指定规则)、ES（存在指定规则）、UG（全称推广规则）、EG（存在推广规则）。

推理方法

(1) 直接证明法。
(2) CP规则推理法。
(3) 反证法。

消解法（建立在Skolem范式基础上）

(1)为了证明
G₁,G₂,…,G_n?H
根据反证法，即需证明
A={G1,G2,…,Gn,～H} ? R∧ ～R
(2)建立子句集
①先将A化成等值的前束合取范式；
②将前束范式化成Skolem范式(消去存在量词),得到仅含全称量词的公式A*,从而对A的不可满足性(即矛盾式） ,可由A的不可满足性得到。
③将A的全称量词省略。
④A*的母式(已合取化)的合取词‘∧’以‘，’表示,得A的子句集S。
(3) 对S作归结(消解)
例如 C₁=P(x) ∨ Q(x) C₂=～ P(a)∨ R(y)
P(x)与～ P(a)合一置换{a/x},即将变元x换成a,便为互补对,可作归结：R(C₁,C₂)=Q(a) ∨ R(y)
对子句集S的任意两个子句作归结(如果可作归结)并将归结式仍放入S,重复这一过程。
(4)直到归结出空子句F,证明结束