第二章谓词逻辑选编课件

第二章谓词逻辑离散数学引言命题逻辑好像功能强大，但还是有些问题难以解决。

如杨圣洪要喝水、刘翔要喝水、姚明要喝水、姚晨要喝水、刘德华要喝水、……，可归纳为“某某要喝水”，无法表示。所有的人都要呼吸、喝水、吃饭……，“所有”如何表示呢？有些人要升官、有些人要失恋……，“有些”又如何表示？

所有男人都会多看几眼漂亮女人

所有女人都会多喜欢漂亮的衣服

又如有名三段论：所有人都是要变老的，杨圣洪是人，所以杨圣洪也会变老的，无法表示。为此需要我们学习新的逻辑工具-谓词逻辑或一阶逻辑谓词逻辑基本概念个体词和谓词定义：

个体词是指可以独立存在的客体，可以是一个具体的事物或抽象的概念，是原子命题所描述的对象。谓词是用来说明个体的性质或个体间的关系。例如

小王是个大学生

3大于2谓词个体词个体词个体词谓词基本概念1、谓词“某某要喝水”、“喜欢漂亮衣服”、“喜欢帅哥”、“结婚生崽”都是所在句子的谓语部分。

命题逻辑中用小写字母表示命题。

谓词逻辑中用大写字母表示谓语部分，如用W表示“要喝水”，用L表示“喜欢漂亮衣服”，用H表示“喜欢帅哥”，用M表示“结婚生崽”。

这些表示谓语部分的大写字母，称为“谓词”。

基本概念2、个体常元表示某种判断的语句一般都有主语。

主语是表示某个、某些客体，也称为个体。如“刘翔”、“姚明”。为了描述方便，常用小写字母表示这些个体。如a表示“刘翔”，

c表示“姚明”，这些表示具体个体的小写字母，称为“个体常元”或个体常量。其他学科中，也是用字母表中靠前的字母表示常量。基本概念3、个体变元

对于不针对特定个体的泛指，如“某某”、“男人”、“女人”，常用x,y,z,r,s,t等字母表中靠后的字母表示，其他学科中，也是这样表示，

这些小字字母称为“个体变元”。因此“某某要喝水”表示为W(x),x泛指所有的人，

“女人喜欢漂亮衣服”表示为L(x,y)，x泛指“女人”、y泛指“衣服”，

“女人喜欢帅哥”表示为H(y,z)，其中y泛指女人、z泛指帅哥。

“男人结婚生崽”表示为M(z)，z泛指男人。谓词

形如“b是A”类型的命题可表达为A(b)；表示多个个体间关系的命题，可表达为B(a，b)，或P(a，b，c)定义:和一个个体相联系的谓词称为一元谓词，和二个个体相联系的谓词称为二元谓词，和n个个体相联系的谓词称为n元谓词。个体常元

表示具体的或特定的个体，如a，b，c，等；个体变元

表示抽象的或泛指的个体，如x，y，z，等。谓词常项

表示具体性质或关系的谓词，R(a)表示a是人；谓词变项

表示抽象或泛指的谓词

，如：P(a)表示a具有P性质。谓词表达式和命题函数定义:一个原子命题可以用一个谓词常项P和几个个体常元，如a，b，c，，表示成P(a，b，c，)的形式。称P(a，b，c，)为原子命题或命题的谓词表达式。一个谓词常项P和几个个体变元如x，y，z，表示成P(x，y，z，)的形式，称为命题函数，其中的个体变元可以代表任意一个个体。注意：命题的谓词表达式是有真值的，命题函数的真值是不确定的。例题写出下列命题的谓词表达式。

1.小王和小李是大学生。解：设A(x)：x是大学生。a：小王，b：小李。

A(a)A(b)2.

北京是中国的首都。解：设F(x，y)：x是y的首都。a：北京，b：中国。F(a，b)3.如果你来，他就走。解：设P(x)：x来。Q(x)：x走。a：你，b：他。

P(a)

Q(b)例题（续）4.如果32，21，则31。解：设B(x，y)：xy。a：3，b：2，c：1。则

：

B(a，b)

B(b，c)

B(a，c)5.武汉位于北京和广州之间。解：设Q(x，y，z)：y位于x和z之间。a：北京，b：广州，c：武汉。Q(a，c，b)个体域定义:命题函数中，个体变元的取值范围称为个体域或论述域。

个体域可以是有限的，也可以是无限的。把宇宙中一切事物作为对象的的集合称为全总个体域。通常，没有特别说明时，个体变元的论述域是指全总个体域。如：A(x)表示：x是大学生。个体域：计科1班学生，则A(x)是永真式。个体域：希望小学1班学生，则A(x)是永假式。个体域：xx公司员工，其中有些是大学生，有些不是大学生，则对有些人，A(x)为真，对有些人，A(x)为假。例题给出执行语句“If

P(x)then

x：=1”以后x的值，其中P(x)为语句“x1”，且执行到该语句时x的值如下：1)x=02)x=13)x=2解1)若x=0，P(x)为语句“01”，真值为0，不执行赋值语句“x：=1”，所以x=0。2)若x=1，P(x)为语句“11”，真值为0，不执行赋值语句“x：=1”，所以x=1。3)若x=2，P(x)为语句“21”，真值为1，执行赋值语句“x：=1”，所以x=1。量词定义：表示个体常元或个体变元之间数量关系的词称为量词。量词有两种：全称量词

