Prolog/逻辑入门

由于 Prolog 很大程度上基于形式逻辑，因此在开始学习这门语言之前，了解一些逻辑知识非常有用。这是一篇针对想要学习 Prolog 的人的简短逻辑入门。它将讨论两种逻辑语言：命题逻辑和一阶逻辑。

命题逻辑

命题逻辑有两个基本元素：**项**和**联结词**。项由字母表示（通常是大写字母），代表**真**和**假**的值，即项可以是真或假，但并不总是必须明确说明它们代表哪个。从某种意义上说，它们就像数学中的变量一样，代表未知值。

联结词，顾名思义，将两个项连接起来。这种连接的结果将取真或假值，具体取决于两个项的值。例如，考虑联结词 AND。它可以连接项 A 和 B 以形成逻辑句子 "A AND B"。（任何可以取真或假值的东西都被称为句子。）句子 "A AND B" 在 A 和 B 都为真时为真。如果其中一个或两个都为假，那么该句子为假。联结词通常用符号而不是单词表示。下表显示了最常用的联结词、它们的含义以及通常用来表示它们的符号。

名称	用法	翻译	意义	符号
合取	$A\land B$	A 且 B	当且仅当两个项都为真时，该句子才为真	$\land \quad ,$
析取	$A\lor B$	A 或 B	当一个或两个项都为真时，该句子为真	$\lor \quad ;$
异或	$A\oplus B$	A xor B	当其中一个项为真，但不是两个都为真时，该句子为真	$\oplus \quad {\underline {\lor }}\quad$
否定	$\lnot A$	非 A	当该项为假时，该句子为真；当该项为真时，该句子为假	$\sim \quad \lnot \quad {\bar {q}}$
蕴涵	$A\rightarrow B$	A 逻辑蕴涵 B	如果 A 为真，则该句子仅当 B 为真时才为真；如果 A 为假，则该句子为真	$\rightarrow \quad \Rightarrow \quad \models$
等价	$A\leftrightarrow B$	A 逻辑等价于 B	当两个项都为真或两个项都为假时，该句子为真	$\leftrightarrow \quad \Leftrightarrow \quad =$

要注意蕴涵的含义，因为它可能违反直觉。 $A\rightarrow \;B$ 基本上表示，如果 A 为真，那么 B 也为真，否则 B 可以为真或假。

由于每个项只能取两个值，因此所有可能性都可以很容易地在所谓的真值表中枚举出来。

$A$	$B$		$A\land B$	$A\lor B$	$A\oplus B$	$\neg A$	$A\Rightarrow \;B$	$A\Leftrightarrow \;B$
F	F		F	F	F	T	T	T
F	T		F	T	T	T	T	F
T	F		F	T	T	F	F	F
T	T		T	T	F	F	T	T

下一步是使用连接词将这些句子连接起来，以构成更复杂的句子，例如 $(A\land B)\Rightarrow \;(B\Leftrightarrow \;A)$ 或 $(A\lor B)\lor (A\lor C)$。在最后一句话中，括号可以省略，因为 $A\lor (B\lor C)$ 与 $(A\lor B)\lor C$ 相同。但是，如果存在疑问，最好使用括号来使句子的含义完全清晰。

您也可以使用真值表分析复杂的句子。

$A$	$B$		$A\land B$	$A\lor B$	$(A\land B)\lor (A\lor B)$
F	F		F	F	F
F	T		F	T	T
T	F		F	T	T
T	T		T	T	T

现在我们可以将句子分为三类：有效、不可满足和可满足。

• 有效句子（又称重言式）始终为真，无论它们的项取何值。
  有效句子的例子包括
  1. $A\lor (\lnot A)$
  2. $A\Rightarrow A$
  3. $(A\Rightarrow B)\lor (A\land (\lnot B))$
• 不可满足句子（又称矛盾）始终为假，无论它们的项取何值。
  不可满足句子的例子包括
  1. $A\land (\lnot A)$
  2. $(A\Rightarrow B)\land (A\land (\lnot B))$
