教案第3章-一阶逻辑

第3

章—阶逻辑（谓词逻辑）本章主要学习以下内容：3.1

一阶逻辑基本概念3.2

一阶逻辑等值演算＊3.3

一阶逻辑推理理论第3章

一阶逻辑3.1.1

命题逻辑的局限性例1：考虑下述推理:凡偶数都能被2整除，6是偶数，所以，6能被2整除。令p：凡偶数都能被2整除q：6是偶数r：6能被2整除符号化为：(p

q)

r显然，110是其成假赋值。所以，在命题逻辑中不能证明其正确性。3.1

一阶逻辑的基本概念例2：熊猫是动物。长颈鹿是动物。命题符号化：令p：熊猫是动物

q：长颈鹿是动物命题符号不能揭示这两个命题的共性。因此，需要对简单命题的成分、结构、简单命题间的共性等作进一步分析。这正是一阶逻辑所要研究的问题。3.1.1

命题逻辑的局限性例3：分析以下命题的成份。计算机

是科学技术的工具。是个大学生。在一阶逻辑中，将进一步地把简单命题分解为主语（

词）与谓语（谓词）两部分。3.1.2

词 谓词 量词1、词所研究对象中，可以独立存在的具体的或抽象的客体（事物）称为

词。例如：计算机,熊猫,爱国主义,

,,10。2、

常项， 变项常项：表示具体、特指的

词。常用a,b,c…表示。变项：表示抽象、泛指的

词。常用x,

y,z…

表示。一、词及相关概念3、域(

)或论域域，是指

变项的取值范围。常用字母D表示。说明：（1）

域可以是有限集或无限集例：{1,3,5,7}，实数集R

等。（2）全总

域是包含宇宙全体事物的最大

域。若无特别

，

域总是指全总

域。一. 词及相关概念1、谓词概念谓词是用来刻划

词性质或

词之间关系的词。常用大写字母

F,

G,

H…表示。例：分析以下命题或命题变项位于

与杭州之间。比

高(1)

熊猫是动物。(2)(4)(5)3大于2，x

<y，x+y=z二、谓 词

(predicate)（1）一般地：

“

x

是…

”

类型 题，可符号化为F(x)

。例：熊猫是动物、

是动物。F：是动物

x：熊猫

y：则

F(x)：熊猫是动物F(y)：

是动物2、用谓词表示命题（2）

一般地：“x

＜y”、“…比…高”等类型题，可符号化为F(x,

y)。例：

3

>

2，

比设

F：大于高。G：…比…高a：3

b：2则

F(a,

b)：

3

>

2F(b,

a)：

2

>

3c：

d：例：G(c,

d)：

比

高位于

与杭州之间，如何用谓词表示？3、谓词常项，谓词变项表示有具体性质或关系的谓词，称为谓词常项，否则就称为谓词变项。例：（1）他是三好生。（2）每天做广播操是好（3）a

与b

满足关系P。符号化为P(a,

b)。。

谓词常项谓词常项P是谓词变项4、n元谓词称包含

n

个（n≥1）

词（常项或变项）的域为定义域、谓词为n元谓词。可表示为：P(x1,x2,…,xn)。n元谓词，可以看成是以以｛0,1｝为值域的n元函数。例：F(x)

－－

一元谓词，x

为

变项。F(a,

b)－－

二元谓词，a,

b为

常项。注意：谓词P(x1,x2,…,xn)，还不是命题。变项的谓词，称为0元谓词。a：约定：将不含例如：H(a)P(c,

d)c：

d：月亮当谓词H、P

确定含义后，0元谓词H(a)、P(c,

d)为命题。注意：命题逻辑中

题，都可以用0元谓词表示。因此，可以把命题看作是谓词的特殊情况。命题逻辑中的联结词也是谓词，在一阶逻辑中均可使用。例

3.1

将下列命题用0元谓词符号化，并

它们的真值。(1)

2

是素数且是偶数。解：设F(x)：x

是素数，G(x)：x

是偶数，a：2则命题可符号化为：F(a)∧G(a)或F(2)∧G(2)。其真值为1。(2)

若2＞3，则2＞4。解：

设

L(x，y)：

x

＞ya：

2

b：3

c：4则命题可符号化为：L(a，b)

→

L(a，c)或L(2，3)→L(2，4)真值为1。y：鸟例1：所有的鸟都会飞。设F(x)：x