符号：

x表示对个体域“所有的x”，“每一个x”，“一切x”等。存在量词

符号：x表示个体域中“存在这样的x”，“某个x”，“至少有一个x”或“有一些x”等。xF(x)表示个体域中所有个体都有性质FxF(x)表示个体域中存在个体有性质F基本概念4、全称量词为了表示“所有女人都喜欢漂亮的衣服”、

“所有女人都喜欢帅哥”等中

“所有”，引入符号“”，称为全称量词。可能是“ALL”的字母A倒写，表示所有、全部。当用x泛指“人”，“所有人”表示为“x”，

“所有活人都要喝水”表示为xW(x)。当用x表示“女人”,y表示漂亮的衣服时，

“所有女人”则表示为x、

“所有漂亮的衣服”则表示为“y”，因此

“所有女人都喜欢漂亮的衣服”表示为xyL(x,y)。当用x表示“女人”,y表示帅哥时，

“所有女人都喜欢帅哥”表示为xyH(x,y)。

基本概念5、存在量词为了表示“有些男人结婚生崽”中“有些”，引入符号“”，

表示“存在，有些、有部分”等的含义。称为存在量词。 它是Exist的首字母，左旋180度，如用z表示“男人”，那么

“有些男人”表示为“z”，

“有些男人结婚生崽”表示为“zM(z)”。例题假设F(x)表示x选修离散数学，x的个体域是这个班的同学，将下面的两个命题符号化。这个班的所有学生都选修离散数学这个班有些学生选修离散数学解

当个体域是这个班的同学时：xF(x)

xF(x)若个体域是全总个体域时，要引入一个新的谓词表示个体的取值范围。称这个表示个体范围的谓词为特性谓词。例题假设F(x)表示x选修离散数学，将下面的两个命题符号化。这个班的所有学生都选修离散数学这个班有些学生选修离散数学解

（没有特别说明时个体域是全总个体域）设特性谓词S(x)：表示x是这个班的同学，x(S(x)

F(x))

x(S(x)

F(x))注意：在使用全称量词时，

特性谓词和表示个体性质的谓词构成条件关系式；

在使用存在量词时，特性谓词和表示个体性质的谓词构成合取关系式。例题在个体域分别为：(a):自然数集合，(b):实数集合时，将下列命题符号化，并给出它们的真值。对于任意的x，均有x2−3x+2=(x−1)(x−2);存在x，使得x+5=2。解

假设F(x)：x2−3x+2=(x−1)(x−2)，G(x)：x+5=2。(a)个体域为自然数集合。符号化为：xF(x)，真值为1。符号化为：xG(x)，真值为0。(b)个体域为实数集合。符号化为：xF(x)，真值为1。符号化为：xG(x)，真值为1。量词当论述域中的元素个数有限时，例如，论述域为n个元素的集合{a1，a2，a3，an}时，有x

A(x)

A(a1)

A(a2)

A(a3)

A(an)x

A(x)

A(a1)

A(a2)

A(a3)

A(an)例题若P(x)是语句“x2>10”，论述域为不超过4的正整数，xP(x)和x

P(x)的真值是什么？

解

由于论述域为{1，2，3，4}，命题xP(x)为x

P(x)

P(1)

P(2)

P(3)

P(4)而P(1)即“12>10”为假，所以x

P(x)为假。命题xP(x)为x

P(x)

P(1)

P(2)

P(3)

P(4)而P(4)即“42>10”为真，所以x

P(x)为真。例题设P(x，y)表示“x+y>10”，论述域为实数，xyP(x，y)和yxP(x，y)的真值是什么？

解：

xyP(x，y)表示命题：“对每一个实数x，都存在实数y，使得x+y>10成立”，这是个真命题，真值为1。yxP(x，y)表示命题：“存在实数y，对每一个实数x，都有x+y>10成立”，这是个假命题，真值为0。注意：除非所有量词都是全称量词或存在量词，否则，多个量词同时出现时，不能随意颠倒量词的顺序，颠倒后会改变原命题的含义。基本概念6、谓词公式将表示全部的符号“”，表示为部分的“”称为量词，将单个谓词公式如W(x)，带量词的谓词如zM(z)，统称为“谓词公式”。谓词W(x),M(z)中只有1个个体变元,

则称为1元谓词公式，常用来刻划对象的性质、属性。谓词L(x,y)、H(y,z)中有2个个体变元，称为2元谓词。常用来表示二个对象之间的关系，如喜欢，类似如果有n个个体变元则称为n元谓词公式。个体变元的取值范围称为“讨论域”，如果没有交待讨论域，表示对个体变元的取值范围，不做任何限制，泛指宇宙界的万物，称为“全总个体域”，常用大写字母U表示。基本概念利用量词、谓词将自然语言转换为谓词公式

例1：(1)凡人都要呼吸(2)有的人用左手写字。

