离散数学文档第二章.doc

第二章 一阶逻辑

由上一章我们知道，命题逻辑可以形式化地描述一些自然语言中的逻辑思维，也能够用形式化的方法进行一些逻辑推理。但命题逻辑以原子命题作为最小的研究单位，不对原子命题的内部结构做深入研究。然而，这无论是在数学中还是在计算机科学中，都是不够的。例如，下列推理是人所共知的：所有的人都会呼吸,他是人,所以他会呼吸.
但是，命题演算却无法反映上述推理，因为前提和结论都只能表示为原子命题，例如表示为p，q，r。在命题演算系统中,无法由前提p, q推出结论r, 结论r也根本不是前提p，q的逻辑结果。
这三个命题中涉及两个概念，它们表示事物的性质：“是人”，“会呼吸”，我们称之为谓词。它们还涉及两种主体：“所有的人”，“他”，我们称之为个体。前者表示一类个体的全部，这里使用了数量词“所有”，我们称之为量词。只有当这些细节都被清楚地表示出来，同时建立起它们之间逻辑关系的形式描述，那么刻划类似上述本章引例的推理才是可能的。谓词演算及其形式系统正是以此为目的而建立的。一阶逻辑研究的基本内容是：原子命题的个体词、谓词和量词，研究它们的形式结构和逻辑关系、正确的推理形式和规则。

2.1一阶逻辑的基本概念
2.1.1 个体词、谓词、量词
2.1.1.1个体词与谓词
定义2.1.1 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。
个体：原子命题中的主语部分；
个体常元：表示特定的个体，以a，b，c，…(或带下标)表示;
个体变元: 表示个体的变元，以x，y，z，…(或带下标)表示;
个体域：个体变元的取值范围；
谓词: 原子命题中的谓语(或表语)部分，常用大写字母P，Q，R，…(或带下标)表示;
定义2.1.2 一个原子命题的谓词形式为：
谓词符号(个体常元1，个体常元2，…)。
［例2.1.1］ 张明是位大学生。
设S(x)：x是大学生，c：张明，则原句的谓词形式为S(c)。
我坐在张三和李四中间。
设S(x,y,z)：x坐在y和z之间，i：我，z：张三，l：李四，则原句的谓词形式为S(i，z，l)。
谓词常项：表示特定的谓词，以F,G,H(或带下标)表示;
谓词变项: 表示不确定的谓词，以F,G,H(或带下标)表示;
2.1.1.2量词
在自然语言表示的命题中，经常要对某个个体域的整体进行描述，诸如“对于每一个”，“所有的”，“存在某一个”，“至少有一个”等。为了表示这些，引入了量词的概念。
定义2.1.3 (1) 全称量词符，表示“对所有的，每一个，一切，对任何一个”。全称量词的形式为x，x称为指导变元；
(2) 存在量词符，指代“ 存在一些，至少有一个，对于一些，某个”。存在量词形式为x，x为指导变元；
说明：
(1) 个体域对命题的真值有影响;
(2) 若非特别指明，个体变元的个体域总是U；
(5) 当个体域为U时，常需用一个特性谓词P(x)来限制个体变元x的取值范围。
2.1.2 举例
［例2.1.2］ 设D为实数域，E(x,y)表示D上关系“x = y”，L(x,y) 表示:x < y那么
（1）"x L(0,x2+1) 真。
（2）$xE(x2-2x-1,0) 真。
（3）$xE(x2+x+1,0) 假。
（4）$xE(x2,y)当y取非负实数时真，否则假。
［例2.1.3］ 设个体域是人类，试将下列语句符号化。
(1) 所有的人都呼吸;
(2)有的人用左手写字;
［例2.1.4］将下列语句用谓词公式形式化：
（1）没有不犯错误的人。
F(x)：“x犯错误”，M(x)：“x是人”，它符号化为
┐$x(M(x)∧┐F(x)) 或 "x(M(x)→F(x))
（2）凡是实数，或者大于零，或者等于零，或者小于零。
R (x)：“x是实数”，它符号化为
"x(R(x)→x<0∨x=0∨x>0)
［例2.1.5］ 试将下列命题进行谓词量化:
（1）有人勇敢，但不是所有的人都勇敢。
用B(x)表示“x勇敢”，它符号化为$xB(x) ∧┐"x B(x)
（2）人人都不相互依靠，但互相帮助。
用R(x,y)表示“x依靠y”，H(x,y)表示“x帮助y”，它符号化为
"x"y┐R(x,y) ∧"x"yH(x,y)

