第 4章 一阶逻辑基本概念离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 一阶逻辑基本概念,命题符号化
– 一阶逻辑公式,解释及分类
本章与后续各章的关系
– 克服命题逻辑的局限性
– 是第五章的先行准备引言
命题逻辑的局限性在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。
例如：
所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
这个简单而有名的苏格拉底三段论，却无法用命题逻辑予以证明。
一阶逻辑所研究的内容为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到 表达出个体与总体的内在联系和数量关系 。
本章内容
4.1 一阶逻辑命题符号化
4.2 一阶逻辑公式及解释本章小结习题作业
4.1一阶逻辑命题符号化
一阶逻辑命题符号化的三个基本要素
– 个体词
– 谓词
– 量词
个体词及相关概念
个体词一般是充当主语的名词或代词。说明
个体词,指所研究对象中可以独立存在的具体或抽象的客体 。
举例
– 命题：电子计算机是科学技术的工具。
个体词：电子计算机。
– 命题：他是三好学生 。
个体词：他。
个体常项,表示具体或特定的客体的个体词,用小写字母 a,
b,c,… 表示 。
个体变项,表示抽象或泛指的客体的个体词,用 x,y,z,… 表示 。
个体域 （ 或称论域 ）,指个体变项的取值范围 。
– 可以是有穷集合,如 {a,b,c},{1,2}。
– 可以是无穷集合,如 N,Z,R,… 。
全总个体域 （ universe） —— 宇宙间一切事物组成 。
个体词及相关概念
本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。
说明谓词及相关概念
谓词（ predicate） 是用来刻画个体词性质及个体词之间相互关系的词。
(1)?是无理数。
是个体常项,,? 是无理数,是谓词，记为 F,命题符号化为 F(?) 。
(2) x是有理数。
x是个体变项,,? 是有理数,是谓词，记为 G,命题符号化为 G(x)。
(3) 小王与小李同岁。
小王、小李都是个体常项,,? 与? 同岁,是谓词，记为 H
,命题符号化为 H(a,b),其中 a,小王,b：小李 。
(4) x与 y具有关系 L。
x,y都是个体变项，谓词为 L,命题符号化为 L(x,y)。
谓词常项,表示具体性质或关系的谓词。用大写字母表示。
如 (1),(2),(3) 中谓词 F,G,H。
谓词变项,表示抽象的、泛指的性质或关系的谓词。用大写字母表示。如 (4) 中谓词 L。
n(n?1)元谓词,P(x1,x2,…,xn)表示含 n个命题变项的 n元谓词。
– n=1时，一元谓词 —— 表示 x1具有性质 P。
– n≥2 时，多元谓词 —— 表示 x1,x2,…,xn具有关系 P。
0元谓词,不含个体变项的谓词。如 F(a),G(a,b)、
P(a1,a2,…,an)。
n元谓词是命题吗？
不是，只有用谓词常项取代 P,用个体常项取代
x1,x2,…,xn时，才能使 n元谓词变为命题。
思考谓词及相关概念例题例 4.1 将下列命题在一阶逻辑中用 0元谓词符号化，并讨论真值。
(1)只有 2是素数,4才是素数。
(2)如果 5大于 4，则 4大于 6,
解：
(1)设一元谓词 F(x):x是素数,a:2,b:4。
命题符号化为 0元谓词的蕴涵式
F(b)→F(a)
由于此蕴涵前件为假，所以命题为真。
(2)设二元谓词 G(x,y):x大于 y,a:4,b:5,c:6。
命题符号化为 0元谓词的蕴涵式
G(b,a)→G(a,c)
由于 G(b,a)为真，而 G(a,c)为假，所以命题为假。
例题将命题,这只大红书柜摆满了那些古书。,符号化,
(1)设 F(x,y),x摆满了 y,R(x),x是大红书柜
Q(y),y是古书,a,这只，
b,那些符号化为,R(a)∧Q(b)∧F(a,b)
(2)设 A(x),x是书柜,B(x),x是大的
C(x),x是红的,D(y),y是古老的
E(y),y是图书,F(x,y),x摆满了 y
a,这只 b,那些符号化为,A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)
量词 （ quantifiers） 是表示个体常项或个体变项之间数量关系的词 。
1,全称量词,符号化为,?”
日常生活和数学中所用的,一切的,,,所有的,,,每一个,,,任意的,,,凡,,,都,等词可统称为全称量词
。
x表示个体域里的所有个体,?xF(x)表示个体域里所有个体都有性质 F。
2.存在量词,符号化为,?”
日常生活和数学中所用的,存在,,,有一个,,,有的,
,,至少有一个,等词统称为存在量词 。
y表示个体域里有的个体,?yG(y)表示个体域里存在个体具有性质 G等 。
量词及相关概念例 4.2 在个体域分别限制为 (a)和 (b)条件时，将下面两个命题符号化,
(1) 凡人都呼吸。
(2) 有的人用左手写字。
其中,(a)个体域 D1为人类集合；
(b)个体域 D2为全总个体域。
一阶逻辑命题符号化解,(a)个体域为人类集合。
令 F(x):x呼吸。 G(x):x用左手写字。
(1) 在个体域中除了人外，再无别的东西，因而,凡人都呼吸,应符号化为
xF(x)
(2) 在个体域中除了人外，再无别的东西，因而,有的人用左手写字,符号化为
xG(x)
(b)个体域为全总个体域 。
即除人外，还有万物，所以必须考虑将人先分离出来。
令 F(x):x呼吸。 G(x):x用左手写字。 M(x):x是人。
(1),凡人都呼吸,应符号化为
x(M(x)→F(x))
(2),有的人用左手写字,符号化为
x(M(x)∧G(x))
在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词 M(x),称为 特性谓词 。
同一命题在不同的个体域中符号化的形式可能不同。
思考,在全总个体域中，能否将 (1)符号化为
x(M(x)∧F(x))？ 能否将 (2)符号化为?x(M(x)→G(x))？
结论例题例 4.3 在个体域限制为 (a)和 (b)条件时，将下列命题符号化,
(1) 对于任意的 x,均有 x2-3x+2=(x-1)(x-2)。
(2) 存在 x,使得 x+5=3。
其中,(a)个体域 D1=N(N为自然数集合 )
(b)个体域 D2=R(R为实数集合 )
(a)令 F(x),x2-3x+2=(x-1)(x-2),G(x),x+5=3。
命题 (1)的符号化形式为?xF(x) （ 真命题）
命题 (2)的符号化形式为?xG(x)) （ 假命题）
(b)在 D2内,(1)和 (2)的符号化形式同 (a),皆为真命题。
在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。
同一个命题，在不同个体域中的真值也可能不同。
说明例 4.4 将下列命题符号化，并讨论真值。
（ 1）所有的人长着黑头发。
（ 2）有的人登上过月球。
（ 3）没有人登上过木星。
（ 4）在美国留学的学生未必都是亚洲人。
分析：谓词逻辑中命题的符号化，主要考虑：
(1)非空个体域的选取。若是为了确定命题的真值，一般约定在某个个体域上进行，否则，在由一切事物构成的全总个体域上考虑问题时，需要增加一个指出个体变量变化范围的特性谓词。
(2)量词的使用及作用范围。
(3)正确地语义。
例题例题解：没有提出个体域，所以认为是全总个体域。
（ 1）所有的人长着黑头发。
令 F(x):x长着黑头发,M(x):x是人。命题符号化为
x(M(x)→F(x)) 。
命题真值为假。
（ 2）有的人登上过月球。
令 G(x):x登上过月球,M(x):x是人。命题符号化为
x(M(x)∧G(x)) 。
命题真值为真。
例题
（ 3）没有人登上过木星。
令 H(x):x登上过木星,M(x):x是人。命题符号化为
┐?x(M(x)∧H(x)) 。
命题真值为真。
（ 4）在美国留学的学生未必都是亚洲人。
令 F(x):x是在美国留学的学生,G(x):x是亚洲人。符号化
┐?x(F(x)→G(x))
命题真值为真。
例题 n元谓词的符号化例 4.5 将下列命题符号化
（ 1）兔子比乌龟跑得快。
（ 2）有的兔子比所有的乌龟跑得快。
（ 3）并不是所有的兔子都比乌龟跑得快。
（ 4）不存在跑得同样快的两只兔子。
解,令 F(x):x是兔子,G(y):y是乌龟，
H(x,y):x比 y跑得快,L(x,y):x与 y跑得同样快。
（ 1）?x?y(F(x)∧G(y)?H(x,y))
（ 2）?x(F(x)∧?y(G(y)?H(x,y)))
（ 3） ┐?x?y(F(x)∧G(y)?H(x,y))
（ 4） ┐?x?y(F(x)∧F(y)∧L(x,y) )
一阶逻辑命题符号化时需要注意的事项
分析命题中表示性质和关系的谓词，分别符号为一元和 n（
n?2） 元谓词。
根据命题的实际意义选用全称量词或存在量词。
一般说来，多个量词出现时，它们的顺序不能随意调换。
– 例如,考虑个体域为实数集,H(x,y)表示 x+y=10，
– 则命题,对于任意的 x,都存在 y,使得 x+y=10”的符号化形式为?x?yH(x,y),为真命题 。
– 如果改变两个量词的顺序,得?y?xH(x,y),为假命题 。
有些命题的符号化形式可不止一种。（例 4.5之 (3)）
–x?y(F(x)∧G(y)?H(x,y))
–?x?y(F(x)∧G(y)∧ ┐ H(x,y))
4.2一阶逻辑公式及解释
同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，
必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。
一阶语言 是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。
一阶语言的形式是多种多样的,本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为 F。
一阶语言中的字母表定义 4.1 一阶语言 F的 字母表 定义如下,
(1)个体常项,a,b,c,…,ai,bi,ci,…,i?1
(2)个体变项,x,y,z,…,xi,yi,zi,…,i?1
(3)函数符号,f,g,h,…,fi,gi,hi,…,i?1
(4)谓词符号,F,G,H,…,Fi,Gi,Hi,…,i?1
(5)量词符号,?,?
(6)联结词符号,┐,∧,∨,→,?
(7)括号与逗号,(,),，
一阶语言中的项定义 4.2 一阶语言 F的 项 的定义如下,
(1) 个体常项和个体变项是 项 。
(2) 若?(x1,x2,…,xn)是任意的 n元函数,t1,t2,…,tn是任意的 n个项，则?(t1,t2,…,tn)是 项 。
(3) 所有的项都是有限次使用 (1),(2)得到的。
一阶语言中的原子公式定义 4.3 设 R(x1,x2,…,xn)是一阶语言 F的任意 n元谓词，
t1,t2,…,tn是一阶语言 F的任意的 n个项，则称
R(t1,t2,…,tn)是一阶语言 F的 原子公式 。
例如,1元谓词 F(x),G(x),2元谓词 H(x,y),L(x,y)等都是原子公式。
一阶语言 F的合式公式定义 4.4 一阶语言 F的 合式公式 定义如下,
(1) 原子公式是合式公式。
(2) 若 A是合式公式，则 (┐ A)也是合式公式。
(3) 若 A,B是合式公式，则 (A∧B),(A∨B),(A→B),(A?B)
也是合式公式。
(4) 若 A是合式公式，则?xA,?xA也是合式公式。
(5) 只有有限次的应用 (1)～ (4)构成的符号串才是合式公式。
一阶语言 F的合式公式也称为 谓词公式,简称 公式 。
A,B代表任意公式，是元语言符号。
下文的讨论都是在一阶语言 F中，因而不再提及。
说明自由出现与约束出现定义 4.5 指导变元、辖域、约束出现、自由出现
在公式?xA和?xA中，称 x为 指导变元 。
在公式?xA和?xA中,A为相应量词的 辖域 。
在?x和?x的辖域中,x的所有出现都称为 约束出现 。
A中不是约束出现的其他变项均称为是 自由出现 的。
例 4.6 指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。
(1)?x(F(x,y)→G( x,z))
(2)?x(F(x)→G(y))→?y(H(x)∧L(x,y,z))
例题解答 (1) x是指导变元。量词?的辖域 A=(F(x,y)→G(x,z)) 。 在 A
中,x的两次出现均是约束出现。 y和 z均为自由出现。
(2) 前件上量词?的指导变元为 x,量词?的辖域
A=(F(x)→G(y)),x在 A中是约束出现的,y在 A中是自由出现的。后件中量词?的指导变元为 y,量词?的辖域为
B=(H(x)∧L(x,y,z)),y在 B中是约束出现的,x,z在 B中均为自由出现的。
本书中的记法
用 A(x1,x2,…,xn)表示含 x1,x2,…,xn自由出现的公式。
用 Δ 表示任意的量词?或?,则 Δx 1A(x1,x2,…,xn)是含有 x2,x3,…,xn自由出现的公式，可记为 A1(x2,x3,…,xn)。
类似的,Δx 2Δx 1A(x1,x2,…,xn)可记为 A2(x3,x4,…,xn)
Δx n-1Δx n-2… Δx 1A(x1,x2,…,xn)中只含有 xn是自由出现的个体变项，可以记为 An-1(xn)。
Δx n… Δx 1A(x1,x2,…,xn)没有自由出现的个体变项。
举例 将例 4.6(1)中的公式简记为 A(y,z),表明公式含有自由出现的个体变项 y,z。 而?yA(y,z)中只含有 z为自由出现的公式,?z?yA(y,z)中已经没有自由出现的个体变项了，
闭式定义 4.6 设 A是任意的公式，若 A中不含有自由出现的个体变项，则称 A为 封闭的公式,简称 闭式 。
例如,?x?y(F(x)?G(y)?H(x,y)) 为闭式，
x(F(x)?G(x,y)) 不是闭式 。
一阶公式的解释一阶公式没有确定的意义,一旦将其中的变项 （ 项的变项,谓词变项 ） 用指定的常项代替后,所得公式就具备一定的意义,有时就变成命题了 。
例题 4.7
例 4.7 将下列两个公式中的变项指定成常项使其成为命题,
(1)?x(F(x)→G(x))
(2)?x?y(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))
(1)指定个体变项的变化范围，并且指定谓词 F,G的含义，下面给出两种指定法,
(a)令个体域 D1为全总个体域，
F(x)为 x是人，
G(x)为 x是黄种人，
则命题为,所有人都是黄种人,,这是假命题。
(b)令个体域 D2为实数集合 R，
F(x)为 x是自然数，
G(x)为 x是整数，
则命题为,自然数都是整数,,这是真命题。
例题 4.7
(2)?x?y(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))
含有两个 2元函数变项，两个 1元谓词变项，两个 2元谓词变项。
指定个体域为全总个体域，
F(x)为 x是实数,G(x,y)为 x≠y,
H(x,y)为 x>y,f(x,y)=x2+y2，
g(x,y)=2xy，
则表达的命题为,对于任意的 x,y,若 x与 y都是实数，且
x≠y,则 x2+y2>2xy”,这是真命题。
如果 H(x,y)改为 x<y，
则所得命题为假命题。
一阶公式的解释定义 4.7 一阶公式的解释 I由下面 4部分组成,
(a)非空个体域 DI。
(b)DI中一些特定元素的集合 。
(c)DI上特定函数集合 { |i,n≥1} 。
(d)DI上特定谓词的集合 { |i,n≥1} 。
12{,,,}ia a a
n
if
n
iF
为第 i个 n元谓词，如 i=2,n=3时,表示第 2个 3元谓词，它可能以 (x,y,z)的形式出现在解释中，公式 A若出现 F2(x,y,z)就解释成 (x,y,z)。
为第 i个 n元函数。例如,i=1,n=2时,表示第一个二元函数，它出现在解释中，可能是 (x,y)=x2+y2，
(x,y)=2xy等，一旦公式中出现 f1(x,y)就解释成
(x,y),出现 g1(x,y)就解释成 (x,y)=2xy。
对解释 I的几点说明
被解释的公式不一定全部包含解释中的四部分。
nif 21f
1f
1g 1f
1g
niF 32F
2F
2F
在解释的公式 A中的个体变项均取值于 DI。
若 A中含有个体常项,就解释成 。
ia
在解释的定义中引进了几个元语言符号，如
ia
n
if niF
例 4.8 给定解释 I如下,
(a) 个体域 D=N(N为自然数集合，即 N={0,1,2,… })
(b) =0a
(c) (x,y)=x+y,(x,y)=x?y。f g
(d) (x,y)为 x=y。F
在 I下，下列哪些公式为真?哪些为假?哪些的真值还不能确定?
例题 4.8
例题 4.8
(1) F(f(x,y),g(x,y))
(2) F(f(x,a),y)→F(g(x,y),z)
(3) ┐F(g(x,y),g(y,z))
(4)?x F(g(x,y),z)
(5)?x F(g(x,a),x)→F(x,y)
(6)?x F(g(x,a),x)
(7)?x?y(F(f(x,a),y)→F(f(y,a),x))
(8)?x?y?z F(f(x,y),z)
(9)?x F(f(x,x),g(x,x))
例题 4.8
(1) F(f(x,y),g(x,y))
公式被解释成,x+y=x· y”,这不是命题。
(2) F(f(x,a),y)→F(g(x,y),z)
公式被解释成,(x+0=y)→(x · y=z)”,这也不是命题。
(3) ┐F(g(x,y),g(y,z))
公式被解释成,x· y≠y · z”,同样不是命题。
(4)?x F(g(x,y),z)
公式被解释成,?x(x· y=z)”,不是命题。
例题 4.8
(5)?x F(g(x,a),x)→F(x,y)
公式被解释成,?x(x· 0=x)→(x=y),,由于前件为假，所以被 解释的公式为真。
(6)?x F(g(x,a),x)
公式被解释成,?x(x· 0=x)”,为假命题。
(7)?x?y(F(f(x,a),y)→F(f(y,a),x))
公式被解释成,?x?y((x+0=y)→(y+0=x)),,为真命题。
(8)?x?y?z F(f(x,y),z)
公式被解释成,?x?y?z(x+y=z)”,这也为真命题。
(9)?x F(f(x,x),g(x,x))
公式被解释成,?x(x+x=x· x)”,为真命题。
闭式在给定的解释中都变成了命题。如 (6)?(8)。
不是闭式的公式在某些解释下也可能变为命题。如 (5)。
结论例题 4.8
定理 4.1 封闭的公式在任何解释下都变成命题。
一阶公式的分类定义 4.8 永真式、永假式、可满足式
设 A为一个公式，若 A在任何解释下均为真，则称 A为 永真式
(或称 逻辑有效式 )。
设 A为一个公式，若 A在任何解释下均为假，则称 A为 矛盾式
(或 永假式 )。
设 A为一个公式，若至少存在一个解释使 A为真，则称 A为 可满足式 。
永真式一定是可满足式，但可满足式不一定是永真式。
在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。
但对某些特殊的公式还是可以判断的。
说明代换实例定义 4.9 设 A0是含有命题变项 p1,p2,…,pn的命题公式，
A1,A2,…,An是 n个谓词公式，用 Ai(1≤i≤n) 处处代替 A0
中的 pi,所得公式 A称为 A0的 代换实例 。
例如,F(x)?G(x),?xF(x)yG(y)等都是 p?q的代换实例，而?x(F(x)?G(x))等不是 p?q的代换实例。
定理 4.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。
例 4.9 判断下列公式中，哪些是永真式，哪些是矛盾式？
（ 1）?x(F(x)?G(x))
（ 2）?x(F(x)?G(x))
（ 3）?xF(x)?(?x?yG(x,y)xF(x))
（ 4）?(?xF(x)yG(y))yG(y)
解,(1)?x(F(x)?G(x))
解释 1：个体域为实数集合 R,F(x),x是整数,G(x),x是有理数，因此公式真值为真。
解释 2：个体域为实数集合 R,F(x),x是无理数,G(x),x能表示成分数，因此公式真值为假。
所以公式为非永真式的可满足式。
例题 4.9
例题 4.9
（ 2）?x(F(x)?G(x))
公式为非永真式的可满足式。
（ 3）?xF(x)?(?x?yG(x,y)xF(x))
为 p?(q?p)（ 重言式 ） 的代换实例,故为永真式 。
（ 4）?(?xF(x)yG(y))yG(y)
为?(p?q)?q（ 矛盾式）的代换实例，故为永假式。
例题例 4.10 判断下列公式的类型。
(1)?xF(x) →?xF(x)
(2)?x?yF(x,y)→?x?yF(x,y)
(3)?x(F(x)∧G(x)) →?yG(y)
解 记 (1),(2),(3)中的公式分别为 A,B,C。
(1)设 I为任意一个解释，个体域为 D。
若存在 x0∈D,使得 F(x0)为假，则?xF(x)为假，所以 A的前件为假，故 A为真。
若对于任意 x∈D,F(x)均为真，则?xF(x),?xF(x)都为真
，从而 A为真。
所以在 I下 A为真。由 I的任意性可知,A是永真式。
例题
(2)?x?yF(x,y)→?x?yF(x,y)
取解释 I,个体域为自然数集合 N,F(x,y)为 x≤y 。
在 I下 B的前件与后件均为真，所以 B为真。这说明 B不是矛盾式。（ 在?x?yF(x,y)中,x＝ 0 ）
再取 I‘,个体域仍然为 N,F(x,y)为 x=y。
在 I’下,B的前件真而后件假，所以 B为假。这说明 B不是永真式。
故 B是非永真式的可满足式。
(3)?x(F(x)∧G(x)) →?yG(y)
C也是非永真式的可满足式。
小节结束本章主要内容
个体词
①个体常项
②个体变项
③个体域
④全总个体域
谓词
①谓词常项
②谓词变项
③ n(n≥1) 元谓词
④特性谓词
量词
①全称量词
②存在量词本章主要内容
一阶逻辑中命题符号化
一阶逻辑公式
①原子公式
②合式公式（或公式）
③闭式
解释
一阶逻辑公式的分类
①逻辑有效式（或永真式）
②矛盾式（或永假式）
③可满足式本章学习要求
要求准确地将给出的命题符号化：
①当给定个体域时，在给定个体域内将命题符号化。
②当没给定个体域时，应在全总个体域内符号化。
③在符号化时，当引入特性时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。
深刻理解逻辑有效式、矛盾式、可满足式的概念。
记住闭式的性质：在任何解释下均为命题。
对给定的解释，会判别公式的真值或不能确定真值。
小节结束习题选讲 — 命 题符号化
1,在一阶逻辑中将下列命题符号化。
（ 1） 每个人都有心脏。
（ 2） 有的狗会飞。
（ 3） 没有不犯错误的人。
（ 4） 发光的不都是金子。
（ 5） 一切人都不一样高。
（ 6） 并不是所有的汽车都比火车快。
（ 7） 没有一个自然数大于等于任何自然数。
（ 8） 有唯一的偶素数。
（ 9） 不管黑猫白猫，抓住老鼠就是好猫。
（ 10）对平面上任意两点，有且仅有一条直线通过这两点。
习题选讲 — 命 题符号化解：由于没指出个体域,故用全总个体域
（ 1） 每个人都有心脏 。
本命题的含义：对于每一个 x,如果 x是人,则 x有心脏 。
因而应首先从宇宙间的一切事物中,将人分离出来,这就必须引入特性谓词 。
令 M(x):x是人,H(x):x有心脏。
命题符号化为,?x(M(x)→ H(x))
如果将其中的 → 改为 ∧,即?x(P(x)∧H(x)),它表示的意思是：,对于每个 x,x是人且 x有心脏,。这是一个假命题，而
,每个人都有心脏,是真命题。
这说明将命题,每个人都有心脏,符号化为 (x)(P(x)∧H(x))
是错误的。
习题选讲 — 命 题符号化
（ 2） 有的狗会飞 。
命题的意思是：存在一个 x,使得 x是狗,并且 x会飞 。
设 D(x),x是狗,F(x),x会飞 。
命题符号化为,?x(D(x)∧ F(x))
如果将其中的 ∧ 改为 →,即?x(D(x)→F(x)),
如果用 a表示某只猫,则 D(a)为假,因而,D(a)→F(a) 为真,
所以?x(D(x)→F(x)) 为真,而,有的狗会飞,为假,
这说明将,有的狗会飞,符号化为 (x)(D(x)→F(x)) 是错误的
。
习题选讲 — 命 题符号化
（ 3） 没有不犯错误的人 。
命题的意思是,① 存在不犯错误的人是不可能的 。
② 只要是人,必然犯错误 。
设 M(x),x是人,F(x):x犯错误命题符号化为
① ┐?x(M(x)∧ ┐ F(x))
②?x(M(x)→F(x))
习题选讲 — 命 题符号化
（ 4） 发光的不都是金子 。
命题的意思是,① 不是发光的东西都是金子 。
② 存在着发光的东西不是金子 。
设 L(x),x是发光的东西,G(x),x是金子 。
命题符号化为
① ┐?x(L(x)→G(x))
②?x(L(x)∧ ﹁ G(x))
（ 5） 一切人都不一样高 。
设 F(x):x是人,H(x,y),x与 y相同,L(x,y),x与 y一样高,
命题符号化为
x(F(x)y(F(y)H(x,y)L(x,y)))
或?x?y(F(x)?F(y)H(x,y)L(x,y))
（ 6） 并不是所有的汽车都比火车快 。
设 F(x):x是汽车,G(y):y是火车,H(x,y):x比 y快,
命题符号化为
x?y(F(x)?G(y)?H(x,y))
或?x?y(F(x)?G(y)H(x,y))
习题选讲 — 命 题符号化习题选讲 — 命 题符号化
（ 7）没有一个自然数大于等于任何自然数。
设 N(x):x是自然数,G(x,y):x?y
命题符号化为：
x(N(x)y(N(y)?G(x,y)))
（ 8） 有唯一的偶素数 。
设,Q(x):x是偶数,P(x):x是素数,E(x,y):x＝ y
命题符号化为：
x(Q(x)?P(x)y(Q(y)?P(y)E(x,y)))
习题选讲 — 命 题符号化
（ 9） 不管黑猫白猫,抓住老鼠就是好猫 。
需要考虑问题：
① 只是限制黑猫白猫,还是包含其它颜色的猫？
②是指至少抓住一只就可以，还是抓住所有的？
因此在描述命题时，总是将这些模糊概念做某种确切理解。
设 C(x),x是猫,W(x),x是白的,B(x),x是黑的
G(x),x是好的,M(x),x是老鼠,K(x),x抓住 y
命题符号化为
x?y(C(x)∧M(y)∧(B(x)∨W(x))∧K(x,y))→G(x))
习题选讲 — 命 题符号化
（ 10）对平面上任意两点，有且仅有一条直线通过这两点。
设 P(x),x是一个点,L(x),x是一条直线
R(x,y,z),z通过 x,y,E(x,y),x等于 y
命题符号化为
x?y(P(x)∧P(y)∧ ﹁ E(x,y))
→?z(L(z)∧R(x,y,z)∧?u((L(u)∧R(x,y,u))→E(u,z)))
习题选讲 — 公式 判 断
2、判断下列各式是否是永真式？证明你的判断。
(1)?x(F(x)?G(x))
(2)?x(F(x)?G(x))
(3)?x?y(F(x)?G(y)?H(x,y))
(4)?x?y(P(x,y)?Q(a,y))x?y(P(x,y)?Q(x,y))
其中 a是个体常元。
解：
(1) 不是永真式 。
(2) 不是永真式 。
(3) 不是永真式 。
(4) 不是永真式 。
(4)?x?y(P(x,y)?Q(a,y))x?y(P(x,y)?Q(x,y))
其中 a是个体常元。
令个体域为某个元素个数大于等于 2的有限整数集，其中 a为最小的数。
P(x,y),x大于等于 y，
Q(x,y),x小于等于 y。
x?yP(x,y)?Q(a,y)解释为：存在一个 x,对于所有的 y,有
x大于等于 y,并且 a小于等于 y。 命题为真，只要取 x为个体域中最大数即可。
x?y(P(x,y)?Q(x,y))解释为：存在一个 x,对于所有的 y，
有 x大于等于 y,并且 x小于等于 y。 命题为假。
3,判断下列公式是否为永真公式 。
（ 1） (?x A(x)x B(x))x (A(x)? B(x))
（ 2） (?x A(x)x B(x))x (A(x)? B(x))
（ 3） (?x A(x)x B(x))x (A(x)? B(x))
（ 4） (?x A(x)x B(x))x (A(x)? B(x))
解：
（ 1） 永真公式 。
（ 2） 不是永真公式 。
（ 3） 永真公式 。
（ 4） 永真公式 。
小节结束习题选讲 — 公式 判 断作业习题四,2,3,4,5,9,10,14
结束习题说明
判断下面推理是否正确。先将简单命题符号化，再写出前提、结论、推理的形式结构（以蕴涵式的形式给出）和判断过程（至少给出两种判断方法）：
（ 5）若今天是星期一，则明天是星期二或星期三。
推理形式结构为
p→(q∨r)
它不是重言式，故推理不正确。
本章的主要内容
– 一阶逻辑基本概念,命题符号化
– 一阶逻辑公式,解释及分类
本章与后续各章的关系
– 克服命题逻辑的局限性
– 是第五章的先行准备引言
命题逻辑的局限性在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。
例如：
所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
这个简单而有名的苏格拉底三段论，却无法用命题逻辑予以证明。
一阶逻辑所研究的内容为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到 表达出个体与总体的内在联系和数量关系 。
本章内容
4.1 一阶逻辑命题符号化
4.2 一阶逻辑公式及解释本章小结习题作业
4.1一阶逻辑命题符号化
一阶逻辑命题符号化的三个基本要素
– 个体词
– 谓词
– 量词
个体词及相关概念
个体词一般是充当主语的名词或代词。说明
个体词,指所研究对象中可以独立存在的具体或抽象的客体 。
举例
– 命题：电子计算机是科学技术的工具。
个体词：电子计算机。
– 命题：他是三好学生 。
个体词：他。
个体常项,表示具体或特定的客体的个体词,用小写字母 a,
b,c,… 表示 。
个体变项,表示抽象或泛指的客体的个体词,用 x,y,z,… 表示 。
个体域 （ 或称论域 ）,指个体变项的取值范围 。
– 可以是有穷集合,如 {a,b,c},{1,2}。
– 可以是无穷集合,如 N,Z,R,… 。
全总个体域 （ universe） —— 宇宙间一切事物组成 。
个体词及相关概念
本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。
说明谓词及相关概念
谓词（ predicate） 是用来刻画个体词性质及个体词之间相互关系的词。
(1)?是无理数。
是个体常项,,? 是无理数,是谓词，记为 F,命题符号化为 F(?) 。
(2) x是有理数。
x是个体变项,,? 是有理数,是谓词，记为 G,命题符号化为 G(x)。
(3) 小王与小李同岁。
小王、小李都是个体常项,,? 与? 同岁,是谓词，记为 H
,命题符号化为 H(a,b),其中 a,小王,b：小李 。
(4) x与 y具有关系 L。
x,y都是个体变项，谓词为 L,命题符号化为 L(x,y)。
谓词常项,表示具体性质或关系的谓词。用大写字母表示。
如 (1),(2),(3) 中谓词 F,G,H。
谓词变项,表示抽象的、泛指的性质或关系的谓词。用大写字母表示。如 (4) 中谓词 L。
n(n?1)元谓词,P(x1,x2,…,xn)表示含 n个命题变项的 n元谓词。
– n=1时，一元谓词 —— 表示 x1具有性质 P。
– n≥2 时，多元谓词 —— 表示 x1,x2,…,xn具有关系 P。
0元谓词,不含个体变项的谓词。如 F(a),G(a,b)、
P(a1,a2,…,an)。
n元谓词是命题吗？
不是，只有用谓词常项取代 P,用个体常项取代
x1,x2,…,xn时，才能使 n元谓词变为命题。
思考谓词及相关概念例题例 4.1 将下列命题在一阶逻辑中用 0元谓词符号化，并讨论真值。
(1)只有 2是素数,4才是素数。
(2)如果 5大于 4，则 4大于 6,
解：
(1)设一元谓词 F(x):x是素数,a:2,b:4。
命题符号化为 0元谓词的蕴涵式
F(b)→F(a)
由于此蕴涵前件为假，所以命题为真。
(2)设二元谓词 G(x,y):x大于 y,a:4,b:5,c:6。
命题符号化为 0元谓词的蕴涵式
G(b,a)→G(a,c)
由于 G(b,a)为真，而 G(a,c)为假，所以命题为假。
例题将命题,这只大红书柜摆满了那些古书。,符号化,
(1)设 F(x,y),x摆满了 y,R(x),x是大红书柜
Q(y),y是古书,a,这只，
b,那些符号化为,R(a)∧Q(b)∧F(a,b)
(2)设 A(x),x是书柜,B(x),x是大的
C(x),x是红的,D(y),y是古老的
E(y),y是图书,F(x,y),x摆满了 y
a,这只 b,那些符号化为,A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)
量词 （ quantifiers） 是表示个体常项或个体变项之间数量关系的词 。
1,全称量词,符号化为,?”
日常生活和数学中所用的,一切的,,,所有的,,,每一个,,,任意的,,,凡,,,都,等词可统称为全称量词
。
x表示个体域里的所有个体,?xF(x)表示个体域里所有个体都有性质 F。
2.存在量词,符号化为,?”
日常生活和数学中所用的,存在,,,有一个,,,有的,
,,至少有一个,等词统称为存在量词 。
y表示个体域里有的个体,?yG(y)表示个体域里存在个体具有性质 G等 。
量词及相关概念例 4.2 在个体域分别限制为 (a)和 (b)条件时，将下面两个命题符号化,
(1) 凡人都呼吸。
(2) 有的人用左手写字。
其中,(a)个体域 D1为人类集合；
(b)个体域 D2为全总个体域。
一阶逻辑命题符号化解,(a)个体域为人类集合。
令 F(x):x呼吸。 G(x):x用左手写字。
(1) 在个体域中除了人外，再无别的东西，因而,凡人都呼吸,应符号化为
xF(x)
(2) 在个体域中除了人外，再无别的东西，因而,有的人用左手写字,符号化为
xG(x)
(b)个体域为全总个体域 。
即除人外，还有万物，所以必须考虑将人先分离出来。
令 F(x):x呼吸。 G(x):x用左手写字。 M(x):x是人。
(1),凡人都呼吸,应符号化为
x(M(x)→F(x))
(2),有的人用左手写字,符号化为
x(M(x)∧G(x))
在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词 M(x),称为 特性谓词 。
同一命题在不同的个体域中符号化的形式可能不同。
思考,在全总个体域中，能否将 (1)符号化为
x(M(x)∧F(x))？ 能否将 (2)符号化为?x(M(x)→G(x))？
结论例题例 4.3 在个体域限制为 (a)和 (b)条件时，将下列命题符号化,
(1) 对于任意的 x,均有 x2-3x+2=(x-1)(x-2)。
(2) 存在 x,使得 x+5=3。
其中,(a)个体域 D1=N(N为自然数集合 )
(b)个体域 D2=R(R为实数集合 )
(a)令 F(x),x2-3x+2=(x-1)(x-2),G(x),x+5=3。
命题 (1)的符号化形式为?xF(x) （ 真命题）
命题 (2)的符号化形式为?xG(x)) （ 假命题）
(b)在 D2内,(1)和 (2)的符号化形式同 (a),皆为真命题。
在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。
同一个命题，在不同个体域中的真值也可能不同。
说明例 4.4 将下列命题符号化，并讨论真值。
（ 1）所有的人长着黑头发。
（ 2）有的人登上过月球。
（ 3）没有人登上过木星。
（ 4）在美国留学的学生未必都是亚洲人。
分析：谓词逻辑中命题的符号化，主要考虑：
(1)非空个体域的选取。若是为了确定命题的真值，一般约定在某个个体域上进行，否则，在由一切事物构成的全总个体域上考虑问题时，需要增加一个指出个体变量变化范围的特性谓词。
(2)量词的使用及作用范围。
(3)正确地语义。
例题例题解：没有提出个体域，所以认为是全总个体域。
（ 1）所有的人长着黑头发。
令 F(x):x长着黑头发,M(x):x是人。命题符号化为
x(M(x)→F(x)) 。
命题真值为假。
（ 2）有的人登上过月球。
令 G(x):x登上过月球,M(x):x是人。命题符号化为
x(M(x)∧G(x)) 。
命题真值为真。
例题
（ 3）没有人登上过木星。
令 H(x):x登上过木星,M(x):x是人。命题符号化为
┐?x(M(x)∧H(x)) 。
命题真值为真。
（ 4）在美国留学的学生未必都是亚洲人。
令 F(x):x是在美国留学的学生,G(x):x是亚洲人。符号化
┐?x(F(x)→G(x))
命题真值为真。
例题 n元谓词的符号化例 4.5 将下列命题符号化
（ 1）兔子比乌龟跑得快。
（ 2）有的兔子比所有的乌龟跑得快。
（ 3）并不是所有的兔子都比乌龟跑得快。
（ 4）不存在跑得同样快的两只兔子。
解,令 F(x):x是兔子,G(y):y是乌龟，
H(x,y):x比 y跑得快,L(x,y):x与 y跑得同样快。
（ 1）?x?y(F(x)∧G(y)?H(x,y))
（ 2）?x(F(x)∧?y(G(y)?H(x,y)))
（ 3） ┐?x?y(F(x)∧G(y)?H(x,y))
（ 4） ┐?x?y(F(x)∧F(y)∧L(x,y) )
一阶逻辑命题符号化时需要注意的事项
分析命题中表示性质和关系的谓词，分别符号为一元和 n（
n?2） 元谓词。
根据命题的实际意义选用全称量词或存在量词。
一般说来，多个量词出现时，它们的顺序不能随意调换。
– 例如,考虑个体域为实数集,H(x,y)表示 x+y=10，
– 则命题,对于任意的 x,都存在 y,使得 x+y=10”的符号化形式为?x?yH(x,y),为真命题 。
– 如果改变两个量词的顺序,得?y?xH(x,y),为假命题 。
有些命题的符号化形式可不止一种。（例 4.5之 (3)）
–x?y(F(x)∧G(y)?H(x,y))
–?x?y(F(x)∧G(y)∧ ┐ H(x,y))
4.2一阶逻辑公式及解释
同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，
必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。
一阶语言 是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。
一阶语言的形式是多种多样的,本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为 F。
一阶语言中的字母表定义 4.1 一阶语言 F的 字母表 定义如下,
(1)个体常项,a,b,c,…,ai,bi,ci,…,i?1
(2)个体变项,x,y,z,…,xi,yi,zi,…,i?1
(3)函数符号,f,g,h,…,fi,gi,hi,…,i?1
(4)谓词符号,F,G,H,…,Fi,Gi,Hi,…,i?1
(5)量词符号,?,?
(6)联结词符号,┐,∧,∨,→,?
(7)括号与逗号,(,),，
一阶语言中的项定义 4.2 一阶语言 F的 项 的定义如下,
(1) 个体常项和个体变项是 项 。
(2) 若?(x1,x2,…,xn)是任意的 n元函数,t1,t2,…,tn是任意的 n个项，则?(t1,t2,…,tn)是 项 。
(3) 所有的项都是有限次使用 (1),(2)得到的。
一阶语言中的原子公式定义 4.3 设 R(x1,x2,…,xn)是一阶语言 F的任意 n元谓词，
t1,t2,…,tn是一阶语言 F的任意的 n个项，则称
R(t1,t2,…,tn)是一阶语言 F的 原子公式 。
例如,1元谓词 F(x),G(x),2元谓词 H(x,y),L(x,y)等都是原子公式。
一阶语言 F的合式公式定义 4.4 一阶语言 F的 合式公式 定义如下,
(1) 原子公式是合式公式。
(2) 若 A是合式公式，则 (┐ A)也是合式公式。
(3) 若 A,B是合式公式，则 (A∧B),(A∨B),(A→B),(A?B)
也是合式公式。
(4) 若 A是合式公式，则?xA,?xA也是合式公式。
(5) 只有有限次的应用 (1)～ (4)构成的符号串才是合式公式。
一阶语言 F的合式公式也称为 谓词公式,简称 公式 。
A,B代表任意公式，是元语言符号。
下文的讨论都是在一阶语言 F中，因而不再提及。
说明自由出现与约束出现定义 4.5 指导变元、辖域、约束出现、自由出现
在公式?xA和?xA中，称 x为 指导变元 。
在公式?xA和?xA中,A为相应量词的 辖域 。
在?x和?x的辖域中,x的所有出现都称为 约束出现 。
A中不是约束出现的其他变项均称为是 自由出现 的。
例 4.6 指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。
(1)?x(F(x,y)→G( x,z))
(2)?x(F(x)→G(y))→?y(H(x)∧L(x,y,z))
例题解答 (1) x是指导变元。量词?的辖域 A=(F(x,y)→G(x,z)) 。 在 A
中,x的两次出现均是约束出现。 y和 z均为自由出现。
(2) 前件上量词?的指导变元为 x,量词?的辖域
A=(F(x)→G(y)),x在 A中是约束出现的,y在 A中是自由出现的。后件中量词?的指导变元为 y,量词?的辖域为
B=(H(x)∧L(x,y,z)),y在 B中是约束出现的,x,z在 B中均为自由出现的。
本书中的记法
用 A(x1,x2,…,xn)表示含 x1,x2,…,xn自由出现的公式。
用 Δ 表示任意的量词?或?,则 Δx 1A(x1,x2,…,xn)是含有 x2,x3,…,xn自由出现的公式，可记为 A1(x2,x3,…,xn)。
类似的,Δx 2Δx 1A(x1,x2,…,xn)可记为 A2(x3,x4,…,xn)
Δx n-1Δx n-2… Δx 1A(x1,x2,…,xn)中只含有 xn是自由出现的个体变项，可以记为 An-1(xn)。
Δx n… Δx 1A(x1,x2,…,xn)没有自由出现的个体变项。
举例 将例 4.6(1)中的公式简记为 A(y,z),表明公式含有自由出现的个体变项 y,z。 而?yA(y,z)中只含有 z为自由出现的公式,?z?yA(y,z)中已经没有自由出现的个体变项了，
闭式定义 4.6 设 A是任意的公式，若 A中不含有自由出现的个体变项，则称 A为 封闭的公式,简称 闭式 。
例如,?x?y(F(x)?G(y)?H(x,y)) 为闭式，
x(F(x)?G(x,y)) 不是闭式 。
一阶公式的解释一阶公式没有确定的意义,一旦将其中的变项 （ 项的变项,谓词变项 ） 用指定的常项代替后,所得公式就具备一定的意义,有时就变成命题了 。
例题 4.7
例 4.7 将下列两个公式中的变项指定成常项使其成为命题,
(1)?x(F(x)→G(x))
(2)?x?y(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))
(1)指定个体变项的变化范围，并且指定谓词 F,G的含义，下面给出两种指定法,
(a)令个体域 D1为全总个体域，
F(x)为 x是人，
G(x)为 x是黄种人，
则命题为,所有人都是黄种人,,这是假命题。
(b)令个体域 D2为实数集合 R，
F(x)为 x是自然数，
G(x)为 x是整数，
则命题为,自然数都是整数,,这是真命题。
例题 4.7
(2)?x?y(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))
含有两个 2元函数变项，两个 1元谓词变项，两个 2元谓词变项。
指定个体域为全总个体域，
F(x)为 x是实数,G(x,y)为 x≠y,
H(x,y)为 x>y,f(x,y)=x2+y2，
g(x,y)=2xy，
则表达的命题为,对于任意的 x,y,若 x与 y都是实数，且
x≠y,则 x2+y2>2xy”,这是真命题。
如果 H(x,y)改为 x<y，
则所得命题为假命题。
一阶公式的解释定义 4.7 一阶公式的解释 I由下面 4部分组成,
(a)非空个体域 DI。
(b)DI中一些特定元素的集合 。
(c)DI上特定函数集合 { |i,n≥1} 。
(d)DI上特定谓词的集合 { |i,n≥1} 。
12{,,,}ia a a
n
if
n
iF
为第 i个 n元谓词，如 i=2,n=3时,表示第 2个 3元谓词，它可能以 (x,y,z)的形式出现在解释中，公式 A若出现 F2(x,y,z)就解释成 (x,y,z)。
为第 i个 n元函数。例如,i=1,n=2时,表示第一个二元函数，它出现在解释中，可能是 (x,y)=x2+y2，
(x,y)=2xy等，一旦公式中出现 f1(x,y)就解释成
(x,y),出现 g1(x,y)就解释成 (x,y)=2xy。
对解释 I的几点说明
被解释的公式不一定全部包含解释中的四部分。
nif 21f
1f
1g 1f
1g
niF 32F
2F
2F
在解释的公式 A中的个体变项均取值于 DI。
若 A中含有个体常项,就解释成 。
ia
在解释的定义中引进了几个元语言符号，如
ia
n
if niF
例 4.8 给定解释 I如下,
(a) 个体域 D=N(N为自然数集合，即 N={0,1,2,… })
(b) =0a
(c) (x,y)=x+y,(x,y)=x?y。f g
(d) (x,y)为 x=y。F
在 I下，下列哪些公式为真?哪些为假?哪些的真值还不能确定?
例题 4.8
例题 4.8
(1) F(f(x,y),g(x,y))
(2) F(f(x,a),y)→F(g(x,y),z)
(3) ┐F(g(x,y),g(y,z))
(4)?x F(g(x,y),z)
(5)?x F(g(x,a),x)→F(x,y)
(6)?x F(g(x,a),x)
(7)?x?y(F(f(x,a),y)→F(f(y,a),x))
(8)?x?y?z F(f(x,y),z)
(9)?x F(f(x,x),g(x,x))
例题 4.8
(1) F(f(x,y),g(x,y))
公式被解释成,x+y=x· y”,这不是命题。
(2) F(f(x,a),y)→F(g(x,y),z)
公式被解释成,(x+0=y)→(x · y=z)”,这也不是命题。
(3) ┐F(g(x,y),g(y,z))
公式被解释成,x· y≠y · z”,同样不是命题。
(4)?x F(g(x,y),z)
公式被解释成,?x(x· y=z)”,不是命题。
例题 4.8
(5)?x F(g(x,a),x)→F(x,y)
公式被解释成,?x(x· 0=x)→(x=y),,由于前件为假，所以被 解释的公式为真。
(6)?x F(g(x,a),x)
公式被解释成,?x(x· 0=x)”,为假命题。
(7)?x?y(F(f(x,a),y)→F(f(y,a),x))
公式被解释成,?x?y((x+0=y)→(y+0=x)),,为真命题。
(8)?x?y?z F(f(x,y),z)
公式被解释成,?x?y?z(x+y=z)”,这也为真命题。
(9)?x F(f(x,x),g(x,x))
公式被解释成,?x(x+x=x· x)”,为真命题。
闭式在给定的解释中都变成了命题。如 (6)?(8)。
不是闭式的公式在某些解释下也可能变为命题。如 (5)。
结论例题 4.8
定理 4.1 封闭的公式在任何解释下都变成命题。
一阶公式的分类定义 4.8 永真式、永假式、可满足式
设 A为一个公式，若 A在任何解释下均为真，则称 A为 永真式
(或称 逻辑有效式 )。
设 A为一个公式，若 A在任何解释下均为假，则称 A为 矛盾式
(或 永假式 )。
设 A为一个公式，若至少存在一个解释使 A为真，则称 A为 可满足式 。
永真式一定是可满足式，但可满足式不一定是永真式。
在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。
但对某些特殊的公式还是可以判断的。
说明代换实例定义 4.9 设 A0是含有命题变项 p1,p2,…,pn的命题公式，
A1,A2,…,An是 n个谓词公式，用 Ai(1≤i≤n) 处处代替 A0
中的 pi,所得公式 A称为 A0的 代换实例 。
例如,F(x)?G(x),?xF(x)yG(y)等都是 p?q的代换实例，而?x(F(x)?G(x))等不是 p?q的代换实例。
定理 4.2 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。
例 4.9 判断下列公式中，哪些是永真式，哪些是矛盾式？
（ 1）?x(F(x)?G(x))
（ 2）?x(F(x)?G(x))
（ 3）?xF(x)?(?x?yG(x,y)xF(x))
（ 4）?(?xF(x)yG(y))yG(y)
解,(1)?x(F(x)?G(x))
解释 1：个体域为实数集合 R,F(x),x是整数,G(x),x是有理数，因此公式真值为真。
解释 2：个体域为实数集合 R,F(x),x是无理数,G(x),x能表示成分数，因此公式真值为假。
所以公式为非永真式的可满足式。
例题 4.9
例题 4.9
（ 2）?x(F(x)?G(x))
公式为非永真式的可满足式。
（ 3）?xF(x)?(?x?yG(x,y)xF(x))
为 p?(q?p)（ 重言式 ） 的代换实例,故为永真式 。
（ 4）?(?xF(x)yG(y))yG(y)
为?(p?q)?q（ 矛盾式）的代换实例，故为永假式。
例题例 4.10 判断下列公式的类型。
(1)?xF(x) →?xF(x)
(2)?x?yF(x,y)→?x?yF(x,y)
(3)?x(F(x)∧G(x)) →?yG(y)
解 记 (1),(2),(3)中的公式分别为 A,B,C。
(1)设 I为任意一个解释，个体域为 D。
若存在 x0∈D,使得 F(x0)为假，则?xF(x)为假，所以 A的前件为假，故 A为真。
若对于任意 x∈D,F(x)均为真，则?xF(x),?xF(x)都为真
，从而 A为真。
所以在 I下 A为真。由 I的任意性可知,A是永真式。
例题
(2)?x?yF(x,y)→?x?yF(x,y)
取解释 I,个体域为自然数集合 N,F(x,y)为 x≤y 。
在 I下 B的前件与后件均为真，所以 B为真。这说明 B不是矛盾式。（ 在?x?yF(x,y)中,x＝ 0 ）
再取 I‘,个体域仍然为 N,F(x,y)为 x=y。
在 I’下,B的前件真而后件假，所以 B为假。这说明 B不是永真式。
故 B是非永真式的可满足式。
(3)?x(F(x)∧G(x)) →?yG(y)
C也是非永真式的可满足式。
小节结束本章主要内容
个体词
①个体常项
②个体变项
③个体域
④全总个体域
谓词
①谓词常项
②谓词变项
③ n(n≥1) 元谓词
④特性谓词
量词
①全称量词
②存在量词本章主要内容
一阶逻辑中命题符号化
一阶逻辑公式
①原子公式
②合式公式（或公式）
③闭式
解释
一阶逻辑公式的分类
①逻辑有效式（或永真式）
②矛盾式（或永假式）
③可满足式本章学习要求
要求准确地将给出的命题符号化：
①当给定个体域时，在给定个体域内将命题符号化。
②当没给定个体域时，应在全总个体域内符号化。
③在符号化时，当引入特性时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。
深刻理解逻辑有效式、矛盾式、可满足式的概念。
记住闭式的性质：在任何解释下均为命题。
对给定的解释，会判别公式的真值或不能确定真值。
小节结束习题选讲 — 命 题符号化
1,在一阶逻辑中将下列命题符号化。
（ 1） 每个人都有心脏。
（ 2） 有的狗会飞。
（ 3） 没有不犯错误的人。
（ 4） 发光的不都是金子。
（ 5） 一切人都不一样高。
（ 6） 并不是所有的汽车都比火车快。
（ 7） 没有一个自然数大于等于任何自然数。
（ 8） 有唯一的偶素数。
（ 9） 不管黑猫白猫，抓住老鼠就是好猫。
（ 10）对平面上任意两点，有且仅有一条直线通过这两点。
习题选讲 — 命 题符号化解：由于没指出个体域,故用全总个体域
（ 1） 每个人都有心脏 。
本命题的含义：对于每一个 x,如果 x是人,则 x有心脏 。
因而应首先从宇宙间的一切事物中,将人分离出来,这就必须引入特性谓词 。
令 M(x):x是人,H(x):x有心脏。
命题符号化为,?x(M(x)→ H(x))
如果将其中的 → 改为 ∧,即?x(P(x)∧H(x)),它表示的意思是：,对于每个 x,x是人且 x有心脏,。这是一个假命题，而
,每个人都有心脏,是真命题。
这说明将命题,每个人都有心脏,符号化为 (x)(P(x)∧H(x))
是错误的。
习题选讲 — 命 题符号化
（ 2） 有的狗会飞 。
命题的意思是：存在一个 x,使得 x是狗,并且 x会飞 。
设 D(x),x是狗,F(x),x会飞 。
命题符号化为,?x(D(x)∧ F(x))
如果将其中的 ∧ 改为 →,即?x(D(x)→F(x)),
如果用 a表示某只猫,则 D(a)为假,因而,D(a)→F(a) 为真,
所以?x(D(x)→F(x)) 为真,而,有的狗会飞,为假,
这说明将,有的狗会飞,符号化为 (x)(D(x)→F(x)) 是错误的
。
习题选讲 — 命 题符号化
（ 3） 没有不犯错误的人 。
命题的意思是,① 存在不犯错误的人是不可能的 。
② 只要是人,必然犯错误 。
设 M(x),x是人,F(x):x犯错误命题符号化为
① ┐?x(M(x)∧ ┐ F(x))
②?x(M(x)→F(x))
习题选讲 — 命 题符号化
（ 4） 发光的不都是金子 。
命题的意思是,① 不是发光的东西都是金子 。
② 存在着发光的东西不是金子 。
设 L(x),x是发光的东西,G(x),x是金子 。
命题符号化为
① ┐?x(L(x)→G(x))
②?x(L(x)∧ ﹁ G(x))
（ 5） 一切人都不一样高 。
设 F(x):x是人,H(x,y),x与 y相同,L(x,y),x与 y一样高,
命题符号化为
x(F(x)y(F(y)H(x,y)L(x,y)))
或?x?y(F(x)?F(y)H(x,y)L(x,y))
（ 6） 并不是所有的汽车都比火车快 。
设 F(x):x是汽车,G(y):y是火车,H(x,y):x比 y快,
命题符号化为
x?y(F(x)?G(y)?H(x,y))
或?x?y(F(x)?G(y)H(x,y))
习题选讲 — 命 题符号化习题选讲 — 命 题符号化
（ 7）没有一个自然数大于等于任何自然数。
设 N(x):x是自然数,G(x,y):x?y
命题符号化为：
x(N(x)y(N(y)?G(x,y)))
（ 8） 有唯一的偶素数 。
设,Q(x):x是偶数,P(x):x是素数,E(x,y):x＝ y
命题符号化为：
x(Q(x)?P(x)y(Q(y)?P(y)E(x,y)))
习题选讲 — 命 题符号化
（ 9） 不管黑猫白猫,抓住老鼠就是好猫 。
需要考虑问题：
① 只是限制黑猫白猫,还是包含其它颜色的猫？
②是指至少抓住一只就可以，还是抓住所有的？
因此在描述命题时，总是将这些模糊概念做某种确切理解。
设 C(x),x是猫,W(x),x是白的,B(x),x是黑的
G(x),x是好的,M(x),x是老鼠,K(x),x抓住 y
命题符号化为
x?y(C(x)∧M(y)∧(B(x)∨W(x))∧K(x,y))→G(x))
习题选讲 — 命 题符号化
（ 10）对平面上任意两点，有且仅有一条直线通过这两点。
设 P(x),x是一个点,L(x),x是一条直线
R(x,y,z),z通过 x,y,E(x,y),x等于 y
命题符号化为
x?y(P(x)∧P(y)∧ ﹁ E(x,y))
→?z(L(z)∧R(x,y,z)∧?u((L(u)∧R(x,y,u))→E(u,z)))
习题选讲 — 公式 判 断
2、判断下列各式是否是永真式？证明你的判断。
(1)?x(F(x)?G(x))
(2)?x(F(x)?G(x))
(3)?x?y(F(x)?G(y)?H(x,y))
(4)?x?y(P(x,y)?Q(a,y))x?y(P(x,y)?Q(x,y))
其中 a是个体常元。
解：
(1) 不是永真式 。
(2) 不是永真式 。
(3) 不是永真式 。
(4) 不是永真式 。
(4)?x?y(P(x,y)?Q(a,y))x?y(P(x,y)?Q(x,y))
其中 a是个体常元。
令个体域为某个元素个数大于等于 2的有限整数集，其中 a为最小的数。
P(x,y),x大于等于 y，
Q(x,y),x小于等于 y。
x?yP(x,y)?Q(a,y)解释为：存在一个 x,对于所有的 y,有
x大于等于 y,并且 a小于等于 y。 命题为真，只要取 x为个体域中最大数即可。
x?y(P(x,y)?Q(x,y))解释为：存在一个 x,对于所有的 y，
有 x大于等于 y,并且 x小于等于 y。 命题为假。
3,判断下列公式是否为永真公式 。
（ 1） (?x A(x)x B(x))x (A(x)? B(x))
（ 2） (?x A(x)x B(x))x (A(x)? B(x))
（ 3） (?x A(x)x B(x))x (A(x)? B(x))
（ 4） (?x A(x)x B(x))x (A(x)? B(x))
解：
（ 1） 永真公式 。
（ 2） 不是永真公式 。
（ 3） 永真公式 。
（ 4） 永真公式 。
小节结束习题选讲 — 公式 判 断作业习题四,2,3,4,5,9,10,14
结束习题说明
判断下面推理是否正确。先将简单命题符号化，再写出前提、结论、推理的形式结构（以蕴涵式的形式给出）和判断过程（至少给出两种判断方法）：
（ 5）若今天是星期一，则明天是星期二或星期三。
推理形式结构为
p→(q∨r)
它不是重言式，故推理不正确。
