离散-05 -一阶逻辑

离散数学(第5讲)章静E-mail:2.1一阶逻辑基本概念本章的主要内容一阶逻辑基本概念、命题符号化一阶逻辑公式、解释及分类本章与后续各章的关系克服命题逻辑的局限性本章内容

一阶逻辑命题符号化一阶逻辑公式及解释本章小结习题作业引言(著名的苏格拉底三段论)设自然语言中的三个命题：1.所有的人都是要死的；2.苏格拉底是人。3.所以，苏格拉底是要死的。 P：所有的人都是要死的；

Q：苏格拉底是人。

R：苏格拉底是要死的。则有：P∧Q→

R但在上述式子中，R不是P，Q的逻辑结果。解：假设这个简单而有名的苏格拉底三段论，却无法用命题逻辑予以证明。命题逻辑的局限性

在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。一阶逻辑所研究的内容

为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系。例：如有句子： 张红是一个福建工程学院的学生； 王南是一个福建工程学院的学生； 李华是一个福建工程学院的学生。则在命题中必须要用三个命题p，q，r来表示。但是，它们都具有一个共同的特征：“…是一个福建工程学院的学生”P：谓词x：个体词P(x)：命题函数则上述句子可写为：P(张红)；P(王南)；P(李华)。一般地，P(x)：x是一个福建工程学院的学生。1一阶逻辑命题符号化一阶逻辑命题符号化的三个基本要素个体词谓词量词

个体词及相关概念个体词一般是充当主语的名词或代词。说明个体词：指所研究对象中可以独立存在的具体或抽象的客体。举例命题：电子计算机是科学技术的工具。

个体词：电子计算机。命题：他是三好学生。

个体词：他。个体常项：表示具体或特定的客体的个体词，用小写字母a,b,c，…表示。个体变项：表示抽象或泛指的客体的个体词，用x,y,z,…表示。个体域（或称论域）：指个体变项的取值范围。可以是有穷集合，如{a,b,c},{1,2}。可以是无穷集合，如N,Z,R,…。全总个体域（universe）——宇宙间一切事物组成。个体词及相关概念本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。说明谓词及相关概念谓词（predicate）是用来刻画个体词性质及个体词之间相互关系的词。(1)是无理数。

是个体常项，“是无理数”是谓词，记为F，命题符号化为F()。(2)x是有理数。

x是个体变项，“是有理数”是谓词，记为G，命题符号化为G(x)。(3)小王与小李同岁。

小王、小李都是个体常项，“与同岁”是谓词，记为H，命题符号化为H(a,b)，其中a：小王，b：小李。(4)x与y具有关系L。

x，y都是个体变项，谓词为L，命题符号化为L(x,y)。谓词常项：表示具体性质或关系的谓词。用大写字母表示。如(1)、

(2)

、(3)

中谓词F、G、H。谓词变项：表示抽象的、泛指的性质或关系的谓词。用大写字母表示。如(4)

中谓词L。n(n1)元谓词：P(x1,x2,…,xn)表示含n个命题变项的n元谓词。n=1时，一元谓词——表示x1具有性质P。n≥2时，多元谓词——表示x1,x2,…,xn具有关系P。0元谓词：不含个体变项的谓词。如F(a)、G(a,b)、

P(a1,a2,…,an)。命题是特殊谓词。n元谓词是命题吗？不是，只有用谓词常项取代P，用个体常项取代x1,x2,…,xn时，才能使n元谓词变为命题。思考谓词及相关概念例题例2.1

