《谓词逻辑在关系数据库中的应用》由会员分享，可在线阅读，更多相关《谓词逻辑在关系数据库中的应用（16页珍藏版）》请在金锄头文库上搜索。
1、谓词逻辑在关系数据库中的应用07 级数学信息(2)班 张益 060207087 一谓词逻辑与数据子语言1、二维表与谓词逻辑我们知道一张二维表可表示为一个 n 元有序组的集合。一个集合可用一个特性谓词刻画，故一个n元有序组的集合可用一个n元特性谓词刻画，由此，一个二维表亦可用谓词刻画。某元 组属于二维表之充分必要条件是使其对应的谓词为真。例1表1所列之二维表可用谓词F(x, y) = (x=y) aN+(x)表示，其中N+(x)表示x是正自然 数。例2表2所列之二维表可用谓词F(x, y) = (x=y+1) a(y/2=y/2) aN+(x)表示。表2表1xY325476981110xy112
2、2334455这样二维表可用特性谓词表示的集合来表示，如上两例的两个二维表分别可用下面两个 以特性谓词表示的集合来表示：(x， y)| (x=y) aN+(x)；(x， y)| (x=y+1) a(y/2=y/2) aN+(x)2、基本操作与谓词公式数据子语言的操作对象二维表，可用谓词逻辑中的谓词表示，而对其对象所进行的操作则可用谓词公式表示，亦即是由一些谓词通过命题联结词及量词来表示。为了说明这一点，首 先我们要对关系式数据库中的谓词公式做一明确的定义。在关系式数据库中，其谓词公式的原子 公式与一般谓词公式的原子公式不同。一个谓词公式可定义如下：1原子公式A. 刻画二维表的谓词R (s ,
3、s，s )是原子公式(其中个体变量s为二维表的第i个属12ni性)；B. se u是原子公式，其中s, u均为个体变量，e为比较符，它可以是：i ji j，,=,w,；C. s e a 是原子公式，其中 a 为常量。i2.公式A. 原子公式是公式；B. R，S是公式，贝IR，(RAS)，(RVS)是公式；C. R(x)是公式，贝归xR(x), VxR(x)是公式；D. 公式是有限次使用A, B, C构成。下面我们用谓词公式刻画基本操作。我们先讨论插入、删除和修改。在关系代数中我们知 道可以用并运算与差运算分别表示插入与删除，而在谓词逻辑这章中我们知道并运算相当于联结 词“或者”，而差运算相当于
4、联结词“并且”再在第二项中加以否定。这样我们设：R=(x , x ,， x)|P(x， x， x)12n 1 2nS=(x , x ,， x)|Q(x， x， x)12n 1 2n贝有插入RUS（x , x，x）|P（x , x，x ） VQ（x , x，x）1 2 n 1 2 n 1 2 n删除R S（x， x， ， x ）|P（x， x， ， x ） AQ（x， x， ， x ）1 2 n 1 2 n 1 2 n而修改操作是由删除和插入两个操作组合而成的，因此删除、插入既然可由谓词刻画，修 改也可由谓词刻画。用上面类似的方法，投影、选择、笛卡尔乘积也可用谓词公式来表示。这样，我们把关系数据
5、库中的数据子语言变成逻辑逻辑中 的谓词公式，因而可以用谓词公 式研究数据子语言，也可用谓词公式对数据子语言进行优化。由于关系代数、谓词逻辑以及数据 库建立了联系，因而使关系式数据库 获得了巨大的生命力，利用这些数学工具，使关系式数据 库研究突飞猛进，近年来在上述研究基础上建立了一整套的关系数据库设计理论，使整个关系数 据库建立在 牢固的数学基础上，而且利用谓词逻辑建立起具有智能功能的数据库。由于和数学 紧密结合，关系数据库在近期得到很大发展。二、 谓词逻辑与逻辑程序设计语言由于引入了假设推理，使得由公理系统中的公理和推理规则出发而求得定理的过程变得十分 简单。于是人们就进一步猜想，是否有一种固
6、定的算法，按照这种算法，可以证明谓词逻辑中的 任何公理系统的任何定理的正确性；若真存在这种算法的话，将这种算法用计算机实现后，则谓 词演算中的定理就可以用计算机证明，从而实现了定理的自动证明。这种想法 1965 年由美国数 理逻辑学家Robinson得到了证明，得到了一个“半可判定”的算法，即在谓词演算中存在一种 算法，只要公式是恒真的，就能用这种算法推出。他所使用的算法叫归结原理（Resolution Principle）。 1972年法国马赛大学的 Colmerauer 在上述研究成果的基础上设计了一种逻辑程 序设计语言，称为PROLOG（Programming in Logic）语言，不
7、久，便在计算机上实现。这样，现实世界中的问题只要能用谓词逻辑公理系统方式表示出来，就可以将它写成 PROLOG 程序，然后用计算机实现。其过程见下图。因此，通过此种方式可以用计算机求解现实世界中的 很多逻辑问题。现实世界n谓词逻辑表示PROLOG程序n计算机实现1、子句与子句集为了便于推理，对谓词逻辑中的恒真公式需要进一步规范化，这可在Skolem范式的基础上 进行，其过程如下：（1）利用 US， ES 将公式中的量词除去。例 4 试将mxVy（A（x, y）V（B（x, y） AB （x， y）进一步规范化。12解：首先由mxVy(A(x, y)V(B(x, y) AB2(x, y)可以推出
8、A(c, y) V (Bi(c, y) AB2(c,y)(2) 除去量词后的公式就是一个命题演算公式。此时,可将公式化成合取范式。在上例中 有：A(c, y) V (B (c, y)AB(c, y)12= (A(c, y)VB(c, y)A(A(c, y)VB2(c, y)(3) 将每个析取式用蕴涵式表示,这种蕴涵式称为子句 (Clause)上例中可以化为：(A(c, y) VB (c, y)A(A(c, y) VB (c, y)12= (A(c, yB/c, y) A (A(c, y)B2(c, y)(4) 最后一个公式可用一个子句集表示,一个公式是恒真的与一个子句集恒真(子句集中 每个子句
9、为恒真)相一致。于是(A(c, y)B(c, y) A (A(c, y)B2(c, y)可用下面的子句集表示：A(c, y)B (c, y), A(c, y)B(c, y)。12这样一个公式总可以用一组子句表示,每个子句具有单一的蕴涵式。这种蕴涵式既简单又 便于推理。下面我们进一步讨论子句的形式。对任何一个析取式，设它有k个带否定符的命题以及n k 个不带否定符的命题：A VA VVA VA VA VVA12k k+1k+2n对这个析取式总可以将其转换成蕴涵式,使得蕴涵式中无否定符出现。转换如下：A VA VVA VA VA VVA12k k+1k+2n=(A AA AAA) VA VA VV
10、A12k k+1k+2n=(A AA AAA) (A VA VVA)12kk+1k+2n通常写成 A VA VVA -A AA AAAk+1k+2n 12k或写成 A , A , , A -A , A , , Ak+1k+2n 12k这个公式给出了子句的标准形式。有一种特殊类型的子句需要讨论，它称为Horn子句。当子句中k = n1时，则称此子句为 Horn 子句。这种子句具有下面的形式：A A , A , , An 12n-1在Horn子句中当n = 1时，称为断言，断言具有下面形式：An在Horn子句中当k = n时，称为假设，它具有下面形式：A， A， A12n在Horn子句中当n =
11、0时，称为空子句，空子句可写成：或口。由于推理中可由 Horn 子句得出唯一的结论，因此 Horn 子句的作用很大。下面我们举几个 例子：例 5、试将“每个人都犯错误”用子句形式表示。我们可以将这语句写成如下形式：Vxy(Human(x) (Mistake(y) ADose(x, y)利用 US， ES 后，可得到：H(x) M(f(x) AD(x， f(x)(这里 H， M， D 分别代表 Human.Mistake,Does )，将所得公式 化成析取范式：H(x)M(f(x)AD(x， f(x)H(x) V (M(f(x) AD(x， f(x)=(H(x) VM(f(x) A (H(x)
12、VD(x， f(x)=(H(x) M(f(x) A( H(x)D(x，f(x) 最后得子句集： M(f(x)H(x)， D(x， f(x)H(x)三、归结原理我们知道，在公理系统中，有公理和定理两部分，公理是已知的恒真公式，定理是要求证 的恒真公式，公理可用子句集表示，设子句集为S,则S=E , E , , E1 2 n其中E i=l, 2,，n表示子句。i设定理用 E 表示。下面分几步讨论。1、子句集的相容性一个子句集如存在一个解释满足它，则称它是相容的，否则称为不相容的。如-P，P- 是不相容的子句集，而PQ, Q-R, x-, y-都是相容的。相容性是一个公理系统的必备条件。 由相容子句
13、集S可推得结论E相当于SUE是不相容的。例如我们可以由A-B, B可得出A, 它相当于A-B, B,A是不相容的。因此要证明由S可推得定理E相当于证明SUE是不相 容的。2、不相容性的证明方法我们讨论子句集不相容性的证明方法。定理 设有恒真公式A VA VVA -A AA AAA ；k+1k+2n12kB VB VVB -B AB AAB ；h+1h+2m12h(其中A=B , iWk, jh)，则必有恒真公式ijA VA VVA VB VB VVB VB VVk+1k+2n h+1h+2j-1j+1B -A AA AA AA AAA AB A AABm 12i-1i+1k 1h证明： 已知A
14、 AA AA AA AA AAA A VA VVA(1)12i-1 i i+1k k+1k+2nB AB AAB B VVB VVB VB VB VVB(2)12h h+1h+2j-1 j j+1m由(1),(2)得A VA VVAVA VAVVA VA VVA12i-1ii+1k k+1nB VB VVB VB VB VVB VB VB VVB (4)12h h+1h+2j-1 j j+1m将（3）和（4）合并得A VA VVA VA VVA VB VB VVB V12i-1i+1k12hA VVA VB VB VVB VB VVBk+1n h+1h+2j-1j+1m由此得到A AA AAA AA AAA AB AB AA12i-1i+1k 12B A VA VVA VB VB VVB VB VVB hk+1 k+2n h+1 h+2j-1
