2.2 谓词公式及解释

2.2谓词公式及解释

定义设R(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是任意的n个项，则称R(t1,t2,…,tn)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4))等均为原子公式

定义合式谓词公式（简称谓词公式）定义如下：

(1)原子谓词公式是谓词公式.(2)若A是谓词公式，则(

A)也是谓词公式

(3)若A,B是谓词公式，则(A

B),(A

B),(A

B),(A

B)也是谓词公式

(4)若A是谓词公式，x是个体变项，则

xA,

xA也是谓词公式

(5)只有有限次地应用(1)~(4)形成的符号串是谓词公式.如x0,

x(F(x)

G(x)),

x

y(x+y=1)定义

在公式

xA和

xAA中，称x为指导变元，A为相应量词的辖域.在

x和

x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现.例如,在公式

x(F(x,y)

G(x,z))中,A=(F(x,y)

G(x,z))为

x的辖域，

x为指导变元,A中x的两次出现均为约束出现，

y与z均为自由出现.闭式:不含自由出现的个体变项的公式.如

x(F(x)

G(x))

定义

设A为谓词公式，给定一非空个体域D，将谓词公式出现的每个个体常项符号指定为D中一特定元素

，每个函数变项符号指定D上一特定函数，每个谓词变项符号指定D上一特定谓词，即构成了谓词公式的一个解释I。注(1)一解释I，可以对多个公式进行解释。(2)一谓词公式A，可以有无穷多个解释。

闭式在任何一解释下都是命题。

给定解释I，对公式中每个自由出现的个体变项指定个体域中的一个元素称作在解释I下的赋值。

在给定的解释和赋值下,任何公式都成为命题.

一个谓词公式（特别是闭式），给定多个解释，有的解释使其为真，有的解释使其为假；也有谓词公式在任何解释下都为真或都为假。基于此，下面给出谓词公式的分类。永真式(逻辑有效式):在任何解释和赋值下为真命题矛盾式(永假式):在任何解释和赋值下为假命题可满足式：存在成真的解释和赋值说明：永真式为可满足式，但反之不真谓词公式的可满足性（永真性,永假性)是不可判定的

定义设A0是含命题变项p1,p2,…,pn的命题公式，

A1,A2,…,An是n个谓词公式，用Ai处处代替A0中的pi(1

i

n)

，所得公式A称为A0的代换实例.如F(x)

G(x),

xF(x)

yG(y)是p

q的代换实例定理

重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.例

判断下列公式的类型(1)∀xF(x)→∃xF(x)；设I为任意的解释，若∀xF(x)为假，则∀xF(x)→∃xF(x)为真.若∀xF(x)为真，则∃xF(x)也为真，所以F(x)→∃xF(x)也为真.是逻辑有效式.(2)∀xF(x)→(∀x∃yG(x,y)→∀xF(x))；重言式p→(q→p)的代换实例，是逻辑有效式.(3)∀xF(x)→(∀xF(x)∨∃yG(y))；重言式p→(p∨q)的代换实例,

是逻辑有效式.(4)

(F(x,y)→R(x,y))∧R(x,y)；矛盾式

(p→q)∧q的代换实例,是矛盾式.(5)∀x∃yF(x,y)→∃x∀yF(x,y).取解释I：个体域N,

F(x,y)为x=y.公式被解释为∀x∃y(x=y)

∃x∀y(x=y)，其值为假.解释I′:个体域N,F(x,y)为x

y,得到一个新的

在I′下,公式被解释为∀x∃y(x

y)

∃x∀y(x

y)，其值为真.是非逻辑有效式的可满足式.(6)∃xF(x,y)取解释I：个体域N,

F(x,y)为x<y.赋值

1：

1(y)=1.

在I和

1下,∃x(