离散数学-第二章一阶逻辑

离散数2.1例所有的人都是要死是所 是要死P：所有的人是要死的 是 PQPQ

不 式，

PQ 2.1例2.1.1考虑下列句是 (2)5是质x大于 生 变元：代 的变元。常用x,y,…表示谓词：刻 的性质 间关系的词。常用Q，R表示 2.1谓词变元：代表谓词的变元例P(x)：“x是质数”，则“5G(x,y)：“x生于y”，则“ P(x)，G(x,y)称为谓词命名式，简称谓词n元谓词：具有n 变元的谓词。一般记P(x1,x2,…,xn) 2.1域 变元的取值范围全 域：一切事物的集合表 数量的词称为量词，量词一般有两种全称量表示“所有”，“任意”的词称为全称量词，x为 。读作“对所有的x”或“对任一”或“对Px)xP(x)表示“对所有的x，P(x)为真

表示“并非对所有x，P(x)为真 2.1存在量表示“存在”，“至少有一个”的词称为存在量词

读作“存在一个x”或“至少Px)xP(

表示“有一x使P(x)为真表示“并非存在一x使P(x)为真 2.1例2.1.2将下列句子符号2是素数，也是偶数任何自然数不是奇数就是偶数，偶数均能被2整除，奇数不能被2整除；整数都是有理数，并不是每个有理数都是整数，有些有理数不是整数。解(1)设P(x)：x是素数；E(x)：x是偶原句可符号化为P(a)

2.1(2)设O(x)：x是奇数N(x)：x是自然数E(x)：x是偶数D(x)：x能被2整除原句可符号化x(N(x)(O(x)E(x)))x(E(x)D(x))x(O(x)D(设I(x)：x是整数Q(x)：x是有理数x(I(x)Q(x))x(Q(x)I(x))x(Q(x)I( 2.1例2.1.3 论证符号化M(x)：x是人D(x)：x是要死原句可符号化x(M(x)

D(x))

M(a)

例2.1.4将下列命题符号存在小于0的实数任意实数的平方都不小于0 解取论述域为实数Lx

：x小于 f(x)：x的平可符号化为

f(取论述域为全 域。设R(x)：x是实

可符号化为R

在谓词公式中可能出现函数 father(x):x的父亲，P(x):x是教师定义2.2.2谓词逻辑中项的归纳定义如下 变元是项tt,

是项

f

t21

tn

也是项 只有通过有限次使用(1),(2) 定义2.2.3设

t1,

,,

是项

P(nt1t2,tn)是P(1

f(1)(a))

，Q(3)(

y,

是原子公式定义2.2.4原子公式是合式公式若A，B是合式公式，则

(A

(A

B)，(A

(A

也是合式公式只有有限次应用步骤(1)、(2)所得到的符号串才是合式公式。 例如

f(a))x(P(

Q(

是合式公式量词的辖域：紧接于量词之后的最小子公式例2.2.1

xP(

Q(

，x的辖域为

x(P(

Q(

x的辖域为

x(P(

y))

P(x,z)x的辖域

P(

Q(x,约束变元：在量词

的辖域内，变元x的切出现称为约束出现，并称这样的x为约束变元 自由变元：变元的非约束出现称为变元的自由现，这样的变元成为自由变元例2.2.2在公式xPy是自由变元

y)Q(

中，x是约束变元,在公式xPx,是约束变元

y)Q(

中，x既是自由变元，换名规则：若要将约束变元x改为将Qx中的x及在Q的辖域中自由出现的x均改为y不在限制x的量词辖域内出现，最好是公式中未出现的符号。 例2.2.3

xP(x)Q(

x(A(x)

B(

y))C(x)

)C(注意换名是对约束变量而言的，而不是对自由变量而言。 定义2.3.1合式公式G的一个解释I是由一个非空集 对中的每个n元函数符号，指定中的一个n元函数；对中的每个n元谓词符号，指定中的一个n元谓词（命题变元指定为1或0）； 例2.3.1给定公

))

，其中a。给定解释I如下a {,

f(

f(),(),

P()

P()1在解释I下，

))

))

)))

(P()Q(,))(P()Q(,例2.3.2试找出一个解释I，使公xP(x)xQ(解设I为

x(P(x)Q(x))

P( P(

Q( 1 在解释I下，()())

x(P(x)Q(((

(11)(00)10例2.3.3试找出一个解释I，使公在I下为假

)

xP

I

P(

P(

在解释I下，x(P(x)Q(x))xP(x)xQ( ()())

(10)(01)100110

10 习题1(1)2(1)3习题1(1)(4)2(2) 定义2.3.2设A是一个合式公式若A在任何解释下为真，则称A 式若A在任何解释下为假，则称A是永假式若至少有一个解释使A为真，则称A是可满足式例2.3.4证明

xP(

xP(

式

xP(

xP(

是 的可满足式 (1)对任何解释I，

xP(

在I下为1，那么aDIP(a)

DI

，因此存

a P(a)式

，即

xP(x)

xPx)xPx(2)首先证

xP(

xP(

是可满足的I解释I1DI

{

P()在解释I1下，xP(x)xP(x)

P()

P() 下面证

xP(x)xP(

是 的2解释I22

{,

P()

P()在解释I2下，xP(x)xP(x)(P()

P())

P()P((10)110 一阶逻辑中与量词有关的基 式

，这里A是不含自由变元的谓词公式量词的否

xP(

(xP(

xP(量词辖域的收缩和扩x(A(x)B)xA(x)x(A(x)B)xA(x) x(A(x)B)xA(x)x(A(x)B)xA(x)

B(y))xA(

yB(

B(y))xy(A(x)

B(xA(x)yB(xA(x)yB(xA(x)yB( (4)量词的分配形①x(A(x)B(x))xA(x)xB(③x(A(x)B(x))xA(x)xB(由①：x(AxBx))xAxxBx(A(x)B(x))xA(x)xB(

由x(A(x)B(x))xA(x)xB(

B(x))xA(x)xB(

(5)两个量词间的关 xyP(

y)yxP(

y（ xyP(

y)xyP(

y)（xP(x)xP(x) xyP( xyP(

y)yxP(x,y)xyP(x,

（由意义（xP(x)xP(x) xyP(

yxP(x,

（由意义表2.2列出了与量词相关的一些基 式 定义2.4.1下列形式的公式称为前束范式Q1x1Q2x2Qrxr (rQi(1

ir)

，B是不含任何量词的公式互不相同。并

Q1x1Q2x2Qr

为前束词，称B

x2,,定义2.4.2设A是合式公式，B是前束范式。若

AB 例2.4.1x(F(

G(x))(xF(

xG(的前束范式解x(FxGx(xFxxGx(F(x)G(x))(xF(x)xG(x(F(x)G(x))xF(x)xG(x(F(x)G(x))yF(y)xyz(F(x)G(x)F(y)G(z)) 定义2.4.3设前束范式

Q1x1Q2x2QrxrB。

Qtxt(1

，那Qt

左边无全称量词时，用B中未出现 a去代替B

的所有出现，并删

Qt Qt

左边的所有全称量词为QxQx(1 1 1

取B未出现的元函数符

fs)

(s)(t1t

,,tst

)代替中xt的所有出现，并删

Qtxt这种消去量词的变换称为Skolem变换 定义2.4.4称F是公式G的Skolem范式，若F是通过G的前束范式经Skolem变换所得到的无存在量词的公式. 例2.4.2求例2.4.1中公式的Skolem范式。解原式的一个前束范式为xyz(F(x)G(x)F(y)G(z))原式的一个Skolem范式y(F(a)G(a)F(y)

f(定理2.4.1设A是合式公式，那么A是永假式当且仅A的Skolem范式是永假式 例判断下列各式是否成立，并证明你的论断

x(A(x)

B(

(xA(

xB(

(xA(

xB(

x(A(x)

B((1)成x(A(x)

B(

xA(

x((A(x)

B(x))

B(x))

B(x)

B(x)

x(B(x)

不成立 {,

A(

A(

B(

B((xA(x)

xB(

x(A(x)

B(

A()

B())(A()

B())(A()

B((1001)(10)(0(0

0)

0

10 用)表示x是中的自由变量，那么)表示用y替代中x的所有自由出现所得到的结果。例如(

xP(x)Q(x)

Rxy)，

xP(x)Q(y)

4个有关量词的推理规则：全称指定规则，存在指定规则，全称推广规则，存在推广规则。 全称指定规则（简称US规则x)其中y是任意不在A(x)中约束出现 符号若允许y在A(x)中约束出现，则可能出现推理错误例

在实数域成立，

y(y

不成立 (2)存在推广规则（简称EG规则A(c)x)其中x不在A(c)中出现若允许x在A(c)中出现,则可能出现推理错误例2.5.2在实数域中

成立，不成立

xx(x 存在指定规则（简称ES规则xA(x)A(c)其中c不在A(x)中或其前的推导中例2.5.3观察下列推理过程xP(x)xQ(x)x(P(x)Q(①xP(x)②P(c)

xQ(x) P(c)Q(c) x(P(x)Q(全称推广规则（简称UG规则x)其中A(y)对y的任意取值都成立 例2.5.5观察下列推理过程：xP(

xP(x)①xP(x)②P(③xP(x) 2.5例2.5.7证明：xHxx(Hx

M(x))xM(证①xHx)②H(c)③x(H(x)

M(④H(c)⑤M(c)⑥xM(

M(c) 2.5例2.5.8证明：x(PxQxxPxxQ证①xPx) P(c) x(P(x)Q( P(c)Q(c) x) xP(x)xQ( 2.5例2.5.9证明：x(PxQxxPxxQ证用反证法①(xP(x)xQ( xP(x)xQ( xP(x) xP(x) P(c) 2.5⑦xQ(x)⑧⑨P(c)Q(c)⑩(P(c) x(P(x)Q( P(c)Q(c)13(P(c)Q(c))(P(c) 2.5例2.5.1