《《离散数学》第二章-一阶逻辑-讲稿分析》由会员分享，可在线阅读，更多相关《《离散数学》第二章-一阶逻辑-讲稿分析（14页珍藏版）》请在金锄头文库上搜索。
1、2.1 一阶逻辑基本概念一、本节主要内容基本概念个体词、谓词、量词 命题符号化二、教学内容个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体，它可以是一个具体的事物，也可以是一个抽象的概念. 表示主语的词（名词或代词）：苏格拉底，2，黑板，自然数，思想，定理. 个体常项：具体的或特定的个体词， 用a, b, c表示 个体变项：抽象的或泛指的个体词， 用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如a, b, c, 1, 2 无限个体域，如N, Z, R, 全总个体域: 宇宙间一切事物组成 基本概念 谓词: 表示个体词的性质或相互之间关系的词 谓词常项：表示具体性质或
2、关系的谓词 F: 是人，F(a)：a是人 G： 是自然数， F(2)：2是自然数 谓词变项：表示抽象的或泛指的谓词 F: 具有性质F，F(x)：x具有性质F 元数：谓词中所包含的个体词数 一元谓词: 表示事物的性质 多元谓词(n元谓词, n2): 表示个体词之间的关系 如 L(x,y)： x与y有关系L， L(x,y)： x比y高2厘米 注意：多元谓词中，个体变项的顺序不能随意改动 个体变项和谓词的联合体，F(x),L(x,y)，也称为谓词 n元谓词 L(x1, x2, xn)可看作一个函数，定义域为个体变项的个体域，值域为0,1n元谓词 L(x1, x2, xn)的真值不确定，不是命题, 如
3、：L(x,y) 如果L(x,y)表示 “x小于y”，谓词部分已经是常项，但 还不是命题. 考虑L(2,3)和L(3,2) L(x1, x2, xn)是命题：只有当L是常项， x1, x2, xn是个体常项0元谓词: 不含个体变项的谓词, 如L(a, b) 如L的意义明确，则0元谓词都是命题 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶 逻辑中符号化 (1) 墨西哥位于南美洲 在命题逻辑中, 设 p: 墨西哥位于南美洲 符号化为 p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a)例1(续) (2) 是无理数仅
4、当 是有理数 在命题逻辑中, 设 p： 是无理数，q： 是有理数. 符号化为 p q, 这是假命题 在一阶逻辑中, 设F(x): x是无理数, G(x): x是有理 数符号化为 (3) 如果23，则33，q：3y，G(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) 或 $x$y(F(x)G(y)L(x,y) 两者等值一阶逻辑中命题符号化(续)几点注意： 1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般
5、不要随便颠倒 例：对任意x，存在着y，使得x+y=5. 个体域为实数集. 符号化为： x $y H（x,y), 其中H（x,y):x+y=5 考虑 $y x H（x,y) 否定式的使用例：在一界逻辑中命题符号化 没有不呼吸的人 不是所有的人都喜欢吃糖 不是所有的火车都比所有的汽车快 $x( F(x) G(x) 其中F(x)：x是人， G(x)：x呼吸 或者： x( F(x) G(x) x( F(x) G(x) 其中F(x)：x是人， G(x)：x喜欢吃糖 或者： $x( F(x) G(x) x( F(x) y (G(y) H(x,y) ) 或者： $x( F(x) $ y (G(y) H(x,
6、y) )例：在一界逻辑中命题符号化 一切人都不一样高 每个自然数都有后继数 有的自然数无先驱数 x y( F(x) F(y) G(x,y) H(x,y) 其中F(x)：x是人， G(x,y) :x和y不是同一个人， H(x,y)： x和y一样高 或者： $ x $ y( F(x) F(y) G(x,y) H(x,y) x( F(x) $y(G(y) H(x,y) 其中F(x)：x是自然数， H(x,y) ：y是x的后继数 或者： x( F(x) L(x) ， L(x) ：x有后继数 $ x( F(x) y(G(y) H(x,y) 或者： $x( F(x) L(x) ) ，L(x) ：x有先驱数
7、2.2 一阶逻辑公式及解释一、本节主要内容字母表合式公式(简称公式)个体变项的自由出现和约束出现解释永真式（逻辑有效式）矛盾式（永假式）可满足式 二、教学内容字母表 定义 字母表包含下述符号： (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) 括号与逗号：( , ), ， 项
8、 定义 项的定义如下： (1) 个体常项和个体变项是项. (2) 若j(x1, x2, , xn)是任意的n元函数，t1,t2,tn是任意的n个项，则j(t1, t2, , tn) 是项. (3) 所有的项都是有限次使用 (1), (2) 得到的.例：a，b，x，y，f(x,y)=x+y， g(x,y)=x-y都是项 f(a, g(x,y)=a+ (x-y)是项 其实, 个体常项、变项是项，由它们构成的n元函数和复合函数还是项原子公式 定义 设R(x1, x2, , xn)是任意的n元谓词，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)形成的符号串 才是合式公式(谓词公式).个体变项的
