离散数学课件 第二章 谓词逻辑

离散数学

Discrete

Mathematics第二章谓词逻辑2.1谓词的基本概念2.2谓词公式与解释2.3谓词公式的等值式与前束范式2.4谓词演算的推理理论2.5应用22.1

谓词的基本概念第2章谓词逻辑

个体与谓词量词3离散数学2.1.1个体与谓词4定义2.1

在原子命题中，可以独立存在的客体（句子中的主语、宾语等）称为个体词，简称个体。个体词可以是具体的，也可以是抽象的。表示具体的或特定的个体词称为个体常项，一般用小写英文字母a，b，c，…表示。表示抽象的或泛指的个体词称为个体变项，常用小写英文字母x，y，z，…表示。个体变项的取值范围称为个体域（或论域）。个体域可以是有限的集合，如{a,b,c}，{1,2}等。也可以是无限的集合，如自然数集，整数集，实数集等。特别地，如无特别声明时，由宇宙间一切事物组成的个体域称为全总个体域。离散数学5定义2.2

用来刻画个体词性质或个体词之间关系的部分称为谓词。谓词通常用大写英文字母表示，如A，B，C，…。例题2.1

指出下列语句中的个体和谓词。（1）4是偶数。（2）信阳是一个美丽的城市。（3）小王比小李高。（4）满足性质。离散数学2.1.1个体与谓词6谓词也有常项和变项之分，表示具体性质或关系的谓词称为谓词常项，表示抽象或泛指的性质或关系的谓词称为谓词变项。谓词常项和变项都用大写英文字母表示。要用谓词表达命题，一般有2部分组成，即谓词和个体2部分。谓词一般用大写字母表示，而小写字母用来表示个体的名称，如A(x)表示个体变项x具有性质A，P(x,y)表示个体变项x，y满足关系P.例如，Q(x)表示“x是有理数”，G(x,y)表示“x大于y”。离散数学2.1.1个体与谓词7

离散数学2.1.1个体与谓词8

离散数学2.1.1个体与谓词9

离散数学2.1.2量词10

离散数学2.1.2量词11

离散数学2.1.2量词12

离散数学2.1.2量词13

离散数学2.1.2量词2.2

谓词公式与解释第2章谓词逻辑

谓词公式的定义约束变元与自由变元谓词公式的解释14离散数学2.2.1谓词公式的定义15离散数学谓词逻辑中涉及的字母表包含下述符号：

(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)圆括号与逗号：(,),，2.2.1谓词公式的定义16离散数学定义2.3项的递归定义如下：

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

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

(t1,t2,…,tn)是项；(3)只有有限次地使用(1),(2)生成的符号串才是项。个体常项、变项是项，由它们构成的n元函数和复合函数还是项.2.2.1谓词公式的定义17离散数学原子公式定义2.4

设P(x1,x2,…,xn)是任意的n(n>=1)元谓词，t1,t2,…,tn是任意的n个项，则称P(t1,t2,…,tn)是原子公式.原子公式是由项组成的n元谓词.例如，S(x),G(x,y),G(f(x1,x2),g(x3,x4))等均为原子公式.2.2.1谓词公式的定义18离散数学合式公式定义2.5合式公式（又称谓词公式，简称公式）定义如下：

(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)2.2.2约束变元与自由变元19离散数学个体变项的自由出现与约束出现定义2.6

在公式

xA和

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

x和

x的辖域中，x的所有出现都称为约束出现，约束出现的变项称为约束变元，A中不是约束出现的其他变项的出现均称为自由出现，自由出现的变项称为自由变元.2.2.2约束变元与自由变元20离散数学例2.5指出下列各公式中的指导变元、辖域、自由变元和约束变元。(1)

x(P(x)

y

Q(x,y))解：在整个公式中，x是指导变元，

的辖域为(P(x)

y

Q(x,y))，x的两次出现都是约束出现。在

yQ(x,y)中，y为指导变项，

的辖域为Q(x,y)，y是约束出现。

Q(x,y)中的x也是约束出现，但它受前面

x的约束。2.2.2约束变元与自由变元21离散数学(2)

xF(x)

∧G(x,y)解：在

xF(x)中，x是指导变元，