将下列命题在一阶逻辑中用0元谓词符号化，并讨论真值。(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6.解：(1)设一元谓词F(x):x是素数，a:2，b:4。命题符号化为0元谓词的蕴涵式

F(b)→F(a)

由于此蕴涵前件为假，所以命题为真。(2)设二元谓词G(x,y):x大于y，a:4，b:5，c:6。命题符号化为0元谓词的蕴涵式

G(b,a)→G(a,c)

由于G(b,a)为真，而G(a,c)为假，所以命题为假。书P38例2.1例题将命题“这只大红书柜摆满了那些古书。”符号化.(1)设 F(x,y)：x摆满了y，R(x)：x是大红书柜

Q(y)：y是古书， a：这只，

b：那些 符号化为：R(a)∧Q(b)∧F(a,b)(2)设 A(x)：x是书柜， B(x)：x是大的

C(x)：x是红的， D(y)：y是古老的

E(y)：y是图书， F(x,y)：x摆满了y a：这只 b：那些 符号化为：A(a)∧B(a)∧C(a)∧D(b)∧E(b)∧F(a,b)量词及相关概念在上述三段论的例子中，如要对句子

P：所有的人都是要死的。如果表示成：H(x)→D(x)，求否定说明其原因在于：命题P的确切含义是：“对任意的x，如果x是人，则x是要死的”。但H(x)→D(x)并没有确切地表示出“对任意x”这个意思，亦即H(x)→D(x)不是一个命题。例符号化下述命题：所有的老虎都要吃人；每一个人都会犯错误；有一些人会摔跤；有一些人是大学生；每一个带伞的人都不怕雨；有一些自然数是素数。解：设立如下谓词：R（x）：x会吃人；P（x）：x会犯错误；N（x）：x会摔跤；Q（x）：x是大学生；C（x）：x不怕雨；S（x）：x是素数。量词（quantifiers）是表示个体常项或个体变项之间数量关系的词。1.全称量词：符号化为“”日常生活和数学中所用的“一切的”、“所有的”、“每一个”、“任意的”、“凡”、“都”等词可统称为全称量词。x表示个体域里的所有个体，xF(x)表示个体域里所有个体都有性质F。2.存在量词：符号化为“”日常生活和数学中所用的“存在”、“有一个”、“有的”、“至少有一个”等词统称为存在量词。y表示个体域里有的个体，yG(y)表示个体域里存在个体具有性质G等。量词及相关概念例(续)符号化下述命题：所有的老虎都要吃人；每一个人都会犯错误；有一些人会摔跤；有一些人是大学生；每一个带伞的人都不怕雨；有一些自然数是素数。解：设立如下谓词：R（x）：x会吃人；P（x）：x会犯错误；N（x）：x会摔跤；Q（x）：x是大学生；C（x）：x不怕雨；S（x）：x是素数。(x)R(x)(x{老虎})(x)P(x)(x{人})(x)N(x)(x{人})(x)Q(x)(x{人})(x)C(x)(x{带伞的人})(x)S(x)(x{自然数})

有时，由于个体域的注明不清楚，造成无法确定其真值。对于同一个公式，不同的个体域有可能带来不同的真值。

分析书P39例题（1）所有的人都要死的。(x)F(x) 其中F(x)：x是要死的， (x{人})（2）有的人活百岁以上。(x)G(x)

其中G(x)：x活百岁以上，(x{人})(x)(M(x)→F(x))(x)(M(x)∧G(x))全总个体域对于全称量词，刻划其对应个体域的特性谓词作为蕴涵的前件加入。对于存在量词，刻划其对应个体域的特性谓词作为合取式之合取项加入。基于上述情况，必须对个体域进行统一，全部使用全总个体域，此时，对每一个句子中个体变量的变化范围用一定之特性谓词刻划之。而统一成全总个体域后，此全总个体域在谓词公式中就不必特别说明，常常省略不记。同时，这种特性谓词在加入到命题函数中时必定遵循如下原则：例(续)解：U(x)：x是老虎(x)(U(x)→R(x))H(x)：x是人； (x)(H(x)→P(x))H(x)：x是人； (x)(H(x)∧N(x))H(x)：x是人； (x)(H(x)∧Q(x))M(x)：x是带伞的人； (x)(M(x)→L(x))T(x)：x是自然数； (x)(T(x)∧S(x))对于前例中的例子运用特性谓词描述。苏格拉底三段论中的P也可表示为：(x)(H(x)→D(x))。例2.2

在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:(a)个体域D1为人类集合；

(b)个体域D2为全总个体域。一阶逻辑命题符号化解:(a)个体域为人类集合。令F(x):x呼吸。 G(x):x用左手写字。(1)在个体域中除了人外，再无别的东西，因而“凡人都呼吸”应符号化为

xF(x)

(2)在个体域中除了人外，再无别的东西，因而“有的人用左手写字”符号化为xG(x)

(b)个体域为全总个体域。即除人外，还有万物，所以必须考虑将人先分离出来。令F(x):x呼吸。 G(x):x用左手写字。M(x):x是人。(1)“凡人都呼吸”应符号化为

x(M(x)→F(x))

(2)“有的人用左手写字”符号化为x(M(x)∧G(x))

在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词M(x)，称为特性谓词。同一命题在不同的个体域中符号化的形式可能不同。（P39注意（1））思考：在全总个体域中，能否将(1)符号化为x(M(x)∧F(x))？能否将(2)符号化为x(M(x)→G(x))？结论例2.3

在个体域限制为(a)和(b)条件时，将下列命题符号化:(1)对于任意的x，均有x2-3x+2=(x-1)(x-2)。(2)存在x，使得x+5=3。其中:(a)个体域D1=N(N为自然数集合) (b)个体域D2=R(R为实数集合)(a)令F(x):x2-3x+2=(x-1)(x-2)，G(x):x+5=3。 命题(1)的符号化形式为 xF(x)

（真命题） 命题(2)的符号化形式为 xG(x)) （假命题）(b)在D2内，(1)和(2)的符号化形式同(a)，皆为真命题。在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。同一个命题，在不同个体域中的真值也可能不同。说明例2.4

