谓词逻辑基本概念最全资料课件

1

一阶逻辑(谓词逻辑）1 一阶逻辑(谓词逻辑）12内容要点：谓词和个体量词一阶逻辑公式置换规则一阶逻辑等值式一阶逻辑前束范式推理理论CH4CH4CH4CH5CH5CH5CH52内容要点：谓词和个体量词一阶逻辑公式置换规则一阶逻辑等值式23例：凡偶数都能被2整除，

6是偶数。所以，6能被2整除将它们命题符号化：

p：凡偶数都能被2整除

q：6是偶数

r：6能被2整除则推理的形式结构符号化为：

(p

q)

r由于上式不是重言式，所以不能由它判断推理的正确性。为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是谓词逻辑。

引言3例：凡偶数都能被2整除，由于上式不是重言式，所以不能由它判34第五讲一阶逻辑主要内容一、谓词的概念与表示法二、命题函数与量词 三、特性谓词的使用四、一阶逻辑合式公式的翻译及解释五、变元的约束

4第五讲一阶逻辑主要内容45(1)８是自然数。(2)21世纪末，人类将住在月球。

(3)x+y=y+x(4)只有x能被2整除，x才能被4整除。x,y的取值范围：复数域a的取值范围：整数域是指所研究对象中可以独立存在的具体的或抽象的客体。表示具体或特定的客体的个体词称作个体常项；常用a,b,c,…表示。表示抽象或泛指的客体的个体词称作个体变项；常用x,y,z,…表示。个体变项的取值范围为个体域，个体域可以是有穷集合，也可以是无穷集合。全总个体域：由宇宙间一切事物组成的域为全总个体域。

一、谓词的概念及表示法----个体词5(1)８是自然数。x,y的取值范围：复数域是指所研究对象中56(1)８是自然数。(2)21世纪末，人类将住在月球。

(3)x

与y

具有关系L(4)只有x能被2整除，x才能被4整除。谓词：用来刻划个体词性质及个体词之间相互关系的词表示具体性质或关系的谓词称为谓词常项谓词变项：表示抽象的或泛指的性质或关系的谓词两者都用大写英文字母表示一、谓词的概念及表示法----谓词6(1)８是自然数。谓词：用来刻划个体词性质及个体词之间相互6前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。③施行后的结果不同。(3)DI上特定函数集合{fin|i,n≥1}.在P(x)，P(x,y)等前加上x或x，称变元x被存在量化或全称量化。谓词变项：表示抽象的或泛指的性质或关系的谓词b:4;f(x,y)=x+y;F(x,y):x=y一、谓词的概念及表示法b:5;f(x,y)=x-y;F(x,y):x>y定义2复合命题函数：由一个或几个简单命题函数及逻辑联结词组合的表达式。(2)令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：x>y6是偶数。R(x):x住在中国如果事先没有给出个体域，都应以全总个体域为个体域。是指所研究对象中可以独立存在的具体的或抽象的客体。7

谓词命名式

是谓词与个体常元和个体变元结合的表现形式，有时简称谓词。规定：小写字母表示个体变元，大写字母表示谓词。例“张明是位大学生”这是命题，作为谓词逻辑的对象，“张明”是个体，“是位大学生”是谓词，它刻划了“张明”的性质。设P：是位大学生a：张明则“张明是位大学生”可表示为P(a)，或者写成P(a)：张明是位大学生。一、谓词的概念及表示法前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)78一般的用F(a)表示个体常项a具有性质F（F是谓词常项或谓词变项），用F(x)表示个体变项x具有性质F。而用F(a,b)表示个体常项a,b具有关系F，用F(x,y)表示个体变项x,y具有关系F。一、谓词的概念及表示法8一般的一、谓词的概念及表示法89定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体变元，称该谓词为n元谓词。例如

S(x):表示x是大学生。一元谓词

G(x,y)：表示x>y。二元谓词

B(x,y,z)：表示x在y与z之间。三元谓词一般地

P(x1,x2,…,xn)是n元谓词。一、谓词的概念及表示法9定义：一个大写英文字母后边有括号，括号内是若干个客体变元，9100元谓词：有时将不带个体变项的谓词称为0元谓词，例如到的F(a)，H(a,b)，P(a1,a2,…,an)等都是0元谓词，当F,H,P为谓词常项时，0元谓词为命题。这样，命题逻辑中的命题均可表示成0元谓词，因而可以将命题看成是特殊的谓词。注意：命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。一、谓词的概念及表示法100元谓词：有时将不带个体变项的谓词称为0元谓词，例如到的1011将下列命题用0元谓词符号化，并讨论它们的真值。(1)2是素数且是偶数(2)如果2大于3，则2大于4

解：(1)设一元谓词F(x)：x是素数；一元谓词G(x)：x是偶数；a：2。则(1)中命题符号化为0元谓词的合取式：

F(a)

G(a)。(2)

设二元谓词L(x,y)：x大于y；a：2；b：3；c：4.命题符号化为L(a,b)

L(a,c)一、谓词的概念及表示法11将下列命题用0元谓词符号化，并讨论它们的真值。一、谓词的1112二、命题函数与量词定义1简单命题函数：由一个谓词、一些个体变元组成的表达式。n元谓词P(x1,…,xn)是n个个体变元的命题函数。是以个体域为定义域，{0，1}为值域的n元命题函数。定义2复合命题函数：由一个或几个简单命题函数及逻辑联结词组合的表达式。命题逻辑联结词的意义在谓词逻辑中可看作相同解释。命题函数不是命题，取值与个体域也有关。12二、命题函数与量词定义1简单命题函数：由一个谓词、一些1213例如S(x)：x是大学生，x的个体域为某单位职工；那么S(x)可表示：某单位职工都是大学生，也可表示某单位有一些职工是大学生。利用n元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题。为了避免理解上的歧义，需要引入用以刻划“所有的”、“存在一些”等表示不同数量的词，即量词，其定义如下：量词13例如S(x)：x是大学生，x的个体域为某单位职工；量词1314量词定义量词——表示数量的词

全称量词

x:对个体域中所有的x

如,

xF(x)表示个体域中所有的x具有性质F

x

yG(x,y)表示个体域中所有的x和y有关系G

存在量词

x:个体域中有一个x

如,

xF(x)表示个体域中有一个x具有性质F

x

yG(x,y)表示个体域中存在一个x使得对每一个y,x和y有关系G14量词定义量词——表示数量的词1415

在P(x)，P(x,y)等前加上

x或

x，称变元x被存在量化或全称量化。

将谓词F(x)变成命题有两种方法a.将x取定值例：F(x)：x是质数，那么F(4)是命题（假）b.将谓词量化

例：1).