解：当个体域为“人类”时xB(x),其中B(x)表示x人呼吸breath.xWL(x)，其中WL(x)表示x用左边写字。当个体域为全总个体域(宇宙万物组成)x(H(x)B(x))H(x)表示个体x是人类x(H(x)WL(x))，WL(x)表示x用左边写字。

个体域不同，谓词公式不同。例2(1)任意x,x2-2x+1=(x-1)2.有x,使得x*5=3解：当x的取值范围即个体域为自然数N时xE(x)E(x)表示x2-2x+1=(x-1)2xF(x)F(x)表示x*5=3

当x的个体域为实数R时，谓词公式相同但真值不同！例题用谓词逻辑将下列命题符号化。1.所有的偶数均能被2整除。解

设A(x)：x是偶数，B(x)：x能被2整除。x(A(x)

B(x))2.这个班有些学生有电脑。解设A(x)：x是这个班的学生，B(x)：x有电脑。

x(A(x)

B(x))。3.没有不犯错误的人。解设A(x)：x是人，B(x)：x犯错误。

x(A(x)

B(x))。例题（续）4.尽管有人聪明，但未必一切人都聪明。解设A(x)：x是人，B(x)：x聪明。

x(A(x)

B(x))x(A(x)

B(x))5.有些人喜欢某些体育运动。解

设A(x)：x是人，B(y)：y是体育运动，

C(x，y)：x喜欢y。x(A(x)y(B(y)

C(x，y)))。6.并非所有的工作都可以由一些机器人来完成。解设A(x)：x是工作，B(x，y)：x可以由y来完成，

R(x)：x是机器人。

x(A(x)y(R(y)

B(x，y)))。基本概念例3(1)兔子比乌龟跑得快

(2)有的兔子比所有的乌龟跑得快

(3)并不是所有的兔子都比乌龟跑得快

(4)不存在跑得同样快的两只兔子.解：H(x,y)表示x比y跑得快.L(x,y)表示x与y一样快

R(x)表示x是兔子T(x)表示x是乌龟

(1)xy(R(x)T(y)H(x,y))(2)xy(R(x)T(y)H(x,y))(3)xy(R(x)T(y)H(x,y))xy(R(x)T(y)H(x,y))(4)xy(R(x)R(y)L(x,y))xy(R(x)R(y)L(x,y))基本概念例4任意两个不相等实数，其平方和大于积的二倍。

解：个体域为全总个体域即不对个体变元的取值做任何限制。

F(x)表示x是实数，

G(x,y)表示xy，

H(x,y)表示x>y，则原话表示为

xy(F(x)F(y)G(x,y)H(x2+y2,2xy))。若用f(x,y)表示x2+y2，g(x,y)表示2xy，则原话表示为

(F(x)F(y)G(x,y)H(f(x,y),g(x,y)))

因为对于实数x，y，(x2-2xy+y2)=(x-y)2，当xy时，有(x-y)2>0，故(x2-2xy+y2)>0，故x2+y2>2xy，故H(x2+y2,2xy))

为真故原话正确，故以上公式的真值为1。故谓词公式可出现个体变元,平方,乘、倍数、函数等。基本概念例5表示“所有人都要变老的，杨圣洪是人，所以杨圣洪也会变老的”。解：个体域为全总个体域，即对个体变元的取值不做任何限。

H(x)表示对象x是人类，

O(x)表示对象x变老，

c表示个体常元“杨圣洪”，则

H(c)表示个体常元杨圣洪是人类，

O(c)表示个体常元杨圣洪要变老，原句表示

(x(H(x)O(x))H(c))O(c)。该公式不仅有个体变元，还有个体常元基本概念例6表示“所有人都要死的，苏格拉底是人，所以苏格拉底也会死”。解：个体域为全总个体域，即对个体变元的取值不做任何限制。

H(x)表示对象x是人类，

O(x)表示对象x要死的，

c表示个体常元“苏格拉底”，则

H(c)表示个体常元苏格拉底是人类，

O(c)表示个体常元苏格拉底要死，原句表示

(x(H(x)O(x))H(c))O(c)。这两个例题，语句不同，但是最后的谓词公式相同。谓词公式及解释上节得到一些谓词公式，获得一些结论，也有存在一些疑惑？

(1)谓词公式有个体常元、个体变元，还可以有个体变元的表达式，那么谓词公式究竟还有哪些形式，究竟什么的字符串是合法的谓词公式？

(2)同一句话有二个不同的公式，那么这二个公式等值吗？

(3)不同的话拥有同样的谓词公式，到底这二句话有何共性？

(4)同一样公式在不同的论域下真值不同，究竟如何确定一个公式的真值呢？谓词公式及解释合法的谓词公式1.合法的谓词公式非逻辑符号:个体常元、函数符号、谓词符号逻辑符号:个体变元、量词符号、联结词、逗号、括号。项的定义：个体常元与变元及其函数式为项。(1)个体常元和个体变元是项。(2)若(x1,x2,…,xn)是n元函数,t1,t2,…tn是n个项，则(t1,t2,…,tn)是项。(3)有限次使用(2)得到的表达式是项。原子公式：设R(x1,x2,…,xn)是n元谓词，t1,t2,…,tn是项，则R(t1,t2,…,tn)是原子公式。谓词公式及解释合法的谓词公式项的定义：个体常元与变元及其函数式为项。原子公式：设R(x1,x2,…,xn)是n元谓词，t1,t2,…,tn是项，则R(t1,t2,…,tn)是原子公式。合式谓词公式：

