离散结构及应用-ALL_第1页
离散结构及应用-ALL_第2页
离散结构及应用-ALL_第3页
离散结构及应用-ALL_第4页
离散结构及应用-ALL_第5页
已阅读5页,还剩205页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、离散结构与应用湖北经济学院湖北经济学院 软件工程系软件工程系第1部分 数理逻辑第1章 命题逻辑第2章 一阶逻辑第1章 命题逻辑这章是以“命题”为中心,主要讨论: 1、命题的表示、命题的演算 2、命题演算中的公式,及其应用 3、命题逻辑推理1.1 1.1 命题与联结词命题与联结词 命题是一个能确定是真的或是假的判断。(判命题是一个能确定是真的或是假的判断。(判断都是用陈述句表示)断都是用陈述句表示) 判断一个语句是否为命题,首先看是否为陈述句,再看其真值是否唯一。 例:判定下面这些句子哪些是命题。例:判定下面这些句子哪些是命题。 2是个素数。 雪是黑色的。 2017年人类将到达火星。 如果 ab

2、且bc,则ac。 x+yb、bc、ac)构成的复合命题。1.1 1.1 命题与联结词命题与联结词 复合命题:是用“联结词”将原子命题联结起来构成的。定义了六个逻辑联结词: (1) 否定: (2) 合取: 并且 (3) 析取: 可兼取的或者 (4) 异或: 不可兼取的或 (教程未提) (5) 蕴涵: 如果。,那么。 (6) 等价:1.1 1.1 命题与联结词命题与联结词 P Q PQ PQ PQ PQ F F F F T T F T F T T F T F F T F F T T T T T T1.1 1.1 命题与联结词(课题练习)命题与联结词(课题练习) 已知PQ为T,则P为( ),Q为(

3、)。 已知PQ为F,则P为( ),Q为( )。 已知P为F,则PQ为( )。 已知P为T,则PQ为( )。 已知PQ为T,且P为F ,则Q为( )。 已知PQ为F,则P为( ),Q为( )。 已知P为F,则PQ为( )。 已知Q为T,则PQ为( )。1.1 1.1 命题与联结词(课题练习)命题与联结词(课题练习) 已知 PQ为F,则P为( ), Q为( )。 已知P为T,PQ为T,则Q为( )。 已知Q为T, PQ为T,则P为( )。 已知PQ为T,P为T , 则Q为( ). 已知PQ为F,P为T , 则Q为( ). PP 的真值为( ). PP 的真值为( )。1.2 1.2 命题公式及符号

4、化命题公式及符号化 常值命题:常值命题:即是我们前面所说的命题。它有具体含义 (真值)。 例如:“3是素数。”就是常值命题。 命题变元:命题变元:用大写的英文字母如P、Q等表示任何命题。称这些字母为命题变元。 对命题变元作指派对命题变元作指派( (给命题变元一个解释给命题变元一个解释) ):将一个常值命题赋予命题变元的过程,或者是直接赋给命题变元真值“T”或“F”的过程。 注意:注意:命题变元本身不是命题,只有给它一个解释,才变成命题。1.2 1.2 命题公式及符号化命题公式及符号化 合式公式合式公式 ( wff ) (well formed formulas) ( wff ) (well f

5、ormed formulas):对计算机而言,最方便的定义方式就是构造性的(或递归性的),即用简单的原子命题变元和联结词,通过有限步构造出新的复合命题来。因此,我们给出下面的定义: 见教程 P6/定义1.10 注意:注意:这个定义是递归的。(1)是递归的基础,由(1)开始,使用(2)、(3)规则,可以得到任意的合式公式。1.2 1.2 命题公式及符号化命题公式及符号化 对每个命题变元可以有两个真值(T,F)被指派,所以有n个命题变元的命题公式 A(P1,P2,Pn) 的真值表有2n行。 为有序地列出A(P1,P2,Pn)的真值表,可将F看成0、T看成1,按二进制数次序列表。如A(P,Q)的真值

6、表可按照如下次序指派:00(FF),01(FT),10(TF),11(TT) A(P,Q,R)的真值表可按照如下次序指派: 0 1 2 3 4 5 6 7000 001 010 011 100 101 110 111FFF FFT FTF FTT TFF TFT TTF TTT1.2 1.2 命题公式及符号化命题公式及符号化命题符号化定义: 用命题公式的符号串来表示给定的命题。命题符号化的方法: 1.首先要明确给定命题的含义。 2.对于复合命题,找联结词,用联结词断句,分解出各个原子命题。 3.设原子命题符号,并用逻辑联结词联结原子命题符号,构成给定命题的符号表达式。1.2 1.2 命题公式及

7、符号化命题公式及符号化例 如果小张与小王都不去,则小李去。 P:小张去。 Q:小王去。 R:小李去。 该命题可写成: (PQ)R 如果小张与小王不都去,则小李去。 该命题可写成: (PQ)R 也可以写成: (PQ)R1.2 1.2 命题公式及符号化命题公式及符号化重言式(矛盾式)定义定义:A(P1,P2,Pn) 是含有命题变元P1,P2, Pn的命题公式,如不论对P1, P2 , , Pn作任何指派,都使得A(P1,P2, Pn) 为真(假),则称之为重言式(矛盾式), 也称之为永真式 (永假式)。重言式的证明方法证明方法: 方法1:列真值表。 方法2:公式的等价变换,化简成“T”。 方法3:

8、用公式的主析取范式。1.2 1.2 命题公式及符号化命题公式及符号化例如,证明 (P(PQ)Q 为重言式。 P Q PQ P(PQ) (P(PQ)QF F T F TF T T F TT F F F T T T T T T1.3 1.3 等值演算(定义)等值演算(定义) 定义:定义:A、B 是含有命题变元 P1,P2, Pn 的命题公式,如不论对 P1, P2 , , Pn 作任何指派,都使得 A 和 B 真值相同,则称之为 A与B 等值,记作AB。 例如:PQ P Q Q P 定义:定义:根据已知等值式,推演出另一些等值式的过程称为 等值演算等值演算。1.3 1.3 等值演算(重要的等值公式

9、等值演算(重要的等值公式1 1) 双重否定律,对合律 P P 幂等律 PP P PP P 结合律 P(QR) (PQ)R P(QR) (PQ)R 交换律 PQQP PQQP 分配律 P(QR)(PQ)(PR) P(QR)(PQ)(PR) 吸收律 P(PQ)P P(PQ)P1.3 1.3 等值演算(重要的等值公式等值演算(重要的等值公式2 2)德-摩根定律 (PQ) PQ (PQ) PQ 同一律 P0 P P1 P 零律 P1 1 P0 0 互补律 PP 1 PP 0 PQ PQ PQQP PQ (PQ)(QP) 等价等值式 PQ (PQ)(PQ) PQ (PQ) (PQ ) 1.3 1.3 等

10、值演算(和集合公式关系)等值演算(和集合公式关系) 对合律 AA A表示A的绝对补集 幂等律 AAA AAA 结合律 A(BC)(AB)C A(BC)(AB)C交换律 ABBA ABBA分配律 A(BC)(AB)(AC) A(BC)(AB)(AC)1.3 1.3 等值演算(和集合公式关系)等值演算(和集合公式关系) 吸收律 A(AB)A A(AB)A 德-摩根定律 (AB)AB (AB)AB 同一律 AA AEA E表示全集 零律 AEE A 否定律 AAE AA1.3 1.3 等值演算(判断等值方法)等值演算(判断等值方法) 方法方法1 1:用列真值表。 方法方法2 2:用公式的等价变换。(

11、即置换定律) 置换定律: A是一个命题公式,X是A中的一部分且也是合式公式,如果XY,用Y代替A中的X得到公式B,则AB。 应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换。1.3 1.3 等值演算(等值判断例)等值演算(等值判断例)例. 求证 (PQ)(PQ) P 证明: (PQ)(PQ) (PQ)(PQ) (蕴涵等值式) (PQ)(PQ) (摩根定律) (PQ)(PQ) (对合律) P(QQ) (分配律) PT (互补律) P (同一律)1.3 1.3 等值演算(等值化简例)等值演算(等值化简例)例.化简 (PQ)(P(PQ) 解 原公式 (PQ)(PP)Q) (蕴涵等值 结合

12、) (PQ)(PQ) (对合律 幂等律) (PQ)(QP) (交换律) (PQ)Q)P (结合律) QP (吸收律)1.3 1.3 等值演算(性质)等值演算(性质) 1). 自反性:任何命题公式A,有AA。 2). 对称性:若 AB,则BA 3). 传递性:若 AB 且 BC,则 AC 4). 如果A(P1,P2,Pn) B(P1,P2,Pn),则A(P1, P2, Pn) B(P1, P2, Pn) 1.4 1.4 范式(定义,合取式,析取式)范式(定义,合取式,析取式) 范式就是命题公式形式的规范形式。这里约定在范式中只含有联结词 、 和 。 合取式:合取式:是用“”联结命题变元命题变元

13、或 变元的否变元的否定定 构成的式子。 析取式:析取式:是用“”联结 命题变元命题变元 或 变元的变元的否定否定 构成的式子。1.4 1.4 范式(定义,合取范式,析取范式)范式(定义,合取范式,析取范式)合取范式:合取范式:公式 A 如果写成如下形式: A1 A2 . An (n1) ,每个Ai (i=1,2,n)都是是析取式 ,称之为 A 的合取范式合取范式。析取范式:析取范式:公式 A 如果写成如下形式: A1 A2 . An (n1) ,每个Ai (i=1,2,n)都是是合取式 ,称之为 A 的析取范式析取范式。1.4 1.4 范式(范式(求求 合取范式,析取范式)合取范式,析取范式)

14、1 1、先用相应的公式去掉 和 。2 2、用 对偶式性质对偶式性质 或 摩根定律摩根定律 将 后移到命题变元前。3 3、用分配律分配律、幂等律幂等律 等公式进行整理。1.5 1.5 推理演算推理演算推理推理就是根据一个或几个已知的判断得出一个新的判断的思维过程。称这些已知的判断为前提。得到的新的判断为前提的有效结论。实际上,推理的过程就是证明重言蕴含式 的过程,即令 H1,H2,Hn 是已知的命题公式(前提),若有 H1 H2 . Hn C则称C是H1,H2,Hn的有效结论,简称结论。1.X 1.X 小结小结命命 题题原子命题原子命题复合命题复合命题联结词联结词命题公式命题公式永真式永真式永真

