词公式
简单起见，谓词公式简称为公式。
5
定义4.5（量词的辖域） 在公式xA和xA中，称x是指导变元，A为
相应量词的辖域。 在x和x的辖域中，x的所有出现都称为约束
出现 A中不是约束出现的变项均称为是自由出现的
说明：量词的辖域以量词后第一个括号的范围为准
6
例4.6 指出下列公式中的指导变元，各量词的 辖域，自由出现以及约束出现的个体变项：
（3）但可以利用代换实例的相关性质来判断 某些特殊的公式。而对于一般的公式只能通过构 造解释的方法来判断。
16
定义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)
4
定义4.4（谓词公式）
谓词公式也称为合式公式，其递归定义如下： （1）原子公式是谓词公式 （2）若A谓词公式，则┐A也是谓词公式 （ 3 ） 若 A，B 是 谓 词 公 式 ， 则 A∧B，A∨B，A→B，
AB也是谓词公式 （4）若A是公式，则xA，xA也是谓词公式 （5）只有有限次使用（1）-（4）生成的符号串才是谓
在谓词逻辑中，项起的是名词的作用，不是句子。
原子公式是谓词逻辑公式的最小单位，最小的句子单位
3
例：D是个体名称的集合， x,y（∈D）为个体变项，a：张三，b：李四 所以x，y，a，b是项 假设f(x):x的父亲，F(x,y):x是y的父亲 f(a), f(f(a)), F(a,b), F(f(f(a)),b) 则f(a):张三的父亲，是项 f(f(a)):张三的祖父，是项 而F(a,b):张三是李四的父亲，是原子公式 F(f(f(a)),b):张三的祖父是李四的父亲，是原子公式
说明：在使用一个解释I解释一个公式A时， 将A中的个体常项、函数和谓词分别用I中指定的 个体常项、函数和谓词代替。
10
例4.8 给定解释I： （a）个体域D=N（自然数集合）； （b）a=0； （c）f(x, y)=x+y、 g(x, y)=x*y； （d）F(x, y)：x=y。 在I下，判断下列公式的真值？ （1）F(f(x, y), g(x, y)) （2）F(f(x, a), y) →F(g(x, y), z) （3）xF(g(x, y), z) （4）xF(g(x, a), x)→F(x, y) （5）xF(g(x, a), x) （6）xy(F(f(x, a), y)→F(f(y, a), x)) （7）xyzF(f(x, y), z)
而后件xy(x=y)是假的，所以公式为假。 取解释I2为：个体域为自然数集合N， F(x, y):x≤y。 在解释I2下，公式的前件和后件都为真，所以
公式为真。 所以（3）为非永真的可满足式。
22
（4）xF(x)→xF(x) 设I为任意的解释，个体域为D。 按xF(x)是否为真分两种情况进行讨论： 若xF(x)为真，则xF(x)为真，因此公式为
15
定义4.8（一阶公式的分类）
设A为一公式，若A在任何解释下均为真，则称A 是永真式（或称逻辑有效式）。若A在任何解释下均 为假，则称A是矛盾式（或永假式）。若至少存在一 个解释使A为真，则称A是可满足式。
说明：（1）永真式是可满足式，反之不然。 （2）由于公式的复杂性和解释的多样性，到
目前为止，还没有一个可行的算法判断某一公式 是否是可满足的。
真。 若xF(x)为假，则公式为真。 由以上讨论及解释I的任意性，所以（4）为
永真式。
23
11
（1）F(f(x, y), g(x, y)) 公式被解释成：x+y=x*y 在解释I下，该公式不是命题
（2）F(f(x, a), y)→F(g(x, y), z) 公式被解释成：(x+0=y)→(x*y=z) 在解释I下，该公式不是命题
（3）xF(g(x, y), z) 公式被解释成：x(x*y=z) 在解释I下，该公式不是命题
数，G(x):x是有理数。 在解释I1下，公式为真，所以不是矛盾式。 取解释I2：个体域为实数集合R，F(x):x是整
数，G(x):x是无理数。 在解释I2下，公式为假，所以不是永真式。 所以（2）为非永真的可满足式。
21
（3）xyF(x, y)→xyF(x, y) 取解释I1为：个体域为自然数集合N， F(x, y) : x=y。 在解释I1下，公式的前件xy(x=y)是真的，
（7）xyz F(f(x, y), z) 公式被解释成：xyz(x*y=z)， 在解释I下公式为真命题
13
例4.8 给定解释I：
（a）个体域D=N（自然数集合）；
（b）a=0；
（c）f(x, y)=x+y、 g(x, y)=x*y；
（d）F(x, y)：x=y。
在I下，判断下列公式的真值？ （1）F(f(x, y), g(x, y)) （2）F(f(x, a), y) →F(g(x, y), z) （3）xF(g(x, y), z) （4）xF(g(x, a), x)→F(x, y) （5）xF(g(x, a), x) （6）xy(F(f(x, a), y)→F(f(y, a), x)) （7）xyzF(f(x, y), z)
2
定义4.2（项）
项的递归定义如下： （1）个体常项和个体变项是项。 （2）如果(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任
意的n个项，则(t1,t2,…,tn)仍然是项。 （3）只有有限次使用(1)，(2)生成的符号串才是项。
定义4.3（原子公式）
设R(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是任意的n 个项，则称R（t1,t2,…,tn）为原子公式。
4.2 一阶逻辑公式及解释
上节学了
一阶逻辑的基本概念：个体词、谓词、量词 一阶逻辑符号化的有关概念和方法
本节学习
一阶逻辑公式的概念：字母表、项、原子公式、公式、 指导变元、辖域、闭式等 一阶逻辑公式的解释及公式类型的判断。
1
定义4.1（字母表）
以下是字母表的成员： (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)括号和逗号:（） ，
判断方法：如果公式不是命题逻辑永真式或矛盾式的代 换实例，则只能通过构造解释的方法来进行判断。
（1）对于非永真的可满足式，需要分别具体构造一个成 真解释和一个成假解释来说明。
（2）对于永真式（矛盾式），则必须证明该公式在任意 的解释下都是真（假）的。
19
（1）x(F(x)→G(x)) 取解释I1：个体域为实数集合R，F(x):x是整
数，G(x):x是有理数。 在解释I1下， 公式为真，所以不是矛盾式。 取解释I2：个体域为实数集合R，F(x):x是有
理数，G(x): x是整数。 在解释I2下，公式为假，所以不是永真式。 所以（1）式为非永真的可满足式。
20
（2）x(F(x)∧G(x)) 取解释I1：个体域为实数集合R，F(x):x是整
不是命题 不是命题 不是命题 真命题 假命题 真命题 真命题
14
说明： (1)有的公式在具体的解释中真值确定，
即为命题；有的公式在具体的解释中真值不 确定，即不是命题。
(2)闭式在任意的解释下都变成可命题 (定理4.1)，但在不同的解释下，可能有不 同的真值。
(3)非闭式的公式就不一定具有这种性 质，它可能在有的解释中是命题，有的解释 中不是命题。
前件：x是指导变元，量词的辖域为 F(x)→G(y)，其中x是约束出现的，y是自由出现的
后件：y是指导变元，量词的辖域为 H(x)∧L(x,y,z)，其中y是约束出现的，x和z是自由 出现的。
在整个公式中，x约束出现1次，自由出现2次 y约束出现1次，自由出现1次 z自由出现1次。
8
定义2.6（闭式） 设A为任意的公式，若A中无自由出现的个体
都是p→q的代换实例 问x(F(x)→G(x))是p→q的代换实例么？ 定理4.2 永真式的代换实例都是永真式，
矛盾式的代换实例都是矛盾式。
17
例 判断下列公式的类型。 （1）xF(x)→(xyG(x,y)→xF(x)) （2）┐( x F(x)→yG(y))∧yG(y)
解： （1）xF(x)→(xyG(x,y)→xF(x))
12
（4）xF(g(x, a), x)→F(x, y) 公式被解释成：x(x*0=x)→(x=y) 由于蕴涵式的前件为假，所以在解释I下公式为真命题
（5）xF(g(x, a), x) 公式被解释成：x(x*0=x) 在解释I下公式为假命题
（6）xy(F(f(x, a), y)→F(f(y, a), x)) 公式被解释成：xy((x+0=y)→(y+0=x)) 在解释I下公式为真命题
公式是p→(q→p)的代换实例， 而p→(q→p)是永真式，所以公式（1）是永真式 （2）┐( x F(x)→yG(y))∧yG(y) 公式是┐（p→q）∧q的代换实例， 而┐（p→q）∧q是矛盾式，所以公式（2）是矛盾式
说明：对于这些类型的公式完全可以采用等值演算的 方法加以判断。
18
例 判断下列公式的类型？ （1）x(F(x)→G(x)) （2）x(F(x)∧G(x)) （3）xyF(x, y)→xyF(x, y) （4）xF(x)→xF(x)
（1）x（ F（x，y）→G（x，z）） （2） x（ F（x）→G（y））→
y（ H（x）∧L（x，y，z））