一阶逻辑(FOL: First Order Logic)

一阶逻辑用下面的形式描述世界

对象：人、房屋、数字、颜色、游戏、战争、披萨
关系：可以是一元关系或属性, 如红色的、圆的、伪造的；更普适的是n元关系, 如大于、…和…是兄弟、在…里
函数: 有唯一值, 如…的父亲, …最好的朋友, …的左胳膊, …加1 等

关系又可称为谓词

FOL的语法

常量/Constants: KingJohn, 2, USTC, ...
谓词/Predicates: Brother, >, ...
函数/Function: Sqrt, LeftLegOf, ...
变量/Variables: $x, y, a, b, \dots$

FOL还需要表示逻辑的符号（就跟命题逻辑一样）

联结词/Connectives: $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$
等词/Equality: $=$
量词/Quantifiers: $\forall, \exists$

常量和变量称为项，即对象。对项应用函数也会得到项，称为复合项。如有 $n$ 元函数 $\varphi$

\varphi(x_1,x_2,\cdots,x_n)

将其作用到 $n$ 个项 $t_1,t_2,\cdots,t_n$ 上会得到复合项

\varphi(t_1,t_2,\cdots,t_n)

Note

所有项都是0次或有限次复合得到的

谓词作用在项上形成原子语句，项也可以是复合项，如

>(Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))

原子语句由逻辑词链接得到复合语句，如

> (1,2) \land \neg >(1,2)

一阶逻辑语句的真值与数据库语义

语句的真值是由一个模型和对句子符号的解释来判定，其中模型包含对象域和对象的关系，解释是指对FOL语句中的三类符号(常量符号、谓词符号、函数符号)指代的对象、关系和函数进行解释

如对于

Brother (Richard, John)

根据Brother，Richard，John解释的不同，该语句的真值也不同。 FOL语言中，3类符号在模型中的对应数量可以从1到无穷大，无法枚举，因而需要引入数据库

数据库语义定义为

唯一名称假设：每个常量符号指代一个唯一对象
封闭世界假设：假设未知的所有原子语句均为假
论域闭包：每个模型只包含常量符号指代的对象

全称量词与存在量词

量词: 表示数量的词
全称量词 $\forall$ : 表示任意的，所有的，一切的
存在量词 $\exists$ : 表示存在，有的，至少有一个

量词的使用需要注意避免两类错误

全称量词

全称量词 $\forall$ 和与 $\land$ 逻辑混合使用，如记 $M(x)$ 表示x是人， $F(x)$ 表示x爱美

\forall x(M(x)\land F(x))

它的语义是任何事物 $x$ 都是人并且任何事物 $x$ 都爱美。事实上如果希望表达人都爱美，应当使用蕴含逻辑

\forall x(M(x)\Rightarrow F(x))

存在量词

存在量词 $\exists$ 和蕴含 $\Rightarrow$ 逻辑混合使用，如记 $M(x)$ 表示x是人， $F(x)$ 表示x爱美

\exists x(M(x)\Rightarrow F(x))

它的语义是存在事物x，如果x是人x就爱美。事实上如果想表示有的人爱美应该使用与

\exists x(M(x)\land F(x))

量词的性质

两个相同的量词可以交换

\forall x\forall y,~\forall y \forall x

它们是等价的，因而可以简写为 $\forall x,y$ 。同样存在量词也有相同的等价关系

\exists x\exists y,~\exists y \exists x

它们是等价的，因而可以简写为 $\exists x,y$ 。但是注意

注意

$\forall x\exists y$ 和 $\exists y\forall x$ 不等价。随便找个函数试试就能发现了

量词否定等值式

对含量词的逻辑表达式取反时应先将量词取反

\neg \forall x A(x)\equiv \exists x\neg A(x)\\ \neg\exists x A(x)\equiv\forall x\neg A(x)

量词可以分配

$\forall$ 对与 $\land$ 可以分配， $\exists$ 对或 $\lor$ 可以分配

\forall x(A(x)\land B(x))\equiv \forall xA(x)\land\forall xB(x)\\ \exists x(A(x)\lor B(x))\equiv \exists xA(x)\lor\exists xB(x)\\

反过来则不成立

等词`=`

等词=意为相同的对象而不是值相同，表征它俩就是同一个东西。例如可以用父母关系定义兄弟姐妹

\forall x, y \, Sibling(x, y) \iff \\ [\neg(x = y) \land \exists m, f \, (\neg(m = f) \land Parent(m, x) \land Parent(f, x) \land Parent(m, y) \land Parent(f, y))]