离散数学：2-2 一阶逻辑

复习思考题5将下面命题符号化：所有的兔子比所有的乌龟跑得快。有的兔子比所有的乌龟跑得快。所有的兔子比有的乌龟跑得快。不存在跑得同样快的两只兔子。第2章一阶逻辑

2.1一阶逻辑基本概念、命题符号化2.2一阶逻辑公式、解释及分类2.3一阶逻辑等值式、前束范式2.4一阶逻辑推理理论

在使用量词时，应注意以下特点在不同个体域中，命题符号化的形式可能不一样。如“有的人很聪明。”在人类集合个体域中：xG(x)在全总个体域中：x(M(x)G(x))若事先没有给出个体域，都默认为全总个体域。在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的如“有的人很聪明。”x(M(x)

G(x))如“每个人都有一双手”x(M(x)

F(x))全称量词后是条件式存在量词后是合取式在使用量词时，应注意以下特点个体域和谓词的含义确定之后，n元命题函数要转化为命题至少需要n个量词。当个体域为有限集时，如D={a1,a2,a3,….,an}。对于任意谓词，都有

x

A(x)=A(a1)

A(a2)……

A(an)

x

A(x)=A(a1)

A(a2)……

A(an)

这实际上是将一阶逻辑中命题公式转化为命题逻辑中的命题公式问题。随意颠倒量词顺序可能会改变原命题的含义取个体域为实数集，

H(x,y)

：x+5=y

则x

y

H(x,y)表示“对任意的x，存在着y

，使得x+5=y

。”这是真命题。将量词的顺序颠倒，得，

y

x

H(x,y)表示“存在着y

，对任意的x

，都有x+5=y。”，这是假命题。两个量词的次序变化语句何时为真何时为假xy

H(x,y)yx

H(x,y)对每一对x、y，H(x,y)均为真有一对x、y

使

H(x,y)为假xy

H(x,y)对每个x,都有y使

H(x,y)为真有x,使

H(x,y)对每个y

总是假xy

H(x,y)有一个x,使H(x,y)对所有y均为真对每个x都有y使

H(x,y)为假xy

H(x,y)yxH(x,y)有一对x、y使

H(x,y)为真对每一对x、y，

H(x,y)均为假2.2一阶逻辑公式及解释本课程中用到的字母表：

(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)括号与逗号：(,),，原子公式

原子公式

