第10讲谓词逻辑等值式

一阶逻辑的字母表2021/9/91一阶逻辑个体常项:个体变项:函数符号:谓词符号:量词符号:联结词符号:a,

b,

c,

…,

a1,b1,

c1,…x,y,

z,

…,x1,

y1,

z1,…f,

g,

h,

…,f1,

g1,

h1,…F,G,

H,

…,F1,

G1,

H1,

…$,

",

, ,

fi

,

«括号与逗号: (,

),，一阶(firstorder)逻辑的合式公式2021/9/92一阶逻辑项原子公式合式公式合式公式中的变项2021/9/93一阶逻辑量词辖域:域.

例如:在$xA,

"xA中,A是量词的辖$x(F(x)

"

y(G(y)fi

H(x,y)))指导变项:

紧跟在量词后面的个体变项.例如:

$x(F(x)

"

y(G(y)fi

H(x,y)))约束出现:在辖域中与指导变项同名的变项.

例如:

$x(F(x)

"

y(G(y)fi

H(x,y)))自由出现:既非指导变项又非约束出现.例如:

"

y(G(y)fi

H(x,y))解释(interpret)2021/9/94一阶逻辑对一个合式公式的解释包括给出个体域谓词函数个体常项的具体含义赋值(举例)2021/9/95一阶逻辑F(f(a,a),b)赋值1：

个体域是全体自然数; a:

2;b:

4;

f(x,y)=x+y; F(x,y):

x=y原公式赋值成:

“2+2=4”。赋值2：

个体域是全体实数; a:

3;b:

5; f(x,y)=x-y; F(x,y):

x>y原公式赋值成:

“3-3>5”。一阶逻辑永真式(tautology)2021/9/96一阶逻辑永真式:在各种解释下取值均为真(逻辑有效式)命题逻辑永真式:在各种解释下取值均为真(重言式)永假式:在各种解释下取值均为假(矛盾式)命题逻辑永假式:在各种解释下取值均为假(矛盾式)可满足式：非永假式代换实例2021/9/97一阶逻辑在含命题变项p1,p2,……,pn的命题公式中,每个命题变项代换成一阶逻辑公式所得

到的式子,称为原来公式的代换实例.例：

F(x)→G(y)¬

"

xF(x)∨G(y)一阶逻辑公式分类2021/9/98一阶逻辑例：

"

xF(x)

↔

$x

F(x)"

xF(x)

→(G(y)

→"

xF(x)

)$xF(x)

→

"

yG(y)("

xF(x)

→$yG(y)

)

$yG(y)命题符号化(举例)2021/9/99一阶逻辑例:

“不存在最大的自然数”。(论域取全体自然数)解:

设: G(x,y):

x£y;原命题符号化成:$x"

yG(y,x)或:

"

x$y

G(y,x)一阶逻辑等值式(定义)等值：

A

B读作：A等值于B含义：A与B在各种赋值下取值均相等A B

当且仅当A↔B是永真式例如：

"

xF(x)

$x

F(x)FF2021/9/910一阶逻辑一阶逻辑等值式(来源)2021/9/911一阶逻辑命题逻辑等值式的代换实例与量词有关的有限个体域量词消去量词否定量词辖域收缩与扩张量词分配相同量词的交换与变项命名有关的换名规则代替规则代换实例2021/9/912一阶逻辑在命题逻辑等值式中,代入一阶逻辑公式所得到的式子,称为原来公式的代换实例.例1：AA,"

xF(x)令A="

xF(x),

得到"

xF(x)例2：A→B¬A∨B,令A=F(x),B=G(y),

得到F(x)→G(y)¬F(x)∨G(y)有限个体域上消去量词2021/9/913一阶逻辑设个体域为有限集D={a1,a2,…,an},则"

xA(x) A(a1)∧A(a2)

∧

…

∧

A(an)$xA(x) A(a1)∨A(a2)

∨

…

∨

A(an)例:

个体域D={a,b,c},

则

$x"

yF(x,y)$x

(F(x,a)∧F(x,b)∧F(x,c))(F(a,a)∧F(a,b)∧F(a,c))∨(F(b,a)∧F(b,b)∧F(b,c))∨(F(c,a)∧F(c,b)∧F(c,c))量词否定等值式"

xA(x)$xA(x)$x

A(x)"

x

A(x)AA2021/9/914一阶逻辑量词否定等值式(举例)

?lim

an

=

anfi

¥nfi

¥"e

$N

"

n (

n>N

→

|an-a|<e

)a1,a2,a3,…,aN

,aN+1,aN+2

,…,an,…e

ealim

an

„

a2021/9/915一阶逻辑量词否定等值式(举例、续)

lim

an

„

anfi

¥lim

an

=

anfi

¥"e

$N"

n( n>N

→

|an-a|<e

)$e

$N"

n( n>N

→

|an-a|<e

)$e

"

N"

n( n>N

→

|an-a|<e

)$e

"