的辖域为F(x)，

x是约束出现。G(x,y)中x、y都是自由出现。在整个公式中，x的第一次出现是约束出现，第二次出现是自由出现，

所以第一个x是约束变元，第二个x是自由变元。本质上这两个x的含义是不同的。y的出现是自由出现，所以y仅是自由变元。2.2.2约束变元与自由变元22离散数学(3)

x(x=y且x2+x<5→x<z)→

x=5y2解：x是指导变变元，

的辖域为(x=y且x2+x<5→x<z)。因此，x第一、二、三、四次出现是约束出现，x第五次出现是自由出现。而y，z的出现均是自由出现。2.2.2约束变元与自由变元23离散数学2.2.2约束变元与自由变元24离散数学规则1(约束变元换名规则)（1）将量词辖域内出现的某个约束变元及其相应量词中的指导变元，可以换成另外一个其他变元；（2）换名时要改为辖域中没有出现过的变元名称，最好是整个公式中都没有出现的变元名称，其他部分不改变。例题2.6对公式中的约束变元进行换名。

xF(x,y)

∧

x

G(x,y)

x的两次出现尽管均是约束的，但分别在不同的辖域，含义是互相无关的。可将它其中一处的约束出现替换成u,得

xF(x,y)∧

uG(u,y)

。

2.2.2约束变元与自由变元25离散数学规则2(自由变元代入规则)（1）进行代入时，公式中出现该自由变元的每一处都应该进行代入；（2）用以代入的变元与原公式中其他变元的名称不能相同。

例题2.7对公式中的变元进行换名。

解x前两次出现是约束的，后两次出现是自由的。y第一次出现是自由的，第二次是约束的，可将自由变元x改为u，自由变元y改为v。2.3.1谓词公式的解释26离散数学定义2.7

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

(a)

非空个体域D；

(b)

每一个个体常项指定D中的一个元素；(c)

每一个n元函数符号指定D”到D的一个映射；

(d)

每一个n元谓词符号指定D”到{0,1}的一个映射。27离散数学2.2.3谓词公式的解释例2.8给定解释I如下:(1)D={2,3};(2)a=2;(3)函数f:D→D，

指定f(2)=3,f(3)=2;(4)谓词F(x):

F(2)=0,F(3)=1;

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

L(x,y):L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0。在解释I下，求下列各式的真值。

(1)

x(F(x)∧G(x,a))解：(F(2)∧G(2,2))∧(F(3)∧G(3,2))

(0∧1)∧(1∧1)

0.28离散数学2.2.3谓词公式的解释例2.8给定解释I如下:(1)D={2,3};(2)a=2;(3)函数f:D→D，

指定f(2)=3,f(3)=2;(4)谓词F(x):

F(2)=0,F(3)=1;

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

L(x,y):L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0。在解释I下，求下列各式的真值。

(2)

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))

(1∧1)

∨(0∧1)

1.29离散数学2.2.3谓词公式的解释例2.8给定解释I如下:(1)D={2,3};(2)a=2;(3)函数f:D→D，

指定f(2)=3,f(3)=2;(4)谓词F(x):

F(2)=0,F(3)=1;

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

L(x,y):L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0。在解释I下，求下列各式的真值。

(3)

x

y

L(x,y)解：

(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))

(1∨0)∧(0∨1)

1.30离散数学2.2.3谓词公式的解释公式的分类定义2.8设A为一公式，如果A在任何解释下均为真，则称A为永真式（或逻辑有效式）；如果A在任何解释下均为假，则称A是矛盾式（或永假式）；若至少存在一个解释使A为真，则称A是可满足式。说明：(1)永真式为可满足式，但反之不真(2)谓词公式的可满足性（永真性,永假性)是不可判定的31离散数学2.2.3谓词公式的解释例2.9判断下列公式哪些是永真式，永假式或可满足式:

(1)A:

x(P(x)

Q(x))

(2)B:

x(P(x)∧Q(x))

(3)C:(

xP(x)∧

y

xQ(x,y))∧

xP(x)(4)D:

xP(x)

(

y

xQ(x,y)

xP(x))

32离散数学2.2.3谓词公式的解释例2.9判断下列公式哪些是永真式，永假式或可满足式:

