02离散数学课件资料-PPT精选文档_图文

在命题逻辑中,命题是命题演算的基本 单位,不关心每个简单命题反映的具体内容, 没有进一步研究命题的内部结构,因而在实 际应用中存在很多缺陷。

著名的苏格拉底三段论:
“所有的人都是要死的,苏格拉底是人,所以是苏格
拉底是要死的。” p: 所有的人是要死的; q: 苏格拉底是人;

r: 苏格拉底是要死的.
由上述文字构造的命题逻辑推理结构为: (p ? q)? r 可知: (p ? q)? r不是一个重言式,因此,按命题逻辑的 方法,无法证明上述问题.

为了在命题演算中,反映命题的内在联系,常 常要将简单命题分解成 个体词、谓词、量词 等, 并对它们的形式结构及逻辑关系加以研究,总结出 正确的推理形式和规则,这就是本章一阶逻辑要研

究的内容。

第二章
§2.1 一阶逻辑基本概念

一阶逻辑

§2.2 一阶逻辑合式公式及解释 §2.3 一阶逻辑等值式及前束范式

离散数学

4

§2.1一阶逻辑基本概念
个体词:可以独立存在的客体,既可以是抽象的概念, 也可以是具体的事物。 如:李明、自然数、
2。

谓 词:用来刻划个体词的性质或个体词之间关系的。 如:(1)
2

是无理数

(性质)
(关系)

(2) 小李比小赵高2厘米

简单命题总可以被分解成个体词和谓词两部分。

个体常项:指具体或特定的个体的词,用小写字 母a, b, c,……,表示。 个体变项:表示抽象的或泛指的个体的词,用x, y, z,……,表示。

个体域:个体变项的取值范围。
全总个体域:当无特殊声明时,表示宇宙间的一切 事物组成的个体域,又称全总域。

谓词常项:表示具体性质或关系的谓词,用大写 英文字母F,G,……,表示。 谓词变项:表示抽象的或泛指的性质或关系的谓词,

也用大写字母F,G,……,表示。
一般根据上、下文区分常项与变项。 个体变项x具有性质F:记作F(x) 个体变项x、y具有关系L:记作L(x,y)

将下列两命题符号化: (1)
2

是无理数

(性质)

解: 设F(x) : x 是无理数, a: 2 , 则(1)可表示为F(a)

(2) 小李比小赵高2厘米

(关系)

解: 设H(x, y) : x 比 y 高2厘米

a : 小李, b : 小赵
则(2)可表示为: H(a, b) (不是H(b, a))

元数:在谓词中所包含的个体词(变项)数。 n元谓词:含n(n?1)个个体词的谓词,可 用D(x1, x2,……,xn)表示。 一元谓词表性质; 二元或更多元谓词表示关系。

0元谓词:不含个体变项的谓词 。 如:a为2,b为3,L(a,b)是0元谓词。

例1.将下列命题用0元谓词符号化 (1) 2是素数且是偶数 ;
(2) 如果2大于3,则2大于4 ; (3) 如果张明比李民高,李民比赵亮高, 则张明比赵亮高 ; (1)解:设F(x) : x是素数,G(x):x是偶数,

a:2,则 (1) 符号化为F(a) ? G(a) (0元谓词)
(2)解:引入二元谓词:L(x, y):x比y大

a:2,b:3,c:4, (2) 符号化为L(a,b) ? L(a, c)
(3)解:引入二元谓词:H(x, y):x比y高 (3) 符号化为(H(a,b)?H(b,c))?H(a, c) a:张,b:李,c:赵,

考虑以下形式命题的符号化: (1) 所有的人都是要死的; (2) 有些人活百岁以上;

量 词 表示数量的词,分全称量词与存在量词。

?:一切、所有的、任意的;
?:存在着、有一个、至少有一个;

?x:个体域中所有个体;
?x:个体域中存在某个个体; ?xF(x):个体域中所有个体具有性质F; ?xF(x):个体域中存在着某个个体具有性质F。

将命题 “所有的人都是要死的”符号化
(个体域为人类集合)

符号化为:?xF(x) 其中F(x)表示:x是要死的。 将命题 “有的人活百岁以上”符号化 (个体域为人类集合) 符号化为:?xF(x) 其中F(x)表示:x活百岁以上。