(1)原子公式是合式公式；

(2)若A是合式公式，则(A)也是合式公式；

(3)若A,B合式，则AB,AB,AB,AB合式

(4)若A合式，则xA、xA合式

(5)有限次使用(2)~(4)得到的式子是合式。谓词公式及解释合法的谓词公式

(F(x)F(y)G(x,y)H(f(x,y),g(x,y)))、xy(R(x)T(y)H(x,y))、xy(R(x)T(y)H(x,y))、……x(H(x)WL(x))、(x(H(x)O(x))H(c))O(c)，因此以上公式均是合法的公式，而F(x)F(y)G(x,y)、F(y)G(x,y)不是合法的公式。凡按照以上5条规则写出的表达式，就是合法谓词公式(也称为合式公式)。

不再拘泥于某个具体的自然语句。直接研究含义不确定或泛指的谓词公式。从形式上研究合式公式的性质。谓词公式及解释个体变元的身份个体变元的身份量词指导变元：xA和xA中的x量词辖域：xA和xA中的A为量词/辖域变元的约束出现：指导变元的每次出现(称约束变元)。变元的自由出现：不是约束出现的变元(称自由变元)。例题x(F(x,y)G(x,z))解：

x是量词的指导变元。

(F(x,y)G(x,z))是量词的辖域在(F(x,y)G(x,z))中x是约束出现，出现2次。在(F(x,y)G(x,z))自由出现的变元y/z，各一次。谓词公式及解释个体变元的身份个体变元的身份量词指导变元：xA和xA中的x量词辖域：xA和xA中的A为量词/辖域变元的约束出现：指导变元的每次出现(称约束变元)。变元的自由出现：不是约束出现的变元(称自由变元)。例题x(F(x,y)G(x,z))例题x(F(x)G(y))y(H(x)L(x,y,z))解：

量词的指导变元x,(F(x)G(y))是量词的辖域，其中x是约束出现，y是自由出现。

量词的指导变元y,H(x)L(x,y,z)是量词的辖域，其中x是自由2次，y是约束出现。整个公式中是约束1自由2次。谓词公式及解释个体变元的身份个体变元的身份

例题

分析x(F(x)G(y))y(H(x)L(x,y,z))变元身份解：x的辖域是：(F(x)G(y))，约束变元是x，x有1次约束出现，y是自由变元，有1次自由出现。y的辖域是：H(x)L(x,y,z)，约束变元是y，y有1次约束出现，x与z是自由变元，各有1次自由出现。尽管x在公式x(F(x)G(y))出现，又在y(H(x)L(x,y,z))出现，但两个x不是一回事，只是恰巧二个名字相同而矣，好比有2个李勇，一个是正坐在家里看电视的“李勇”，一个是在马路上散步的“李勇”，为了避免这种“误会”出现，要对“约束变元”改名。谓词公式及解释个体变元的身份个体变元的身份

例题

分析x(F(x)G(y))y(H(x)L(x,y,z))变元身份解：尽管x在公式x(F(x)G(y))出现，又在y(H(x)L(x,y,z))出现，但两个x不是一回事，只是恰巧二个名字相同而矣，为避免这种“误会”出现要对“约束变元”改名。将量词x的指导变元x，x的每次约束出现换成公式中未出现的r。将量词y指导变元y、约束变元y的每次出现换成公式中未出现的s，则原式为r(F(r)G(y))s(H(x)L(x,s,z))，所有约束变元与自由变元均不重名，无误会。

谓词公式及解释个体变元的身份个体变元的身份

例题

分析xy(P(x,y)Q(y,z))xP(x,y)作用域与变元约束情况解：x、y的作用域是(P(x,y)Q(y,z))，x的作用域是P(x,y)。

将与自由变元同名约束变元yr，将与前一个同名约束变元xs，则原公式xr(P(x,r)Q(r,z))sP(s,y)谓词公式及解释个体变元的身份个体变元的身份

例题

x(P(x)xQ(x,z)yR(x,y))Q(x,y)解：x的辖域是P(x)xQ(x,z)yR(x,y)，。

x的辖域是Q(x,z)

y的辖域是R(x,y)

s(P(s)rQ(r,z)tR(s,t))Q(x,y)

改名规则：一般仅对约束变元改名后出现者约束变元也要改名。

方法：将量词的指导变元，及辖域中约束变元每次约束出现，全部换成公式中未出现的字母。谓词公式及解释个体变元的身份个体变元的身份

闭公式：不含自由变元的谓词公式。x(F(x,y)G(x,z)) 因y,z是自由变元，故不是。r(F(r)G(y))s(H(x)L(x,s,z)) 因为y,x,z自由故不是xr(P(x,r)Q(r,z))sP(s,y)

