计算机数学基础-第9章.ppt

第9章谓词逻辑根底;9.1谓词逻辑的根本概念;9.1.1个体、谓词与谓词表达式;个体：谓词演算中把要讨论对象称为个体，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。

表示法：

个体常元：确定的个体常用a，b，c等小写字母或字母串表示。

个体变元:不确定的个体常用字母x，y，z，u，v，w等来表示。;谓词的元数：通常把谓词所含个体的数目称为谓词的元数。

表示单个个体性质的谓词是一元谓词，例如P(x)。表示两个个体之间关系的谓词是二元谓词，例如Q〔x,y〕;依此类推得n元谓词。N=0时，称为0元谓词，它本身就是一个命题。故命题就是n元谓词的特殊情况;例将以下语句写成谓词表达式形式:

(1)苏格拉底是要死的;

(2)-5的平方非负;

(3)董旎生于青岛;

(4)3+5=8.;9.1.2命题函数与个体域;(4)“y是非负实数当且仅当y大于等于零”可表示为:NN(y)?0≤y,其中;9.1.3量词与辖域;例将以下命题符号化.

(1)?每个母亲都爱自己的孩子；

(2)所有的人都呼吸；

(3)某些实数是有理数.;定义:在公式?xP(x)和?xP(x)中,称x为指导变元或者作用变元,P(x)为相应量词的辖域或作用域.;约束变元更名规那么：

对于约束变元可以更名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余局部不变。

更名时一定要更改为作用域中没有出现过的变元名称。;(3)?x的辖域是,?x的辖域是.;例：对公式?x(F(x)→G(x,y))∧H(x,y)换名,下面的几种做法中哪个是正确的?;两点说明:;例：设个体域为整数集合,L(x,y):x+y=10.判断以下公式的真值.;9.1.4谓词公式与语句的形式化;(3)有限步使用(1),(2)所形成的符号串是公式.;(2)准确地使用量词和确定量词的辖域,当辖域中多于一个谓词时必须注意括号的使用.;例设个体域是人类,试将以下语句译为谓词公式.(1)有人勇敢,但不是所有的人都勇敢.(2)我为人人,人人为我.(3)勇敢者未必都是成功者.;当语句中涉及不同类个体时，需要采用全总个体域。这时候就需要使用“限定谓词”。;例将以下语句用谓词公式形式化.;∧?x(M(x)∧?y(F(y)→L(x,y)));9.2谓词逻辑的等价式和蕴涵式;9.2.1谓词公式的永真、

永假与可满足式;定义9.3给定个体域D及谓词公式A,如果对A的所有赋值谓词公式A都为真,那么称A在D上永真;假设公式A在任何个体域D上及对其谓词的任何解释都为真,那么称A为永真式,或称A永真.;定义9.4给定个体域D及谓词公式A,如果对A的所有赋值谓词公式A都为假,那么称A在D上永假;假设公式A在任何个体域D上及对其谓词的任何解释都为假,那么称A为永假式,或称A永假.;定义9.5给定个体域D及谓词公式A,如果对A的所有赋值谓词公式A有的为真,有的为假,那么称A在D上可满足,假设公式A在某一个体域D上及对其谓词的某一解释为可满足,那么称A为可满足式.;9.2.2谓词逻辑的等价式与蕴涵式;谓词逻辑中的等价式和蕴涵式;例如:;约定:量词之前的否认联结词,不是否认该量词,而是否认该量词及其辖域.;解释：对等价式?(?xA(x))??x(?A(x))而言,?(?x(A(x))表示:并不是所有的x都有性质A.?x(?A(x))表示:存在x没有性质A.显然“并不是所有的x都有性质A”和“存在x没有性质A”是相同的,所以?(?x(A(x))??x(?A(x)).;(5)量词辖域的扩张与收缩时的等价式;前者可以理解为:“所有的x有性质A和性质B”和“所有的x有性质A且所有的x有性质B”是等同的.后者可以利用前者来证明.;例.设个体域为某联欢会上的所有人,A(x):x在

联欢会上唱歌;B(x):x在联欢会上跳舞.;联欢会上所有的人唱歌,或者联欢会上所有的人跳舞可表示为:;例证明如下等价式:;