都会飞F(y)：鸟都会飞－－－－语气不足例2：有的人活百岁以上。设

G(x)：

x

活百岁以上

y：人G(y)：人活百岁以上－－－－不合题意三、

量

词

称表示

常项或变项之间数量关系的词，为量词。1、全称量词表示“所有”、“任意”等的词，称为全称量词。记为“”。域中的所有

x。域中的所有

x，都x

－－表示对x

F(x)－－表示有性质F。三、

量

词2、存在量词表示“存在着”、“有某些”等的词，称为存在量词。记为“

”符号。x－－表示存在

域中的

x

。x

F(x)－－表示存在

域中的有性质F。注意：（1）量词可看作是对x

，具词附加的约束词。（2）量词的使用，要配合域的取值范围。域D：鸟集合。例子：设F(x)：x

会飞，x

F(x)－－“所有的鸟都会飞”。(2)

设G(x)：x

是白的， 域

D：菊花集。x

G(x)－－“有些菊花是白的”。题的真值，与

域的范围有关。注意：

含有量词三、

量

词例子：(3)

设F(x)：x会飞，D为全总

域。x

F(x)－－“宇宙间的一切事物都会飞”。(假命题)引进特性谓词，一般用字母M表示设M(x)：x

是鸟，则x

(M(x)→F(x))－－“所有的鸟都会飞”。(真命题)例子：(4)

有些菊花是白的。

全总

域上

。设

G(x)：x

是白的，xG(x)－－“有些事物是白的”。(真命题，不合题意)设M(x)：x是菊花。x

(M(x)∧G(x))－－“有些菊花是白的”(真命题，合题意)3、特性谓词在

域D中，为某部分

的性质而引入的谓词，称为特性谓词。常用字母M表示。在全总

域中，特性谓词用于限制

变项的取值范围。注意：量词后的特性谓词，接蕴涵（→）联结词；量词后的特性谓词，接合取（∧）联结词。一、命题符号化的步骤二、命题符号化示例三、命题符号化的注意事项3.1.3

一阶逻辑命题符号化一、一阶逻辑命题符号化的步骤1、把每个简单命题分解成

词、谓词；在全总

域中

，要给出特性谓词。2、找出恰当量词。注意：全称量词(x)后，跟条件式，存在量词(x)后，跟合取式。3、用恰当的联结词。把给定

题表示出来。3.1.3一阶逻辑命题符号化例3.2

在一阶逻辑中将下面命题符号化:人都爱美。域D

分别取：(a)人类集合,解:

(a)

设

F(x):(b)

全总

域。x

爱美命题符号化为：x

F(x)(b)

设

F(x):

x

爱美M(x):

x

是人命题符号化为：x

(M(x)F(x))二、一阶逻辑命题符号化示例例3.3

将下列命题符号化，并

其真值：对任意x，均有

x23x+2=(x1)(x2)。存在x，使得x+5=3。D分别取：(a)

域

D1=N,

(b)

域

D2=R解：

设

F(x)：x23x+2=(x1)(x2),G(x):

x+5=3(a)

命题(1)

符号化为：x

F(x)命题(2)符号化为：x

G(x)(b)

命题(1)符号化为：xF(x)命题(2)

符号化为：x

G(x)真值为1真值为0真值为1真值为1真值。例3.4

(P.88)

将下面命题符号化，并所有的人都长着黑头发有的人登上过月球没有人登上过木星留学的学生未必都是亚洲人(4)在注意：没有给出域，一般在全总域上考虑。二、一阶逻辑命题符号化示例例3.5

(P.89)

将下面命题符号化:兔子比乌龟跑得快。有的兔子比所有的乌龟跑得快。并不是所有的兔子都比乌龟跑得快。不存在跑得一样快的兔子和乌龟。解：在全总

域上考虑。令

F(x)：x是兔子,

G(y)：y是乌龟,H(x,y)：x

比y

跑得快,L(x,y)：x

和y跑得一样快x

y(F(x)G(y)H(x,y))x

(

F(x)

y

(G(y)H(x,y))

)x

y

(F(x)G(y)H(x,y))x

y(F(x)G(y)L(x,y))例子：将下列命题符号化：没有最大的自然数。解：即“对任意的自然数x，一定存在自然数y，且y

比x

大”。令N(x)：x

是自然数G(x,y)：x

大于y则原命题表示为：x

(

N(x)

y

(N(y)G(y,

x))

)例子：本章开头之例如何符号化？课堂练习（