N$n( n>N

→

|an-a|<e

)$e

"

N$n( n>N∨

|an-a|<e

)$e

"

N$n(n>N

∧

|an-a|<e

)$e

"

N$n(n>N

∧

|an-a|‡e

)2021/9/916一阶逻辑量词辖域收缩与扩张(")2021/9/917一阶逻辑"

x(A(x)∨B)"

x(A(x)∧B)"

xA(x)∨B"

xA(x)∧B"

xF(x)∨G(y)说明:

B中不含x的出现例1:

"

x(F(x)∨G(y))例2:

"

x"

y(F(x)∧G(y))"

x(F(x)∧"

yG(y))"

xF(x)∧"

yG(y)量词辖域收缩与扩张("、续)2021/9/918一阶逻辑"

x(A(x)→B)"

x(B→A(x))证明:"

x

A(x)∨B$xA(x)→B证明:"

x(A(x)→B)"

x(

A(x)∨B)$xA(x)∨B"

x(B→A(x))"

x(

B∨A(x))B∨"

xA(x)B∨"

xA(x)B→"

xA(x)$xA(x)→BB→"

xA(x)量词辖域收缩与扩张($)2021/9/919一阶逻辑$x(A(x)∨B)$x(A(x)∧B)$x(A(x)→B)$x(B→A(x))$xA(x)∨B$xA(x)∧B"

xA(x)→BB→$xA(x)说明: B中不含x的出现例1:

$x(F(x)∨G(y))例2:

"

x$y(F(x)∧G(y))$xF(x)∨G(y)"

x(F(x)∧$yG(y))"

xF(x)∧$yG(y)量词辖域收缩与扩张($、续)2021/9/920一阶逻辑$x(A(x)→B)

"

xA(x)→B证明:

$x(A(x)→B)$x(

A(x)∨B)"

xA(x)∨B$x

A(x)∨B"

xA(x)→B$x(B→A(x))

B→$xA(x)证明:

$x(B→A(x))$x(

B∨A(x))B∨$xA(x)B∨$xA(x)B→$xA(x)量词分配2021/9/921一阶逻辑"

x(A(x)∧B(x))$x(A(x)∨B(x))"

xA(x)∧"

xB(x)$xA(x)∨$xB(x)量词分配(反例)"

x(A(x)∨B(x))

"

xA(x)∨"

xB(x)"

x(A(x)∨B(x))

"

xA(x)∨"

xB(x)个体域为全体自然数;

A(x):

x是偶数B(x):

x是奇数;

左

1,

右

0$x(A(x)∧B(x))

$xA(x)∧$xB(x)$x(A(x)∧B(x))

$xA(x)∧$xB(x)个体域为全体自然数;

A(x):

x是偶数B(x):

x是奇数;

左

0,

右

12021/9/922一阶逻辑相同量词的交换2021/9/923一阶逻辑"

x"

yφ(x,y)$x$yφ(x,y)"

y"

xφ(x,y)$y$xφ(x,y)另："x"yφ(x,y)

$y"xφ(x,y)

"

x$yφ(x,y)

$x$yφ(x,y)"

y"

xφ(x,y)

$x"

yφ(x,y)

"

y$xφ(x,y)

$y$xφ(x,y

)换名(rename)规则2021/9/924一阶逻辑把某个指导变项和其量词辖域中所有同名的约束出现,都换成某个新的个体变项符号.例如:"

x(A(x)∧B(x))"

xA(x)∧"

xB(x)"

y(A(y)∧B(y))"

yA(y)∧"

zB(z)H(x,y)∨$xF(x)∨"

y(G(y)fi

H(x,y))H(x,y)∨$zF(z)∨"

u(G(u)fi

H(x,u))代替(substitute)规则2021/9/925一阶逻辑把某个自由变项的所有出现,都换成某个新的个体变项符号.例如:A(x)∧B(x)"

xA(x)∧B(x)A(y)∧B(y)"

xA(x)∧B(y)H(x,y)∨$xF(x)∨"

y(G(y)fi

H(x,y))H(s,t)∨$xF(x)∨"

y(G(y)fi

H(s,y))置换(permutation)规则2021/9/926一阶逻辑设φ(A)是含公式A的一阶谓词公式，

φ(B)是用公式B置换φ(A)中所有出现的A后得到的公式。若A

B,则φ(A)

φ(B)举例2021/9/927一阶逻辑"

x(A(x)∧B(x))"

xA(x)∧"

xB(x)"

xA(x)

∨

"

xB(x)"

yA(y)

∨

"

xB(x)"

y(A(y)

∨

"

xB(x))"

y"

x(A(y)

∨

B(x))特点：所有量词都在最前面前束范式2021/9/928一阶逻辑设φ为一谓词公式，如果φ具有如下形式：Q1x1Q2x2...Qnxnψ其中Qi(1≤i≤n)为"或$，ψ为不含量词的公式，则称φ为前束范式.前束范式存在定