• 可满足句子（又称偶然式）是指可以为真或假的句子，具体取决于其项的取值。
  可满足句子的例子包括
  1. $A$
  2. $A\lor B$
  3. $A\land B$

意义和意图

在逻辑语言中，要意识到这些句子可以以不同的方式使用，这一点非常重要。例如，$A\wedge B$ 本身没有隐含任何意义。它只是一种创建逻辑结构的形式化方法。有人可以 **声明** $A\wedge B$ 为真，这将赋予句子意义（即 A 和 B 都为真），可以用来推导出进一步的真理，如果已知关于 A 和 B 的其他信息。有人也可能 **询问** $A\wedge B$ 是否为真，被问到这个问题的人必须根据已经知道的关于 A 和 B 的东西找到答案。换句话说，一个逻辑句子本身没有意义。读者需要知道句子的意图（通常是问题或陈述）才能对其进行操作。逻辑中常见的结构是知识库，它是一组被声明为真的句子，以及一个作为问题提出的单个句子。问题是，鉴于知识库，该问题是否为真。例如，考虑以下知识库

$A\wedge B$
$~B$

以及问题

$A$

也就是说，鉴于知识库，A 是否为真。很明显，这个问题确实是真，因为 $A\wedge B$ 为真，B 也为真。这种知识库/问题结构实际上是 Prolog 的工作方式。你编写一个知识库（你的程序）并向 Prolog 提出一个问题。与传统的编程语言相比，知识库是你的程序，问题是它的输入，Prolog 解决你的问题就是运行程序。

一阶逻辑

一阶逻辑（也称为谓词逻辑）扩展了命题逻辑，使用谓词、变量和对象。在命题逻辑中，原子句子（可以取真/假值的最小元素）是项，由字母表示的符号。在一阶逻辑中，原子句子是 **谓词**。谓词有一个名称（以大写字母开头），后面跟着几个 **变量**（以小写字母开头）。以下是谓词的示例

• Predicate(variable1, variable2)
• BrotherOf(sibling, brother)
• MotherOf(child, mother)
• HasWheels(thing)

这些变量可以用 **对象** 来实例化。对象是以大写字母开头的词语表示的元素。例如，在谓词 $HasWheels(thing)$ 中，变量 thing 可以用对象 Car、Bike 或 Banana 来实例化。根据变量的实例化，谓词为真或假（$HasWheels(Car)$ 为真，而 $HasWheels(Banana)$ 为假）。但是，请注意，这些名称仅是为了可读性，它们本身实际上没有任何意义。 $HasWheels(Banana)$ 与 $X(A)$ 或 $WrUlS(OvqPv)$ 在功能上没有区别。是否 $HasWheels(Banana)$ 为真或假需要以某种形式化方式定义（例如知识库，将在下面描述）。

这些谓词可以用连接词（连接词与命题逻辑中的连接词相同）连接在句子中，就像命题逻辑中的项一样。通常，有一组被假定为真的句子，用于创建谓词的逻辑定义。这样一组被假定为真的句子被称为 **知识库**。例如，这样一个知识库可能包含以下句子

HasWheels(Car)
MotherOf(Charles, Elizabeth)

这些句子告诉我们，如果第一个元素是汽车，则 HasWheels 谓词为真；如果第一个元素是 Charles，第二个是 Elizabeth，则 MotherOf 谓词为真。为了构建这种包含变量的句子，我们需要说明在使用变量时我们究竟指的是什么。如果 HasWheels(x) 为真，我们指的是它对 x 的实例化都为真，还是说存在 x 的一个实例化使得 HasWheels(x) 为真？为了定义这一点，我们使用 **量词**，即它们确定变量的数量。一阶逻辑有两个量词：**全称量词** $\forall$ 和 **存在量词** $\exists$。这些量词放在变量之前，以表明变量在量词之后的句子中所代表的含义。例如，句子 $\forall xHasWheels(x)$ 表示对 x 的所有可能实例化，HasWheels(x) 都为真，也就是说，所有可能的物体都有轮子。句子 $\exists xHasWheels(x)$ 表示存在至少一个物体 x 使得 HasWheels(x) 为真，换句话说，至少存在一个东西有轮子。为了理解量词的使用，请考虑以下示例