p102

习题

3.5）二、一阶逻辑命题符号化示例2、

域不同，命题符号化的形式可能不同。3、若没给出

域的范围，则考虑全总

域。4、在引入特性谓词后，使用全称量词或存在量词符号化的形式，是不同的。5、多个量词同时出现时，一般不能随意颠倒它们的次序，因为有可能会改变原命题的含义。三、一阶逻辑命题符号化注意事项1、分析命题中表示性质和关系的谓词，分别符号化为1元和n（n≥2）元谓词。例子：yx

F(x,y)，F(x,y)：x<y域为实数集R。：原命题是真命题。若将量词次序改为：xy

F(x,y)表示存在一个实数

x，对任何实数y，均有x<y，是假命题。三、一阶逻辑命题符号化注意事项6、

当

域是有限集时，量词可用联结词替代。设

域

D

={a1,

a2,…,

an}，则包含有全称量词的谓词公式：x

A(x)表示a1

有性质A，a2

有性质A,…an

有性质A。因此：x

A(x)

A(a1)∧A(a2)∧…∧A(an)思考：x

A(x)

A(a1)∨A(a2)∨…∨A(an)三、一阶逻辑命题符号化注意事项一、一阶语言

ℱ二、谓词的

合式公式三、量词的

辖域四、谓词公式的解释及分类3.1.4

一阶逻辑公式与分类一、一阶语言ℱ定义3.1（P.90）一阶语言ℱ的字母表定义如下：(3)函数符号：f,g,h,…,fi,gi,hi,…,常项：a,

b,c,…,

ai,

bi,ci,…,

i1变项：x,

y,

z,

…,

xi,

yi,

zi,

…,

i

1i1谓词符号：F,G,H,…,Fi,Gi,Hi,…,i

1量词符号：,联结词符号：,,,,括号与逗号：(),，定义3.2

(P.90)ℱ的项的定义如下：常项、

变项是项。若

(x1,x2,…,xn)是任意的n

元函数，t1,t2,…,tn

是任意的n个项，则

(t1,t2,…,tn)是项。所有的项都是有限次使用

(1),(2)得到的。说明：①

项是

词，而非谓词。一、一阶语言ℱ说明②：有了项的概念，常项、变项可以利用函数表示。例子：试利用函数及谓词表示：“5

是自然数”令

函数

f

(x,y)=

x+y，谓词N(x)：x

是自然数，则

f

(2,3)

表示

常项

5，而

N(f

(2,3))

表示

5

是自然数。一、一阶语言ℱ例子：试用函数及谓词表示“的父亲是教授”。设

P(x)：x

是教授f

(x)：x

的父亲c：（f

(x)仍是词）则命题可符号化为：P

(f(c))注意：函数与谓词的区别（谓词是特殊的函数）。一、一阶语言ℱ说明③：函数的使用，使谓词表示更方便。例子：用谓词表示以下命题：对任意整数

x，

x2-1=(x+1)(x-1)。令

F(x)：x

是整数f

(x)

=

x2-1g(x)

=

(x+1)(x-1)E(x,

y)：x=y则该命题可表示成：x

(F(x)E

(f(x),g(x)))。一、一阶语言ℱ定义3.3

(P.90)设

R

(x1,

x2,…,

xn)

是

ℱ

的任意

n

元谓词，t1,

t2,…,

tn是

ℱ

的任意

n

个项，则称R

(t1,t2,…,tn)是ℱ的原子公式。即：一个n

元谓词：R

(t1,t2,…,tn)是一个原子公式。其中，t1,

t2,

…,

tn

是ℱ

的任意

n

个项。二、谓词公式定义3.4

（

P.91）ℱ的合式公式定义如下：原子公式是合式公式。若A

是合式公式，则(A)也是合式公式。若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。若A是合式公式，则xA，xA

也是合式公式。只有有限次地应用(1)~(4)形成的符号串才是合式公式。合式公式又称谓词公式，简称公式。注意：命题公式是谓词公式。二、谓词公式三、量词的辖域定义3.5

（P.91）在公式xA

和xA

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

和x

的辖域中，

x

的所有出现都称为约束出现，A中不是约束出现的其他

变项称为

出现。说明：①若量词后有括号，该量词的辖域，为括号内的子公式；②若量词后无括号，该量词的辖域，为与其邻接的子公式。例子