2.2一阶逻辑合式公式及其解释
2.2.1一阶逻辑合式
定义2.2.1 项可以按如下方式递归定义而成:
(1) 个体变元和常元都是项;
(2) 若f是n元函数，且t1，t2，…，tn是项，则f(t1，t2，…，tn)也是项;
(3) 只有有限次经过使用(1)和(2)所得到的才是项。
注:项起到一个个体的作用。
定义2.2.2 若R(x1，x2，…，xn)是n元谓词，t1，t2，…，tn都是项，则称R(t1，t2，…，tn)为原子公式。
定义2.2.3 合式公式可由如下方式递归定义：
(1) 原子公式是合式公式；
(2) 若A，B是公式，则(┐A)，(A∧B)，(A∨B)，(A→B)，(AB)都是合式公式；
(3) 若A为合式公式，x为A中的个体变元，则xA，xA，!xA都为合式公式；
(4) 仅由有限次(2)，(3)得到的才是合式公式。
定义2.2.4 在一个谓词公式A中，形如xB(x)、xB(x)的部分称为A的约束部分，B(x)为相应量词的辖域；在辖域中，x的所有出现称为x的约束出现，x称为约束变元。若x的出现不是约束出现，则称x为自由变元。
注(1) : 若量词后有括号，则括号内的子公式就是该量词的辖域;
(2) : 若量词后无括号，则与量词紧邻的子公式为该量词的辖域;
(3) : 自由变元可以用个体域中的特定个体替代，而约束变元则不能用个体域中的特定个体替代。
［例2.2.1］指出下是中的指导变元、量词的辖域、个体变项的自由出现和约束出现
　(1) x(P(x)→yQ(x，y))
(2) xH(x)→L(x，y)
　　 (3) xy(P(x，y)Q(y，z))xR(x，y)
定义２.２.５ 称一个无自由出现的个体变项的公式为闭式。
注: 闭式都是命题，一般说来，n元谓词没有确定的意义，将公式中的变项指定为常项后才是命题。
2.2.2 一阶逻辑公式的解释与分类
定义２.２.５一个一阶逻辑公式的解释由以下４部分组成
(1)非空个体域D;
(2) D中一部分特定元素；
(3) D上一部分特定函数；
(5) D上一部分特定谓词。
［例2.2.2］分别对个体域D1={3，4}，把P(x)解释为“x是质数”，a=3,讨论 P(a)$x P(x) 的真值。
P(a)$x P(x)
定义２.２.6若公式A在每一解释I下均真，那么称A为永真式。若公式A在每一解释I下均假，那么称A为矛盾式。若公式A存在成真解释，则称A为可满足式。
说明：对于一阶逻辑公式判断其类型至今没有一般的方法。
定义２.２.7设A0是含命题变项p1,p2,…,pn的命题公式，A1,A2,…,An是n个谓词公式，用Ai（1in）处处代替pi所得公式A叫公式A0的代换实例。
定理２.２.1永真式的代换实例都是永真式；矛盾式的代换实例都是矛盾式。
［例2.2.3］因为，所以
（1）
（2）
都是永真式。
对于可满足式通过举例子的方法说明。
［例2.2.4］是非矛盾式的可满足式。在自然数集中，及，两种解释一个使其为真一个使其为假。

