第四章 一阶逻辑基本概念 主要内容 一阶逻辑命题符号化 个体词、谓词、量词 一阶逻辑公式及其解释 一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式

4.1 一阶逻辑命题符号化 个体词——所研究对象中可以独立存在的具体或抽象的客体 个体常项：具体的事务，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域(论域)——个体变项的取值范围 有限个体域，如 {a, b, c}, {1, 2} 无限个体域，如 N, Z, R, … 全总个体域——由宇宙间一切事物组成

谓词 谓词——表示个体词性质或相互之间关系的词 谓词常项 如, F(a)：a是人 谓词变项 如, F(x)：x具有性质F n（n1）元谓词 如, L(x,y)：x与 y 有关系 L，L(x,y)：xy，… 0元谓词——不含个体变项的谓词, 即命题常项 或命题变项

量词 量词——表示数量的词 全称量词: 表示所有的. x : 对个体域中所有的x 如, xF(x)表示个体域中所有的x具有性质F xyG(x,y)表示个体域中所有的x和y有关系G 存在量词: 表示存在, 有一个. x : 个体域中有一个x 如, xF(x)表示个体域中有一个x具有性质F xyG(x,y)表示个体域中存在x和y有关系G xyG(x,y)表示对个体域中每一个x都存在一个y使得 x和y有关系G xyG(x,y)表示个体域中存在一个x使得对每一个y,

实例1 例1 用0元谓词将命题符号化 (1) 墨西哥位于北美洲 (2) 是无理数仅当 是有理数 (3) 如果2>3，则3<4 例1 用0元谓词将命题符号化 (1) 墨西哥位于北美洲 (2) 是无理数仅当 是有理数 (3) 如果2>3，则3<4 解：在命题逻辑中： (1) p, p为墨西哥位于北美洲 （真命题） (2) p→q, 其中, p： 是无理数，q： 是有理数. 是假命题 (3) pq, 其中，p：2>3，q：3<4. 是真命题

实例1解答 在一阶逻辑中： (1) F(a)，其中，a：墨西哥，F(x)：x位于北美洲 . (2) F( )G( ), 其中，F(x)：x是无理数，G(x)：x是有理数 (3) F(2, 3)G(3, 4)，其中，F(x, y)：x>y，G(x, y)：x<y

实例2 例 2 在一阶逻辑中将下面命题符号化 (1) 人都爱美 (2) 有人用左手写字 个体域分别为 (a) D为人类集合 例 2 在一阶逻辑中将下面命题符号化 (1) 人都爱美 (2) 有人用左手写字 个体域分别为 (a) D为人类集合 (b) D为全总个体域 解 (a) (1) xG(x), G(x)：x爱美 (2) xG(x), G(x)：x用左手写字 (b) F(x)：x为人，G(x)：x爱美 (1) x(F(x)G(x)) (2) x(F(x)G(x)) 1. 引入特性谓词F(x) 2. (1),(2)是一阶逻辑中两个“基本”公式

实例3 例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解 注意：题目中没给个体域，一律用全总个体域 (1) 令F(x)：x为正数，G(y)：y为负数, L(x,y)：x>y xy(F(x)G(y)L(x,y)) (2) 令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：x>y xy(F(x)G(y)L(x,y))