：求下列公式中的指导变元、各量词的辖域、

出现、约束出现的 变项。(1)

x

P(x)∧Q(y)解：x

是指导变元，约束出现。x

的辖域：P(x)y

是

出现。(2)

x

(A(x)∨yB(x,

y))解：x，y

是指导变元，都是约束出现。x

的辖域：(A(x)∨y

B(x,

y))y

的辖域：B(x,

y)三、量词的辖域例子

：求下列公式中的指导变元、各量词的辖域、

出现、约束出现的

变项。(3)x

A(x)

B(x)解：x

的辖域：A(x)x

在A(x)

中，是约束出现，x

在

B(x)

中，是

出现。三、量词的辖域例3.6

公式

x

(F(x,

y)

y

G(x,

y,

z))x

的辖域：(F(x,y)y

G(x,y,z))，指导变元为x；x

的两次出现，均为约束出现。y

的辖域：G(x,y,z)，指导变元为y；y

的第1次出现，为

出现，第2次出现，为约束出现。出现。z

为三、量词的辖域例：公式x

(F(x)xG(x))x

的辖域:(F(x)xG(x))，指导变元为

xx

的辖域:G(x)，指导变元为

xx

的两次出现均为约束出现。但是,第一次出现的

x

是x

中的x,第二次出现的x

是x

中的x.三、量词的辖域说明：本书用A(x1,x2,…,xn)表示含

x1,x2,…,xn

为

出现的公式。在公式⊿xi

A(x1,x2,…xi-1,xi

,xi+1

,…,xn)中，只有xi

为约束出现。其中，⊿表示

或。在公式⊿x1⊿x2

…

⊿

xn

A(x1,x2,

…,

xn)

中，无

出现的

变项。课堂练习（

p103

习题

3.14）三、量词的辖域定义3.6

（P.92）设

A为任意一个公式，若

A中无

出现的个体变项，则称

A为封闭的公式，简称闭式。变项，均为约束出现。即：闭式中所有例子：x

(P(x)Q(x))，是闭式，xy

(P(x)Q(x,y))x

(P(x)Q(x,y))，

yz

L(x,y,z)不是闭式。三、量词的辖域1、公式的解释

一般谓词公式中含有：

常项、

变项（约束出现或

出现）、函数变项、谓词变项等。对各种变项，用指定的特殊常项去代替，就构成了一个公式的解释。被赋予解释的谓词公式才可能成为命题，才可能有确定的真值。四、谓词公式解释与类型例3.7：将公式

x

(F(x)G(x))中的变项，指定成常项，使其成为命题。解：指定1：令

域

D：全总

域，F(x)：x

是人，G(x)：x

是黄种人假命题。指定2:

令

域D

:实数集,F(x)：x

>10，G(x)：x

>0真命题。对于其它不同的指定，可以得到不同题。四、谓词公式解释与类型定义3.7

设一阶语言ℱ

的常项集为{ai

|i1},函数符号集为{fi

|

i1}，谓词符号集为{Fi

|

i1},ℱ的解释I

由下面4

部分组成:(1)

非空

域

D。(2)

对每一个(3)对每一个n

元的函数fi，

D上的n元函数称作函数fi

的解释。常项

ai,

ai

D，称作

ai

的解释。fi

，(4)

对每一个n

元谓词符号Fi，

D上的n元谓词Fi

,称作谓词Fi

的解释。四、谓词公式解释与类型(d)

谓词其真值。试说明下列公式在解释I

下的含义，并(1)

x

F(g(x,

a),

x)例3.8（P.93）

给定解释I

如下：域D

=Na

2f

(x,

y)

x

y,

g(x,

y)

xyF

(

x,

y)

:

x

y公式解释为：

x

(

2x

=

x

)

假命题(2)

xy

(F

(

f(x,

a),

y

)

F

(

f(y,

a),

x

))公式解释为：xy

(

x+2=y

y+2=x

)

假命题四、谓词公式解释与类型xyz

(x+y=z)

真命题x

(2x

=x2

)

真命题x+2

=

2x例3.8（P.93）

给定解释I

如下：(c)域D=Na

2f

(

x,

y)

x

y,

g(

x,

y)

xy(d)谓词F

(x,y):x

yxyz

F

(f

(x,y),z

)x

F

(

f(x,x),

g(x,

x)

)F

(

f(x,

a),g(x,

a)

)不是命题(6)

x

(

F(x,y)