第四章:一阶逻辑基本概念 本章的主要内容 一阶逻辑命题符号化 一阶逻辑公式、解释及分类 本章与其他章的联系 克服命题逻辑的局限性 是第五章的先行准备

第一节：一阶逻辑命题符号化

4.1 一阶逻辑命题符号化 例子 命题逻辑的表示能力缺陷 命题之间的联系无法刻画 凡是人都要死 pq 苏格拉底是人 r 推出：苏格拉底要死？ 命题逻辑的表示能力缺陷 命题演算的基本单元为简单命题 不能研究命题的结构、成分和内部逻辑的特征 不能表达二个原子命题所具有的共同特征，无法处理一些简单又常见的推理 命题之间的联系无法刻画

4.1 一阶逻辑命题符号化 一阶逻辑 命题分解 例： 对命题做进一步分解 揭示命题的内部结构以及命题间的内在联系 个体词（名词、代词） 谓词 量词 例： 南京是城市 个体词：南京 谓词：是城市

4.1 一阶逻辑命题符号化 个体词：研究对象中独立存在的具体或抽象的个体 个体常项：具体或特定的个体词 个体变项：抽象或泛指的个体词 南京，东南大学，1，2 个体变项：抽象或泛指的个体词 x,y,z 取值范围称为个体域或论域 空集不能作为论域 全总个体域：宇宙间一切事物

4.1 一阶逻辑命题符号化 谓词：刻画个体词性质及个体词之间的关系的词 n元谓词P(x1,…,xn) 谓词常项：具体性质或关系的谓词 F(a,b)：小王和小李是同学 G(x)：x是有理数 谓词变项：抽象或泛指的性质或关系的谓词 L(x,y)：x,y具有关系L n元谓词P(x1,…,xn) P(x1,…,xn): Dn{F,T}，D为个体域 不带个体变项的谓词为0元谓词，当为谓词常项时，即命题

4.1 一阶逻辑命题符号化 例:将下列命题用0元谓词符号化 2既是素数又是偶数 如果3>5，则2>3 F(x)：x是素数 G(x)：x是偶数 a:2 F(a)  G(a) 如果3>5，则2>3 F(x,y):x>y a:3, b:5, c:2 F(a,b)F(c,a)

4.1 一阶逻辑命题符号化 量词：表示个体常项或变项之间数量关系的词 全称量词： x表示个体域里的所有个体x 对应日常语言中的“一切的”、“所有的”等 一元谓词F(x)个体域为D， xF(x)真值 xF(x)为真：F(a)为真，对所有aD xF(x)为假：F(a)为假，对某个aD xyG(x,y)：个体域里所有个体x,y有关系G xyG(x,y)为真：G(a,b)为真，对所有a,bD xyG(x,y)为假：G(a,b)为假，对某对a,bD

4.1 一阶逻辑命题符号化 存在量词： x表示个体域里有一个个体x 全称量词与存在量词联合 对应日常语言中的“存在”、“有一个”等 一元谓词F(x)个体域为D， xF(x)真值 xF(x)为真：F(a)为真，存在某个aD xF(x)为假：F(a)为假，对任意aD xyG(x,y)：个体域里存在个体x,y有关系G 全称量词与存在量词联合 xyG(x,y)： 个体域里任意x,存在个体y, x, y有关系G xyG(x,y)： 个体域里存在x和所有个体y都有关系G

4.1 一阶逻辑命题符号化 讨论：xF(x), xF(x), F(x)的联系、区别 F(x)是不能确定真值的谓词

4.1 一阶逻辑命题符号化 例：将下列命题符号化 凡是人都呼吸 （个体域为人类集合） F(x): x呼吸 xF(x) 有的人用左手写字（个体域为人类集合） G(x): x用左手写字 xG(x) 凡是人都呼吸（个体域为全总个体域） F(x): x呼吸, M(x): x是人 x（M(x)F(x)) 有的人用左手写字（个体域为全总个体域） G(x): x用左手写字, M(x): x是人 x(M(x)G(x))

4.1 一阶逻辑命题符号化 例：将下列命题符号化并判断真假值 所有有理数都是整数 （个体域为有理数集合） F(x): x是整数 xF(x) 所有有理数都是整数 （个体域为实数集合） F(x): x是整数, Q(x): x是有理数 x（Q(x)F(x))

4.1 一阶逻辑命题符号化 例：将下列命题符号化并判断真假值 任意x，x2-3x+2=(x-1)(x-2) （个体域为自然数集合） F(x): x2-3x+2=(x-1)(x-2) xF(x) 存在x, x+5=3 （个体域为自然数集合） G(x): x+5=3 xG(x) 任意x，x2-3x+2=(x-1)(x-2) （个体域为实数集合） 存在x, x+5=3 （个体域为实数集合）

