离散数学及应用 课件 第2章 谓词逻辑

DiscreteMathematics离散数学2课程引入

为什么要有谓词逻辑？命题是一种简单的陈述，不足以表现人们想要表达的内容，甚至无法处理一些简单而常见的推理。命题逻辑的局限性例：苏格拉底三段论：

凡是人都要死的.

苏格拉底是人.

所以苏格拉底是要死的.在命题逻辑中，只能用p、q、r表示以上3个命题，上述推理可表成(p∧q)→r（计算真值表）这不是重言式，但实际上它总是正确的。为什么？原因：“凡是人都要死的”作为命题p失去了内在含义

命题逻辑没有体现p、q、r之间的联系。3命题逻辑的局限性

在上一章的命题逻辑项目中，我们构建了一个简单的医疗专家系统，该系统能够基于一组已知的病情条件，通过逻辑推理得出诊断结论。然而，命题逻辑的表达能力是有限的，它只能处理整体命题的真假关系，而无法直接表示个体与属性之间的联系。例如，在命题逻辑中，我们只能写出“某个患者有某种症状”这样的具体命题，而无法灵活地表达“所有具有某种症状的患者都可能患某种疾病”这样的普遍性规则。45第2章谓词逻辑2.1谓词逻辑基本概念2.2谓词逻辑合式公式及解释2.3谓词逻辑等值式与前束范式62.1谓词逻辑基本概念

个体词谓词量词谓词逻辑中命题符号化7基本概念个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a,b,c表示个体变项：抽象的事物，用x,y,z表示个体域:个体变项的取值范围

有限个体域，如{a,b,c},{1,2}

无限个体域，如N,Z,R,…

全总个体域:宇宙间一切事物组成8基本概念(续)谓词:表示个体词性质或相互之间关系的词

谓词常项：F(a)：a是人

谓词变项：F(x)：x具有性质F

元数:谓词中包含的个体词数

一元谓词:表示事物的性质如L(x)：x是深职大的老师

L(x)属于命题吗？（学习通—抢答）

当x为鄢小虎时，L(x)是命题，并且是真命题。

当x为刘德华时，L(x)是假命题。

9基本概念(续)多元谓词(n元谓词,n

2):表示事物之间的关系

如L(x,y)：x与y是同事；G(x,y)：x

y。当x为鄢小虎，y为刘德华时，L(x,y)是命题，并且是假命题。当x=10，y=9时，G(x,y)是真命题。

0元谓词:不含个体变项的谓词,即命题常项或命题变项。例如：

L(鄢小虎，刘德华)；G(9,2)。是命题吗？10基本概念(续)量词:表示数量的词

全称量词

:表示任意的,所有的,一切的等

如

x表示对个体域中所有的x

例如：班上所有同学都非常优秀。

存在量词

:表示存在,有的,至少有一个等

如

x

表示在个体域中存在x例如：班上有的同学非常优秀。11谓词逻辑中命题符号化

例

用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化

(1)墨西哥位于南美洲在命题逻辑中,设p:

墨西哥位于南美洲

符号化为

p

在谓词逻辑中,设a：墨西哥，F(x)：x位于南美洲,符号化为F(a)例(续)(2)

是无理数仅当是有理数解：

(2)在谓词逻辑中,设F(x):x是无理数,G(x):x是有理数,符号化为(3)在谓词逻辑中,设F(x,y)：x>y，G(x,y)：x<y,

符号化为F(2,3)

G(3,4)(3)如果2>3，则3<4在谓词逻辑中将下面命题符号化10比较与命题逻辑符号化的不同之处13谓词逻辑中命题符号化(续)例

在谓词逻辑中将下面命题符号化

(1)正数都大于负数

(2)有的无理数大于有的有理数解

注意:题目中没给个体域,使用全总个体域

(1)令F(x):x为正数,G(y):y为负数,L(x,y):x>y

x(F(x)

y(G(y)

L(x,y)))

或x

y(F(x)

G(y)

L(x,y))两者等值

(2)令F(x):x是无理数,G(y):y是有理数,L(x,y)：x>y

x(F(x)

y(G(y)

L(x,y)))或x

y(F(x)

G(y)

L(x,y))两者等值课堂练习习题1中的(1)-(4)15谓词逻辑中命题符号化(续)几点注意：

0元谓词、1元谓词与多元谓词的区分无特别要求,应使用全总个体域,引入特性谓词量词顺序一般不能随便颠倒

162.2谓词逻辑公式合式公式(简称公式)个体变项的自由出现和约束出现公式分类

永真式，矛盾式,可满足式可认为谓词逻辑是命题逻辑的推广，命题逻辑中的很多概念、规则都可推广到谓词逻辑中延用17字母表

定义字母表包含下述符号：

(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)括号与逗号：(,),，18项定义项的定义如下：

(1)个体常项和个体变项是项.(2)若

(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则

(t1,t2,…,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.个体常项、变项是项，由它们构成的n元函数和复合函数还是项19原子公式

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

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

A)也是合式公式

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

B),(A

B),(A

B),(A

B)也是合式公式