15、蕴涵式永真蕴涵式等价公式等价公式范式范式命题逻辑推理命题逻辑推理直接推理直接推理间接推理间接推理条件论证条件论证反证法反证法析取析取合取合取主析取主析取主合取主合取第2章 一阶逻辑这章是以“谓词”为中心,主要讨论: 1、命题中的谓词、量词 2、谓词公式及翻译、等价式 3、谓词推理演算2.1 2.1 谓词概念(个体)谓词概念(个体) 定义:定义:能够独立存在的事物,称之为个体,也称之为客体。它可以是具体的,也可以是抽象的事物。通常用小写英文字母a、b、c、.表示。例如,小张、小李、8、a、沈阳、社会主义等等都是个体个体。 定义:定义:用小写英文字母x、y、z.表示任何个体,则称这些字母为个体变项

16、个体变项(客体变元)。 注意:注意:个体变项本身不是个体。2.1 2.1 谓词概念(谓词)谓词概念(谓词) 定义:定义:一个大写英文字母后边有括号,括号内是若干个个体变项个体变项,用以表示客体的属性或者客体之间的关系,称之为 谓词谓词。如果括号内有n个个体变项个体变项,称该谓词为 n n元谓词元谓词。 例如: S(x): S(x):表示表示x x是大学生。是大学生。 一元谓词一元谓词 G(x,y) G(x,y):表示:表示 xy xy。 二元谓词二元谓词 B(x,y,z) B(x,y,z):表示:表示x x在在y y与与z z之间。之间。 三元谓词三元谓词2.1 2.1 谓词概念(谓词理解)谓

17、词概念(谓词理解) 谓词本身并不是不是命题,只有谓词的括号内填入足够的客体,才变成命题。例如 a表示小张,b表示小李,则 S(a) 表示小张是大学生。S(b)表示小李是大学生。 (7,3)表示:。 如果c表示锦州,d表示沈阳,e表示山海关, B(c,d,e)表示:锦州在沈阳与山海关之间。 这时 S(a)S(a)、S(b)S(b)、G(7,3)G(7,3)、B(c,d,e) B(c,d,e) 才是命题。才是命题。2.1 2.1 谓词概念(命题函数)谓词概念(命题函数) 定义:定义:n元谓词P(x1,x2,xn)称之为简单命题函数。规定:当命题函数P(x1,x2,xn)中 n=0 时,即0元谓词,

18、表示不含有个体变项的谓词,它本身就是一个命题变元。 定义:定义:将若干个简单命题函数简单命题函数用逻辑联结词联结起来,构成的表达式,称之为复合命题函数。简单命题函数与复合命题函数统称为命题函数命题函数。2.1 2.1 谓词概念(命题函数例)谓词概念(命题函数例) 例如,给定简单命题函数: A(x):x 身体好, B(x):x 学习好, C(x):x 工作好, 复合命题函数 A(x) ( B(x) C(x) ) 表示:如果 x 身体不好,则 x 的学习与工作都不好。2.1 2.1 谓词概念(量词)谓词概念(量词) 例如在“有些人是大学生”,“所有事物都是发展变化的。”中,“ “有些有些”,“”,

19、“所有的所有的” ”,就是对客体量化的词。 定义:定义:在命题中表示对客体数量化的词,称之为量词量词。 (1). (1). 存在量词:存在量词:记作记作 ,表示,表示“ “至少一个至少一个” ”、“ “一些一些” ”、“ “某些某些” ”、“ “有些有些” ”等。等。 (2). (2). 全称量词:全称量词:记作记作 ,表示,表示“ “任何一个任何一个” ”、“ “每个每个” ”、“ “一切一切” ”、“ “所有的所有的” ”、“凡是凡是”、“任任意的意的”等。等。2.1 2.1 谓词概念(量词解析)谓词概念(量词解析) 量词后边要有一个个体变项,用以指明对哪个个体变项量化,可称之为指导变项。