4.1 一阶逻辑命题符号化 谓词逻辑符号化几点说明 不同的个体域，符号化形式可能不一样，命题真值也可能不同 一般默认是全总个体域，即包含一切个体 特性谓词：描述个体变元取值范围的谓词 全称量化中，特性谓词常作为蕴涵式的前件 x（M(x)F(x)) 存在量化中，特性谓词常作为合取项之一 x (M(x)G(x))

4.1 一阶逻辑命题符号化 例：将下列命题符号化并判断真假值 凡是学生都需要学习和考试 在北京工作的人未必是北京人 没有人登上过木星

4.1 一阶逻辑命题符号化 例：将下列命题符号化并判断真假值 没有人登上过木星 凡是学生都需要学习和考试 在北京工作的人未必是北京人 F(x): x是学生；G(x)：x学习；H(x)：x考试 x(F(x)  G(x)  H(x)) 在北京工作的人未必是北京人 F(x): x在北京工作；G(x)：x是北京人  x(F(x)  G(x)) x(F(x)   G(x)) 没有人登上过木星 M(x): x是人； H(x)：x登上过木星  x(M(x)  H(x))

4.1 一阶逻辑命题符号化 例：将下列命题符号化 不存在跑得同样快的两只兔子 有的兔子比所有的乌龟跑得快 尽管有些人聪明，未必所有人都聪明

4.1 一阶逻辑命题符号化 例：将下列命题符号化 不存在跑得同样快的两只兔子 有的兔子比所有的乌龟跑得快 尽管有些人聪明，未必所有人都聪明 F(x)：x是兔子，L(x,y):x和y跑得同样快  xy(F(x)  F(y)  L(x,y)) 有的兔子比所有的乌龟跑得快 F(x)：x是兔子， G(y)：y是乌龟， H(x,y):x比y跑得快 x(F(x)  y(G(y)  H(x,y))) 尽管有些人聪明，未必所有人都聪明 F(x): x是人；G(x)：x聪明 x(F(x)  G(x))   x(F(x)G(x)) x(F(x)  G(x))  x(F(x)  G(x))

4.1 一阶逻辑命题符号化 注意事项 根据命题的实际意义选取全称量词或存在量词 多个量词同时出现时，不能随意颠倒顺序 T F 符号化：对任意的x，存在着y，使得x+y=5 给定实数域 F(x,y)：x+y=5 xyF(x,y) 不同于yxF(x,y) T F

4.1 一阶逻辑命题符号化 例子 凡是人都要死 苏格拉底是人 推出：苏格拉底要死？ F(x) : x是人；G(x) : x要死 a: 苏格拉底 x(F(x)  G(x))  F(a)  G(a)

第二节：一阶逻辑公式及其解释

4.2一阶逻辑公式及其解释 一阶谓词语言ℒ的字母表 函数符号不同于谓词符号 非逻辑符号 逻辑符号 个体常项符号：a, b, c, … 函数符号：f, g, h, … 谓词符号：F, G, H, … 逻辑符号 个体变项符号：x, y, z, … 量词符号：， 联结词符号：，，，， 括号与逗号：( ，)，， 函数符号不同于谓词符号

4.2一阶逻辑公式及其解释 一阶谓词语言ℒ的项： 例：下列符号串是否为项？ 个体常项符号和个体变项符号是项 若f(x1,…,xn)是n元函数符号，t1,…,tn是n个项，则f(t1,…,tn)是项 有限次使用①，②生成的符号串才是项 例：下列符号串是否为项？ a, b x, y f(x,y)：x+y; f(a,y): a-y f(f(a,b),b)：f(a,b)+b

4.2一阶逻辑公式及其解释 一阶谓词语言ℒ的原子公式： 例：下列符号串为原子公式 F(x1,…,xn)为n元谓词符号 t1,…,tn为n个项 F(t1,…,tn)为ℒ的原子公式 例：下列符号串为原子公式 F(a, b) F(x, y) F(f(x,y),a)

4.2一阶逻辑公式及其解释 原子公式是合式公式 A为合式公式，则A是合式公式 一阶谓词语言ℒ的合式公式（谓词公式）： 原子公式是合式公式 A为合式公式，则A是合式公式 A，B为合式公式,则(AB), (AB), (AB), (AB) 为合式公式 如A是合式公式，则xA, xA也是合式公式 只有有限次应用1-4构成的符号串才是合式公式

4.2一阶逻辑公式及其解释 例子 F(a, b) F(a, b)G(x,y) F(a, b) xG(x,y) x(F(a, b)G(x,y)) (y)(x)(G(x,y))

4.2一阶逻辑公式及其解释

4.2一阶逻辑公式及其解释 辖域：紧接在量词后面括号内的合式公式 自由变元与指导变元 闭式（封闭公式）：不含自由出现的个体变项的公式 x P(x)，x (P(x) Q(x)) x M(x)  D(x) 自由变元与指导变元 指导变元：出现在量词x, x辖域内的变元x 自由变元：非约束出现的变元 闭式（封闭公式）：不含自由出现的个体变项的公式