因z与y自由，故不是。s(P(s)rQ(r,z)tR(s,t)) 因z自由故不是(F(x)F(y)G(x,y)H(f(x,y),g(x,y)))因x/y自由故不是以下公式均没有自由变元，均为闭公式：xy(R(x)T(y)H(x,y))、xy(R(x)T(y)H(x,y))、xy(R(x)T(y)H(x,y))、xy(R(x)T(y)H(x,y))、xy(R(x)R(y)L(x,y))、xy(R(x)R(y)L(x,y))、x(H(x)B(x))、x(H(x)WL(x))、(x(H(x)O(x)))H(c)O(c)谓词公式及解释谓词公式的真值谓词公式的真值前面我们学习“合式公式”时，说过不再拘泥于某个具体的自然语句，从形式上研究合式公式的性质。但谓词公式是逻辑公式，它总得有一个真假呀？如何确定其真假呢？神马不能总是浮云？总得落地。确定真值的方法：

(1)确定个体域，即个体的取值范围，哪个范围？

(2)将个体常元指定为个体域的具体值。哪个对象？

(3)函数常元表示指定个体域中个体变元的项。

(4)用指定个体域中的对象来解释各个原子公式。

(5)用原子公式的解释来描述整个公式的含义。原义？根据个体域中知识，判断整个公式的含义是否正确，若对则公式的真值为1，否则为0谓词公式及解释谓词公式的真值谓词公式的真值例题：x(F(x)G(x))

其中x的取值范围是什么？

F(x)的含义是什么？G(x)的含义是什么？将这些问题确定后，表达式x(F(x)G(x))的真值就确定了，这就是公式的解释。

dom(x)=D1=全总个体域

F(x)表示x是人，G(x)表示x是黄种人。

x(F(x)G(x))：所有的人都是黄种人，值为F.

dom(x)=D2=实数集R

F(x)表示x是自然数，G(x)表示x是整数。

x(F(x)G(x))：所有的自然数都是整数，值为T.谓词公式及解释谓词公式的真值例：xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y))f(x,y),g(x,y)是函数变元，一元谓词公式F(x),二元谓词G与H。

x与y的个体域：全总个体域。

F(x):x是实数

G(x,y):xyH(x,y):x>yf(x,y)=x2+y2g(x,y)=2xy

这时整个公式的含义：对于任意的x和y，若x与y是实数且xy，那么x2+y2>2xy，其真值为1.

如果H(x,y):x<y，则以上解释为假。谓词公式及解释谓词公式的真值例题：xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y))f(x,y),g(x,y)是函数变元，一元谓词公式F(x),二元谓词G与H。

x与y的个体域：全总个体域。

F(x):x是实数G(x,y):xyH(x,y):x>yf(x,y)=x2+y2g(x,y)=2xy

这时整个公式的含义：对于任意的x和y，若x与y是实数且xy，那么x2+y2>2xy，其真值为1.

总结：

个体常元的值、个体变元的值域、确定函数、谓词公式的含义。谓词公式及解释谓词公式的真值

个体常元的值、个体变元的值域、确定函数、谓词公式的含义。例4：个体变元的值域D=N,常元的a=0,函数f(x,y)=x+y,g(x,y)=x*y谓词F(x,y):x=y解释下列各公式的含义：

(1)F(f(x,y),g(x,y))原式=F(x+y,x*y)，x+y=x*y，对于自然数x/y，此式真假不确定，故不是命题。

(2)F(f(x,a),y)F(g(x,y),z)代入各式=F(x+0,y)F(x*y,z)=F(x,y)F(x*y,z)确定F后:x=yx*y=z,真假难定,不是命题.谓词公式及解释谓词公式的真值

个体常元的值、个体变元的值域、确定函数、谓词公式的含义。例：个体变元的值域D=N,常元的a=0,函数f(x,y)=x+y,g(x,y)=x*y谓词F(x,y):x=y解释下列各公式的含义：

(3)F(g(x,y),g(y,z))将函数确定后:F(x*y,y*z)将谓词确定后:x*y=y*z,

是否成立要看x,y,z的值,非命题!(4)xF(g(x,y),z)确定函数后:xF(x*y,z)确定谓词后:x(x*y=z)为0,

当x=y=z>1时(x*y=z)为0xF(x)F(x0)F(x1)...F(xk)...(*)(*)式为0则左=0

xF(x)=1F(x0)=1,F(x1)=1...F(xk)=1...,若F(xi0)=0则谓词公式及解释谓词公式的真值例：个体变元的值域D=N,常元的a=0,函数f(x,y)=x+y,g(x,y)=x*y谓词F(x,y):x=y解释下列各公式的含义：

(5)xF(g(x,a),x)F(x,y)确定个体常量xF(g(x,0),x)F(x,y)确定函数后:xF(x*0,x)F(x,y)确定谓词后:x(0=x)(x=y)

条件式的前式为假,无论后件为何,均为真……谓词公式及解释谓词公式的真值

因为全称量词x是指个体域中所有对象具有某性质、或具有某相互关系。

存在量词x是指个体域中部分对象具有某性质、或具有某相互关系故当个体域dom(X)={a1,a2,…,an}有限,即n有限,

xA(x)即为A(a1)A(a2)…A(an)。

xA(x)即为A(a1)A(a2)…A(an)。

利用这两个展开式，在解释公式的含义时，可能会带来某种便利！谓词公式及解释谓词公式的真值