将下列命题符号化，并讨论真值。（1）所有的人长着黑头发。（2）有的人登上过月球。（3）没有人登上过木星。（4）在美国留学的学生未必都是亚洲人。分析：谓词逻辑中命题的符号化，主要考虑：(1)非空个体域的选取。若是为了确定命题的真值，一般约定在某个个体域上进行，否则，在由一切事物构成的全总个体域上考虑问题时，需要增加一个指出个体变量变化范围的特性谓词。(2)量词的使用及作用范围。(3)正确地语义。解：没有提出个体域，所以认为是全总个体域。（1）所有的人长着黑头发。令F(x):x长着黑头发，M(x):x是人。命题符号化为x(M(x)→F(x))。命题真值为假。（2）有的人登上过月球。令G(x):x登上过月球，M(x):x是人。命题符号化为

x(M(x)∧G(x))。命题真值为真。（3）没有人登上过木星。令H(x):x登上过木星，M(x):x是人。命题符号化为

┐x(M(x)∧H(x))。命题真值为真。（4）在美国留学的学生未必都是亚洲人。 令F(x):x是在美国留学的学生，G(x):x是亚洲人。符号化 ┐x(F(x)→G(x))

命题真值为真。一元谓词：书P40例题2.2-2.4例题n元谓词的符号化例2.5

将下列命题符号化

（1）兔子比乌龟跑得快。

（2）有的兔子比所有的乌龟跑得快。

（3）并不是所有的兔子都比乌龟跑得快。

（4）不存在跑得同样快的两只兔子。解：令F(x):x是兔子，G(y):y是乌龟，

H(x,y):x比y跑得快，L(x,y):x与y跑得同样快。（1）xy(F(x)∧G(y)H(x,y))（2）x(F(x)∧y(G(y)H(x,y)))（3）┐xy(F(x)∧G(y)H(x,y))（4）┐xy(F(x)∧F(y)∧L(x,y))n元谓词：书P41例题2.5一阶逻辑命题符号化时需要注意的事项