实例4 例4 在一阶逻辑中将下面命题符号化 (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喜欢吃糖 x(F(x)G(x)) x(F(x)G(x))

实例5 例5 设个体域为实数域, 将下面命题符号化 (1) 对每一个数x都存在一个数y使得x<y 解 L(x,y):x<y (1) xyL(x,y) (2) xyL(x,y) 注意: 与不能随意交换 显然(1)是真命题, (2)是假命题

4.2 一阶逻辑公式及解释 定义4.1 设L是一个非逻辑符集合, 由L生成的一阶语言L 的 字母表包括下述符号： 非逻辑符号 (1) 个体常项符号：a, b, c, …, ai, bi, ci, …, i 1 (2) 函数符号：f, g, h, …, fi, gi, hi, …, i 1 (3) 谓词符号：F, G, H, …, Fi, Gi, Hi, …, i 1 逻辑符号 (4) 个体变项符号：x, y, z, …, xi, yi, zi, …, i 1 (5) 量词符号：,  (6) 联结词符号：, , , ,  (7) 括号与逗号：(, ), ，

一阶语言L 的项与原子公式 定义4.2 L 的项的定义如下： (1) 个体常项和个体变项是项. (2) 若(x1, x2, …, xn)是任意的n元函数，t1, t2, …, tn是任意的 n个项，则(t1, t2, …, tn) 是项. (3) 所有的项都是有限次使用(1),(2)得到的 如, a, x, x+y, f(x), g(x,y)等都是项 定义4.3 设R(x1, x2, …, xn)是L 的任意n元谓词，t1, t2, …, tn 是L 的任意n个项，则称R(t1, t2, …, tn)是L 的原子公式. 如，F(x, y), F(f(x1, x2), g(x3, x4))等均为原子公式

一阶语言L 的公式 定义4.4 L 的合式公式定义如下： (1) 原子公式是合式公式. (2) 若A是合式公式，则 (A)也是合式公式 (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是 合式公式 (4) 若A是合式公式，则xA, xA也是合式公式 (5) 只有有限次地应用(1)—(4)形成的符号串才是合式公式. 合式公式简称公式 如, F(x), F(x)G(x,y), x(F(x)G(x)) xy(F(x)G(y)L(x,y))等都是合式公式

封闭的公式 定义4.5 在公式 xA 和 xA 中，称x为指导变元，A为相应 量词的辖域. 在x和 x的辖域中，x的所有出现都称为约束 出现，A中不是约束出现的其他变项均称为是自由出现的. 例如，x(F(x,y)G(x,z))， x为指导变元，(F(x,y)G(x,z))为 x 的辖域，x的两次出现均为约束出现，y与 z 均为自由出现 又如, x(F(x,y,z)y(G(x,y)H(x,y,z))), x中的x是指导变元, 辖域为(F(x,y,z)y(G(x,y)H(x,y,z))). y中的y是指导变元, 辖 域为(G(x,y)H(x,y,z)). x的3次出现都是约束出现, y的第一次出 现是自由出现, 后2次是约束出现, z的2次出现都是自由出现

封闭的公式 定义4.6 若公式A中不含自由出现的个体变项，则称A为封闭 的公式，简称闭式. 例如，xy(F(x)G(y)H(x,y)) 为闭式， 而 x(F(x)G(x,y)) 不是闭式

公式的解释 定义4.7 设L 是L生成的一阶语言, L 的解释I由4部分组成： (a) 非空个体域 DI . (b) 对每一个个体常项符号aL, 有一个 DI, 称 为a在I 中的解释. (c) 对每一个n元函数符号fL, 有一个DI上的n元函数 , 称 为f在I中的解释. (d) 对每一个n元谓词符号FL, 有一个DI上的n元谓词常项 , 称 为F在I中的解释. 设公式A, 取个体域DI , 把A中的个体常项符号a、函数符 号f、谓词符号F分别替换成它们在I中的解释 、 、 , 称 所得到的公式A为A在I下的解释, 或A在I下被解释成A.

实例 例6 给定解释 I 如下： (a) 个体域 D=R (b) (c) (d) 写出下列公式在I下的解释, 并指出它的真值. (1) xF(f(x,a),g(x,a)) x(x+0=x0) 真 (2) xy(F(f(x,y),g(x,y))F(x,y)) xy(x+y=xyx=y) 假 (3) xF(g(x,y),a) x(xy=0) 真值不定, 不是命题

公式的类型 定理4.1 闭式在任何解释下都是命题 注意: 不是闭式的公式在解释下可能是命题, 也可能不是命题. 定理4.1 闭式在任何解释下都是命题 注意: 不是闭式的公式在解释下可能是命题, 也可能不是命题. 定义4.8 若公式A在任何解释下均为真, 则称A为永真式(逻辑 有效式). 若A在任何解释下均为假, 则称A为矛盾式(永假式). 若至少有一个解释使A为真, 则称A为可满足式. 几点说明： 永真式为可满足式，但反之不真 判断公式是否是可满足的(永真式, 矛盾式)是不可判定的

代换实例 定义4.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的代换实例. 定理4.2 重言式的代换实例都是永真式，矛盾式的代换实例 都是矛盾式.

实例 例7 判断下列公式中，哪些是永真式，哪些是矛盾式？ (1) xF(x)(xyG(x,y)xF(x)) 例7 判断下列公式中，哪些是永真式，哪些是矛盾式？ (1) xF(x)(xyG(x,y)xF(x)) 重言式 p(qp) 的代换实例，故为永真式. (2) (xF(x)yG(y))yG(y) 矛盾式 (pq)q 的代换实例，故为永假式. (3) x(F(x)G(x)) 解释I1: 个体域N, F(x):x>5, G(x): x>4, 公式为真 解释I2: 个体域N, F(x):x<5, G(x):x<4, 公式为假 结论: 非永真式的可满足式

第四章 习题课 主要内容 个体词、谓词、量词 一阶逻辑命题符号化 一阶语言L 项、原子公式、合式公式 公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释 公式的类型 永真式(逻辑有效式)、矛盾式(永假式)、可满足式

基本要求 准确地将给定命题符号化 理解一阶语言的概念 深刻理解一阶语言的解释 熟练地给出公式的解释 记住闭式的性质并能应用它 深刻理解永真式、矛盾式、可满足式的概念, 会判断简 单公式的类型

练习1 1. 在分别取个体域为 (a) D1=N (b) D2=R (c) D3为全总个体域 的条件下, 将下面命题符号化，并讨论真值 (1) 对于任意的数x，均有 解 设G(x): (a) xG(x) 假 (b) xG(x) 真 (c) 又设F(x):x是实数 x(F(x)G(x)) 真

练习1(续) (2) 存在数x，使得 x+7=5 解 设H(x)：x+7=5 (a) xH(x) 假 (b) xH(x) 真 (c) 又设F(x)：x为实数 x(F(x)H(x)) 真 本例说明：不同个体域内，命题符号化形式可能不同（也可 能相同），真值可能不同（也可能相同）.

练习2 2. 在一阶逻辑中将下列命题符号化 (1) 大熊猫都可爱 设F(x): x为大熊猫，G(x): x可爱 x(F(x)G(x)) 2. 在一阶逻辑中将下列命题符号化 (1) 大熊猫都可爱 设F(x): x为大熊猫，G(x): x可爱 x(F(x)G(x)) (2) 有人爱发脾气 设F(x): x是人，G(x): x爱发脾气 x(F(x)G(x)) (3) 说所有人都爱吃面包是不对的 设F(x): x是人，G(x): x爱吃面包 x(F(x)G(x)) 或 x(F(x)G(x))

练习2 (4) 没有不爱吃糖的人 设F(x): x是人，G(x): x爱吃糖 x(F(x)G(x)) 或 x(F(x)G(x)) (5) 任何两个不同的人都不一样高 设F(x):x是人, H(x,y), x与y相同, L(x,y): x与y一样高 x(F(x)y(F(y)H(x,y)L(x,y))) 或 xy(F(x)F(y)H(x,y)L(x,y)) (6) 不是所有的汽车都比所有的火车快 设F(x):x是汽车, G(y):y是火车, H(x,y):x比y快 xy(F(x)G(y)H(x,y)) 或 xy(F(x)G(y)H(x,y))

练习3 3. 给定解释 I 如下: (a) 个体域D=N (b) =2 (c) (d) 说明下列公式在 I 下的涵义,并讨论真值 (1) xF(g(x,a),x) x(2x=x) 假 (2) xy(F(f(x,a),y)F(f(y,a),x)) xy(x+2=yy+2=x) 假

练习3 (3) xyzF(f(x,y),z) xyz(x+y=z) 真 (4) xyzF(f(y,z),x) xyz(y+z=x) 假 (3),(4)说明与不能随意交换 (5) xF(f(x,x),g(x,x)) x(x+x=xx) 真

练习4 4. 证明下面公式既不是永真式，也不是矛盾式: (1) x(F(x)G(x)) 解释1: D1=N, F(x):x是偶数, G(x): x是素数, 真 解释2: D2=N, F(x):x是偶数, G(x): x是奇数, 假 (2) xy(F(x)G(y)H(x,y)) 解释1: D1=Z, F(x):x是正数, G(x): x是负数, H(x,y):x>y 真 解释2: D2=Z, F(x):x是偶数, G(x): x是奇数, H(x,y):x>y 假

练习5 5. 证明下列公式为永真式: (1) (xF(x)yG(y))xF(x)yG(y) (AB)AB的代换实例 (2) x(F(x)(F(x)G(x))) 设I是任意的一个解释, 对每一个xDI, F(x)(F(x)G(x))恒为真