例题：个体域D={2,3}，常元a=2，f(2)=3，f(3)=2，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0，

求下列谓词公式的值:(1)x(F(x)G(x,a))解：代入个体常元得x(F(x)G(x,2))，展开全称量词得(F(2)G(2,2))(F(3)G(3,2))，代入谓词的值得(01)(11)，即为0。谓词公式及解释谓词公式的真值

例题：个体域D={2,3}，常元a=2，f(2)=3，f(3)=2，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0，

求下列谓词公式的值:(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))，代入谓词的值(11)(01))，即为1。谓词公式及解释谓词公式的真值

例题：个体域D={2,3}，常元a=2，f(2)=3，f(3)=2，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0，

求下列谓词公式的值:(3)xyL(x,y)解：展开y得x(L(x,2)L(x,3))，展开x得((L(2,2)L(2,3)))((L(3,2)L(3,3)))，代入谓词的值得((10))(01))，即为1。谓词公式及解释谓词公式的真值

例题：个体域D={2,3}，常元a=2，f(2)=3，f(3)=2，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0，

求下列谓词公式的值:(3)xyL(x,y)代入谓词的值得((10))(01))，即为1。(4)yxL(x,y)展开x得：y(L(2,y)L(3,y))，展y得：(L(2,2)L(3,2))(L(2,3)L(3,3))，代入谓词值得(10)(01)，即为0。说明：x与y次序很重要！

谓词公式及解释

谓词公式的类型正如命题公式有永真/永假/可满足一样，谓词公式也有这3种类型。永真式(逻辑有效式):在任何解释下均为真。永假式(矛盾式):在任何解释下均为假。可满足式:至少存在一种解释下为真。说明：

(1)命题逻辑,使用真值表可以判断一个公式的类型。

(2)在一阶逻辑即谓词逻辑中，不存在一个算法，在有限步内判断任意一个公式的类型。

(3)不可判定的！

(4)“任何解释”如何穷尽？不可能，因此只能根据某些原则如“代换实例”，即“类比命题逻辑原则”。谓词公式及解释谓词公式的类型谓词公式的类型永真式(逻辑有效式):在任何解释下均为真。永假式(矛盾式):在任何解释下均为假。可满足式:至少存在一种解释下为真。代换实例：设A0是含命题变元p1,p2,...,pn的命题公式，A1,A2,...,An是n个谓词公式(其中个体常元/变元/函数/谓词公式都未确定含义)，将A0中pi的每次出现都换成Ai，所得公式A称为A0的代换实例。A(x)A(x),xA(x)xA(x)是pp代换实例.A(x)A(x),xA(x)xA(x)是pp的代换实例谓词公式及解释谓词公式的类型代换实例：设A0是含命题变元p1,p2,...,pn的命题公式，A1,A2,...,An是n个谓词公式(其中个体常元/变元/函数/谓词公式都未确定含义)，将A0中pi的每次出现都换成Ai，所得公式A称为A0的代换实例。定理：命题重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。例题判断公式F(x,y)(G(x,y)F(x,y))的类型。解：F(x,y)p,G(x,y)q，得命题公式p(qp)，

F(x,y)(G(x,y)F(x,y))是p(qp)的代换实例。

p(qp)p(qp)ppq1，即为重言式,

故其代换实例F(x,y)(G(x,y)F(x,y))是永真式。称p(qp)为F(x,y)(G(x,y)F(x,y))的原型谓词公式及解释谓词公式的类型2.2谓词公式：设A0是含命题变元p1,p2,...,pn的命题公式，A1,A2,...,An是n个谓词公式，用Ai处处代替A0中pi的每次出现，所得公式A称为A0的代换实例。

定理：命题重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。(1)x(F(x)G(x))不是永真/永假/可满足实-整(2)xF(x)(xyG(x,y)xF(x))，是

p(qp)的代换实例，而p(qp)p(qp)1故永真式(3)(xF(x)yG(y))yG(y))

是(pq)q的代换实例，而(pq)qpqq0永假，故为永假谓词公式等值演算定义1

设A、B是两个合法的谓词公式,如果在任何解释下两个公式的真值都相等，则称A与B等值记为AB。因AB时在任何解释下，公式A与公式B的真值都相同，故AB为永真式，故有定义2。定义2

设A、B是两个合法谓词公式，如果在任何解释下，AB为永真式，则A与B等值，记为AB。等值问题，转换为永真问题，通过代换实例原则找原型

并不是所有的谓词公式有对应的原型，因此有些结论是无法证明，只能当作显然成立的公理。谓词公式等值演算谓词逻辑推理的公理：1、个体域为有限集D={a1,a2,...,an},则有

xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)

无法证明，只能理解！2.量词的德摩律xA(x)xA(x)xA(x)xA(x)

当否定符“”移过时，变成、变成、变成、变成。谓词公式等值演算2、量词否定等值式-对于量词的德摩律设公式A(x)含自由出现的个体变项x,则

(1)xA(x)xA(x)

不是所有的个体有某性=有些个体没有该特性

(2)xA(x)xA(x)

没有x有某些特性=所有的没有这个特性如：

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