（P39注意）分析命题中表示性质和关系的谓词，分别符号为一元和n（n2）元谓词。根据命题的实际意义选用全称量词或存在量词。一般说来，多个量词出现时，它们的顺序不能随意调换。例如，考虑个体域为实数集，H(x，y)表示x+y=10，则命题“对于任意的x，都存在y，使得x+y=10”的符号化形式为xyH(x,y)，为真命题。如果改变两个量词的顺序，得yxH(x,y)，为假命题。有些命题的符号化形式可不止一种。例如（3）并不是所有的兔子都比乌龟跑得快。xy(F(x)∧G(y)H(x,y))xy(F(x)∧G(y)∧┐H(x,y))练习P522.1—2.32.2一阶逻辑合式公式及解释同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。一阶语言是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为F。一阶语言中的字母表定义2.1一阶语言F的字母表定义如下:(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)个体常项和个体变项是项。(2)若f(x1,x2,…,xn)是任意n元函数，t1,t2,…,tn是项，则f(t1,t2,…,tn)也是项。(3)只有有限次地使用(1)，(2)生成的符号串才是项。看书P42例子定义2.3设R(x1,x2,…,xn)是的任意n元谓词，t1,t2,…,tn是项，则称R(t1,t2,…,tn)为原子公式。定义2.4合式公式定义如下:

合式公式也称为谓词公式，简称公式。1.原子公式是合式公式；2.若A，B是合式公式，则(┐A)、(┐B)、(A∨B)、(A∧B)、(A→B)、(AB)也是合适公式；3.若A是合式公式，x是个体变量，则(x)A、(x)A也是合式公式；4.只有有限次地应用1-3构成的符号串才是合式公式。

在定义2.4中出现的字母A，B是代表任意公式的元语言符号。为方便起见，公式(┐A)，(A∧B)，…中的最外层括号可以省去，使其变成┐A，A∧B，…。定义2.5在公式xA和xA中，称x为指导变项，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现。A中不是约束出现的其他变项均称为是自由出现的。例2.6

指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。

(1)x(F(x,y)→G(x,z))

(2)x(F(x)→G(y))→y(H(x)∧L(x,y,z))解答(1)x是指导变项。量词的辖域A=(F(x,y)→G(x,z))。在A中，x的两次出现均是约束出现。y和z均为自由出现。(2)前件上量词的指导变项为x，量词的辖域A=(F(x)→G(y))，x在A中是约束出现的，y在A中是自由出现的。后件中量词的指导变项为y，量词的辖域为B=(H(x)∧L(x,y,z))，y在B中是约束出现的，x、z在B中均为自由出现的。再看书P43例2.6注意用A(x1,x2,…,xn)表示含x1,x2,…,xn自由出现的公式。用Δ表示任意的量词或，则Δx1A(x1,x2,…,xn)是含有x2,x3,…,xn自由出现的公式，可记为A1(x2,x3,…,xn)。类似的，Δx2Δx1A(x1,x2,…,xn)可记为A2(x3,x4,…,xn)Δxn-1Δxn-2…Δx1A(x1,x2,…,xn)中只含有xn是自由出现的个体变项，可以记为An-1(xn)。Δxn…Δx1A(x1,x2,…,xn)没有自由出现的个体变项。将x(F(x,y)→G(x,z))简记为A(y,z)，表明公式含有自由出现的个体变项y，z。而yA(y,z)中只含有z为自由出现的公式，zyA(y,z)中已经没有自由出现的个体变项了，定义2.6设A是任意的公式，若A中不含有自由出现的个体变项，则称A为封闭的公式，简称闭式。要想使含r（r1）个自由出现个体变项的公式变成闭式至少要加r个量词。如x(F(x)→G(x))，x(F(x)→G(x,y))换名规则例

xF(x)∧G(x,y)换名为zF(z)∧G(x,y)让公式中不会有既约束出现又自由出现的变项。P43换名规则:将一个指导变项及其在辖域中所有约束出现替换成公式中没有出现的个体变项符号。例

x(R(x,y,z)∧yH(x,y,z))换名为x(R(x,y,z)∧tH(x,t,z))例2.7

将下列两个公式中的变项指定成常项使其成为命题: (1)x(F(x)→G(x))

(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))(1)指定个体变项的变化范围，并且指定谓词F，G的含义，下面给出两种指定法:

(a)令个体域D1为全总个体域，

F(x)为x是人，

G(x)为x是黄种人， 则命题为“所有人都是黄种人”，这是假命题。(b)令个体域D2为实数集合R，

F(x)为x是自然数，

G(x)为x是整数， 则命题为“自然数都是整数”，这是真命题。(2)xy(F(x)∧F(y)∧G(x,y)→H(f(x,y),g(x,y)))

