《离散数学-耿素云PPT(第5版)2.1-2》由会员分享,可在线阅读,更多相关《离散数学-耿素云PPT(第5版)2.1-2(27页珍藏版)》请在金锄头文库上搜索。
1、1,第2章 一阶逻辑,2.1 一阶逻辑基本概念 2.2 一阶逻辑合式公式及解释 2.3 一阶逻辑等值式与前束范式,2,2.1 一阶逻辑基本概念,个体词 谓词 量词 一阶逻辑中命题符号化,命题逻辑的局限性,苏格拉底三段论: 凡是人都要死的. 苏格拉底是人. 所以苏格拉底是要死的. 在命题逻辑中,只能用p、q、r表示以上3个命题, 上述推理可表成 (pq)r 这不是重言式,3,4,基本概念个体词、谓词、量词,个体词(个体): 所研究对象中可以独立存在的具 体或抽象的客体 个体常项:具体的事物,用a, b, c表示 个体变项:抽象的事物,用x, y, z表示 个体域: 个体变项的取值范围 有限个体域
2、,如a, b, c, 1, 2 无限个体域,如N, Z, R, 全总个体域: 宇宙间一切事物组成,5,基本概念 (续),谓词: 表示个体词性质或相互之间关系的词 谓词常项:F(a):a是人 谓词变项:F(x):x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n2): 表示事物之间的关系 如 L(x,y):x与y有关系L,L(x,y):xy, 0元谓词: 不含个体变项的谓词, 即命题常项或命 题变项,6,基本概念(续),量词: 表示数量的词 全称量词: 表示任意的, 所有的, 一切的等 如 x 表示对个体域中所有的x 存在量词: 表示存在, 有的, 至少有一个等 如 x 表示在个
3、体域中存在x,7,一阶逻辑中命题符号化,例 用0元谓词将命题符号化 要求:先将它们在命题逻辑中符号化,再在一阶 逻辑中符号化 (1) 墨西哥位于南美洲,在命题逻辑中, 设 p: 墨西哥位于南美洲 符号化为 p,在一阶逻辑中, 设a:墨西哥,F(x):x位于南美洲, 符号化为F(a),8,例(续),(2) 是无理数仅当 是有理数,在命题逻辑中, 设 p: 是无理数,q: 是有理数. 符号化为 p q,在一阶逻辑中, 设F(x): x是无理数, G(x): x是有理数 符号化为,在命题逻辑中, 设 p:23,q:34. 符号化为 pq,在一阶逻辑中, 设 F(x,y):xy,G(x,y):xy,
4、符号化为 F(2,3)G(3,4),(3) 如果23,则34,9,一阶逻辑中命题符号化(续),例 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解:,(a) (1) 设G(x): x爱美, 符号化为 x G(x) (2) 设G(x): x用左手写字, 符号化为 x G(x),(b) 设F(x): x为人,G(x): 同(a)中 (1) x (F(x)G(x) (2) x (F(x)G(x),这是两个基本公式, 注意它们的使用,10,一阶逻辑中命题符号化(续),例 在一阶逻辑中将下面命题符号化 (1) 正数都大于
5、负数 (2) 有的无理数大于有的有理数 解,注意: 题目中没给个体域, 使用全总个体域,(1) 令F(x): x为正数, G(y): y为负数, L(x,y): xy x(F(x)y(G(y)L(x,y) 或 xy(F(x)G(y)L(x,y) 两者等值,(2) 令F(x): x是无理数, G(y): y是有理数, L(x,y):xy x(F(x)y(G(y)L(x,y) 或 xy(F(x)G(y)L(x,y) 两者等值,11,一阶逻辑中命题符号化(续),几点注意: 1元谓词与多元谓词的区分 无特别要求,应使用全总个体域,引入特性谓词 量词顺序一般不能随便颠倒 两个基本形式x (F(x)G(x
6、)和 x (F(x)G(x) 的使用 否定的表示,如 “没有不呼吸的人”等同于“所有的人都呼吸” “不是所有的人都喜欢吃糖”等同于“存在不喜欢吃糖的人”,12,2.2 一阶逻辑公式及解释,合式公式(简称公式) 个体变项的自由出现和约束出现 解释与赋值 公式分类 永真式,矛盾式, 可满足式,13,字母表,定义 字母表包含下述符号: (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, ,
7、Fi, Gi, Hi, , i 1 (5) 量词符号:, (6) 联结词符号:, , , , (7) 括号与逗号:(, ), ,,14,项,定义 项的定义如下: (1) 个体常项和个体变项是项. (2) 若(x1, x2, , xn)是任意的n元函数,t1,t2,tn 是任意的n个项,则(t1, t2, , tn) 是项. (3) 所有的项都是有限次使用 (1), (2) 得到的. 个体常项、变项是项,由它们构成的n元函数和复 合函数还是项,15,原子公式,定义 设R(x1, x2, , xn)是任意的n元谓词,t1,t2, tn 是任意的n个项,则称R(t1, t2, , tn)是原子公式.
8、 原子公式是由项组成的n元谓词. 例如,F(x,y), F(f(x1,x2),g(x3,x4)等均为原子公式,16,合式公式,定义 合式公式(简称公式)定义如下: (1) 原子公式是合式公式. (2) 若A是合式公式,则 (A)也是合式公式 (3) 若A, B是合式公式,则(AB), (AB), (AB), (AB)也是合式公式 (4) 若A是合式公式,则xA, xA也是合式公式 (5) 只有有限次地应用(1)(4)形成的符号串是合 式公式. 如 x0, x (F(x)G(x), xy(x+y=1),17,个体变项的自由出现与约束出现,定义 在公式xA和xA中,称x为指导变元,A为相 应量词的
9、辖域. 在x和x的辖域中,x的所有出现都 称为约束出现,A中不是约束出现的其他变项均称 为是自由出现. 例如, 在公式 x(F(x,y)G(x,z) 中, A=(F(x,y)G(x,z)为x的辖域, x为指导变元, A中x的两次出现均为约束出现, y与z均为自由出现. 闭式: 不含自由出现的个体变项的公式.,18,公式的解释与分类,给定闭式 A=x(F(x)G(x) 取个体域N, F(x): x2, G(x): x1 代入得A=x(x2x1) 真命题 给定非闭式 B=xF(x,y) 取个体域N, F(x,y): xy 代入得B=x(xy) 不是命题 令y=1, B=x(x1) 假命题,19,解
10、释和赋值,定义 解释I由下面4部分组成: (a)非空个体域DI (b)对每一个命题常项a 指定一个 DI (c)对每一个函数符号f指定一个DI上的函数 (d)对每一个谓词符号F指定一个DI上的谓词 赋值:对每一个命题变项x指定一个值(x)DI 公式A在解释I和赋值下的含义: 取个体域DI, 并将公式中出现的a、f、F 分别解释成 、 、 , 把自由出现的x换成(x)后所得到的命题. 在给定的解释和赋值下, 任何公式都成为命题.,20,实例,例 给定解释I 如下: (a) 个体域 D=N (b) (c) (d) 谓词 以及赋值:(x)=0, (y)=1, (z)=2. 说明下列公式在 I 与下的
11、涵义,并讨论真值 (1) xF(g(x,a),y),x(2x=1) 假命题,21,例(续),(2) xF(f(x,a),y)yF(x,f(y,a),x(x+2=1)y(0=y+2) 真命题,xyz (x+y=z) 真命题,(3) xF(f(x,y),g(x,z),x(x+1=2x) 真命题,(5) xyzF(f(y,z),x),xyz (y+z=x) 假命题,(4) xyzF(f(x,y),z),闭式只需要解释, 如(4),(5),22,公式的分类,永真式(逻辑有效式):在任何解释和赋值下为真命题 矛盾式(永假式):在任何解释和赋值下为假命题 可满足式:存在成真的解释和赋值 说明: 永真式为可
12、满足式,但反之不真 谓词公式的可满足性(永真性,永假性)是不可判 定的,23,代换,定义 设A0是含命题变项p1, p2, ,pn的命题公式, A1,A2,An是n个谓词公式,用Ai处处代替A0中的pi (1in) ,所得公式A称为A0的代换实例. 如 F(x)G(x), xF(x)yG(y)是pq的代换实例 定理 重言式的代换实例都是永真式,矛盾式的代 换实例都是矛盾式.,实例,例 判断下列公式的类型 (1) xF(x)xF(x);,24,设I为任意的解释,若xF(x)为假,则xF(x)xF(x)为真. 若xF(x)为真,则xF(x)也为真,所以xF(x)xF(x)也为真. 是逻辑有效式.,
13、(2) xF(x)(xyG(x,y)xF(x);,重言式p(qp) 的代换实例,是逻辑有效式.,例(续),(3) xF(x)(xF(x)yG(y);,25,重言式p(pq)的代换实例, 是逻辑有效式.,(4) (F(x,y)R(x,y)R(x,y);,矛盾式(pq)q的代换实例, 是矛盾式.,例(续),(5) xyF(x,y)xyF(x,y).,26,取解释I:个体域N, F(x,y)为x=y. 公式被解释为xy(x=y)xy(x=y),其值为假.,解释I: 个体域N, F(x,y)为xy, 得到一个新的 在I下,公式被解释为xy(xy)xy(xy),其值为真. 是非逻辑有效式的可满足式.,例(续),(6) xF(x,y),27,取解释I:个体域N, F(x,y)为xy. 赋值1:1(y)=1. 在I和1下, x(x1),真命题.,取解释I: 个体域N, F(x,y)为xy. 赋值2:2(y)=0. 在I和2下, x(x0), 假命题 是非逻辑有效式的可满足式.,