xF(x)F(x)：任意的x是质数

2).

y(y<y+1)3).

y(y<y+1)

量词作用15在P(x)，P(x,y)等前加上x或x，称变1516特别注意：一个谓词中所有个体变元都量化了，该谓词才能变成命题。这如同数学中的函数f(x)， 的值是不确定的，但 可确定其值。量词作用16特别注意：一个谓词中所有个体变元都量化了，该谓词才能变成1617

(1)分析命题中表示性质和关系的谓词，分别符号化为一元和n（n

2）元谓词。

(2)根据命题的实际意义选用

或。

(3)在不同的个体域中，命题符号化的形式可能不一样。如果事先没有给出个体域，都应以全总个体域为个体域。

(4)多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。量词使用注意事项17(1)分析命题中表示性质和关系的谓词，分别符号1718(5)当个体域为有限集时，如D={a1,a2,…,an}，由量词的意义可以看出，对于任意的谓词A(x)，都有①

xA(x)

A(a1)

A(a2)

…

A(an)②

xA(x)

A(a1)

A(a2)

…

A(an)这实际上是将谓词逻辑中命题公式转化为命题逻辑中的命题公式问题。量词使用注意事项18(5)当个体域为有限集时，如D={a1,a2,…1819三、特性谓词的使用特性谓词：用P(x)来限制个体变元的取值范围。如在全总个体域（全总论域）中，用M(x)表示x是人；用R(x)表示x是实数等。19三、特性谓词的使用特性谓词：用P(x)来限制个体变元的取1920

1.设个体域为D={0,1,2,……,10},将下列命题符号化：

(1)D中所有元素都是整数；

(2)D中有的元素是偶数；

(3)D中所有的偶数都能被2整除；

(4)D中有的偶数是4的倍数。

举例∀xF(x),其中F(x)：x是整数∃xG(x),其中G(x)：x是偶数∀x(G(x)

H(x)),其中G(x):x是偶数;H(x):x能被2整除∃x(G(x)∧R(x)),其中G(x):x是偶数;R(x):x是4的倍数20举例∀xF(x),其中F(x)：x是整数∃xG(x20212.设个体域为D={x|x为人}，将下列命题符号化：(1)人都生活在地球上；(2)有的人长着黑头发；(3)中国人都用筷子吃饭；(4)有的中国人不住在中国；

∀xF(x),其中F(x)：x生活在地球上∃xG(x),其中G(x)：x长着黑头发∀x(H(x)

I(x)),其中H(x):x是中国人；I(x)：x用筷子吃饭∃x(H(x)∧

R(x)),其中H(x):x是中国人；R(x):x住在中国举例212.设个体域为D={x|x为人}，将下列命题符号化：∀21223.用量词、谓词来表述命题。

(1)凡是人都是要死的。

(2)某些实数是有理数。

∀x(F(x)

H(x)),其中F(x):x是人；H(x):ｘ是要死的；∃x(G(x)∧Q(x)),其中G(x):x是实数；H(x):ｘ是有理数；举例223.用量词、谓词来表述命题。∀x(F(x)H2223特性谓词加入规则（1）对全称量词，特性量词作为蕴含前件加入。（2）对存在量词，特性量词作为合取项加入。23特性谓词加入规则（1）对全称量词，特性量词作为蕴含前件加23p：凡偶数都能被2整除四、一阶逻辑公式翻译及解释G(x,y)：表示x>y。(2)21世纪末，人类将住在月球。③施行后的结果不同。xyG(x,y)表示个体域中存在一个x使得对每一个y,x和y有关系Gp：凡偶数都能被2整除用F(x,y)表示个体变项x,y具有关系F。xyG(x,y)表示个体域中所有的x和y有关系G24实例3例3

在一阶逻辑中将下面命题符号化

(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))p：凡偶数都能被2整除24实例3例3在一阶逻辑中将下面命2425原子公式：不出现命题联结词和量词的谓词命名式，P(X1,X2…Xn)称为谓词演算的原子公式。前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。

四、一阶逻辑公式翻译及解释25原子公式：四、一阶逻辑公式翻译及解释2526定义4

合式公式定义如下：

(1)原子公式是合式公式.(2)若A是合式公式，则(

A)也是合式公式

(3)若A,B是合式公式，则(A

B),(A

B),(A

B),(A

B)也是合式公式

(4)若A是合式公式，则

xA,

xA也是合式公式

(5)只有有限次地应用(1)—(4)形成的符号串才是合式公式.合式公式简称公式

如,F(x),F(x)

G(x,y),x(F(x)G(x))等都是合式公式谓词公式26定义4合式公式定义如下：谓词公式2627定义

一个解释

I

由下列4部分组成：(1)非空个体域DI。(2)DI中一些特定元素的集合{a1,a2,…ai,…}.(3)DI上特定函数集合{fin|i,n≥1}.(4)DI上特定谓词的集合{Fin|i,n≥1}.所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等。谓词公式的解释27定义一个解释I由下列4部分组成：谓词公式的解释2728解释(举例)F(f(a,a),b)解释1：个体域是全体自然数;a:2;b:4;f(x,y)=x+y;F(x,y):x=y

原公式解释成:“2+2=4”。解释2：个体域是全体实数;a:3;b:5;f(x,y)=x-y;F(x,y):x>y

原公式解释成:“3-3>5”。28解释(举例)F(f(a,a),b)2829(1)量词的辖域定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。例：

XP(X)→Q(X)

X的辖域是P(X)

X(P(X,Y)→Q(X，Y))

P(Y,Z)

X的辖域是P(X，Y)→Q(X，Y)

变元的约束29(1)量词的辖域变元的约束2930定义：在量词

X，

X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元；变元的非约束出现称为自由出现,称这样的变元为自由变元。

例：指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域。

X(P(X)

R(X))→

XP(X)

Q(X)

解：表达式中的

X(P(X)

R(X))中X的辖域是P(X)

R(X),其中的X是约束出现，Q(X)中的X是自由变元。

变元的约束30定义：在量词X，X辖域内变元X的一切出现叫约束出现，3031

注意：在一个公式中，一个变元既可以约束出现，又可以自由出现。为避免混淆可采用下面两个规则：①约束出现改名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。例

xF(x)∧G(x,y)(换名规则,将约束出现

zF(z)∧G(x,y)的x改成z)约束变元改名规则31注意：在一个公式