R(t1,t2,…,tn)它是任意的n元谓词，t1,t2,…,tn是任意的n个项.项的递归定义个体常项和个体变项是项.若(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是项，则(t1,t2,…,tn)也是项.只有有限次使用(1),(2)生成的符号才是项其实，原子公式是由项组成的n元谓词.如，F(x,y),F(f(x1,x2),g(x3))等均为原子公式。合式公式

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

(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式

(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式

(4)若A是合式公式，则xA,xA也是合式公式

(5)只有有限次地应用(1)~(4)形成的符号串才是合式公式.如：x(M(x)F(x))个体变项的自由出现与约束出现

定义

在公式xA和xA中，称x为指导变元，称A为辖域。

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

x(F(x,y)G(x,z))

中

A=(F(x,y)G(x,z))为x的辖域，

x是约束出现，

y与z均为自由出现。闭式:不含自由出现的个体变项的公式.约束变元的换名规则如：(x)P(x)∨R(x,y)(x)的辖域为P(x)，x是约束出现R(x,y)中x,y都是自由出现x既可以是约束的、又可以是自由的，容易混淆。换名规则将量词辖域中的某个约束出现的个体变项及对应的指导变项改成公式中未曾出现的个体变项符号，公式中的其余部分不变。注意：改名时一定要更改为辖域中没有出现的变元名称。例如：(x)P(x)∨R(x,y)改名为：(z)P(z)∨R(x,y)或(x)P(x)∨R(z,y)公式的解释

给定公式

A=x(F(x)G(x))成真解释:个体域N,F(x):x>2,G(x):x>1

代入得A=x(x>2x>1)

真命题成假解释:个体域N,F(x):x>1,G(x):x>2代入得A=x(x>1x>2)

假命题问:xF(x)xF(x)有成真解释吗？xF(x)xF(x)有成假解释吗？

公式的解释

定义：

解释I由下面4部分组成：

(a)

非空个体域D(b)

D中一些特定元素的集合

(c)

D上特定函数集合

(d)

D上特定谓词的集合

说明：在使用一个解释I解释一个公式A时，将A中的个体常项用解释I中特定元素代替，函数和谓词用解释I中的特定函数和特定谓词代替公式的解释举例[P44例2.7]给定解释I如下：D={2,3};D中特定元素a=2;谓词:

F(x):F(2)=0,F(3)=1

G(x,y):G(i,j)=1,i,j=2,3Ax(F(x)G(x,a))

x(F(x)G(x,2))

(F(2)G(2,2))

(F(3)G(3,2))

(01)

(11)0

x

A(x)=A(a1)A(a2)…A(an)公式的解释举例[P44例2.7]给定解释I如下：D={2,3};函数f(x):f(2)=3,f(3)=2谓词:

F(x):F(2)=0,F(3)=1

G(x,y):G(i,j)=1,i,j=2,3

B

x(F(f(x))G(x,f(x)))

(F(f(2))G(2,f(2)))

(F(f(3))G(3,f(3)))(F(3)G(2,3))

(F(2)G(3,

2))

(11)

(01)

1

x

A(x)=A(a1)

A(a2)…

A(an)

公式的解释举例[P44例2.7]给定解释I如下：D={2,3};谓词:L(x,y):L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0

C

xyL(x,y)

yL(2,y)

yL(3,y)

(L(2,2)L(2,3))

(L(3,2)L(3,3))

(10)

(01)1

x

A(x)=A(a1)

A(a2)…

A(an)

x

A(x)=A(a1)A(a2)…A(an)

x(L(x,2)

L(x,3))公式的分类

问题：xF(x)xF(x)

有成真解释吗？xF(x)xF(x)

有成假解释吗？

永真式（逻辑有效式）：无成假赋值。矛盾式（永假式）：无成真赋值。可满足式：至少有一个成真赋值。几点说明：永真式为可满足式，但反之不真;判断公式是否为永真式不是易事;某些代换实例可判公式类型。代换实例

定义

设A0是含命题变项p1,p2,…,pn的命题公式，A1,A2,…,An是n个谓词公式，用Ai处处代替A0中的pi(1in)

，所得公式A称为A0的代换实例.

例如:

F(x)G(x),xF(x)yG(y)都是pq的代换实例但：x(F(x)G(x))不是pq的代换实例.

定理

重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。代换实例举例例：判断下列公式中哪些是逻辑有效式？哪些是矛盾式？

(1)xF(x)xF(x)

因为若前件是真，则后件肯定为真；不存在前件是真，后件为假的情况；所以，此公式为逻辑有效式（永真式）

(2)(F(x,y)R(z))R(z)代换实例：(p

q)q

(p

q)q(p

q)q0所以是矛盾式代换实例举例例：判断下列公式中哪些是逻辑有效式？哪些是矛盾式？

(3)xyF(x,y)xyF(x,y)

取解释I如下：个体域N；F(x,y)：x≤yxy(x≤y)xy(x≤y)

逻辑真逻辑真取解释I如下：个体域N；F(x,y)：x=yxy(x=y)xy(x=y)

逻辑真逻辑假可见，此公式是非逻辑有效式的可满足式2.3

一阶逻辑等值式定义设A、B是一阶逻辑中任意的两公式，若AB为逻辑有效式，则称A与B是等值的，记作AB，并称AB为等值式.

命题逻辑中等值式的推广因为重言式都是逻辑有效式，所以第1章中的24个等值式及其代换实例都是一阶逻辑中的等值式：如：(AB)AB

(xF(x)yG(y))xF(x)yG(y)如：ABAB

xF(x)yG(y)

xF(x)yG(y)一阶逻辑等值式消去量词等值式当个体域为有限集时，如D={a1,a2,a3,….,an}。对于任意谓词，都有x

A(x)=A(a1)A(a2)……A(an)x

A(x)=A(a1)

A(a2)……

A(an)

量词否定等值式设A(x)是含自由变项x的任意谓词公式。则

¬(x)A(x)(x)¬A(x)¬(x)A(x)(x)¬A(x)约定量词之前的否定联结词，不是否定该量词，而是否定该量词及其辖域.量词作用域的扩展与收缩等值式

(x)(A(x)

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

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

(x)(BA(x))B

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

A(x))B

(x)A(x)(x)(A(x)

B)(x)A(x)

B(x)(A(x)

B)(x)A(x)

B

设：A(x)是含自由变元x的任意谓词公式。

B是不含变元x的谓词公式量词对应两边没改变量词对应两边有改变

量词作用域的扩展量词作用域的收缩一阶逻辑等值式量词分配等价式设A(x)和B(x)是含自由变项x的任意谓词公式，

(x)(A(x)B(x))(x)A(x)(x)B(x)可以理解为：“所有的x有性质A和性质B”和“所有的x有性质A且所有的x有性质B”等同。

(x)(A(x)B(x))(x)A(x)(x)B(x)注意：对无分配律，对无分配律例将下面命题用两种形式符号化

(1)没有不犯错误的人。解：设M(x)：x是人，F(x)：x犯错误.x(M(x)F(x))x

(M(x)F(x))x(

M(x)

F(x))x(M(x)F(x))(2)不是所有的人都爱看电影。解：令M(x)：x是人，G(x)：x爱看电影.

x(M(x)G(x))x

(M(x)G(x))x

(M(x)G(x))x(M(x)G(x))¬(x)A(x)(x)¬A(x)

¬(x)A(x)