特性谓词:在全总个体域的情况下,为了指定某个 个体变项的范围,引入特性谓词。 有了个体词、谓词、量词等概念,我们就可 以更细致地刻划命题公式。 将命题(公式)“所有的人都是要死的”符号 化 解: M(x):x是人 (特性谓词) F(x):x是要死的 命题(公式)符号化为: ?x(M(x)?F(x)) 分析一下: 它与?xF(x)有什么区别?

将命题(公式)“有些人活百岁以上”符号化
解: M(x):x是人(特性谓词) F(x):x活百岁以上

命题(公式)符号化为: ?x(M(x) ?F(x))
分析一下: 它与?xF(x)有什么区别?

使用量词时, 应该注意以下几点:
1 .在不同的个体域中,命题符号化的形式可能不一样; 2. 如没有事先给出个体域,都应以全总个体域为个体域。 3. 在引入特性谓词后,引入全称量词与存在量词符号化 的形式是不同的; 4.当个体域为有限集时,如D={a1,a2,a3,…an},对于任意 的谓词A(x),都有 (1) ?xA(x) ? A(a1) ? A(a2) ? …...? A(an) (2) ?xA(x)?A(a1)?A(a2)?……?A(an)

5.多个量词同时出现时,不能随意颠倒顺序;

例: 对于任意的x, 存在y,使得x+y=5,

取个体域为实数集合,该如何符号化? ?x ?y H(x,y) , 其中H(x,y) : x+y=5
量词颠倒顺序成立吗?

例2.在谓词逻辑中将下列命题符号化

(1) 对所有的x,均有x2–1=(x+1)(x–1) (个体域为自然数集)
(2) 存在x,使得x+5=2 (个体域为自然数集) (3) 凡偶数均能被2整除 (4) 存在着偶素数 (5) 没有不犯错误的人 (6) 在北京工作的人未必都是北京人

(7) 一切人都不一样高
(8) 每个自然数都有后继数 (9) 有的自然数无先驱数 (10) 有的有理数是整数 (个体域为实数集) (11) 每个人都有一些缺点。

符号化方法 1、 找到所有的个体词; 2、 是否要引入特性谓词; 3、 描述个体词性质:性质谓词(一元);

描述个体词关系:关系谓词(二元);
4、 按原命题的实际意义进行刻划。

(1) 对所有的x,均有x2 –1=(x+1)(x–1) (个体域为自然数集)

解: 设F(x) :x满足x2–1=(x+1)(x – 1)
(1)符号化:?xF(x) (2) 存在 x,使得x +5=2 (个体域为自然数集) 解: 设G(x) :x满足x +5=2 (2)符号化:?xG(x)

(3) 凡偶数均能被2整除 解:要引入特性谓词: F(x) : x是偶数 G(x) : x能被2整除 符号化: ?x(F(x)?G(x)) (4) 存在着偶素数 解:F(x) : x是偶数 G(x) : x是素数 符号化: ?x(F(x)?G(x))

(5) 没有不犯错误的人 解:特性谓词M(x):x是人

F(x):x犯错误
符号化: ??x(M(x) ? ? F(x))

或?x(M(x) ? F(x))
(6) 在北京工作的人未必都是北京人 解:F(x) : x是在北京工作的人,G(x) :x是北京人 符号化:??x(F(x) ? G(x)) 或: ?x(F(x) ? ?G(x))

(7) 一切人都不一样高 解:M(x) : x是人, L(x,y) : x与y一样高 H(x,y):x与y是同一个人 符号化:?x?y(M(x) ? M(y) ? ?H(x,y) ? ? L(x,y)) 或:??x ?y(M(x) ? M(y) ? ?H(x,y) ? L(x,y))

(8) 每个自然数都有后继数
解:F(x):x自然数 H(x,y):y是x的后继数

