计算机推理的语义与语法
闫硕，吴尽昭*
基金项目： 本论文得到了高等学校博士学科点专项科研基金的资助，课题名称为嵌入式软件设计验证与评
估若干关键问题研究，课题编号为（20090009110006）
作者简介：闫硕，(1987-)，男，北京交通大学硕士研究生，主要研究方向是计算机代数以及数理逻辑. E-mail:
09120549@bjtu.edu.cn
通信联系人：吴尽昭，（1965-），男，广西民族大学副校长，北京交通大学教授，博士生导师，主要研究
方向是计算机软件与理论。E-mail: himrwujz@yahoo.com.cn
（北京交通大学计算机与信息技术学院，北京 100044）
5 摘要：数理逻辑中的经典和非经典逻辑都以研究推理为主要目的，其研究方法是通过两种渠
道展开的，即语义推理和语法推理。本文分别对语义推理和语法推理进行了定义和讨论，并
且针对其不同的特点，论述了它们与计算机推理之间的关系。在此基础上，以语法推理为基
本理论依据，给出了实现推理程序化的一种算法。
关键词：语义推理；语法推理；真值
10 中图分类号：TP181
The Semantic and Grammar of Computer Reasoning
YAN Shuo, WU Jinzhao
(School of Computer and Information Technology,Beijing Jiaotong University, Beijing 100044)
15 Abstract: In mathematical logic, the main task for the research of the classical and non-classical
logic is to study the inference. Typically there are two methods of inference, which are the
semantic reasoning and syntactic reasoning. In this paper, the author first gives the definitions of
the semantic reasoning and syntactic reasoning, then discusses the properties and relations
between them and the inference of computer. At last, an algorithm on mechanical reasoning is
20 shown.
Keywords: ksemantic reasoning; syntactic reasoning; truth value
0 引言
计算机科学中所涉及的逻辑，如经典逻辑的命题演算、谓词演算和非经典逻辑中的模态
25 逻辑、时序逻辑、非单调逻辑等，都是研究推理的科学。它们的研究方法皆是从两个角度展
开的，即语义推理和语法推理。这两种推理可以作为计算机推理的数学基础，下面将研究和
讨论这个问题。
1 语义推理与计算机推理
尽管数理逻辑（经典或非经典）[1-2]要从命题的语义出发研究推理，但是一般情况下，
30 逻辑中并没有对语义推理给出明确的定义。因此，首先给出语义推理的定义。
定义1. 推理时涉及命题真值（即真与假）的推理称为语义推理。 ▍
语义推理时，要考虑命题的真假意义。这与人们通常推理的习惯是一致的，因为在推理
时，人们自然或不自然地要考虑到所讨论命题的真与假。比如，数学推理都是在假设前提为
真的情况下，证明结论也为真。在证明过程中，总是认为命题非真即假，也就是说推理是涉
35 及命题语义的。在数理逻辑中，语义推理完全从命题的真与假出发展开讨论，请看下例：
例1. 如果汽车有翅膀，汽车就能飞上天，如果汽车飞上天，汽车就会取代所有交通工
具，而汽车没有取代所有交通工具，所以汽车没有翅膀。将这些命题符号化，然后用语义推
理的方法证明之。
 解：设P、Q、R 分别表示的命题为：
40 P：汽车有翅膀，Q：汽车飞上天，R：汽车取代所有交通工具。于是本推理可以符号化
为：
(P→Q)∧(Q→R)∧ R P 。
语义推理证明：假设(P→Q)∧(Q→R)∧ R 为真，则有P→Q 为真，Q→R 为真且R 为
真。于是R 为假，再由Q→R 为真，知Q 为假。由Q 为假及P→Q 为真便知P 为假。所以P
45 为真。故(P→Q)∧(Q→R)∧ R P。
该例中推理的每一步都涉及了命题的真与假，所以是语义推理。在命题逻辑中，当采用
语义推理方法推证时，一个从前提H1，H2，…，Hn 推出结论A 的推理：H1∧H2∧…∧Hn A
可以转化为一个判定命题公式H1∧H2∧…∧Hn→A 是否为重言式的问题，若为重言式，则
有：H1∧H2∧…∧Hn A。
50 任意的命题公式是否为重言式是可判定的，即存在算法。例如真值表法就是一个可行的
算法，真值表中的每一步都是从命题的语义出发进行讨论的。所以，对命题演算来说，只要
进行一些技术上的处理，就能够利用某种计算机语言编制出相应的程序，于是命题演算的语
义推理可以转化为计算机上的推理。尽管如此，人们一点也不感到满意，这是因为命题逻辑
的描述能力十分有限，很多命题不能在其中符号化，当然就更谈不上推理啦。
55 谓词逻辑完全弥补了命题逻辑描述能力上的缺陷，一阶谓词公式具有非常强的表达能
力，用它可以将自然语言表述的命题语句和几乎所有数学命题符号化。因而，在人工智能研
究领域里，广泛地将它用于知识表示。在计算机的其他研究领域中，通常它也作为形式描述
的工具。在语义推理方面，由于谓词逻辑中引入了量词，且需要在论域中讨论，所以与命题
逻辑相比，其推理过程要复杂得多。
60 例2. 利用语义推理证明：
x(Q(x)→ R(x))∧ x(Q(x)∧I(x)) x(R(x)∧I(x)) 。
证：对任意论域U，假设x(Q(x)→R(x))∧ x(Q(x)∧I(x))在U 上真，则x(Q(x)→ R(x))
在U 上真,且x(Q(x)∧I(x))在U 上真。因此，对任意x∈U, Q(x)→ R(x)为真，并且存在a∈U，
使得Q(a)∧I(a)为真，于是Q(a)、I(a)和Q(a)→R(a)为真。由Q(a)和Q(a) → R(a)为真便知
65 R(a)为真，所以R(a)ΛI(a)为真，故x(R(x)∧I(x))在U 上真。于是原命题得证，即：
x(Q(x)→R(x))∧ x(Q(x)∧I(x)) x(R(x)∧I(x))。
例2 中推理的每一步都涉及到了命题的真值，所以推理完完全全是语义上的推理。谓词
演算中这种语义推理是否适合作为计算机推理的算法基础呢？可以作如下分析：
尽管理论上已经证明，谓词逻辑中的推理是半可判定的，即存在一个算法，可以对谓词
70 逻辑中的任何定理（即从前提出发一定能够证得结论的推理）作出肯定的判决。但是，就谓
词逻辑语义推理具体方法来讲，其推理步骤是难以在计算机上实现的。因为撇开其它不说，
仅就推理时涉及到命题的真与假，计算机是无法做出判断的。命题的真或假是人脑思维而产
生的，计算机不会思维，它不会判定命题是真还是假。所以，涉及到语义时，算法难以产生。
针对语义推理，文献[3]与[4]给出了一些研究成果。
75 总之，命题的真与假蕴含着人们的思维。而计算机不具有思维能力。所以，涉及命题真
值的语义推理本身不适于作为计算机推理的算法。如果推理时不考虑命题的语义，仅注重符
号化后命题（或公式）的形式，只要满足某种形式，就可以得到某一结论。这对计算机来说
易于接受，因为识别公式是计算机容易处理的工作。下面讨论的语法推理正是基于这种思想
展开推理研究的。
 80 2 语法推理与计算机推理