x(M(x)F(x))x(M(x)F(x))x(M(x)F(x))xy(F(x)M(x)H(x,y))

xx(F(x)M(x)H(x,y))谓词公式等值演算1、个体域为有限集D={a1,a2,...,an},则有

xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)

无法证明，只能理解！2.量词的德摩律xA(x)xA(x)xA(x)xA(x)3、量词分配律 x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x)

无法证明，只能理解！谓词公式等值演算1、个体域为有限集D={a1,a2,...,an},则有

xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)2.量词的德摩律xA(x)xA(x)xA(x)xA(x)3、量词分配律 x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x)4、量词作用域的收缩与扩张律

A(x)含自由x，B不含有自由出现的x，则有：

(1)/x(A(x)B)/xA(x)B(2)/x(A(x)B)/xA(x)B谓词公式等值演算1、

xA(x)A(a1)A(a2)…A(an)个体域为有限xA(x)A(a1)A(a2)…A(an)2.量词的德摩律xA(x)xA(x)xA(x)xA(x)3、量词分配律x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)4、量词作用域的收缩与扩张律

(1)/x(A(x)B)/xA(x)BA(x)含自由x(2)/x(A(x)B)/xA(x)BB不含有自由x5、约束变元改名规则将A中某量词辖域中变元的每次约束出现，全部换成公式中未出现的字母，所得到的公式记为B，则AB6、置换规则：公式局部等值变换后,仍与原公式等值。谓词公式等值演算例题、x(A(x)B)xA(x)Bx(A(x)B)x(A(x)B) pqpq的代换实例xA(x)B 量词作用域的收缩与扩张律xA(x)B 德摩律xA(x)B pqpq的代换实例谓词公式等值演算例题、x(BA(x))BxA(x)x(BA(x))x(BA(x)) pqpq的代换实例BxA(x) 量词作用域的收缩与扩张律BxA(x)

pqpq的代换实例例题、x(A(x)B)

xA(x)Bx(A(x)B)x(A(x)B)pqpq的代换实例xA(x)B 量词作用域的收缩与扩张律xA(x)B德摩律xA(x)B pqpq的代换实例谓词公式等值演算例题、x(BA(x))BxA(x)x(BA(x))x(BA(x)) pqpq的代换实例BxA(x) 量词作用域的收缩与扩张律BxA(x)pqpq的代换实例例题、x(M(x)F(x))x(M(x)F(x))x(M(x)F(x))x(M(x)F(x)) 德摩律x(M(x)F(x)) 德摩律x(M(x)F(x))pqpq的代换实例谓词公式等值演算例题、x(M(x)F(x))x(M(x)F(x))x(M(x)F(x))x(M(x)F(x))pqpq的代换实例x(M(x)F(x)) 德摩律x(M(x)F(x))德摩律x(M(x)F(x)) pp的代换实例谓词公式等值演算例题、xy(F(x)G(y)H(x,y))

xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y)) 德摩律xy((F(x)G(y))H(x,y))pqpq

xy((F(x)G(y))H(x,y)) 德摩律xy((F(x)G(y))H(x,y)) ppxy(F(x)G(y)H(x,y))结合律

谓词公式等值演算例题、xy(F(x)G(y)L(x,y))

xy(F(x)G(y)L(x,y))

xy(F(x)G(y)L(x,y))xy(F(x)G(y)L(x,y)) 德摩律xy((F(x)G(y))L(x,y)) 德摩律xy((F(x)G(y))L(x,y))pqpq

谓词公式等值演算例1

将下面公式化成等值的公式,使其不含有既是约束出现又是自由出现的个体变项。xF(x,y,z)yG(x,y,z)解：x在前件中是约束变元，在后件是自由变元,y在前件中是自由变元，在后件是约束变元，容易产生歧义，故要改名！

约束变元改名：tF(t,y,z)sG(x,s,z)也可以对自由变元改名：xF(x,s,z)yG(t,y,z)谓词公式等值演算例将下面公式化成等值的公式,使其不含有既是约束出现又是自由出现的个体变项。xF(x,y,z)yG(x,y,z)解：x在前件中是约束变元，在后件是自由变元,y在前件中是自由变元，在后件是约束变元，

