《离散数学第二章一阶逻辑知识点总结.doc》由会员分享，可在线阅读，更多相关《离散数学第二章一阶逻辑知识点总结.doc（8页珍藏版）》请在金锄头文库上搜索。
1、 数理逻辑部分第2章 一阶逻辑2.1 一阶逻辑基本概念个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示个体域: 个体变项的取值范围有限个体域，如a, b, c, 1, 2无限个体域，如N, Z, R, 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质多元谓词(n元谓词, n2): 表示事物之间的关系如 L(x,y)：x与y有关系L，L(x,y)：xy，0元谓词: 不含个体变项的谓词, 即
2、命题常项或命题变项 量词: 表示数量的词全称量词: 表示任意的, 所有的, 一切的等 如 x 表示对个体域中所有的x 存在量词$: 表示存在, 有的, 至少有一个等 如 $x 表示在个体域中存在x一阶逻辑中命题符号化例1 用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化 (1) 墨西哥位于南美洲在命题逻辑中, 设 p: 墨西哥位于南美洲 符号化为 p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲符号化为F(a)例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 .解
3、：(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)这是两个基本公式, 注意这两个基本公式的使用.例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (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) 两者等值 (
4、2) 令F(x): x是无理数, G(y): y是有理数, L(x,y)：xy $x(F(x)$y(G(y)L(x,y) 或 $x$y(F(x)G(y)L(x,y) 两者等值几点注意： 1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般不能随便颠倒 否定式的使用思考： 没有不呼吸的人 不是所有的人都喜欢吃糖 不是所有的火车都比所有的汽车快以上命题应如何符号化？ 2.2 一阶逻辑合式公式及解释字母表定义 字母表包含下述符号： (1) 个体常项：a, b, c, , ai, bi, ci, , i 1 (2) 个体变项：x, y, z, , xi, yi, zi, , i 1 (3)
5、 函数符号：f, g, h, , fi, gi, hi, , i 1 (4) 谓词符号：F, G, H, , Fi, Gi, Hi, , i 1 (5) 量词符号：, $ (6) 联结词符号：, , , , (7) 括号与逗号：(, ), ， 定义 项的定义如下： (1) 个体常项和个体变项是项. (2) 若j(x1, x2, , xn)是任意的n元函数，t1,t2,tn 是任意的n个项，则j(t1, t2, , tn) 是项. (3) 所有的项都是有限次使用 (1), (2) 得到的.个体常项、变项是项，由它们构成的n元函数和复合函数还是项定义 设R(x1, x2, , xn)是任意的n元谓
6、词，t1,t2, tn 是任意的n个项，则称R(t1, t2, , tn)是原子公式. 原子公式是由项组成的n元谓词. 例如，F(x,y), F(f(x1,x2),g(x3,x4)等均为原子公式 定义 合式公式（简称公式）定义如下： (1) 原子公式是合式公式. (2) 若A是合式公式，则 (A)也是合式公式 (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式 (4) 若A是合式公式，则xA, $xA也是合式公式 (5) 只有有限次地应用(1)(4)形成的符号串是合 式公式.请举出几个合式公式的例子. 定义 在公式xA和$xA中，称x为指导变元，A为相应量
7、词的辖域. 在x和$x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.例如, 在公式 x(F(x,y)G(x,z) 中, A=(F(x,y)G(x,z)为x的辖域， x为指导变元, A中x的两次出现均为约束出现， y与z均为自由出现. 闭式: 不含自由出现的个体变项的公式.给定公式 A=x(F(x)G(x)成真解释: 个体域N, F(x): x2, G(x): x1 代入得A=x(x2x1) 真命题成假解释: 个体域N, F(x): x1, G(x): x2 代入得A=x(x1x2) 假命题问: xF(x)$xF(x) 有成真解释吗？ $xF(x)xF(x)
8、 有成假解释吗？ 被解释的公式不一定全部包含解释中的4部分. 闭式在任何解释下都是命题，注意不是闭式的公式在某些解释下也可能是命题. 永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满足式：至少有一个成真赋值几点说明：永真式为可满足式，但反之不真谓词公式的可满足性（永真性,永假性)是不可判定的利用代换实例可判某些公式的类型 定义 设A0是含命题变项p1, p2, ,pn的命题公式， A1,A2,An是n个谓词公式，用Ai处处代替A0中的pi (1in) ，所得公式A称为A0的代换实例. 例如: F(x)G(x), xF(x)$yG(y) 等都是pq的换实例， x(F(x)G(x)
9、 等不是 pq 的代换实例. 定理 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式. 2.3 一阶逻辑等值式 等值式定义 若AB为逻辑有效式，则称A与B是等值的，记作 AB，并称AB为等值式. 基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)$yG(y) xF(x)$yG(y) (xF(x)$yG(y) xF(x)$yG(y) 等 消去量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an) $xA(x)A(a1)A(a2)A(an)量词否定等值式设A(x)是含x自由出现的公式 xA(x) $x A(x) $xA(x)x A(x) 量词分配等值式 x(
10、A(x)B(x)xA(x)xB(x) $x(A(x)B(x)$xA(x)$xB(x)注意：对无分配律，$对无分配律 例 将下面命题用两种形式符号化 (1) 没有不犯错误的人 (2) 不是所有的人都爱看电影解 (1) 令F(x)：x是人，G(x)：x犯错误. $x(F(x)G(x) x(F(x)G(x) 请给出演算过程，并说明理由. (2) 令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x) $x(F(x)G(x) 给出演算过程，并说明理由. 前束范式定义 设A为一个一阶逻辑公式, 若A具有如下形式Q1x1Q2x2QkxkB, 则称A为前束范式, 其中Qi (1ik)为或$，B为不含
11、量词的公式.例如，x$y(F(x)(G(y)H(x,y) x(F(x)G(x)是前束范式, 而 x(F(x)$y(G(y)H(x,y) $x(F(x)G(x)不是前束范式.定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式 注意: 公式的前束范式不惟一 求公式的前束范式的方法: 利用重要等值式、 置换规则、换名规则、代替规则进行等值演算. 换名规则: 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成其他辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.代替规则: 对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，则
12、所得公式与原来的公式等值. 例 求下列公式的前束范式 (1) $x(M(x)F(x)解 $x(M(x)F(x) x(M(x)F(x) （量词否定等值式） x(M(x)F(x) 两步结果都是前束范式，说明前束范式不惟一.(2) xF(x)$xG(x)解 xF(x)$xG(x) xF(x)xG(x) （量词否定等值式） x(F(x)G(x) （量词分配等值式）另有一种形式 xF(x)$xG(x) xF(x)xG(x) xF(x)yG(y) ( 换名规则 ) xy(F(x)G(y) ( 量词辖域扩张 )两种形式是等值的 (3) $xF(x)xG(x) 解 $xF(x)xG(x) $xF(x)$xG(x) $x(F(x)G(x) （为什么？） 或 $x$y(F(x)G(y) （为什么？） (4) xF(x)$y(G(x,y)