(1)A:

x(P(x)

Q(x))

(2)B:

x(P(x)∧Q(x))

(3)C:(

xP(x)∧

y

xQ(x,y))∧

xP(x)(4)D:

xP(x)

(

y

xQ(x,y)

xP(x))

(1)

A:

x(P(x)

Q(x))

解：取解释I1为：个体域为实数集R，P(x):x能被2整除，Q(x):x是偶数。取解释I2为：个体域为实数集R，P(x):x能被2整除，Q(x):x是奇数。A为真命题A为假命题A为可满足式33离散数学2.2.3谓词公式的解释例2.9判断下列公式哪些是永真式，永假式或可满足式:

(1)A:

x(P(x)

Q(x))

(2)B:

x(P(x)∧Q(x))

(3)C:(

xP(x)∧

y

xQ(x,y))∧

xP(x)(4)D:

xP(x)

(

y

xQ(x,y)

xP(x))

(2)B:

x(P(x)∧Q(x))

解：分别取（1）中的解释I1和I2，可验证B为可满足式，且不是永真式。B为可满足式34离散数学2.2.3谓词公式的解释例2.9判断下列公式哪些是永真式，永假式或可满足式:

(1)A:

x(P(x)

Q(x))

(2)B:

x(P(x)∧Q(x))

(3)C:(

xP(x)∧

y

xQ(x,y))∧

xP(x)(4)D:

xP(x)

(

y

xQ(x,y)

xP(x))

(3)C:(

xP(x)∧

y

xQ(x,y))∧

xP(x)解：C是(P∧Q)∧

P的代换，而(P∧Q)∧

P是永假式。C为永假式35离散数学2.2.3谓词公式的解释例2.9判断下列公式哪些是永真式，永假式或可满足式:

(1)A:

x(P(x)

Q(x))

(2)B:

x(P(x)∧Q(x))

(3)C:(

xP(x)∧

y

xQ(x,y))∧

xP(x)(4)D:

xP(x)

(

y

xQ(x,y)

xP(x))

(4)D:

xP(x)

(

y

xQ(x,y)

xP(x))解：D是P(Q

P)的代换，而P(Q

P)是永真式。D为永真式2.3

谓词公式的等值式与前束范式谓词公式的等值式前束范式36离散数学37离散数学2.3.1谓词公式的等值式定义2.9设A、B是任意两个谓词公式，若A

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

B，并称A

B为等值式.基本等值式:命题逻辑中24个基本等值式的代换实例如，

xF(x)

yG(y)

xF(x)

yG(y)

(

xF(x)

yG(y))

xF(x)

yG(y)等消去量词等值式

设D={a1,a2,…,an}

xA(x)

A(a1)

A(a2)

…

A(an)

xA(x)

A(a1)

A(a2)

…

A(an)38离散数学2.3.1谓词公式的等值式

xA(x)

x

A(x)

xA(x)

x

A(x)量词否定等值式：设A(x)是含x的任意公式量词否定等值式，可以在有限个体域上证明39离散数学2.3.1谓词公式的等值式

xA(x)

x

A(x)

xA(x)

x

A(x)量词否定等值式：设A(x)是含x的任意公式量词否定等值式，可以在有限个体域上证明40离散数学2.3.1谓词公式的等值式设A(x)是含x自由出现的公式，B中不含x的自由出现。（1）关于全称量词的：

①

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)量词辖域收缩与扩张等值式证明（1）③：

x(A(x)

B)

x(

A(x)

B)

x

A(x)

B

xA(x)

B

xA(x)

B41离散数学2.3.1谓词公式的等值式设A(x)是含x自由出现的公式，B中不含x的自由出现。（1）关于全称量词的：

①

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)（2）关于存在量词的:

①

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)

量词辖域收缩与扩张等值式证明（1）③：

x(A(x)

B)

x(

A(x)

B)

x

A(x)

B

xA(x)

B

xA(x)

B42离散数学2.3.1谓词公式的等值式（1）x(A(x)

B(x))

xA(x)

xB(x)（2）

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)

量词分配等值式例：A(x)：x是奇数，B

(x)：x是偶数

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)真假假真43离散数学2.3.1谓词公式的等值式例2.10