(4)若A是合式公式，则

xA,

xA也是合式公式

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

x(F(x)

G(x)),

x

y(x+y=1)21个体变项的自由出现与约束出现

定义在公式

xA和

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

x和

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

x(F(x,y)

G(x,z))中,

x为指导变元,A=(F(x,y)

G(x,z))为

x的辖域，A中x的两次出现均为约束出现，

y与z均为自由出现.22公式的解释与分类

闭式:不含自由出现的个体变项的公式.给定闭式A=

x(F(x)

G(x))取个体域N,F(x):x>2,G(x):x>1

代入得A=

x(x>2

x>1)真命题给定非闭式B=

xF(x,y)取个体域N,F(x,y):x

y

代入得B=

x(x

y)不是命题（判断结果不确定）令y=1,B=

x(x1)假命题23解释和赋值

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

(a)

非空个体域DI(b)

对每一个命题常项a

指定一个

DI

(c)

对每一个函数符号f指定一个DI上的函数

(d)

对每一个谓词符号F指定一个DI上的谓词赋值

：对每一个命题变项x指定一个值

(x)

DI公式A在解释I和赋值

下的含义：

取个体域DI,并将公式中出现的a、f、F

分别解释成、、,把自由出现的x换成

(x)后所得到的命题.

在给定的解释和赋值下,任何公式都成为命题.类似真值表中的命题变项的真值指派24实例例

给定解释I如下:

(a)个体域D=N(b)(c)(d)谓词以及赋值

：

(x)=0,

(y)=1,

(z)=2.说明下列公式在I与

下的涵义,并讨论真值

(1)

xF(g(x,a),y)

x(2x=1)假命题

xF(f(x,y),g(x,z))；

x

y

zF(f(x,y),z)？25例(续)

x

y

z(x+y=z)真命题(2)

xF(f(x,y),g(x,z))

x(x+1=2x)真命题(3)

x

y

zF(f(x,y),z)26公式的分类

永真式(逻辑有效式):在任何解释和赋值下为真命题矛盾式(永假式):在任何解释和赋值下为假命题可满足式：存在成真的解释和赋值说明：永真式为可满足式，但反之不真谓词公式的可满足性（永真性,永假性)是不可判定的（丘奇-图灵定理），解释有无限多种27代换

定义设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)∨∃yG(y))；28重言式p→(p∨q)的代换实例,是重言式.(2)

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

(p→q)∧q的代换实例,是矛盾式.DiscreteMathematics鄢小虎

离散数学2.3谓词逻辑等值式与前束范式等值式基本等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式前束范式等值式与基本等值式

基本等值式:命题逻辑中16个基本等值式的代换实例如，

xF(x)

yG(y)

xF(x)

yG(y)(蕴涵等值式)

xF(x)

(

xF(x)

yG(y))

xF(x)(吸收律)课堂练习：

(

xF(x)

yG(y))

xF(x)

yG(y)(德摩根)定义若A

B为逻辑有效式，则称A与B是等值的，记作A

B，并称A

B为等值式.基本等值式(续)量词辖域收缩与扩张等值式

设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的：

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)关于存在量词的:

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)B与x无关;A(x)与x相关，因此x必须靠近A(x)基本的等值式(续)量词否定等值式（

互换）设A(x)是含x自由出现的公式

xA(x)

x

A(x)(不是所有=存在不是)

xA(x)

x

A(x)量词分配等值式

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)注意：

对

无分配律，

对

无分配律,即

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)

例计算下列公式的真值（提示：代换实例）

(1)xF(x)→(

xyG(x,y)→xF(x))

(2)xF(x)→(

xF(x)yG(y))

(3)

(F(x,y)→R(x,y))R(x,y)解(1)把xF(x)和(

xyG(x,y)分别用P和Q表示则原式P→(Q→P)P(

Q

P)

1把xF(x)和yG(y)分别用P和Q表示

(2)则原式P→(PQ)P(PQ)

1把F(x,y)和R(x,y)分别用P和Q表示(P→Q)

Q

P(QQ)

0

(3)命题逻辑——析取（合取）范式谓词逻辑，规范形式？前束范式前束范式

例如，

x

y(F(x)

(G(y)

H(x,y)))

x

(F(x)

G(x))是前束范式,而

x(F(x)

y(G(y)

H(x,y)))不是前束范式.定义设A为一个谓词逻辑公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi

(1

i

k)为

或

，B为不含量词的公式.简言之：量词都在前面；辖域都在后面抢答：

x(F(x)

G(x))、H(x,y)是不是前束范式？公式的前束范式例求下列公式的前束范式

(1)

xF(x)

xG(x)解

定理（前束范式存在定理）谓词逻辑中的任何公式都存在与之等值的前束范式，但不唯一求前束范式:使用重要等值式、置换规则、换名规则进行等值演算.步骤：消除

、

；利用否定等值式将

内移；利用分配等值式将

x和

x等前移

xF(x)

x

G(x)（量词否定等值式）

x(F(x)

G(x))（量词分配等值式）例(续)(2)

x(M(x)

F(x))解(3)