我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:双彩网 > 蕴含谓词 >

工学]第二章一阶逻辑ppt

归档日期:06-06       文本归类:蕴含谓词      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  作业 P59(1,2) 作业 P62(1a,c,e,h) P66(4,5) 作业 P71(1,2a,c,4,7) P75(1a) 作业 P79(1,2b,3a,3b) * 离散数学 * 例:求下列公式的前束合取范式 * 离散数学 * 一阶逻辑知识结构 2.1 一阶逻辑基本概念 2.2 一阶逻辑等值演算 2.3 一阶逻辑的推理理论 第四次课 第一、二次课 第三次课 * 离散数学 * 一阶逻辑推理理论知识点 推理理论的形式结构 推理规则 全称量词消去规则 全称量词引入规则 存在量词消去规则 存在量词引入规则 * 离散数学 * 推理理论的形式结构 从前提A1, A2…… Ak出发推出结论B的推理形式结构为: 若此式为永真式,则推理正确;否则,称推理不正确。 * 离散数学 * 谓词演算是命题演算的扩展 命题演算中的等价式、蕴含式、推理规则都可以用在谓词演算。 某些前提和结论受量词的限制,因而需要量词的引入和消去。 * 离散数学 * ?xA(x)∨?xB(x) ??x (A(x)∨B(x)) 量词分配的推理定律 ?x (A(x)∧B(x))??xA(x) ∧ ?xB(x); ?x(A(x)→B(x))??xA(x)→?xB(x); ?x(A(x)→B(x))? ? xA(x)→ ? xB(x); * 离散数学 * 全称指定规则 (Universal Specification) ?x P(x) ? P(c) 又称为全称量词消去规则,表示为 US。 P是谓词,而c是个体域中的任意个体。如果个体域中全部个体有P(x),那么全称指定规则有结论P(c)。 其中x是P(x)中自由出现的个体变元。 例:个体域取为偶数集合,P(X):x是整数。 ?x P(x) 成立,6是个体域中的一个个体,则必有P(6)成立。 * 离散数学 * 全称推广规则 (Universal Generalization) 该式成立的条件是: 无论P(y) 中自由出现的个体变项 y 取何值,P(y)取值应该均为真. 又称为全称量词引入规则,表示为UG P(y) ? ?x P(x) 即:如果能够证明对个体域中每一个个体都具有某性质,则个体域中的全体个体都具有此性质。 例:设个体域为人类集合。P(x)表示x是要死的。对于任意的一个人a都有P(a),必然可以得到?x P(x)。 * 离散数学 * 存在指定规则(Existential Specification) 又称为存在量词消去规则,表示为ES ?x P(x) ? P(c) 这里的c是个体域中某个确定的个体,而不是任意的。这个规则是说,如果个体域中存在具有性质P的个体,则个体域中必有某一元素具有此性质。 例:设个体域取整数集合。P(x):x是偶数。 则P(8)取值为线)取值为假。 * 离散数学 * 存在推广规则 (Existential Generalization ) 此规则表示:如果个体域中有某个个体具有性质P,则可以说个体域中存在具有性质P的个体。 又称为存在量词引入规则,表示为EG P(c) ? ?x P(x) 例:设个体域为某班全体学生,P(x):x通过了英语六级。如果王明通过了英语六级,必然可以得到结论“该班有人通过了英语六级”。 * 离散数学 * 一阶逻辑自然推理系统 F ????3. 推理规则: 定义2.3 .1 自然推理系统 F 定义如下: ??1. 字母表. 同一阶语言 的字母表 2. 合式公式. 同 合式公式的定义 * 离散数学 * (1) 前提引入规则. (2) 结论引入规则. (3) 置换规则. (4) 假言推理规则. ????(5) 附加规则. ?(6) 化简规则. (7) 拒取式规则. (8) 假言三段论规则. * 离散数学 * ????(15)EG规则. ????F 中的推理过程类似命题演算自然推理系统 P. (9) 析取三段论规则. (10)构造性二难推理规则. ??(11)合取引入规则. (12)US规则. (14)ES规则. (13)UG规则. * 离散数学 * 谓词演算中推理的一般过程: 利用US或ES规则,把前提条件中的量词消去 使用命题逻辑中的方法进行推理 推出结论后,再利用UG或EG规则把量词引入进来,得出谓词逻辑的结论 谓词逻辑中进行推理的需注意的问题: US、ES、UG、EG这4个规则仅对谓词公式的前束范式适用。 要弄清消去量词后,个体是特定的还是任意的。 如果既有全称量词的前提也有存在量词的前提,必须先指定存在量词的前提,后指定全称量词的前提。 * 离散数学 * 例:证明苏格拉底三段论。 所有的人都是要死的。苏格拉底是人,所以苏格拉底是要死的。 解:F(x):x 是人。G(x):x是要死的。a:苏格拉底 * 离散数学 * 例:在自然推理系统F中,构造下面推理的证明: 任何树都是图;每个图中奇度节点的个数是偶数。所以树中奇度节点的个数是偶数。 解:T(x): x是树;G(x): x是图; E(x):x中奇度节点的个数是偶数。 前提:?x(T(x) →G(x)), ?x(G(x) →E(x)) 结论: ?x(T(x) →E(x)), * 离散数学 * 证明: (1) ?x(T(x) →G(x)) 前提引入 (2) T(y) →G(y) (1) US (3) ?x(G(x) →E(x)) 前提引入 (4) G(y) →E(y) (3) US (5) T(y) →E(y) (2)(4)假言三段论 (6) ?x(T(x) →E(x)) (5) UG 前提:?x(T(x) →G(x)), ?x(G(x) →E(x)) 结论: ?x(T(x) →E(x)), * 离散数学 * 例 在自然推理系统F 中,构造下面推理的证明: ????任何自然数都是整数;存在着自然数. 所以存在 着整数. 个体域为实数集合R. 解:先将原子命题符号化. 结论: 前提: ????设 为自然数, 为整数. * 离散数学 * ?证明: ① ????????前提引入 ③ 前提引入 ④ ③US规则 ⑥ ⑤EG规则 ⑤ ?????????? ? ②④假言推理 ????② ????????? ?①ES规则 结论: 前提: * 离散数学 * ? 如果改变命题序列的顺序: ① ????????前提引入 ????② ?①US规则 ????????前提引入 ③ ④ ③ES规则 在②中取 , 则 为真(前件假), 于是④中 为假,这样从前件真推出了假的中间结果. c为任意一个个体 c为特定的一个个体 * 离散数学 * 例:证明 证: * 离散数学 * 例:在自然推理系统F中,构造下面推理的证明: 前提: 结论: 附加前提证明法 * 离散数学 * 归缪法 证明:?x(P(x)∨Q(x))? ?xP(x) ∨?xQ(x) 证: (1) ?(?xP(x) ∨?xQ(x)) 否定结论引入 (2) ??xP(x) ∧ ? ?xQ(x) (1)置换 (3) ??xP(x) (2) 化简 (4) ? ?xQ(x) (2) 化简 (5) ?x?P(x) (3) 置换 (6) ?P(c) (5) ES (7) ?x(P(x)∨Q(x)) 前提引入 (8) P(c)∨Q(c) (7) US (9) Q(c) (6)(8) 析取三段论 (10) ?xQ(x) (9) EG (11) ?xQ(x) ∧ ? ?xQ(x) (4)(11) 合取 * 离散数学 * 综合应用题 试证明下面推理的有效性。 有些病人喜欢一切医生,但是没有一个病人喜欢庸医。所以医生都不是庸医。 符号化:P(x): x是病人;D(x): x是医生; Q(x): x是庸医;L(x,y): x喜欢y。 前提: ?x(P(x) ∧?y(D(y)?L(x,y))) ?x(P(x) ? ?y(L(x,y)??Q(y))) 结论: ?x(D(x) ? ?Q(x)) * 离散数学 * 证明: (1) ?x(P(x) ∧?y(D(y)?L(x,y))) 前提引入 (2) P(a) ∧?y(D(y)?L(a,y)) (1) ES (3) ?x(P(x) ? ?y(L(x,y)??Q(y))) 前提引入 (4) P(a) ? ?y(L(a,y)??Q(y))) (2) US (5) P(a) (2) 化简 (6) ?y(L(a,y)??Q(y)) (4)(5)假言推理 (7) L(a,w)??Q(w) (6) US (8) ?y(D(y)?L(a,y)) (2) 化简 (9) D(w)?L(a,w) (8) US (10) D(w) ? ?Q(w) (7)(9) 假言三段论 (11) ?x(D(x) ? ?Q(x)) (10) UG 前提: ?x(P(x) ∧?y(D(y)?L(x,y))) ?x(P(x) ? ?y(L(x,y)??Q(y))) 结论: ?x(D(x) ? ?Q(x)) * 离散数学 * * 本章完! * 一种人工语言,排除日常自然语言的歧义和形式上的缺陷,严格刻画概念(的外延)间的关系,进而从形式上表达命题的真假,以建立我们所需要的形式证明系统。这种语言,如果限制于表达一阶命题,则称为一阶语言。 * 答案备课本 * * * 离散数学 * 解: 记(1) ,(2) ,(3)中的公式分别为A, B, C. (1)?设 I 为任意一个解释,个体域为D. 若存在x0∈D,使得F(x0)为假,则 xF (x)为假, 所以A 的前件为假,故A为真. 若对于任意 x∈D , F (x)均为真, 则 xF (x), xF (x)都为真,从而A为真. 所以在I下A为真. 由I的任意性可知,A是永线) ?xF(x)→? xF (x) * 离散数学 * 解:取解释 I :个体域为自然数集合N, F(x,y)为x≤y. 在I下B的前件与后件均为真,所以B为真。这说明B不是矛盾式. 再取 I‘ :个体域仍然为N,F(x,y)为x=y。在I’下, B的前件真而后件假,所以B为假,这又说明B不是永真式。故B是非永线) ? x(F(x)∧G(x))→?yG (y) C也是非永线)?x? yF (x,y)→ ? x? yF (x, y) * 离散数学 * 一阶逻辑知识结构 2.1 一阶逻辑基本概念 2.2 一阶逻辑等值演算 2.3 一阶逻辑的推理理论 第四次课 第一、二次课 第三次课 * 离散数学 * 一阶逻辑等值演算知识点 两组一阶逻辑等值式 命题逻辑中重言式的代换实例 量词消去等值式、量词否定等值式、量词辖域收缩与扩张等值式、量词分配等值式 三条规则 置换规则 换名规则 代替规则 前束范式 * 离散数学 * 一阶逻辑等值式 定义2.2.1:设A、B是一阶逻辑中任意的两个公式,若A ?B为逻辑有效式,则称A与B是等值的,记作:A ? B,称A ? B 为等值式。 * 离散数学 * 举例说明: 等价: A?B 读作:A等价于B 含义:A与B在各种赋值下取值均相等 A?B 当且仅当 A ? B是永真式 例如: ??xF(x)??x?F(x) * 离散数学 * 命题公式的推广 命题演算中的等价公式和蕴含公式都可以推广到谓词演算中使用。 例1:A???A, 令A=?xF(x), 得到 ?xF(x)????xF(x) 例2:A→B??A∨B, 令 A=F(x), B=G(y), 得到 F(x)→G(y)??F(x)∨G(y) * 离散数学 * 定理2.2.1:量词否定等值式 (1)??x A(x) ? ?x ?A(x) (2)? ? x A(x) ? ? x ?A(x) 直观理解 例:设P(x):x今天上班。个体域为某公司全体员工。 * 离散数学 * 有限个体域内的证明 ??x A(x) ? ?x ?A(x) ? ? x A(x) ? ? x ?A(x) 设个体域为有限集 * 离散数学 * 基本等值式的非形式化的证明方法 用叙述的方法证明在任何的解释下 若公式左边取1,则右边取1; 若公式左边取0,则右边取0 例:??x A(x) ? ?x ?A(x) 证明: 假设个体域为D (1)在给定的解释I下,若公式的左边??x A(x) 为真,则?x A(x) 为假。因此,必有a∈D,使得A(a)为假,即?A(a) 为真。这表示?x ?A(x)。 (2) 若公式的左边??x A(x) 为假,则?x A(x) 为真。因此,对于任意的a∈D,都有A(a)为真,即?A(a) 取值为假。这表示?x ?A(x)为假。 由解释I的任意性,得到此公式成立。 * 离散数学 * 定理2.2.2 量词辖域收缩与扩张等值式(1) (1)?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中不含x的出现 证明 * 离散数学 * 证明:假设个体域为D。在任意的解释I下, (1)若?xA(x) ∧ B 为真,则?xA(x) 为真且B为真。即对于任意的x∈D,都有A(x)为真且B为真。所以?x (A(x)∧B)为真。 ?xA(x) ∧ B ? ?x (A(x)∧B) (2)若?xA(x) ∧ B 为假,则?xA(x) 为假或B为假。 若?xA(x) 为假,则必有a ∈D,使得A(a)为假。这样, A(a)∧B为假。即?x (A(x)∧B)为假。 若B为假,B中不出现x,则对于任意的a ∈D,同样有A(a)∧B为假。即?x (A(x)∧B)为假。 由解释I的任意性,得到此公式成立。 * 离散数学 * 例1: (?x)(F(x)∨G(y)) ? (?x)F(x)∨G(y) 例2: (?x)(?y)(F(x)∧G(y)) ?(?x)(F(x)∧(?y)G(y)) ? (?x)F(x)∧(?y)G(y) 例3: (?x)(F(x)∨G(y)) ? (?x)F(x)∨G(y) 例4: (?x)(?y)(F(x)∧G(y)) ?(?x)(F(x)∧(?y)G(y)) ?(?x)F(x)∧(?y)G(y) * 离散数学 * 定理2.2.2 量词辖域收缩与扩张等值式(2) ((?x)A(x)→B)? (?x)(A(x)→B) ((?x)A(x)→B) ? (?x)(A(x)→B) (B→(?x)A(x)) ? (?x)(B→A(x)) (B→(?x)A(x)) ? (?x)(B→A(x)) 说明: B中不含x的出现 * 离散数学 * 例1:(?x)(A(x)→B) ? (?x)A(x)→B 证明: (?x)(A(x)→B) ? (?x)(?A(x)∨B) ? (?x)?A(x)∨B ? ?(?x)A(x)∨B ? (?x)A(x)→B * 离散数学 * 例2:(?x)(B→A(x)) ? B→(?x)A(x) 证明: (?x)(B→A(x)) ? (?x)(?B∨A(x)) ? ?B∨(?x)A(x) ? B→(?x)A(x) * 离散数学 * 例3:(?x)(A(x)→B) ? (?x)A(x)→B 证明: (?x)(A(x)→B) ? (?x)(?A(x)∨B) ? (?x)?A(x)∨B ? ?(?x)A(x)∨B ? (?x)A(x)→B * 离散数学 * 例4:(?x)(B→A(x)) ? B→(?x)A(x) 证明: (?x)(B→A(x)) ? (?x)(?B∨A(x)) ? ?B∨(?x)A(x) ? B→(?x)A(x) * 离散数学 * 定理2.2.3 量词分配等值式 (1)?x (A(x)∧B(x)) ? ?xA(x) ∧ ?xB(x) (2)?x (A(x)∨B(x)) ? ?xA(x) ∨ ?xB(x) 称(1)为“?对∧满足分配律”, (2)为“?对∨满足分配律”。 例1: 联欢会上所有人既唱歌又跳舞; 联欢会上所有人唱歌且所有人跳舞。 例2: 联欢会上有的人唱歌,有的人跳舞。 注意:“?对∨”以及“?对∧”不存在分配等价式。 * 离散数学 * 量词分配蕴含式 定理2.2.4:量词分配蕴含式? (1) (?x)A(x)∨(?x)B(x) ? (?x)(A(x)∨B(x)) (2) (?x)(A(x)∨B(x)) ? (?x)A(x)∨(?x)B(x) 成立 不成立 例: 个体域为全体自然数; A(x): x是偶数; B(x): x是奇数 * 离散数学 * 量词分配蕴含式 定理2.2.4:量词分配蕴含式? (1)(?x)(A(x)∧B(x)) ?(?x)A(x)∧(?x)B(x) 成立 不成立 例: 个体域为全体自然数; A(x): x是偶数; B(x): x是奇数. (2) (?x)A(x)∧(?x)B(x) ? (?x)(A(x)∧B(x)) * 离散数学 * 量词的消去 * 离散数学 * 例:设个体域D={a,b,c},消去公式中的量词. 解:方法1(直接代入) 方法2(量词辖域收缩等值式) 等值判断 * 离散数学 * * 离散数学 * 前束范式知识点 定义 前束范式存在定理 前束范式的求取方法 * 离散数学 * 一阶逻辑公式的标准形——前束范式 定义2.2.2 设A为一个一阶逻辑公式,若A具有如下形式 则称A为前束范式,其中 为 或 , B为不含量词的公式。 * 离散数学 * 等公式都是前束范式,而 等都不是前束范式. 可证明每个一阶逻辑公式都能找到与之等价 的前束范式. * 离散数学 * 定理 2.2.5(前束范式存在定理)一阶逻辑中的 任何公式都存在与之等值的前束范式. ?例 求下面公式的前束范式: (1) (2) * 离散数学 * 解 (1) (换名规则) (量词否定等值式) (量词辖域扩张等值式) (量词辖域扩张等值式) 由此可知,(1)中公式的前束范式是不唯一的. (量词分配等值式) (量词否定等值式) 或者 * 离散数学 * (2) (辖域扩张等值式) (量词否定等值式) (换名规则) (辖域扩张等值式) * 离散数学 * 求一个谓词公式的前束范式的过程 *(1) 通过利用公式消去谓词公式中的蕴含和等价联结词; *(2)消去? ? ; *(3)否定深入,即利用量词转化公式,把否定联结词深入到命题变元和谓词填式的前面; (4)运用换名规则和代入规则。保证各变项约束出现和自由出现的身份和次数不变,且不相互混淆。 (5)量词前移,即利用量词辖域的扩张把量词移到前面。 前束析取范式、前束合取范式(例) * 离散数学 * (4) 不存在跑得同样快的两只兔子. 解:定义特性谓词F(x):x是兔子 定义谓词L(x,y):x和y跑得一样快。 * 离散数学 * 几点说明: 一般说来,多个量词出现时,它们的顺序不能随意调换. 例:个体域取整数集合 ?x? y(x=y-1) 真值:T ? y?x (x=y-1) 真值:F 有些命题的符号化形式可不止一种(如前面的例子). * 离散数学 * 谓词公式知识点 谓词公式 指导变元、辖域 自由出现、约束出现 谓词公式的解释 谓词公式的分类 * 离散数学 * 定义2.1.1 一阶语言 的字母表定义如下: (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,…,Fi , Gi , Hi ,…,i≥1 (5) 量词符号: ?,? (6) 联结词符号: ┐,∧,∨, →, ? (7) 括号与逗号: ( , ), , 一阶语言 * 离散数学 * ?定义2.1.2 的项的定义如下: (3) 有限次使用(1),(2)所得到的符号串都是项. (1) 个体常项和个体变项是项. (2) 若 (x1, x2, …, xn) 是任意的 n 元函数, t1,t2,…,tn 是任意的 n 个项,则 (t1, t2, …, tn) 是项. * 离散数学 * 例: 1元谓词F(x),G(x),2元谓词 H(x, y),L(x, y) 等都是原子公式. 定义2.1.3 原子公式 设 R(x1 , x2 , …,xn) 是任意的n元谓词, t1, t2, …, tn 是 的任意的 n 个项,则称 R(t1, t2, …, tn)是 的原子公式. * 离散数学 * 定义2.1.4 的合式公式定义如下: (1) 原子公式是合式公式. (2) 若A是合式公式,则(┐A)也是合式公式. (3) 若A,B是合式公式,则(A∧B),(A∨B),(A→B),(A?B) 也是合式公式. (5) 只有有限次的应用(1)~(4)构成的符号串才是 合式公式. (4) 若A是合式公式,则 也是合式公式. 合式公式也称为谓词公式,简称公式 . * 离散数学 * 定义2.1.5 在公式 和 中,称x为指导变元,A为相应量词的辖域。在 和 的辖域中, x 的所有出现都称为约束出现. A中不是约束出现的其他变项均称为是自由出现的. 自由与约束 * 离散数学 * 例 指出下列各公式中的指导变元,各量词的辖域,自由出现以及约束出现的个体变项: * 离散数学 * 解:(1) x是指导变元. 量词 的辖域 A=( F(x,y) → G(x,z)), 在A中,x是约束出现的. 而且约束出现两次, y 和 z 均为自由出现的,而且各自由出现一次. * 离散数学 * 解:(2)公式中含有两个量词,前件上的量词 的指导变元为x, 的辖域 A=(F(x)→G(y)), 其中x是约束出现的,y是自由出现的. 后件中的量词 ? 的指导变元为 y,?的辖域为 (H(x)∧L(x,y,z)), 其中y是约束出现的,x, z 均为自由出现的. 在整个公式中,x 约束出现一次,自由出现2次,y自由出现一次,约束出现一次,z 只自由 出现一次. * 离散数学 * 则 Δx1 A( x1, x2, …, xn ) 是含有 x2 , x3,…, xn 自由出现的公式,可记为 A1( x2, …, xn )。 类似的, Δx2Δx1A( x1, x2, …, xn ) 可记为A2( x3, x4, …, xn ) , Δxn-1Δxn-2 …Δx1A(x1, x2, …, xn)中只含有xn是自由出现的 个体变项,可以记为 An-1( xn)。 而Δxn …Δx1 A( x1, x2, …, xn )已经没有自由出现的个体 变项了。 为方便起见,用 A( x1, x2, …, xn )表示含 x1, x2,…, xn 自由出现的公式,并用Δ表示任意的量词 ( 或 )。 * 离散数学 * 定义2.1.6 :设A是任意的公式, 若A中不含有自由出现的个体变项,则称A为封闭的公式,简称闭式. 闭公式 要想使含有 r (r≥1)个自由出现个体变项的公式变成闭式,至少要加上 r 个量词. 闭式 不是闭式 * 离散数学 * 换名规则 将量词辖域中的某个约束出现的个体变项及对应的指导变项,改成另一个辖域中没有出现的个体变项符号,公式中的其它部分不变。 例: * 离散数学 * 代替规则 对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替,且处处代替。 例: * 离散数学 * 一阶公式的解释 由以上讨论可知, 按 中合式公式的形成规则 形成的符号串是 中的公式, 这种公式没有确定的意义。 一旦将其中的变项(项的变项, 谓词的变项)等用指定的常项代替后,所得公式化就具备一定的意义, 有时就变成了命题. * 离散数学 * 例: 将下列两个公式中的变项指定成常项 使其成为命题: (1) x(F(x)→G(x))?????????? (2) x y(F(x)∧F(y)∧G(x,y)→ H( f (x,y),g(x,y))) * 离散数学 * 解:(1) 指定个体变项的变化范围,并且指定谓词F,G 的含义,下面给出两种指定法: ??(a) 令个体域 D1为全总个体域,F(x)为x是人, G(x)为x是黄种人,则表达的命题为 “所有人都是黄种人”,这是假命题. ??(b) 令个体域D2为实数集合R,F(x)为x是自然数, G(x)为x是整数,则表达的命题为 “自然数都是整数” , 这是线) x(F(x)→G(x))?????????? * 离散数学 * (2) 式 中含有函数变项,1元谓词变项,2元谓词变项。指定个体域为全总个体域, F(x)为x是实数, G(x,y)为x≠y,H(x,y)为xy,f (x,y)=x2+y2, g(x,y)=2xy, 则上式表达的命题为 “对于任意的x,y,若x与y都是实数,且x≠y, 则x2+y22xy”. 这是真命题. 若H(x,y)改为 xy,则所得命题就为假命题了. (2)? x ? y(F(x)∧F(y)∧G(x,y)→ H( f (x,y),g(x,y))) * 离散数学 * 在例中所谈的对各种变项的指定也可以称为对它们的解释. 解释包括指定: 个体域 个体域中一些特定的元素 函数 谓词 * 离散数学 * 定义2.1.7 的解释I由下面4部分组成: (a) 非空个体域 D ????(b) D 中一些特定元素的集合 ? ?(c) D 上特定函数集合 ????(d) D 上特定谓词的集合 * 离散数学 * 例:给定解释 I 如下: (a) 个体域 D=N ( N为自然数集合) (b) (c) (d) 在 I 下,下列哪些公式为线) F ( f ( x, y ), g ( x, y )) 解:在I下,(1)中公式被解释成 “ x + y = x y ”,这不是命题. * 离散数学 * (2) F ( f ( x, a ), y )→F ( g( x, y ), z) 解:公式被解释成 “( x + 0 = y )→( x y = z )”, 这也不是命题. (3) ┐F( g ( x, y ), g( y, z ) ) 解:公式被解释成 “ x ·y ≠ y z ”. 不是命题. (4) x F ( g( x, y ), z ) 解:公式被解释成 “ x( x y= z )”. 不是命题. * 离散数学 * 解:公式被解释成“ x ( x· 0 = x)→( x = y )”. 由于蕴涵式的前件为假,所以被解释的公式为线) x F( g( x, a), x )→F ( x, y ) 解:公式被解释成 “ x ( x · 0 = x ) ”. 假命题. (7) x y (F ( f ( x, a), y )→F( f ( y, a), x) ) 解: 公式被解释成“ x y((x+0=y)→(y+0=x))”. 真命题. * 离散数学 * (8) x y z F( f ( x, y ), z ) 解:公式被解释为:x y z (x+y=z),真命题。 从本例可以看出,闭式在给定的解释中都变成了命题。 定理 封闭的公式在任何解释下都变成命题. * 离散数学 * 定义2.1.8 设A为一个公式,若A在任何解释下均为真,则称 A为永真式(或称逻辑有效式). 若A在任何解释下均为假,则称A为矛盾式(或永假式)。 若至少存在一个解释使A为真,则称A为可满足式. 从定义可知,永真式一定是可满足式,但可满足式不一定是永真式。 一阶公式的分类 * 离散数学 * 定义2.1.9 设A0是含有命题变项 p1, p2, …, pn 的命题公式, A1, A2,…, An 是n个谓词公式, 用Ai(1≤i≤n)处处代替A0中的 pi,所得公式 A 称为A0的代换实例。 例如,F (x)→G (x), xF(x)→?yG(y)等都是 p→q 的代换实例,而 x( F(x)→G(x)) 不是 p→q 的代换实例. 定理:重言式的代换实例都是重言式,矛盾式的代换实例都是矛盾式. * 离散数学 * 例 判断下列公式中,哪些是永真式,哪些是 矛盾式? ? ?(1) x(F(x)→G(x)) (2) xF (x)→( x yG (x,y)→ xF (x)) (3) ┐( xF (x)→ yG (y))∧ yG (y) * 离散数学 * ? 解:为方便起见,用A,B,C分别记(1),(2),(3) 中的公式。 ? 取解释 I1: 个体域为实数集合R, F(x):x是整数,G(x):x是有理数. 在I1下A为真,因而A不是矛盾式. 取解释I2: 个体域仍然为R, F(x): x是无理数, G(x): x能表示成分数. 在I2下A为假,所以A不是永真式. 故A是非永线) ?x(F(x)→G(x)) * 离散数学 * (2) ?xF (x)→( ?x ? yG (x,y)→ ?xF (x)) 易知B是命题公式p→(q→ p)的代换实例, 而该命题公式是重言式,所以B是永线) ┐( ? xF (x)→ ? yG (y))∧ ? yG (y) C是命题公式┐(p → q)∧ q的代换实例, 而该命题公式是矛盾式,所以C是矛盾式。 * 离散数学 * (1) xF(x)→ xF (x) (2) x yF (x,y)→ x yF (x, y) (3) x(F(x)∧G(x))→ yG (y) ?例 判断下列公式的类型. 离散数学 离散数学 * 离散数学 * 第二章 一阶逻辑 浙江工业大学计算机学院 浙江工业大学软件学院 * 离散数学 * 所有的人都是要死的。 苏格拉底是人, 所以苏格拉底是要死的。 * 离散数学 * 命题逻辑的局限 符号化: P:所有的人都是要死的。 Q:苏格拉底是人, R:所以苏格拉底是要死的。 P∧Q→R 推理正确吗? 说明:命题逻辑不能表现出简单命题中各部分的内在联系。 * 离散数学 * 本章概要 一阶逻辑,又称一阶谓词逻辑或谓词逻辑。对一阶逻辑的研究能够克服命题逻辑的局限性,对简单命题进行进一步的分解,以表达出个体和总体间的内在联系和数量关系。 * 离散数学 * 一阶逻辑知识结构 2.1 一阶逻辑基本概念 2.2 一阶逻辑等值演算 2.3 一阶逻辑的推理理论 第四次课 第一、二次课 第三次课 * 离散数学 * 一阶逻辑基本概念知识点 谓词和量词概念 一阶逻辑命题的符号化(特性谓词) 谓词公式基本概念 谓词公式的解释 谓词公式的分类 * 离散数学 * 谓词和量词 一个简单命题中表示研究对象即主体或客体(对应名词成分)的词称为个体词。 表示一个个体词性质的或多个个体词之间关系的词称为谓词。 例:小张是学生。小李是学生。 小张在跑步。 小张比小李高2cm。 X是我的同学。 * 离散数学 * 谓词和量词 个体词 个体常项 表示具体的、特指的个体的词 用a,b,c…表示 个体变项 表示抽象的、泛指的或在一定范围内变化的个体的词 用x,y,z…表示 个体域 个体变项的取值范围 全总个体域 * 离散数学 * 谓词和量词 谓词 谓词常项:表示具体性质或关系的谓词 谓词变项:表示抽象的或泛指的性质或关系的谓词 用F,G,H…表示 例:(1)3是整数。 (2)x和y具有关系L。 (3)小张和小李是同学。 * 离散数学 * 谓词函数 一般地: 如果一个语句中包含n个(n=0)变量x1, x2, …,xn,则它可以表示为 xi称为个体变元,P称为谓词函数。 0元谓词:不包含有个体变项的谓词 n 元谓词:包含有n个体变项的谓词 即命题 * 离散数学 * 例:分析下列语句中的个体词和谓词。 (1)离散数学是计算机专业的专业基础课。 (2)网络原理是计算机专业的专业基础课。 (3)小红和小青是同学。 个体词:离散数学 谓词:是计算机专业的专业基础课 个体词:网络原理 谓词:是计算机专业的专业基础课 个体词:小红,小青 谓词:是同学 * 离散数学 * 例:0元谓词符号化下列命题。 (1)如果地球重于月亮,太阳就重于地球。 (2)只有2是素数,5才是素数。 F(x,y): x重于y。a: 地球;b:月亮;c:太阳 F(a,b) → F(c,a) F(x): x是素数。a: 2;b:5 F(b) → F(a) Note:n元谓词中的个体变项的顺序不能随便换。 * 离散数学 * 全称量词和存在量词 量词: 表示个体常项或变项之间数量关系的词 全称量词 用?表示,形成的命题形式为?xF(x),即“对所有的x,F(x)为真”。 存在量词 用?表示,形成的命题形式为?xF(x),即“存在x 值,使F(x)为真”。 将下面的命题符号化: (1) 所有的人都是要死的。 (2) 有的人活百岁以上。 * 离散数学 * 量词的取值 为真 为假 * 离散数学 * 例:判断?x P(x)的线x, x∈R (2) P(x): x2, x∈R (3) P(x): x210, x是小于5的正整数。 T F x∈{1,2,3,4} 4210 F * 离散数学 * 一阶逻辑命题符号化 例:在个体域分别限制为(a)和(b)条件时,将下面两个命题符号化: (1) 凡是人都要呼吸. (2) 有的人用左手写字. 其中: (a)个体域 D1为人类集合; (b)个体域 D2为全总个体域. 解答 * 离散数学 * (1) 凡是人都要呼吸. 解: (a)个体域 D1为人类集合 (b)个体域 D2为全总个体域. 为将人从全总个体域中分离出来,令 M(x)为特性谓词:用于刻画个体域的谓词 * 离散数学 * (2) 有的人用左手写字. 解: (a)个体域 D1为人类集合; (b)个体域 D2为全总个体域. * 离散数学 * 特性谓词的使用 例:对下面的命题进行符号化。 有些狮子不喝咖啡。 解:令F(x): x喝咖啡。M(x):x是狮子。 考虑所有狮子都喝咖啡的情况。 左式为假,符合原句的意思。 对右式而言,设x是老虎,则右式为真。这和原句是矛盾的。 * 离散数学 * 个体域对命题符号化的影响 例:将下列命题符号化。要求个体域为: (1)有理数集合;(2)实数集合;(3)全总个体域。 1. 凡是有理数均可表示成分数。 解:设P (x):x是有理数。 Q (x):x可以表示成分数。 (1)有理数集合:?x Q(x) (2)实数集合: ?x (P(x) ?Q(x)) (3)全总个体域:?x (P(x) ?Q(x)) 2. 有的有理数是整数。 解:设P (x):x是有理数。 I (x):x是整数。 (1)有理数集合: ?x I (x) (2)实数集合: ?x (P(x) ?I(x)) (3)全总个体域: ?x (P(x) ?I(x)) * 离散数学 * 个体域对命题符号化的影响 例:在个体域限制为(a)和(b)条件时,将下列命题符号化: (1) 对于任意的x,均有 x2-3x+2=(x-1)(x-2) . (2) 存在x,使得 x+5=3. 其中: (a) 个体域 D1=N (N为自然数集合) (b) 个体域 D2=R (R为实数集合) * 离散数学 * (1) 对于任意的x,均有 x2-3x+2=(x-1)(x-2) 解:令 (a) 个体域 D1=N (N为自然数集合) 命题符号化为: (b) 个体域 D2=R (R为实数集合) 命题符号化为: T T 真值: 真值: * 离散数学 * (2)存在x,使得 x+5=3. 解: 令 (a) 个体域 D1=N (N为自然数集合) 命题符号化为: (b) 个体域 D2=R (R为实数集合) 命题符号化为: 真值: 真值: F T * 离散数学 * 一阶逻辑命题符号化题例 例:将下列命题符号化,并讨论线) 所有的人都长着黑头发. ? 解:定义特性谓词M(x):x是人。 定义谓词F(x):x长着黑头发。 真值: F * 离散数学 * ?(2) 有的人登上过月球. 解:定义特性谓词M(x):x是人。 定义谓词F(x):x登上过月球。 真值: T * 离散数学 * (3) 没有人登上过木星. 解:定义特性谓词M(x):x是人。 定义谓词F(x):x登上过木星。 真值: T * 离散数学 * (4) 在美国留学的学生未必都是亚洲人. 解:定义特性谓词M(x):x是在美国留学的学生。 定义谓词F(x):x是亚洲人。 真值: T * 离散数学 * 例:将下列命题符号化。 (1) 兔子比乌龟跑得快. 解:定义特性谓词F(x):x是兔子。 G(y): y是乌龟。 定义谓词H(x,y):x比y跑得快。 * 离散数学 * (2) 有的兔子比所有的乌龟跑得快. 解:定义特性谓词F(x):x是兔子。 G(y): y是乌龟。 定义谓词H(x,y):x比y跑得快。 * 离散数学 * (3) 并不是所有的兔子都比乌龟跑得快. 解:定义特性谓词F(x):x是兔子。 G(y): y是乌龟。 定义谓词H(x,y):x比y跑得快。 离散数学 离散数学 * 一种人工语言,排除日常自然语言的歧义和形式上的缺陷,严格刻画概念(的外延)间的关系,进而从形式上表达命题的真假,以建立我们所需要的形式证明系统。这种语言,如果限制于表达一阶命题,则称为一阶语言。 * 答案备课本 * *

本文链接:http://jamescaronna.com/yunhanweici/33.html