20、 例如, x (读作“任意 x”), x (读作“存在 x”),其中的 x 就是量词后的指导变项。 例例. .所有的自然数都是整数。 设 N(x):x是自然数。I(x):x是整数。 此命题可以写成 x(N(x)I(x)2.1 2.1 谓词概念(量词解析)谓词概念(量词解析)例例. .有些自然数是偶数。 设 N(x):x是自然数, E(x):x是偶数。 此命题可以写成 x(N(x)E(x) 例例 3. 3.每个人都有一个生母。 设 P(x): x是个人 M(x,y): y是x的生母。 此命题可以写成 x(P(x) y(P(y)M(x,y)2.2 2.2 谓词公式和符号化(定义)谓词公式和符号化(

21、定义) 定义:定义:称 n元谓词 P(x1,x2,.,xn) 为 原子谓词原子谓词公式公式。 谓词合式公式谓词合式公式 (WFF,Well Formed Formulas)递归定义如教程 P23 页定义2-6。 谓词合式公式谓词合式公式也叫也叫谓词公式谓词公式,简称,简称公式公式。 注意:为了方便,最外层括号可省略,但若注意:为了方便,最外层括号可省略,但若量词后边有括号,则括号不能省。在谓词公式量词后边有括号,则括号不能省。在谓词公式中,量词作用范围称为量词的作用域(辖域)。中,量词作用范围称为量词的作用域(辖域)。 2.2 2.2 谓词公式和符号化(规则)谓词公式和符号化(规则) 如果量词

22、后边只是一个原子谓词公式只是一个原子谓词公式时时,该量词的辖域就是此原子谓词公式。 如果量词后边是括号括号,则此括号所表示的区域就是该量词的辖域。 如果多个量词紧挨着出现,则后边的量词及后边的量词及其辖域其辖域 就是 前边量词的辖域前边量词的辖域。 2.2 2.2 谓词公式和符号化(例题)谓词公式和符号化(例题) 已知 P(x):xP(x):x是素数是素数,E(x):xE(x):x是偶数是偶数,O(x):xO(x):x是奇是奇数数,N(x,y):xN(x,y):x可以整除可以整除y y,将下列各式翻译成自然语言。( x)(E(x)( y)(N(y,x)E(y)( x)(P(x)( y)(O(y

23、)N(y,x)( x)(O(x)( y)(E(y)N(y,x) 2.1 2.1 谓词公式符号化(关于变项)谓词公式符号化(关于变项)定义:定义:在谓词公式中的个体变项可以分成两种:受到量词约束的受到量词约束的,不受量词约束的不受量词约束的。例如: x(F(x,y)x(F(x,y) yP(y) Q(z) yP(y) Q(z) xA(x)xA(x) ,思考那些个体变项受约束,那些不受。定义:定义:如果个体变项 x 在 x 或者 x 的辖域内,则 x 在此辖域内约束出现,并称 x 在此辖域内是 约束变项约束变项。否则 x 是自由出现,并称 x是 自自由变项由变项。2.1 2.1 谓词公式符号化(关于

24、变项)谓词公式符号化(关于变项)对于约束变项和自由变项:对于约束变项和自由变项:(1).对约束变项用什么符号表示无关紧要。对约束变项用什么符号表示无关紧要。即 xA(x)xA(x)与 yA(y)yA(y)是一样的。类似于积分与积分变项无关,即积分f(x)dxf(x)dx与f(y)dyf(y)dy 相同。(2).谓词公式如无自由变项,就表示一个命题。谓词公式如无自由变项,就表示一个命题。例如 A(x) A(x) 表示 x 是大学生。 xA(x) xA(x) 或者 xA(x) xA(x) 就命题,分别表示“有些人是大学生”和“所有人都是大学生”。2.1 2.1 谓词公式符号化(关于论域)谓词公式符

25、号化(关于论域)在谓词演算中,命题的符号化比较复杂,命题命题的符号表达式与论域有关系。的符号表达式与论域有关系。例如:每个自然数都是整数每个自然数都是整数。如论域是自然数集合N,令 I(x)I(x):x x是整数是整数,命题为 xI(x)xI(x)。 如果论域扩大为全总个体域时,上述表达式表示“所有客体都是整数”,显然是假命题。因此需要添加谓词 N(x)N(x):x x是自然数是自然数,命题的符号表达式为: x(N(x)I(x)x(N(x)I(x)2.1 2.1 谓词公式符号化(关于论域)谓词公式符号化(关于论域)再例如:有些大学生吸烟有些大学生吸烟。如果论域是大学生集合 S,令 A(x)A(

26、x):x x吸烟吸烟,命题的符号表达式为 xA(x)xA(x)。如果论域扩大为全总个体域时,上述表达式xA(x)表示“有些客体吸烟”,就不是表示此命题了,故需要添加谓词 S(x)S(x):x x是大学生是大学生,用于表明x的特性,命题的符号表达式为: x(S(x)A(x)x(S(x)A(x)2.1 2.1 谓词公式符号化(关于论域)谓词公式符号化(关于论域)可见命题的符号表达式与论域有关。当论域扩大时,需要添加用来表示客体特性的谓词,称此谓词为特性谓词特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。如上面两个例子中的“所有自然数自然数”、“有些大学生大学生”。如果如果前边是全称量词,特

27、性谓词后边是蕴含联结词“”;如果如果前边是存在量词,特性谓词后边是合取联结词“”。2.2 2.2 谓词公式和符号化(例题谓词公式和符号化(例题B B)1. .所有大学生都喜欢一些歌星。所有大学生都喜欢一些歌星。令令S(x)S(x):x x是大学生,是大学生,X(x)X(x):x x是歌星,是歌星,L(x,y)L(x,y):x x喜欢喜欢y y。 表达式为:表达式为: x(S(x)x(S(x) y(X(y)L(x,y) y(X(y)L(x,y) 2.2.没有不犯错误的人。没有不犯错误的人。此话就是此话就是“ “没有人不犯错没有人不犯错误误” ”,“ “没有没有” ”就是就是“ “不存在不存在”

28、”之意。之意。令令P(x)P(x):x x是人,是人,F(x)F(x):x x犯错误,表达式为:犯错误,表达式为: x(P(x)x(P(x)F(x) F(x) 或者或者 x(P(x)F(x)x(P(x)F(x)2.2 2.2 谓词公式和符号化(例题谓词公式和符号化(例题B B)3.3.如果一个人只是说谎话,那么他所说的每句如果一个人只是说谎话,那么他所说的每句话没有一句是可以相信的。话没有一句是可以相信的。 令令A(x)A(x):x x是人,是人,B(x,y)B(x,y):y y是是x x说的话,说的话, C(x):x C(x):x是谎话,是谎话,D(x)D(x):x x是可以相信的是可以相信

29、的 命题的表达式为命题的表达式为: : x(A(x)(x(A(x)( y(B(x,y)C(y)y(B(x,y)C(y) z(B(x,z)D(z)z(B(x,z)D(z)2.3 2.3 等价式与前束范式(引)等价式与前束范式(引)在命题逻辑中,是通过对公式的命题变元赋值公式的命题变元赋值来讨论永真式、永真蕴含式及等价公式的。在谓词演算中,也要讨论一些重要的谓词公式。但是由于谓词公式中可能有 命题变元、个体变命题变元、个体变项项。对命题变元赋值比较容易,因为只有两个值可赋。而对个体变项作指派却不那么简单,因为论域中的个体可能有无限个。另外谓词公式的真值还与论域有关。2.3 2.3 等价式(定义等价

30、式(定义1 1)定义:定义:若将给定的谓词公式中的命题变元,用确定的命题代替,对公式中的 个体变项个体变项 用论域中的 个体个体 代替,这个过程就称之为对谓词公式作指派,或者称之为对谓词公式赋值谓词公式赋值。定义:定义:给定谓词公式 A,E 是其论域,如果不论对公式公式 A A 作任何赋值作任何赋值,都使得 A 的真值为真,则称公式 A 在论域 E上 是永真式。2.3 2.3 等价式(定义等价式(定义2 2)定义:定义:给定谓词公式 A、B,E是它们的论域,如果不论对公式A、B作任何赋值,都使得 A 与B 的真值相同 (或者说AB是永真式),则称公式 A 与 B 在论域 E上是等值的。记作AB

31、。例:例:I(x):x是整数,N(x):x是自然数,设论域E是自然数集合,公式 I(x) 与 N(x) 在E上是等值的。而公式 N(x)I(x) N(x)I(x) 与 N(x)I(x) N(x)I(x) 就是与论域无关的等值的公式,即即 N(x)I(x) N(x)I(x) N(x)I(x)N(x)I(x)。2.3 2.3 等价式(公式等价式(公式0 0)公式公式 0 0 :可把公式看成一个命题变元。在命题演算的永真式中,将同一个命题变元,用同一个谓词公式代替,所得到也是永真式。即可将命题演算的等价公式推广到谓词演算中使用。例如:例如: x(A(x)B(x)x(A(x)B(x)x(A(x)B(x

32、)x(A(x)B(x)PQ PQ P PQ Q( xA(x)xA(x) xB(x)xB(x)xA(x)xA(x) xB(x)xB(x) 摩根定律摩根定律2.3 2.3 等价式(公式等价式(公式1 1)公式公式 1 1 :一般地,设论域为a1,a2,.,an,则 1. xA(x) A(a1)A(a2).A(an) 2. xB(x) B(a1)B(a2).B(an)有限个体域中量词消去等值式有限个体域中量词消去等值式例如:令例如:令A(x)A(x):x x是整数,论域是是整数,论域是1,2,3,4,51,2,3,4,5,谓词公式谓词公式 xA(x) xA(x) 表示论域内所有的客体都是整表示论域内

33、所有的客体都是整数,显然公式数,显然公式 xA(x)xA(x)真值为真,因为真值为真,因为A(1)A(1)、A(2)A(2)、A(3)A(3)、A(4)A(4)、A(5)A(5)都为真,于是有:都为真,于是有: xA(x)xA(x) A(1)A(2)A(3)A(4)A(5)A(1)A(2)A(3)A(4)A(5)2.3 2.3 等价式(公式等价式(公式2 2)公式公式 2 2 :1. 1. xA(x)xA(x) x x A(x)A(x)2. 2. xA(x)xA(x) x x A(x)A(x)量词否定等值式量词否定等值式证明:证明:设论域为设论域为aa1 1,a,a2 2,.,a,.,an n

34、 ,则,则 xA(x)xA(x) (A(a(A(a1 1)A(a)A(a2 2).A(a).A(an n) A(aA(a1 1) A(aA(a2 2).). A(aA(an n) )x x A(x)A(x) 类似可以证明另一个公式。类似可以证明另一个公式。2.3 2.3 等价式(公式等价式(公式3 3)公式公式 3 3 :如果是个不含客体变元如果是个不含客体变元x x的谓词公式,的谓词公式,且不在且不在 x x 和和 x x 的辖域内,可以将放入的辖域内,可以将放入 x x和和 x x 的辖域内。即得如下公式:的辖域内。即得如下公式:量词辖域收缩扩展等值式量词辖域收缩扩展等值式 1.1. xA

35、(x)BxA(x)Bx(A(x)B)x(A(x)B) 2.2. xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 3.3. xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 4.4. xA(x)BxA(x)Bx(x(x)B) (x)B) 2.3 2.3 等价式(公式等价式(公式4 4)公式公式 4 4 : x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x)xB(x) x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x)xB(x)量词分配等值式量词分配等值式证明证明:设论域为:设论域为aa1 1,a,a2 2,.,a,.,an n , x

36、(A(x)B(x)x(A(x)B(x)(A(a(A(a1 1)B(a)B(a1 1)(A(a)(A(a2 2)B)B(a(a2 2) (A(a(A(an n)B(a)B(an n)(A(a(A(a1 1)A(a)A(a2 2).A(a).A(an n) ) (B(a(B(a1 1)B(a)B(a2 2).B(a).B(an n)xA(x)xA(x) xB(x)xB(x)2.3 2.3 等价式(公式等价式(公式5 5)公式公式 5 5 :在:在 A(x,y) A(x,y) 前有两个量词,如果两个量词是前有两个量词,如果两个量词是相同的,它们的次序是无关紧要,但是如果是不相同的,它们的次序是无关紧

37、要,但是如果是不同的,它们的次序就不可以随便交换。同的,它们的次序就不可以随便交换。多量词等值式多量词等值式例如例如:设:设A(x,y)A(x,y)表示表示“ “x+y=0 x+y=0” ”, ,论域:实数集合,论域:实数集合, x x yA(x,y)yA(x,y)表示表示“ “对于任意给定的一个实数对于任意给定的一个实数x,x,可可以找到一个以找到一个y,y,使得使得x+y=0 x+y=0” ”, ,这是一个为这是一个为“ “真真” ”的命题。的命题。而交换量词后而交换量词后 y y xA(x,y)xA(x,y) 表示表示“ “存在一个实数存在一个实数y,y,与任意给定的与任意给定的一个实数

38、一个实数x x之和都等于之和都等于0 0” ”, ,这是一个为这是一个为“ “假假” ”的命题。的命题。2.4 2.4 谓词演算推理谓词演算推理推理方法:推理方法: 直接推理、条件论证、反证法直接推理、条件论证、反证法所用公式:第所用公式:第1 1、2 2章的等值式和重言蕴含式章的等值式和重言蕴含式规则规则P P:代表引入前提代表引入前提 规则规则T T:代表得到结论代表得到结论四个规则新规则(四个规则新规则(USUS、ESES、EGEG、UGUG):):处理量处理量词时,如推理要使用不含量词的命题公式,应词时,如推理要使用不含量词的命题公式,应去掉量词,如结论有量词,还要添加量词。去掉量词,

39、如结论有量词,还要添加量词。2.4 2.4 谓词演算推理(规则谓词演算推理(规则 US US )全称指定规则全称指定规则 US (Universal Specialization) US (Universal Specialization) 形式:形式: xA(x)xA(x)A(c)A(c) ( (其中其中c c是论域内指定客体是论域内指定客体) ) 含义:如果含义:如果 xA(x)xA(x)为真,则在论域内为真,则在论域内任何指任何指定定客体客体c c,都使得,都使得A(c)A(c)为真。为真。 作用:去掉全称量词。作用:去掉全称量词。 要求:要求:c c不是不是A(x)A(x)中的符号。中

40、的符号。2.4 2.4 谓词演算推理(规则谓词演算推理(规则 ES ES )存在指定规则存在指定规则 ES (Existential Specialization) ES (Existential Specialization) 形式:形式: xA(x)xA(x)A(c)A(c) ( (其中其中c c是论域内指定客体是论域内指定客体) ) 含义:如果含义:如果 xA(x)xA(x)为真,则论域内为真,则论域内指定指定客体客体c c, 都使得都使得A(c)A(c)为真。为真。 作用:去掉存在量词。作用:去掉存在量词。 要求:要求: c c不是不是A(x)A(x)中的符号。中的符号。 用用ESES

41、指定的指定的客体客体c c不应该是不应该是在此之前在此之前用用USUS规则或者用规则或者用ESES规则所规则所指定的客体指定的客体c(c(即本次用即本次用ESES特指客体特指客体c c,不应该是以,不应该是以前特指的客体前特指的客体) )。2.4 2.4 谓词演算推理(规则谓词演算推理(规则 UGUG )全称推广规则全称推广规则 UG (Universal Generalization) UG (Universal Generalization) 形式:形式: A(c)A(c)xA(x)xA(x) ( (其中其中c c是论域内是论域内任何任何指定客体指定客体) ) 含义:如果含义:如果在论域内

42、在论域内任何指定任何指定客体客体c c都都使使 得得A(c)A(c)为真,则为真,则 xA(x)xA(x)为真。为真。 作用:添加作用:添加全称全称量词。量词。 要求:要求:x x不是不是A(c)A(c)中的符号。中的符号。 c c一定是任意一定是任意的客体,否则不可的客体,否则不可全全 称推广称推广。2.4 2.4 谓词演算推理(规则谓词演算推理(规则 EGEG )存在推广规则存在推广规则 EG (Existential Generalization) EG (Existential Generalization) 形式:形式: A(c)A(c)xA(x)xA(x) ( (其中其中c c是论

43、域内指定客体是论域内指定客体) ) 含义:如果含义:如果在论域内在论域内指定指定客体客体c c使得使得 A(c) A(c)为真,则为真,则 xA(x)xA(x)为真。为真。 作用:添加存在量词。作用:添加存在量词。 要求:要求:x x不是不是A(c)A(c)中的符号中的符号。2.4 2.4 谓词演算推理(例题谓词演算推理(例题 A A )例例A. A. 所有金属都导电。铜是金属。所有金属都导电。铜是金属。 故铜导电。故铜导电。令令 M(x):x M(x):x是金属。是金属。C(x):xC(x):x导电。导电。a:a:铜。铜。符号化为:符号化为: x(M(x)C(x),M(a)x(M(x)C(x

44、),M(a)C(a)C(a) x(M(x)C(x)x(M(x)C(x)P P M(a)C(a) US M(a)C(a) US M(a) P M(a) P C(a) T C(a) T 2.4 2.4 谓词演算推理(例题谓词演算推理(例题 B B )例例B. B. 所有自然数都是整数。有些数是自然数。所有自然数都是整数。有些数是自然数。因此有些数是整数。因此有些数是整数。令令A(x)A(x)表示表示x x是自然数,是自然数,B(x)B(x)表示表示x x是整数。是整数。 x(A(x)B(x)x(A(x)B(x), xA(x) xA(x) xB(x)xB(x) xA(x) PxA(x) P A(c)

45、 ES A(c) ES x(A(x)B(x) Px(A(x)B(x) P A(c)B(c) US A(c)B(c) US B(c) T B(c) T xB(x) EG xB(x) EG 2.4 2.4 谓词演算推理(例题谓词演算推理(例题 B B 错误解)错误解)例例B B如果按下面方法推理,是否正确?如果按下面方法推理,是否正确? x(A(x)B(x)x(A(x)B(x), xA(x) xA(x) xB(x)xB(x) x(A(x)B(x) Px(A(x)B(x) P A(c)A(c)B(c) US B(c) US xA(x) PxA(x) P A(c)A(c) ES ES B(c) T B

46、(c) T xB(x) EG xB(x) EG 2.4 2.4 谓词演算推理(注意事项)谓词演算推理(注意事项)1 1. .注意使用注意使用ESES、USUS、EGEG、UGUG的限制条件。的限制条件。2 2. .对于同一个客体变元,既有带对于同一个客体变元,既有带 也有带也有带 的前的前提,去量词时,应先去提,去量词时,应先去 后去后去 ,这样,这样才可以特才可以特指同一个客体指同一个客体 c. c.3. 3.去量词时去量词时,该量词必须是公式的最左边的量,该量词必须是公式的最左边的量词,且此量词的前边词,且此量词的前边无任何符号无任何符号,它的辖域作,它的辖域作用到公式末尾。用到公式末尾。

47、2.4 2.4 谓词演算推理(注意事项例)谓词演算推理(注意事项例)错误的:错误的: x xP(x)P(x) yQ(y) yQ(y) P P x xP(x)Q(b) P(x)Q(b) ES ESP(a)Q(b)P(a)Q(b) US US错误的:错误的: x xP(x)P(x) yQ(y)yQ(y) P PxP(x)xP(x) yQ(y) yQ(y) T T x x P(x)P(x) yQ(y) yQ(y) T T x x y(y( P(x)P(x)Q(y) Q(y) T T y(y( P(a)P(a)Q(y) Q(y) ESES P(a)P(a)Q(b)Q(b)ESES P(a) P(a)Q

48、(b) Q(b) T T2.4 2.4 谓词演算推理(注意事项)谓词演算推理(注意事项)下面的作法是错误的:下面的作法是错误的: 正确作法是:正确作法是: x xP(x) P P(x) P x xP(x) P P(x) P P(c) USP(c) US x x P(x) T(1) P(x) T(1) P(c) ES (2)P(c) ES (2)另:另:令令P(x,y):yP(x,y):y是是x x的的生母,生母, 是假命题是假命题. . x x y yP(x,y) P P(x,y) P x x y yP(x,y) PP(x,y) P x xP(x,c) ESP(x,c) ES y yP(a,y

49、) US P(a,y) US 2.4 2.4 谓词演算推理(注意事项)谓词演算推理(注意事项)4. 4. 添加量词时添加量词时,也要加在公式的最左边,也要加在公式的最左边,( (即新即新加的量词前也无任何符号加的量词前也无任何符号!) )且其辖域作用到且其辖域作用到公式的末尾。公式的末尾。 P(a)P(a)Q(b) Q(b) x xP(x)P(x)Q(b) UG Q(b) UG x xP(x)P(x) y yQ(y) EG Q(y) EG x(x(P(x)P(x)Q(b) UG Q(b) UG y y x x(P(x)(P(x)Q(y) EG Q(y) EG 2.4 2.4 谓词演算推理(课堂

50、练习谓词演算推理(课堂练习 A A)证明下面推理的有效性:证明下面推理的有效性:“ “鸟都会飞。猴子都不鸟都会飞。猴子都不会飞。所以,猴子都不是鸟。会飞。所以,猴子都不是鸟。” ”设设 B(x):x B(x):x是鸟;是鸟;F(x):xF(x):x会飞;会飞;M(x):xM(x):x是猴子。是猴子。即证明:即证明: x(B(x)F(x),x(B(x)F(x), x(M(x)x(M(x) F(x)F(x)x(M(x)x(M(x) B(x)B(x) 2.4 2.4 谓词演算推理(课堂练习谓词演算推理(课堂练习 A A)证明:证明: x(B(x)F(x),x(B(x)F(x), x(M(x)x(M(

51、x) F(x)F(x)x(M(x)x(M(x) B(x)B(x) 证明:证明: x(B(x)F(x) x(B(x)F(x) B(a)F(a) B(a)F(a) x(M(x)x(M(x) F(x) F(x) M(a) M(a) F(a) F(a) F(a)F(a) B(a) B(a) M(a) M(a) B(a) B(a) x(M(x)x(M(x) B(x)B(x) 2.4 2.4 谓词演算推理(课堂练习谓词演算推理(课堂练习 B B )不认识错误的人,也不能改正错误。有些诚实不认识错误的人,也不能改正错误。有些诚实的人改正了错误。所以有些诚实的人是认识了的人改正了错误。所以有些诚实的人是认识了

52、错误的人。错误的人。设设A(x):xA(x):x是认识错误的人。是认识错误的人。 B(x):x B(x):x改正了错误。改正了错误。C(x):xC(x):x是诚实的人。是诚实的人。即证明:即证明: x(x( A(x)A(x) B(x)B(x), x(C(x)B(x) x(C(x)B(x) x(C(x)A(x)x(C(x)A(x)2.4 2.4 谓词演算推理(课堂练习谓词演算推理(课堂练习 B B)证明:证明: x(x( A(x)A(x) B(x)B(x), x(C(x)B(x),x(C(x)B(x), x(C(x)A(x)x(C(x)A(x) x(C(x)B(x) x(C(x)B(x) C(c

53、)B(c) C(c)B(c) C(c) C(c) B(c) B(c) x(x( A(x)A(x) B(x) B(x) A(c)A(c) B(c) B(c) A(c) A(c) A(c) A(c) C(c)A(c) C(c)A(c) x(C(x)A(x) x(C(x)A(x) 2.4 2.4 谓词演算推理(课堂练习谓词演算推理(课堂练习 B B)证明:证明: x(x( A(x)A(x) B(x)B(x), x(C(x)B(x),x(C(x)B(x), x(C(x)A(x)x(C(x)A(x) x(C(x)B(x) x(C(x)B(x) P P C(c)B(c) C(c)B(c) ESES C(c

54、) C(c) T T B(c) B(c) T T x(x( A(x)A(x) B(x) B(x) P P A(c)A(c) B(c) B(c) USUS A(c) A(c) T T ,假言易位,假言易位 A(c) A(c) T T C(c)A(c) C(c)A(c) T T x(C(x)A(x) x(C(x)A(x) EG EG 2.4 2.4 谓词演算推理(课堂练习谓词演算推理(课堂练习 C C)一些病人喜欢所有医生。任何病人都不喜欢一些病人喜欢所有医生。任何病人都不喜欢庸医。所以没有医生是庸医。庸医。所以没有医生是庸医。设设: P(x):x: P(x):x是病人是病人, D(x):x, D

55、(x):x是医生是医生, , Q(x):x Q(x):x是庸医是庸医, L(x,y): x, L(x,y): x喜欢喜欢y. y.即证明:即证明: x(P(x)x(P(x) y y(D(y)L(x,y)(D(y)L(x,y), x(P(x)x(P(x) y(y(Q(y)Q(y) L(x,y) L(x,y) y(D(y)Q(y)y(D(y)Q(y)2.4 2.4 谓词演算推理(课堂练习谓词演算推理(课堂练习 C C) x(P(x)x(P(x) y y(D(y)L(x,y)(D(y)L(x,y), x(P(x)x(P(x) y(y(Q(y)Q(y) L(x,y) L(x,y) y(D(y)Q(y)

56、y(D(y)Q(y) x(P(x)x(P(x) y y(D(y)L(x,y) (D(y)L(x,y) P(a) P(a) y y(D(y)L(a,y) (D(y)L(a,y) P(a) P(a) y y(D(y)L(a,y) (D(y)L(a,y) x(P(x)x(P(x) y(y(Q(y)Q(y) L(x,y) L(x,y) P(a) P(a) y(y(Q(y)Q(y) L(a,yL(a,y2.4 2.4 谓词演算推理(课堂练习谓词演算推理(课堂练习 C C) x(P(x)x(P(x) y y(D(y)L(x,y)(D(y)L(x,y), x(P(x)x(P(x) y(y(Q(y)Q(y)

57、L(x,y) L(x,y) y(D(y)Q(y)y(D(y)Q(y) y(y(Q(y)Q(y) L(a,y) L(a,y) D(b)L(a,b) D(b)L(a,b) Q(b) Q(b) L(a,b) L(a,b) L(a,b) L(a,b) Q(b) Q(b) D(b) D(b) Q(b) Q(b) D(b)D(b) Q(b) Q(b) ( (D(b)Q(b) D(b)Q(b) y y ( (D(y)Q(y) D(y)Q(y) y y( (D(y)Q(y) D(y)Q(y) 第2部分 集合论第3章 集合第4章 关系第 3 章 集合以“集合”基本概念为基础,讨论: 1、集合相关概念 2、集合相

58、关运算、定律 3、幂集、笛卡尔积等概念性质3.1 3.1 集合概述(概念)集合概述(概念)集合集合定义:定义:是由确定的对象(客体)构成的集体。用大写的英文字母表示。这里所谓“确定”是指:论域内任何客体,要么属于这个集合,要么不属于这个集合,是唯一确定的。元素元素定义:定义:集合中的对象,称之为元素。 定义:定义:表示元素与集合的属于关系。例如:N表示自然数集合,2N,而4.5不属于N写成 (4.5N),或写成 4.5 N。3.1 3.1 集合概述(概念)集合概述(概念)这里对有限集合与无限集合只给出朴素的定义,以后再给出严格的形式定义。有限集合有限集合定义:定义:元素是有限个的集合。 如果A

59、是有限集合,用 |A|表示A中元素个数。例如,A=1,2,3,则 |A|=3。无限集合无限集合定义:定义:元素是无限个的集合。元素是无限个的集合。对无限集合的大小的讨论,后续再进行。3.1 3.1 集合概述(表示方法)集合概述(表示方法)列举法:列举法:将集合中的元素一一列出,写在大括号内。例如,N=1,2,3,4, A=a,b,c,d描述法:描述法:用句子(或谓词公式或谓词公式)描述元素的属性。例如,B=x| x是偶数 C=x|x是实数且2x5一般地,A=x|P(x),其中,P(x)是描述元素 x 的特性的谓词公式,如果论域内客体 a 使得P(a)为真,则aA,否则 aA。3.1 3.1 集

60、合概述(表示方法)集合概述(表示方法) 集合中元素间次序无关紧要,但必须是可区集合中元素间次序无关紧要,但必须是可区分的。如分的。如A=a,b,c,aA=a,b,c,a,B=c,b,a,B=c,b,a,,A A等同等同B B。 对集合中的元素无任何限制,例如令对集合中的元素无任何限制,例如令 A= A=人,石头,人,石头,1 1,, B=, B=, 集合中的元素也可以是集合,例如:集合中的元素也可以是集合,例如:a a:王书记:王书记 a a:团支部:团支部( (只有一个书记只有一个书记) ) a a:分团委:分团委( (只有一个团支部只有一个团支部) ) a a:团委:团委 ( (只有一个分

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论