离散数学及应用 课件 2.1-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