语法推理[5]也称为形式推理，先给出定义。
定义2. 推理时不涉及公式（所表示命题）的真值，仅通过判定公式的形式是否满足公
认的推理规则所进行的推理称为语法推理或形式推理。 ▍
由定义可知，语法推理时，只与符号化后的命题公式的形式有关，不考虑公式的真值。
85 如果公式从形式上满足推理规则的要求，便可推出相应结论。此外，推理规则是语法推理时
必须依据的准则。比如，下面列出了一些常用的推理规则：
I1： P，P→Q Q
I2： Q，P→Q P
I3： P，Q P∧Q
90 I4： P∧Q P ；P∧Q Q
ES： xP(x) P(c)，c 为某一常元
US： xP(x) P(c)，c 为任一常元
EG： P(c) xP(x)
例3. 用语法推理的方法证明例1 的结论：(P→Q)∧(Q→R)∧ R P。
95 证：① R 前提
② Q→R 前提
③ Q ①②，I2
④ P→Q 前提
⑤ P ③④，I2
100 该例中的推理是在命题逻辑中进行的，它不考虑公式的真与假，完全从形式上展开，所
以就是语法推理。同样，谓词逻辑中的语法推理也是仅考虑公式的形式。
例4. 形式化下列命题并用语法推理证明之：
所有的有理数是实数，存在有理数是整数，所以存在实数是整数。
解： 设Q(x)、R(x) 和I(x)分别表示的命题如下：
105 Q(x)：x 是有理数；R(x)：x 是实数；I(x)：x 是整数。于是推理可表示为： x(Q(x)→ R(x))
∧ x(Q(x)∧I(x)) x(R(x)∧I(x))。
该式也正是例2 中的推理。语法推理证明如下：
1) x(Q(x)∧I(x)) 前提
2) Q(c)∧I(c) ①，ES
110 3) x(Q(x)→R(x)) 前提
4) Q(c)→R(c) ③，US
5) Q(c) ②，I4
6) R(c) ④⑤，I1
7) I(c) ②，I4
115 8) R(c)∧I(c) ⑥⑦，I3
9) x(R(x)∧I(x)) ⑧，EG
从上述两例的语法推理看，推理的每一步是通过判断公式的形式进行的，这与语义推理
的每一步都要考虑公式的真值完全不同。由于计算机不具有判别命题真假的思维能力，而识
别公式的形式却是其容易完成的工作，所以语法推理作为计算机推理的理论基础是非常自然
 120 的。在所建立的推理规则系统之上，通过识别、判定公式的形式而展开的语法推理是最适合
计算机推理的方法。在研究推理方面，还没有其他方法比语法推理的思想更能被计算机所接
受。因此，语法推理是智能推理研究的一种有效方法。文献[6]给出了结合语法推理与语义
推理的研究结果。
3 题推理的算法问题
125 语义和语法推理是命题逻辑和谓词逻辑（乃至某些非经典逻辑）中研究的两种推理方法。
语法推理中所建立的推理规则系统不仅具有可靠性，而且还具有完备性。这是理论上已经证
明的著名结论，它们可分别通俗地叙述如下：
可靠性：一个命题如果可以用语法推理证之，则一定也可以用语义推理证之。
完备性：一个命题如果可以用语义推理证之，则一定也可以用语法推理证之。
130 可靠性和完备性说明在命题逻辑和谓词逻辑中，语义推理和语法推理可以相互代替。所
以，对于命题逻辑来说，真值表法就是其推理（无论是语义推理还是语法推论）的算法。但
由于命题逻辑描述能力的有限性，其算法的作用在实际应用中显得微不足道。所以，下面针
对谓词逻辑来讨论推理的算法。
前面给出的语法推理规则I1 至I4、ES、US 以及EG 是例3、例4 推理的基础。当然还
135 可以再加入一些规则，形成更强的推理规则系统。如下内容将以I1 至I4、ES、US 以及EG
为推理系统，以语法推理的思想为基础给出逻辑推理的算法。
原创学术论文网Tag：计算机论文 代写代发论文 代写毕业设计 计算机发表 代写理工论文