约束变元改名：tF(t,y,z)sG(x,s,z)对自由变元改名：xF(x,s,z)yG(t,y,z)x(F(x,y)yG(x,y,z))解：y在前件是自由，在后件是约束，有歧义！x(F(x,y)sG(x,s,z))谓词公式范式定义：一个谓词公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式称为前束范式，形如Q1x1Q2x2…QkxkB，其中Qi为或，B中不含有数量词。如xy(F(x)G(y)H(x,y))是前束范式x(F(x)y(G(y)H(x,y))不是！因B有量词

定理1：任何逻辑公式可转换为前束范式。说明：利用代换实例，将、转换为

用德摩律将否定深入到原子公式前面用量词辖域的扩张与收缩律，将量词的前面，左移到最前面，可能还要对约束变元换名。谓词公式范式定理1：任何逻辑公式可转换为前束范式。

步骤：(1)剔除不起作用的量词；(2)若约束变元与自由变元同名则约束变元改名；(3)如果与前面的约束变元同名，则后者改名；(4)利用代换实例，将、转换表示；(5)将否定深入到原子公式的前面；(6)利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边。谓词公式范式例公式xP(x)xQ(x)转换为前束范式xP(x)xQ(x)xP(x)yQ(y) 后方约束变元改名xP(x)yQ(y) 条件式的代换实例xP(x)yQ(y) 否定到底xy(P(x)yQ(y)) 量词辖域的扩张或，显然不唯一xP(x)xQ(x)xP(x)xQ(x) 条件式的代换实例xP(x)xQ(x) 德摩律x(P(x)Q(x)) 量词的分配律谓词公式范式例xP(x,y)yQ(x,y)转换为前束范式xP(x,y)yQ(x,y)rP(r,y)sQ(x,s) 约束变元改名rP(r,y)sQ(x,s) 转换条件式rP(r,y)sQ(x,s) 德摩律rs(P(r,y)Q(x,s)) 量词辖域的扩张谓词公式范式例x(yA(x,y)xy(B(x,y)y(A(y,x)B(x,y))))为前范式x(yA(x,y)xy(B(x,y)y(A(y,x)B(x,y))))x(yA(x,y)xy(B(x,y)r(A(r,x)B(x,r))))改名x(yA(x,y)xs(B(x,s)r(A(r,x)B(x,r))))改名x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))改名书上错了x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))条件式x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))德摩律x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))同上x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r))))xytsr(A(x,y)(B(t,s)(A(r,t)B(t,r))))

谓词推理

引言：推理是永恒的话题，谓词逻辑同样要进行推理，只是比命题逻辑更加复杂。谓词逻辑中不能使用真值表。谓词逻辑的等值式，其判断也只能根据代换实例规则，沿用命题逻辑中的等值式。因此只能使用自然推理的方法，即直接从前提出发，利用基本原则，不断推出结论谓词逻辑自有的等值式并不多，即使有，也是只能理解而无法证明的规律，如德摩律、分配律等。谓词推理定义1

若在各种解释下A1A2A3…AnB只能为真,则称为前提A1,A2,…,An可推出结论B。

定义2当A1A2A3…An为真时B为真，即当A1,A2,A3…,An为真时B为真。方法：当前提条件A1,A2,…,An为真时，利用等值式推出其他公式也为真，或利用谓词推理规律，推出其他公式为真，最终推出结论也为真。谓词推理

常见的推理方法

一、谓词逻辑的等值演算原则、规律：命逻的代换实例、量词德摩律、量词分配律、量词辖域的扩张与收缩、约束变元改名。二、命题逻辑的推理规则的代换实例。如假言推理规则、传递律、合取与析取的性质律、CP规则、反证法等。三、谓词逻辑的推理公理xA(x)xB(x)x(A(x)B(x))x(A(x)B(x))xA(x)xB(x)别反了四条推理铁律 谓词推理三、谓词逻辑推理公理:仅能理解左真时右真xA(x)xB(x)x(A(x)B(x))x(A(x)B(x))xA(x)xB(x)别反了

四条推理铁律 全称量词的指定US或-：xA(x)A(x0) x0是论域中的任意个体存在量词的指定ES或-：xA(x)A(c) c为某个特定的个体，不是任意的个体全称量词的推广UG或+：A(x0)xA(x)x0是论域中的任意个体存在量词的推广EG或+：A(c)xA(x) c为某个体全称量词消去规则(UI)xA(x)A(y)或xA(x)A(c)成立的条件：

x是A(x)中自由出现的个体变元；

y是任意的不在A(x)中约束出现的个体变元；例如若A(x)yF(x,y)，则xA(x)xyF(x,y)，利用UI规则：xA(x)A(y)，于是xyF(x,y)yF(y,y)，这个蕴含式是不成立，原因是使用UI规则时违背了条件②。存在量词消去规则(EI)xA(x)A(c)成立的条件：c是个体域中使A成立的特定的个体常元；c不曾在A(x)中出现过；A(x)中除x外还有其他自由出现的个体变元时，不能用此规则。注意这里的c是使A成立的特定的个体常元，不要和公式中或推理证明过程中前面步骤的其它常元和变元名称相同。例如在实数集上F(x,y)：x>y，若A(x)F(x,c)，c是实数集上的一个常数，则xA(x)为真，例用EI规则，消去量词，用c取代x，得F(c,c)，这是假命题。原因是违背了条件(2)。全称量词引入规则(UG)A(y)

xA(x)成立的条件：y是A(y)中自由出现的个体变元，y取个体域中的任何值，A都为真；取代y的x不能在A(x)中约束出现。例如在实数集上F(x,y)：x>y，若A(y)xF(x,y)，则对任意的y，A(y)为真，用UG规则，用x取代y，得xxF(x,x)，显然这是假命题。原因是违背了条件(2)。存在量词引入规则(EG)A(c)

xA(x)成立的条件：c是特定的个体常元；取代c的x不能在A(c)中出现过。例如在实数集上F(x,y)：x>y，若A(2)xF(x,2)，则A(2)为真，例用EG规则，用x取代2，得xF(x,x)，显然这是假命题。原因是违背了条件(2)。谓词推理例题(x(H(x)O(x))H(c)O(c)，