将下面命题用两种形式符号化

(1)不是所有的人都爱游泳

(2)没有不犯错误的人解：

(1)令F(x)：x是人，G(x)：爱游泳

x(F(x)

G(x))

x

(F(x)

G(x))

x(F(x)

G(x))

(2)令F(x)：x是人，G(x)：x犯错误.

x(F(x)

G(x))

x

(F(x)

G(x))

x(F(x)

G(x))44离散数学2.4.1谓词公式的推理规则定义2.10设A为一个谓词公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi

(1

i

k)为

或

，B为不含量词的公式.是是不是不是例如，

x

y(F(x)

(G(y)

H(x,y)))

x

(F(x)

G(x))

x(F(x)

y(G(y)

H(x,y)))

x(F(x)

G(x))45离散数学2.3.2前束范式换名规则:将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成其他辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.定理2.1（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式.求前束范式:使用重要等值式、置换规则、换名规则进行等值演算.46离散数学2.3.2前束范式例求下列公式的前束范式

(1)

xF(x)

xG(x)解：

xF(x)

x

G(x)（量词否定式）

x(F(x)

G(x))(量词分配式)(2)

xF(x)

xG(x)

解：

xF(x)

x

G(x)（量词否定式）

xF(x)

y

G(y)(换名规则)

x

(F(x)

y

G(y))(定理2.2(1)中的①)

x

y(F(x)

G(y))(定理2.2(1)中的①)

47离散数学2.3.2前束范式(3)

xF(x)

xG(x)解：

xF(x)

xG(x)（蕴涵等值式）

x

F(x)

xG(x)（量词否定式）

x(F(x)

G(x))(量词分配式)(4)

xF(x)

xG(x)

解：

xF(x)

yG(y)(换名规则)

x

(F(x)

yG(y))(量词辖域收缩与扩张③)

x

y

(F(x)

G(y))(量词辖域收缩与扩张④)

③

x(A(x)

B)

xA(x)

B

④

x(B

A(x))

B

xA(x)48离散数学苏格拉底三段论的正确性“凡是人都要死的。苏格拉底是人。所以苏格拉底是要死的。”证明这个三段论是正确的。设F(x)：x是人，G(x)：x是要死的，a：苏格拉底。∀x(F(x)→G(x))∧F(a)→G(a)证明：设前件为真，即∀x(F(x)→G(x))与F(a)都为真。由于∀x(F(x)→G(x))为真，故F(a)→G(a)为真.由F(a)与F(a)→G(a)为真，根据假言推理得证G(a)为真2.4

谓词演算的推理理论谓词公式的推理规则谓词公式的推理49离散数学50离散数学在一阶逻辑中，推理的形式结构仍为

A1∧A2∧…∧AkB

若该式是永真式，则称推理正确，称B是A1，A2，…，Ak的有效结论。此时将该式记为

A1∧A2∧…∧AkB命题逻辑中的推理规则，在一阶逻辑中仍然成立。51离散数学2.4.1谓词公式的推理规则1、全称量词消去规则(UniversalInstantiation

),简记为UI2、全称量词引入规则(UniversalGeneralization)简记为UG3、存在量词消去规则(Existential

Instantiation),简记为EI

4、存在量词引入规则(ExistentialGeneralization)简记为EG

一阶逻辑中新增加4条推理规则52离散数学2.4.1谓词公式的推理规则1、全称量词消去规则

（UniversalInstantiation，简称UI规则）

(1)xA(x)A(y)

(2)xA(x)A(c)规则成立的条件为：①x是A(x)中出现的个体变项；②y为任意的不在A(x)中约束出现的个体变项；③c为个体域中任意的个体常项。

53离散数学2.4.1谓词公式的推理规则2、全称量词引入规则

（UniversalGeneralization，简称UG规则）

A(y)xA(x)

规则成立的条件为：①y在A(x)中自由出现，且y取任何值时A都为真；②取代y的x不能在A(y)中约束出现。

54离散数学2.4.1谓词公式的推理规则3、存在量词引入规则

（ExistentialGeneralization，简称EG规则）

A(c)

xA(x)规则成立的条件为：①c是特定的个体常项；②取代c的x不能在A(c)中出现过。