• 如果 x 是陆地车辆，那么 x 拥有轮子。（如果 x 不是陆地车辆，则该句子对 x 没有任何说法）

$\forall {x}LandVehicle(x)\Rightarrow HasWheels(x)$

• 如果 x 有一个孩子 y 且 x 是男性，则 x 是 y 的父亲。

$\forall {x,y}HasChild(x,y)\wedge Man(x)\Rightarrow FatherOf(y,x)$

• 存在至少一个物体既有轮子，又不是汽车

$\exists {x}HasWheels(x)\wedge \sim Car(x)$

• 所有的母亲都有一个孩子

$\forall {x}Mother(x)\Rightarrow \exists {y}Child(y)\wedge HasChild(x,y)$

Prolog 中的逻辑

Prolog 中使用的逻辑是一阶逻辑的一种版本，使用大写字母反转（谓词和对象以小写字母开头，变量以大写字母开头）。Prolog 程序由一个知识库组成，其中每个句子都是谓词的合取，连接到一个具有蕴涵关系的最终谓词。例如

$\forall a,b,c,dPred1(a,b)\wedge Pred2(b,c)\wedge Pred3(c,d)\Rightarrow Pred4(a)$

这样的句子称为霍恩子句。在 Prolog 中，上面的句子将如下所示

pred4(A) :- pred1(A, B), pred2(B, C), pred3(C, D).

请注意，蕴涵符号被反转，逗号用于合取，句号用于结束句子，并且所有变量都被假定为是全称量词。

示例

对所有 x：猫(x) 或 狗(x) 蕴涵 宠物(x)

练习

(x) 为以下命题逻辑中的句子写出真值表。
a) $(A\wedge B)VC$
b) $A$
c) $A$
d) $A$
e) $A$

(x) 连接两个项的连接词有多少种？为什么？

(x) 尝试找到一个公式来拟合以下真值表
a)
b)
c)
d)

(x) 真值表是证明命题公式为真的一个好方法。你能对一阶逻辑做同样的事情吗？解释如何或为什么不能。

(x) 将以下句子转换为一阶逻辑。尝试密切遵循句子的逻辑结构（使用对象表示个体，使用变量表示人组，使用连接词表示逻辑结构，使用谓词表示其余部分）。
a) 所有的孩子都很矮。
b) 一些孩子拥有鞋子。
c) 如果一个人是孩子且是男孩，那么他喜欢汽车。
d) 所有拥有鞋子的孩子都穿鞋子。
e) 所有的孩子都有母亲。
f) 如果一个女人是母亲，那么她有一个孩子。
g) 如果蔬菜煮过头了，那么没有孩子喜欢蔬菜。
h) 如果老师惩罚了她的孩子，那么没有母亲喜欢老师。

(x) (高级) 以下问题与 = 符号有关。它接受两个变量，如果它们绑定到相同的东西，则为真，换句话说，如果 x 和 y 代表同一个对象，则 x = y 为真。
(a) = 符号是函数、谓词还是连接词？为什么？
(b) = 符号不应该与等式连接词混淆。它们有什么不同？
(c) 你能想到一个一阶逻辑中的句子，当它被添加到知识库中（因此被认为始终为真）时，它与 = 符号做同样的事情吗？也就是说，通过它在知识库中的定义，这个句子，以 'inputs' x 和 y 为输入，如果 x 和 y 相等，则为真。
(d) 存在量词 $\exists x$ 定义了一个句子，如果它对 x 的至少一个可能的实例化都为真，则为真。你能想到一种量化变量 x 用于句子的方法，这样如果句子仅对 x 的一个实例化为真，但不再多，则句子为真？你可能需要为此使用 = 符号。