2.3一阶逻辑等值式
2.3.1一阶逻辑等值式
定义2.3.1 设A，B是两个一阶逻辑公式，若AB是永真式，即在所有的解释下A和B的真值对应相同，则称A与B 是等值的，记作AB，并称AB为逻辑恒等式。
［例2.3.1］
说明：由于永真式的代换实例是永真式，因而，由第一章的命题逻辑等值式可派生出许多一阶逻辑等值式。
定理２.3.1（消去量词等值式）有限个体域中消去量词的两个等价式：若D={a，b，…，c}，则
(1)xA(x)óA(a)∧A(b)∧…∧A(c);
(2)xA(x)óA(a)∨A(b)∨…∨A(c);
定理２.3.2量词否定等值式
（1）
（2）
定理2.3.3量词辖域扩张与收缩等值式
当公式B中不含自由变元x时，
第一组
(1)"x A(x)∨B"x (A(x)∨B)
(2)"x A(x)∧B"x (A(x)∧B)
(3)$x A(x)∨B$x (A(x)∨B)
(4)$x A(x)∧B$x (A(x)∧B)
第二组
(5)"x(B→A(x)) B→"x A(x)
(6) "x(A(x) →B) $x A(x)→B
(7) $x(B→A(x)) B→$x A(x)
(8) $ x(A(x) →B) "x A(x)→B
定理2.3.4量词分配等值式
(1)"x (A(x)∧B(x)) "x A(x)∧"x B(x)
(2)$x (A(x)∨B(x)) $xA(x)∨$x B(x)
说明：
(1)"x A(x)∨"x B(x)"x (A(x)∨B(x))
(2)$x (A(x)∧B(x))$x A(x)∧$x B(x)
定理2.3.4
（1）"x "yA(x,y) "y "x A(x,y)
(2)$x $ y A(x,y) $y $ x A(x,y)
定理2.3.5（换名规则）设A是一个公式，将A中某量词辖域中的某约束变项及相应的指导变元，改成该量词辖域中未曾出现的某个个体变项，公式的其余部分不变，所得公式记为，则。
定理2.3.6（代替规则）设A是一个公式，将A中自由出现的某变项，都改成该量词辖域中未曾出现的某个个体变项，公式的其余部分不变，所得公式记为，则。
2.3.2前束范式
定义2.3.2 ：公式A’称为公式A的前束范式，如果AA’，且A’形如Q1x1…QnxnB ,.其中Q1，…，Qn为量词 " 或 $，B中无量词。
对任何谓词公式均可作出其前束范式，因为我们总可以利用各组逻辑等价式将量词逐个移至公式的前部，其步骤是:
(1)首先将公式中联结词→,« 消除。
(2)其次将否定词 ┐深入到各原子公式之前。
(3)真式将量词逐个移至公式前部。
例如： "xA(x)∨"x B(x)"xA(x)∨"yB(y)"x(A(x)∨"yB(y))
"x"y (A(x)∨B(y))
[例2.3.1] 求以下两式的前束范式：
（1）"xA(x)→$x B(x)
（2）"x"y ($z(P(x,z)∧P(y,z))→$z Q(x,y,z))
解（1）"xA(x)→$x B(x)
┐"xA(x)∨$x B(x)
$x┐A(x)∨$x B(x)
$x(┐A(x)∨B(x))
（2）"x"y ($z(P(x,z)∧P(y,z))→$z Q(x,y,z))
"x"y (┐$z(P(x,z)∧P(y,z))∨$z Q(x,y,z))
"x"y ("z(┐P(x,z)∨┐P(y,z))∨$z Q(x,y,z))
"x"y ("z(┐P(x,z)∨┐P(y,z))∨$u Q(x,y,u))
"x"y "z$u (┐P(x,z)∨┐P(y,z)∨Q(x,y,u))
（或"x"y "z$u (P(x,z)∧P(y,z)→Q(x,y,u))）
据以上讨论可知：
定理2.3.6（前束范式定理） 对任意谓词公式都存在与之等值的前束范式.
2.4一阶逻辑的推理理论

谓词演算是命题演算的深化，因此除了在谓词演算系统中可以使用命题演算系统中的推理规则外，还有它自己独有的推理规则。
2.4.1、四个与量词有关的推理规则
(1)全称量词消去规则（UI规则）
形式：xA(x)A(c)，其中c为不在A(x)出现过的个体常项；
xA(x) A(y)，其中y不在A(x)中约束出现;
说明：使用时要全部替代。
(2) 全称量词引入规则(UG规则)
形式: A(y) xA(x)
应用条件: ①前提A(y)对于y的任意取值都成立；②y不在A(x)中约束出现；
(3)存在量词消去规则(EI规则)
形式: xA（x） A（c），其中c使A(x)真;
应用条件: ①c不在A(x)出现; ②若A(x)中除x外还有其他自由变元时，不能应用本规则；
(4)存在量词引入规则(EG规则)
形式: A(c) xA(x)，其中c是个体常项；
应用条件: 取代c的变元x不在A(c)中出现；
注: （1）要正确地使用这四种规则，常常带有各种限制，稍不注意就出错。
（2）EI规则与UI规则的作用顺序要特别注意;
[例2.4.1]指出下列推导过程中的错误:
(x)(P(x)→Q(x)) P
P(y)→Q(y) UI，(1)
(x)P(x) P
P(y) EI，(3)
Q(y) T，(2)，(4)
(x)Q(x) EG，(5)
2.4.1谓词逻辑中的推理实例
基本等价式，基本蕴涵式，EI规则，UI规则，EG规则，UG规则，演绎法和反证法；
[例2.4.2] 试符号化并证明苏格拉底三段论
前提：(x)(H(x)→M(x))，H(c),
结论：M(c)
证明: ①H(c),
②(x)(H(x)→M(x))
③H(c)→M(c)
④M(c)

[例2.4.3] 证明

[例2.4.4] 证明