一阶逻辑(数据库)

时间：2022-12-03 06:30:01 | 来源：信息时代

时间：2022-12-03 06:30:01 来源：信息时代

    一阶逻辑 : 在命题逻辑基础上作更为深入与广泛研究的一门学科。它研究比命题逻辑更为复杂的符号逻辑体系及推理规律。一阶逻辑是数理逻辑中发展得较为成熟的一个部分,它起源于19世纪,到20世纪中叶已达成熟阶段,它在为符号语言和推理所建立的形式系统中处于重要和核心地位。
由于谓词在一阶逻辑中的重要性,因此它又称一阶谓词逻辑或简称谓词逻辑。在该逻辑中量词仅作用于个体变元,而谓词不可变,为常值,故称一阶逻辑,而当谓词为可变时,量词还可作用于谓词时则称为二阶逻辑,或称高阶逻辑。
一阶逻辑在计算机及数据库领域中具有广泛、基础性的作用,它在关系数据模型、谓词模型的建立中,在演绎数据库、知识库中以及在多种基础性应用中起着重要的理论指导价值。
1.个体与谓词
在一阶逻辑中进一步将原子命题分解成为个体与谓词两部分。个体是一阶逻辑中基本的组成部分,它可分为个体常元与个体变元,可分别用a,b,c,…及x,y,z,…表示,谓词刻画个体的性质与关系。谓词是与个体紧密关联的,当谓词与一个个体关联时称为一元谓词,此时谓词刻画个体性质,当谓词与n个个体关联时称为n元谓词,此时它刻画个体间关系。谓词符号一般可用大写符P,Q,R,…表示,而一元谓词与n元谓词则分别可用P(x),P(x₁,x₂,…,x_n)表示,当谓词中的个体变元全部被赋值为个体常元时,此时谓词必取值为T或F。
2. 量词与个体域
一阶逻辑中的每个个体变元均有一个变化范围称个体域,如在谓词中个体变元对所有个体域中个体均使谓词为T以及有些个体域中个体谓词为T是两个极端不同的概念。因此有必要区分“所有”与“有些”两个概念,由于它们具有量上的区别,因此可称为量词,分别用∀x及∃x表示,称全称量词及存在量词。在量词符号中的“x”表示量词所作用的个体变元,称约束变元,而不受量词约束的个体变元则称为自由变元。
3. 函数
在一阶逻辑中个体与个体间有一定关系,这种关系称函数,函数有一元、二元及n元之分,它们分别可用f(x),f(x,y)及f(x₁,x₂,…,x_n)表示,在函数中个体经函数作用后所得到的仍为个体,所以它是个体到个体的映射。
4. 公式
一阶逻辑的公式是由个体、谓词、量词及函数所组成,其组成规则如下:
在谓词逻辑公式中所使用的符号共有七种:
(1)个体常量符: a,b,c,…。
(2)个体变量符:x,y,z,…。
(3)函数符:f,g,h,…。
(4)谓词符: F,G,H,…。
(5)联结词符: , ∧, ∨,→, ↔。
(6)量词符: ∀, ∃。
(7)括号: (,)。
一个谓词逻辑公式是由上面七种符号按一定规则所组成的符号串。
5.项
(1)个体常量是项。
(2)个体变量是项。
(3)设f为n元函数符,“t₁,t₂,…,t_n”为项,则f(t₁,t₂,…,t_n)是项。
(4)项由且仅由有限次使用(1)、(2)、(3)而得。
原子公式: 设P是n元谓词符,“t₁,t₂,…,t_n”为项,则P(t₁,t₂,…,t_n)是原子公式。
6.谓词逻辑公式(亦可简称公式)
(1)原子公式是公式。
(2)如A, B是公式,则(A),(A∨B),(A∧B),(A→B), (A↔B)是公式。
(3)如A为公式,x为个体变量,则(∀xA),(∃xA)为公式。
(4)公式由且仅由有限次使用(1)、(2)、(3)而得。
7.范式
由于一阶逻辑公式的结构混乱在实际使用中极不方便,因此一般采用具有统一结构的范式:
(1)斯科林范式:此种形式适用于数学领域。一公式如果仅出现全称量词的且在公式首部,而公式尾部出现“∨”、 “∧”及“”符, 此种公式称斯科林范式。
(2)Horn子句形式:此种形式适用于计算机领域(特别是人工智能领域)。Horn子句的一般形式是“A_n:—A₁,A₂,…,A_n-1”。它是“A₁∧A₂∧…∧A_n-1→A_n”的另一种表示方法,其中,A_i(i=1,2,…,n)均是谓词;A_n称为子句的头,而“A₁,A₂,…,A_n-1”则称为子句的体。Horn子句还可以有下面几种特殊表示:①断言:当Horn子句中n=1时,此子句称断言,并可表示为“A_n”。②假设: 当Horn子句中A_n不出现时,此子句称假设,并可表示为“:—A₁,A₂,…,A_n-1”。③空子句: 当Horn子句中n=0时,此子句称空子句,并可表示为“□”。
(3)Datalog子句形式:此种形式适用于数据库领域。Datalog子句是专门为数据库中数据模型设计的一种语言,它的基本形式与Horn子句一样,但是需加一些限制:①Datalog中的变量必须受限,即Datalog中的变量不能在无限域中变化,必须限制在一个有限域内,这主要是由于数据库中数据是有限的特性所决定,而这种限制一般均在Datalog中增加一些限制性谓词而实现。②在Datalog中一般只出现自由变量以及存在量词形式出现的约束变量,在子句的头中所出现的变量均为自由变量,而在子句的体中所出现的变量(除头中变量外)均为约束变量。
8.永真公式
在公式中如果赋予个体(自由)变元为个体域中的任一个体,公式均为真,则称此公式为永真公式。
9. 一阶演算
一阶逻辑的形式系统称一阶演算,又称一阶谓词演算或简称谓词演算,有关形式系统介绍可见参考文献[1],数理逻辑在谓词演算中取一些永真公式为公理,并规定一些推理规则,组成一个公理系统,它可以推出所有的永真公式。谓词演算中常用的推理规则有:
(1)全称推广规则UG:P(x)⊦∀xP(x)。
(2)全称指定规则US:∀xP(X)⊦P(x)。
(3)存在推广规则EG:P(X)⊦∃xP(x)。
(4)存在指定规则ES:∃xP(X)⊦P(e)。
10. 一个典型的公理系统
谓词演算中可以有很多公理系统,下面是一个典型的公理系统:
系统组成部分: 谓词逻辑公式(见前)。
推理部分:
(1)公理: 设P,Q,R为公式,则有公理如下:
p→p;
(P→(Q→R))→(Q→(P→R));
(P→Q)→((Q→R)→(P→R));
(P→(P→Q))→(P→Q);
(P↔Q)→(P→Q);
(P↔Q)→(Q→P);
(P→Q)→((Q→P)→(P↔Q));
P∧Q→Q;
P∧Q→P;
P→(Q→P∧Q);
P→P∨Q;
Q→P∨Q;
(Q→P)→((R→P)→(Q∨R→P));
(P→Q)→(Q→P);P→P;
∀xP(x)→P(x);
P(x)→∃xP(x)。
(2)推理规则:
分离规则: P→Q, P⊦Q;
全称规则: Q→P(x)⊦Q→∀xP(x);
存在规则:P(x)→Q⊦∃xP(x)→Q。
上面17个公理与3个规则中有15个公理与1个规则是命题逻辑公理系统的,真正属谓词逻辑的仅有2个公理与2个规则。
证明(过程)与定理:
证明(过程)是一个公式序列:P₁,P₂,…,P_n,其中每个P_i(i=1,2,…,n)必须满足下条件之一:
(1)P_i是公理。
(2)P_i是由P_k,P_r,(k,r<i)施行分离规则而得。
(3)P_i是由P_k(k<i)施行全称规则而得。
(4)P_i是由P_k(k<i)施行存在规则而得。
最后,P_n＝Q即为定理。
可以证明该公理系统是不矛盾的、完全的但不是独立的。