55离散数学2.4.1谓词公式的推理规则4、存在量词消去规则

（ExistentialInstantiation，简称EI规则）

xA(x)A(c)规则成立的条件为：①c是使A为真的特定的个体常项；②c不在A(x)中出现过；③A(x)中除x外还有其他自由出现的个体变项时，不能使用本规则。

56离散数学2.4.2谓词公式的推理3种常用的证明方法

1、直接证法

2、反证法

3、CP规则一阶逻辑中的推理证明57离散数学2.4.2谓词公式的推理例2.12:

证明苏格拉底三段论“凡人都是要死的。苏格拉底是人.所以苏格拉底是要死的。”命题符号化：M(x)：x是人（特性谓词）；

F(x)：x是要死的；

s：苏格拉底前提：x(M(x)→F(x))，M(s)结论：F(s)证明：①x（M(x)→F(x)）

前提引入②M(s)→F(s)①UI规则③M(s)前提引入④F(s)②③假言推理58离散数学2.4.2谓词公式的推理例2.13

构造下面的推理证明。前提：x(P(x)→Q(x)∧R(x))，x(P(x)∧S(x));结论：x(R(x)∧S(x))58①

x(P(x)∧S(x)) 前提引入②P(a)∧S(a)①EI规则

③P(a)

②化简④S(a)

②化简⑤

x(P(x)→Q(x)∧R(x))

前提引入⑥P(a)→Q(a)∧R(a)

⑤UI规则⑦R(a)∧Q(a)

③⑥假言推理⑧R(a)⑦化简⑨R(a)∧S(a)④⑧合取⑩

x(R(x)∧S(x))

⑨EG规则59离散数学2.4.2谓词公式的推理例题2.14用CP规则证明

x(A(x)

B(x))

xA(x)

xB(x)

首先因为

xA(x)

xB(x)

xA(x)→

xB(x)

所以原题可改为：

x(A(x)

B(x))

xA(x)→xB(x)

60离散数学2.4.2谓词公式的推理

x(A(x)

B(x))

xA(x)→xB(x)推理过程如下：

①

xA(x)

附加前提引入②

x

A(x)①置换

③

A(a) ②EI规则④

x(A(x)

B(x))

前提引入⑤A(a)

B(a)

④UI规则⑥B(a)

⑤⑥析取三段论⑦

xB(x)

⑥EG规则

⑧

xA(x)→xB(x)

CP61离散数学2.4.2谓词公式的推理例题2.15构造下面推理的证明。前提：任何不会逻辑推理的学生都无法通过离散数学课程；所有计算机科学专业的学生都必须通过离散数学课程才能毕业；小王是计算机科学专业的学生并且已经顺利毕业。结论：小王会逻辑推理。证明：先将命题符号化。令R(x):x会逻辑推理，P(x):x通过了离散数学考试，C(x)是计算机科学专业的学生，G(x):毕业，w:小王。则该题即证明以下蕴含式成立。62离散数学2.4.2谓词公式的推理证明：先将命题符号化。令R(x):x会逻辑推理，P(x):x通过了离散数学考试，C(x)是计算机科学专业的学生，G(x):毕业，w:小王。则该题即证明以下蕴含式成立。63离散数学2.4.2谓词公式的推理前提：结论：①C(w)∧G(w)

前提引入②

x(C(x)∧G(x)→P(x))

前提引入

③C(w)∧G(w)→P(w)

②UI规则④P(w)

①③假言推理⑤

x(

R(x)→

P(x))

前提引入⑥

R(w)→

P(w)

⑤UI规则⑦P(w)→R(w)

⑥置换

⑧R(w)④⑦假言推理2.5

应用归结原理的基本归结规则归结原理的应用64离散数学65离散数学2.5.1归结原理的基本归结规则定义2.11谓词逻辑中，原子谓词公式是一个不能再分解的n元谓词，原子谓词公式及其否定，统称为文字（Literal）。P称为正文字，

P称为负文字，P与

P称为互补文字。

任何文字的析取式称为子句，任何文字本身也是子句。如

P

Q，P

QR都是子句，称为单文字子句。由子句构成的集合称为子句集，不包含任何文