一、单项选择题（共 10 道试题，共 100 分
数理逻辑部分 第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元谓词: 不含个体变项的谓词, 即命题常项或命题变项
量词: 表示数量的词
全称量词: 表示任意的, 所有的, 一切的等 如 x 表示对个体域中所有的x
存在量词: 表示存在, 有的, 至少有一个等 如 x 表示在个体域中存在x
一阶逻辑中命题符号化
例1 用0元谓词将命题符号化
要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化 (1) 墨西哥位于南美洲
在命题逻辑中, 设 p: 墨西哥位于南美洲 符号化为 p, 这是真命题
在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲
符号化为F(a)
页脚内容1
一、单项选择题（共 10 道试题，共 100 分
例2 在一阶逻辑中将下面命题符号化 (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))
这是两个基本公式, 注意这两个基本公式的使用. 例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数
(2) 有的无理数大于有的有理数
解 注意: 题目中没给个体域, 一律用全总个体域
(1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y 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)：x>y x(F(x)y(G(y)L(x,y)))
或 xy(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) 函数符号：f, g, h, …, fi, gi, hi, …, i 1 (4) 谓词符号：F, G, H, …, Fi, Gi, Hi, …, i 1 (5) 量词符号：,
(6) 联结词符号：, , , , (7) 括号与逗号：(, ), ，
定义 项的定义如下：
(1) 个体常项和个体变项是项.
(2) 若(x1, x2, …, xn)是任意的n元函数，t1,t2,…,tn
页脚内容2
一、单项选择题（共 10 道试题，共 100 分
是任意的n个项，则(t1, t2, …, tn) 是项.
(3) 所有的项都是有限次使用 (1), (2) 得到的.
个体常项、变项是项，由它们构成的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)形成的符号串是合 式公式.
请举出几个合式公式的例子.
定义 在公式xA和xA中，称x为指导变元，A为相 应量词的辖域. 在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): x>2, G(x): x>1 代入得A=x(x>2x>1) 真命题 成假解释: 个体域N, F(x): x>1, G(x): x>2 代入得A=x(x>1x>2) 假命题 问: xF(x)xF(x) 有成真解释吗？ xF(x)xF(x) 有成假解释吗？
页脚内容3
一、单项选择题（共 10 道试题，共 100 分
被解释的公式不一定全部包含解释中的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)) 等不是 pq 的代换实例.
定理 重言式的代换实例都是永真式，矛盾式的代 换实例都是矛盾式.
页脚内容4
一、单项选择题（共 10 道试题，共 100 分
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)
页脚内容5
等
离散数学第二章一阶逻辑知识点总结