4.2一阶逻辑公式及其解释 例：指出下列公式中的指导变元，各量词的辖域，自由出现和约束出现的个体变项 F(a, b)xG(x,y) x(F(a, b)G(x,y)) x(F(a, x))y(G(x,y)H(z))

4.2一阶逻辑公式及其解释 如何赋予合式公式含义？ 定义域 函数变项需要指定具体函数 谓词变项需要指定具体谓词

4.2一阶逻辑公式及其解释 例：xy(F(x)  F(y)  G(f(x,y), g(x,y))) 定义域：全总个体域 函数变项需要指定具体函数 f(x,y)：x+y g(x,y)：xy 谓词变项需要指定具体谓词 F(x)：x是实数 G(x,y)：x=y 任意x, y，如果x, y是实数，则x+y=xy

4.2一阶逻辑公式及其解释 解释：非逻辑符号集L生成的一阶语言ℒ，ℒ的解释I由4部分组成 非空个体域DI I将任意一个个体常项符号aL映射到DI上的个体a* I将任意一个n元函数fL映射到DI上的n元函数f*: (DI)n  DI I将任意一个n元谓词FL映射到DI上的n元关系RF

4.2一阶逻辑公式及其解释 公式A在I下的解释AI： 取个体域DI A中个体常项符号aL替换为DI上的个体a* A中的n元函数fL替换为DI上的n元函数f*: (DI)n  DI A中n元谓词FL替换为DI上的n元关系RF

4.2一阶逻辑公式及其解释 给定解释I 给出下列公式在I下的解释，讨论真假值 个体域为自然数集N a* = 2 f* =x+y, g* =xy F*：x=y 给出下列公式在I下的解释，讨论真假值 x F(g(x, y), z) x (F(g(x, a), x)F(x, f(x,a))) x F(g(x, a),x)  F(x,y)

4.2一阶逻辑公式及其解释 x F(g(x, y), z) x (F(g(x, a), x)F(x, f(x,a))) 给定解释I 个体域为自然数集N a* = 2 f* =x+y, g* =xy F*：x=y 给出下列公式在I下的解释，讨论真假值 x F(g(x, y), z) x (xy=z) x (F(g(x, a), x)F(x, f(x,a))) x ((2x=x)(x=x+2)) x F(g(x, a),x)  F(x,y) x (2x=x)  x=y

4.2一阶逻辑公式及其解释 合式公式分类：公式A 重言式(永真式)：A在任意的解释下为真 矛盾式(永假式)：A在任意的解释下为假

4.2一阶逻辑公式及其解释 代换实例 给定命题公式A0，含命题变项p1,…,pn A1,…,An是n个谓词公式 A称为A0的代换实例, 如果 A通过用Ai代替A0中的pi得到

4.2一阶逻辑公式及其解释 定理：重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式 证明思路：给定重言式A0 ，对于命题变项p1,…,pn的任意赋值，A0都为真 例：已知p(qp)为重言式，那么 F(x)(G(x)F(x))是否是重言式？ x(F(x)(G(x)F(x)))呢？

4.2一阶逻辑公式及其解释 例：判断下列公式类型 x F(x) x F(x) x (F(x)  G(x))  (xF(x)  yG(y))  yG(y)

4.2一阶逻辑公式及其解释 例：判断下列公式类型 x F(x) x F(x) 永真式 x (F(x)  G(x)) 对任意解释I，如果I使得x F(x)为真，对任意xDI，F(x)为真，I必使得x F(x)为真 x (F(x)  G(x)) 解释I： DI 为实数集R F(x): x是整数；G(x): x是有理数  (xF(x)  yG(y))  yG(y) 是  (p  q)  q 的代换实例 永真式 可满足式 矛盾式

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

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

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

练习2 2. 在一阶逻辑中将下列命题符号化 (1) 大熊猫都可爱 (2) 有人爱发脾气 (3) 说所有人都爱吃面包是不对的 2. 在一阶逻辑中将下列命题符号化 (1) 大熊猫都可爱 (2) 有人爱发脾气 (3) 说所有人都爱吃面包是不对的 (4) 没有不爱吃糖的人 (5) 任何两个不同的人都不一样高 (6) 不是所有的汽车都比所有的火车快 44

练习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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) (2) xy(F(f(x,a),y)F(f(y,a),x)) (3) xyzF(f(x,y),z) (4) xyzF(f(y,z),x) (5) xF(f(x,x),g(x,x)) 47

练习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)) (2) xy(F(x)G(y)H(x,y)) 50

练习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) (2) x(F(x)(F(x)G(x))) 52

练习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))恒为真

作业 1 4 5 10 11