《离散数学-耿素云ppt(第5版)》由会员分享，可在线阅读，更多相关《离散数学-耿素云ppt(第5版)（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(
6、x)和 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. 说明下列公式在
11、I 与下的涵义,并讨论真值 (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)， 假命题 是非逻辑有效式的可满足式.,