符号化:?x(F(x) ? ?y (F(y) ? H(x,y)) 或: ??x(F(x) ? ?y (F(y) ? ?H(x,y)))

(9) 有的自然数无先驱数
解:F(x):x是自然数 ,H(x,y):y是x的先驱数 符号化:?x(F(x) ? ?y(F(y) ? ? H(x,y))) 或:??x(F(x)??y(F(y) ? H(x,y)) (10) 有的有理数是整数 (个体域为实数集) 解: F(x):x是有理数,G(x):x是整数 符号化:?x(F(x) ? G(x)) (11) 每个人都有一些缺点。 解:F(x,y):x都有y,M(x):x是人,G(y):y是缺点 符号化: (?x) (M(x)?(?y) (G(y)?F(x,y)))

或: (?x)(?y)(M(x)?(G(y)?F(x,y)))

§2.2 一阶逻辑合式公式及解释
一、一阶逻辑合式(谓词)公式的概念

原子公式:不出现命题联结词和量词的命题
函数P(x1, x2,…, xn) ,

其中x1,x2,…,xn为个体变项或常项。 谓词演算中的合式公式:
(1) 原子谓词公式是合式公式; (2) 若A是合式公式,则?A也是;

(3)若A和B是合式公式,则(A?B),(A?B),(A?B) 和(A ? B)也是 ; (4)如果A是合式公式,x是A中出现的个体变项, 则 (?x)A和(?x)A是合式公式 ; (5)只有有限次地应用规则(1)、(2)、(3)、(4)所

得到的公式才是合式公式。
谓词合式公式即按规则(1)、(2)、(3)、(4)、(5)由

原子公式、联结词、量词及括号组成的字符串,但
最外层括号可以省略。

二、谓词公式的改写 在谓词公式中,我们还用到以下概念。 指导变元及作用域 在谓词公式中,形如 (?x)P(x) 或 (?x)P(x) 的 部分,叫做公式的约束部分。 量词?,?后面的x叫做量词的作用变元,或指 导变元,P(x)叫做量词的作用域。

在作用域中,x的一切出现为约束出现,非
约束出现的其它变元叫自由出现变元。

例3. 指出下列合式公式中的指导变元,量词的作 用域及变元约束的情况。 (1) (?x)(P(x)?(?y)R (x,y)) ; 解:(?y)R(x, y)中,指导变元是y, ?的作用域为R(x, y),其中y是约束出现,x是自由出现的。 在整个合式公式中,x是作用变元(指导变元),

?的作用域(P(x)?(?y)R(x, y)),x, y 都是约束出现的,
x约束出现2次,y约束出现1次。

(2) (?x) (?y) (P(x, y) ? Q(y, z)) ? (?x) R(x, y)
解:(?x)(?y)(P(x, y)?Q(y, z)),x,y是作用变元,两

个量词?的作用域都是(P(x,y)?Q(y,z)),其中x, y
均为约束出现,x约束出现1次,y约束出现2次, z为自由出现1次。 在(?x)R(x, y)中, x是指导变元,?的作用域为R(x, y),其中x约束 出现 1 次, y 自由出现 1 次。在整个合式公式中,

x 约束出现 2 次, y 约束出现 2 次,自由出现 1 次,
z自由出现1次。

(3) (?x)(P(x) ? (?x)Q(x, z)?(?y)R(x, y))?Q(x, y) ; 解:(?x)Q(x, z)中x是作用变元,?的辖域为Q(x,z),

其中 x 约束出现,z自由出现;(?y)R(x, y)中,y是
作用变元,?的辖域为R(x, y),其中y约束出现,x自 由出现; 在(?x)(P(x)?(?x) Q(x,z)?(?y)R(x, y)) 中, 作用变元为x,?的作用域为(P(x)?(?x)Q(x, z) ?(?y)R(x, y)), 但Q(x, z)中的x不是?的作用变元,x, y 在整个公式中,x约束出现3次,自由出现1次, y约束出现1次,自由出现1次,z自由出现1次。

均为约束出现,z自由出现; Q(x, y)中,x, y为自由变元。

考虑到谓词公式中,有的个体变项既可以约束出现, 又可以自由出现,为避免这种双重性可能引起的混淆, 我们要将谓词公式进行改写,改写规则如下:

1. 换名规则:
将量词作用域中出现的某个约束出现的个体变项及 对应的指导变项改成另一个作用域中没有出现过的 个体变项符号,公式的其余部分不变。 2. 代替规则 对某自由出现的个体变项用与原公式中所有个体

变项符号不同的变项符号去代替,且处处代替。

换名规则与代替规则可避免有的个体变项既 可以约束出现,又可以自由出现。

例4.试对下列公式换名或代替。
(1) (?x)(P(x)?(?y)R (x,y)) ;

(2) (?x)(?y)(P(x,y)?Q(y,z))?(?x)P(x,y) ; (3) (?x)(P(x)?(?x)Q(x,z)?(?y)R(x,y))?Q(x,y) ;

解: (1) (?x)(P(x)?(?y)R (x,y)) ;不用改写

(2) (?x)(?y)(P(x,y)?Q(y,z))?(?x)R(x,y) ;
第一步换名:(?x)(?y)(P(x,y)?Q(y,z))?(?u)R(u,y) ; 第二步代替:(?x)(?y)(P(x,y)?Q(y,z))?(?u)R(u, v) ; (3) (?x)(P(x)?(?x)Q(x,z)?(?y)R(x,y))?Q(x,y) ;

第一步换名:(?x)(P(x)?(?u)Q(u,z)?(?y)R(x,y))?Q(x,y) 第二步代替:(?x)(P(x)?(?u)Q(u,z)?(?y)R(x,y))?Q(s, t)

例5.求下列谓词公式的真值: (?x)(P(x)?Q(x)),其中P(x):x = 1, Q(x):x = 2,且个体域 E = {1,2}; 解题思想 当个体域是有限集时,如D ={a1,a2,……an}

则:(?x)A(x)?A(a1)?A(a2)?……?A(an)
(?x)A(x)?A(a1)?A(a2)?……?A(an) 从而谓词公式的真值等价于命题公式的真值。 (?x)(P(x)?Q(x))?(P(1)?Q(1)?(P(2)?Q(2)) 解: ?(1?0)?(0?1) ?0

三、谓词公式的解释
谓词合式公式的解释 (或指派) 一个一阶逻辑合式公式中往往含有个体变项、

谓词变项等,一组使合式公式成为具有确定真值
的常项(个体常项、谓词常项等)就构成了一个 公式的解释。

例6:给定解释I如下:
DI={2,3};DI中特定的元素a=2;

函数f(x)为f(2)=3,f(3)=2;
谓词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.

(1)?x(F(x) ∧G (x,a))

? (F(2) ∧G (2,2)) ∧ (F(3) ∧G (3,2))
? (0 ∧1) ∧ (1 ∧1) ? 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)) ? (1∧1) ∨(0∧1) ? 1 (3)?x?y L(x,y)

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

? (1∨0) ∧(0∨1) ? 1

四、谓词公式的类型
永真式(逻辑有效式):任一组解释皆使公式真值为1 永假式: (?)

可满足式: (?) ? x(F (x) ? F (x));
没有一个可行的算法来判断一阶逻辑公式的类型, 只能对某些特殊的公式进行判断。

§2.3 一阶逻辑等值式及前束范式
一、谓词演算中常见等值式:
(I) 命题公式的推广 24个常用的命题演算等值式及其代换可推广

到谓词演算中使用,如
1. (?x)(P(x)?Q(x))?(?x)(? P(x)?Q(x)) 2. (?x)P(x)?(?y)R(x,y) ? ? (? (?x)P(x) ? ? (?y)R(x, y)) 3. (?x)H(x,y)?? (?x)H(x,y)?F

一、谓词演算中常见等值式:
(Ⅱ) 量词否定等值式 (量词转换律) ? (?x)P(x) ? (?x)? P(x) ? (?x)P(x) ? (?x)? P(x) 实例:“不是所有人今天都来上课” ? “存在一些人今天没来上课” “没有一个人今天来上课” ? “所有的人今天都没来上课” 。

(Ⅲ) 量词作用域的扩张与收缩等值式 ?xA(x)?B??x(A(x)?B)

?xA(x)?B??x(A(x)?B)
?xA(x)?B??x(A(x)?B) ?xA(x)?B??x(A(x)?B) B??xA(x) ??x(B?A(x))
? ?xA(x) ? B ? ??xA(x) ? B ? ?x(?A(x)) ? B ? ?x(?A(x) ? B) ? ?x(A(x) ? B)

B??xA(x) ??x(B?A(x))
* ?xA(x)?B??x(A(x)?B) * ?xA(x)?B??x(A(x)?B)

注意记住(*),且各等价式中的B可含其他非指导变元。

一、谓词演算中常见等值式:
(Ⅳ) 量词分配等价式

(?x)(A(x)?B(x))?(?x)A(x)? (?x)B(x)(?对?的分配) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x) (?对?的分配) 注意: ?对? ,?对? 不存在分配等价式。
(?x)(A(x) ? B(x))?(?x)A(x) ?(?x)B(x) (?x)(A(x) ? B(x))?(?x)A(x) ? (?x)B(x)