含有两个2元函数变项，两个1元谓词变项，两个2元谓词变项。 指定个体域为全总个体域，

F(x)为x是实数， G(x,y)为x≠y，

H(x,y)为x>y， f(x,y)=x2+y2，

g(x,y)=2xy， 则表达的命题为“对于任意的x，y，若x与y都是实数，且x≠y，则x2+y2>2xy”，这是真命题。 如果H(x,y)改为x<y， 则所得命题为假命题。定义2.7一个解释I由下面4部分组成:(a)非空个体域D；(b)给论及的每一个个体常项符号指定一个D中的元素；

(c)给论及的每一个函数变项符号指定一个D中的函数；(d)给论及的每一个谓词变项符号指定一个D中的谓词。例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。在I下，下列哪些公式为真?哪些为假?哪些的真值还不能确定?(1)F(f(x,y),g(x,y))(2)F(f(x,a),y)→F(g(x,y),z)(3)┐F(g(x,y),g(y,z))(4)xF(g(x,y),z)(5)xF(g(x,a),x)→F(x,y)(6)xF(g(x,a),x)(7)xy(F(f(x,a),y)→F(f(y,a),x))(8)xyzF(f(x,y),z)

(9)xF(f(x,x),g(x,x))

(1)F(f(x,y),g(x,y))

公式被解释成“x+y=x·y”，这不是命题。

(2)F(f(x,a),y)→F(g(x,y),z)

公式被解释成“(x+0=y)→(x·y=z)”，这也不是命题。

(3)┐F(g(x,y),g(y,z))

公式被解释成“x·y≠y·z”，同样不是命题。

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

公式被解释成“x(x·y=z)”，不是命题。例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。(5)xF(g(x,a),x)→F(x,y)

公式被解释成“x(x·0=x)→(x=y)”，由于前件为假，所以被解释的公式为真。

(6)xF(g(x,a),x)

公式被解释成“x(x·0=x)”，为假命题。(7)xy(F(f(x,a),y)→F(f(y,a),x))

公式被解释成“xy((x+0=y)→(y+0=x))”，为真命题。

例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。(8)xyzF(f(x,y),z)

公式被解释成“xyz(x+y=z)”，这也为真命题。(9)xF(f(x,x),g(x,x))

公式被解释成“x(x+x=x·x)”，为真命题。例2.8

给定解释I如下:(a)个体域D=N(N为自然数集合，即N={0,1,2,…})(b)元素a=0(c)函数f(x,y)=x+y,g(x,y)=x•y。(d)谓词F(x,y)为x=y。书P44例题2.7，2.8闭式在给定的解释中都变成了命题。如(6)(8)。不是闭式的公式在某些解释下也可能变为命题。如(5)。结论定理2.1封闭的公式在任何解释下都变成命题。P45在给定的解释和赋值下，任何公式都是命题。一阶公式的分类定义2.8永真式、永假式、可满足式设A为一个公式，若A在任何解释下均为真，则称A为永真式(或称逻辑有效式)。设A为一个公式，若A在任何解释下均为假，则称A为矛盾式(或永假式)。设A为一个公式，若至少存在一个解释使A为真，则称A为可满足式。永真式一定是可满足式，但可满足式不一定是永真式。在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。但对某些特殊的公式还是可以判断的。说明例2.9

判断下列公式中，哪些是逻辑有效式，哪些是矛盾式？（1）x(F(x)G(x))（2）x(F(x)G(x))（3）xF(x)(xyG(x,y)xF(x))（4）(xF(x)yG(y))yG(y)解:(1)x(F(x)G(x))

解释1：个体域为实数集合R，F(x)：x是整数，G(x)：x是有理数，因此公式真值为真。解释2：个体域为实数集合R，F(x)：x是无理数，G(x)：x能表示成分数，因此公式真值为假。所以公式为非永真式的可满足式。（2）x(F(x)G(x))

公式为非永真式的可满足式。（3）xF(x)(xyG(x,y)xF(x))

为p(qp)（重言式）