一、谓词演算中常见等值式:
(Ⅴ) 多个量词的使用 (?x)(?y)A(x,y)?(?y)(?x)A(x,y) (?x)(?y)A(x,y) ? (?y)(?x)A(x,y)

注意: 其他情况下量词换序后一般不等价。

二、常见等值式的应用(前束范式)
借助于常见等价式,我们仿照命题公式可以化成标 准形式,也想把谓词公式化成标准形式。谓词逻辑中, 任何谓词公式的前束范式都存在,但一般不唯一。 前束范式:一个合式谓词公式,它的所有量词均

非否定地出现在公式的最前面,且它们的
作用域一直延伸到公式的末尾。 如: (?x)(?y)(?z)(P(x)?F(y,z)?Q(y,z))

二、常见等值式的应用(前束范式)
例7. 将合式公式((?x)P(x)?(?y)R(y))?(?x)F(x) 化为前束范式: 解题思想 任一合式公式表示成前束范式可按如下步骤进行:

(1) 消去公式中出现的多余量词;

二、常见等值式的应用(前束范式)
(2) 利用双重否定定律、德 ? 摩根律及量词转换律
将公式中的否定字符深入到谓词字母前(否定符

紧贴);
(3) 利用换名和代换规则使所有约束变元均不相同 , 并且使自由变元也与约束变元不同(更名); (4) 利用量词作用域的扩张和收缩律,扩大量词的 作用域至整个公式(扩域)。

二、常见等值式的应用(前束范式)
(?xP(x)??yR(y))??xF(x) 解: (1) 更换变元符号 ? (?xP(x)??yR(y)) ??zF(z) (2) 扩大作用域

? ?x?y?z((P(x) ? R(y)) ? F(z))

二、常见等值式的应用(前束范式)
例8. 求下列合式公式的前束范式

(1) (?x)P(x) ? ?(?x)Q(x)
解: (?x)P(x) ? ?(?x)Q(x) ? (?x)P(x) ? (?x)?Q(x)

? (?x)(P(x) ? ?Q(x))

二、常见等值式的应用(前束范式)
例8. 求下列合式公式的前束范式

(2) (?x)P(x)? ?(?x)Q(x)
解: (?x)P(x)? ?(?x)Q(x) ? (?x)P(x)? (?x)?Q(x)

? (?x)P(x)? (?y)?Q(y)
? (?x)(?y)(P(x)??Q(y))

二、常见等值式的应用(前束范式)
例8. 求下列合式公式的前束范式

(3) (?x)P(x)?(?x)Q(x)
? (?x)P(x)?(?y)Q(y) ? (?x)(?y)(P(x)?Q(y))

(4) (?x)P(x)?(?x)Q(x)
? (?x)P(x)?(?y)Q(y) ? (?x)(?y)(P(x)?Q(y))

二、常见等值式的应用(前束范式)
例8. 求下列合式公式的前束范式

(5) (?xF(x,y)??yG(y))??xH(x,y)
?(?xF(x,z)??yG(y))??xH(x,z) ?(?xF(x,z)??yG(y))??uH(u,z) ??x?y(F(x,z)?G(y))??uH(u,z) ? ?x?y?u((F(x,z)?G(y))?H(u,z)

二、常见等值式的应用
前束合取范式:

前束范式(?x)P(x)的命题公式部分即P(x)为合
取范式。 前束析取范式: 前束范式(?x)P(x)的命题公式部分即P(x)为析 取范式。


相关文档

离散数学课件-第6章-4-PPT精选文档
离散数学课件-第2章-3-PPT精选文档
离散数学课件资料1.ppt
离散数学课件简介-PPT精选文档
离散数学课件第12章文件-PPT精品文档
离散数学课件资料.ppt
离散数学课件第5章6-PPT精品文档
离散数学课件第5章4-PPT精品文档
离散数学课件图论6-PPT精品文档
小学数学课件_免费下载.ppt-文档资料
学霸百科
电脑版 | | 学霸百科