北京大学：《离散数学》系列课程之一《集合论与图论》第2讲 一阶逻辑基础

第2讲一阶逻辑基础 内容提要 1.量词、谓词、个体词、命题符号化 2.合式公式、解释、永真式 3.一阶逻辑等值式 癱4.一阶逻辑推理规则 《集合论与图论》第2讲

《集合论与图论》第2讲 1 第2讲 一阶逻辑基础 内容提要 1. 量词、谓词、个体词、命题符号化 2. 合式公式、解释、永真式 3. 一阶逻辑等值式 4. 一阶逻辑推理规则

阶逻辑的字母表 眷个体常项:a,b,C,…,a1b1,C1灬 秦个体变项:X,y,2,…,X1y1,21 鲁函数符号:fg,h,…,f191 谓词符号:F,G,H,…,F1,G1,H 秦量词符号:彐, 秦联结词符号:-,,V,→,台 括号与逗号:(), 《集合论与图论》第2讲

《集合论与图论》第2讲 2 一阶逻辑的字母表 个体常项: a, b, c, …, a1, b1, c1,… 个体变项: x, y, z, …, x1, y1, z1,… 函数符号: f, g, h, …, f1, g1, h1,… 谓词符号: F, G, H, …, F1, G1, H1, … 量词符号: ∃, ∀ 联结词符号: ¬, ∧, ∨, →, ↔ 括号与逗号: (, ), ，

胃词( predicate) 词:表示性质、关系等;相当于句子 中的谓语。 用大写英文字母F,G,H,…,后跟括号与变 元来表示。例如 F(x):X是人。 G(xy):X与y是兄弟。 n元谓词:含有n个变元。例如 F(x)是一元谓词,Gxy)是二元谓词 《集合论与图论》第2讲

《集合论与图论》第2讲 3 谓词(predicate) 谓词：表示性质、关系等；相当于句子 中的谓语。 用大写英文字母F,G,H,…,后跟括号与变 元来表示。例如： F(x): x是人。 G(x,y): x与y是兄弟。 n元谓词：含有n个变元。例如： F(x)是一元谓词， G(x,y)是二元谓词

量词( (quantifier 全称 (universal)量词:V 所有的”,“全部的, 存在( existential)量词:彐 有一些的,“某些的” 唯一 (unique)存在量词:! 恰好存在一个” 《集合论与图论》第2讲

《集合论与图论》第2讲 4 量词(quantifier) 全称(universal)量词: ∀ “所有的”, “全部的”,… 存在(existential)量词: ∃ “有一些的”, “某些的”,… 唯一(unique)存在量词: ∃! “恰好存在一个”

量词(举例) 鲁设:F(X):X是自然数。G(x):X是偶数。 H(x):x是奇数。(xy):x=y。 “有些自然数是偶数"。彐x((X)AG(x) 既有奇数又有偶数”。彐xH(x)^三yG(y) 存在既奇又偶的数”。彐X(H(x)G(×) “存在唯一的自然数0。3X(F(×)1(x,0) 《集合论与图论》第2讲

《集合论与图论》第2讲 5 量词(举例) 设：F(x)：x是自然数。G(x)：x是偶数。 H(x) ： x是奇数。 I(x,y)：x=y。 “有些自然数是偶数”。 ∃x(F(x)∧G(x)) “既有奇数又有偶数” 。∃xH(x)∧∃yG(y) 存在既奇又偶的数” 。∃x(H(x)∧G(x)) “存在唯一的自然数0”。 ∃!x(F(x)∧I(x,0))

个体常项( constant) 婚表示具体的特定对象 用小写英文字母a,b,c,来表示 癱例如:a:王大明,b:王小明, G(xy):×与y是兄弟, “王大明与王小明是兄弟:G(ab) 《集合论与图论》第2讲

《集合论与图论》第2讲 6 个体常项(constant) 表示具体的特定对象 用小写英文字母a,b,c,…来表示 例如： a:王大明，b:王小明， G(x,y): x与y是兄弟, “王大明与王小明是兄弟”: G(a,b)

个体变项( varible) 表示不确定的泛指对象 用小写英文字母xy,z…来表示 例如:F(×)x是人。G(x):X是数。 “存在着人”:彐XF(x) 仅有一人:3xF(x) 万物皆数;xG(x) 《集合论与图论》第2讲

《集合论与图论》第2讲 7 个体变项(varible) 表示不确定的泛指对象 用小写英文字母x,y,z,…来表示 例如： F(x): x是人。G(x): x是数。 “存在着人”: ∃xF(x) “仅有一人”: ∃!xF(x) “万物皆数”: ∀xG(x)

合式公式(举例) 彐X((X)∧y(G(y)-)H(Xy) F(f(a, a), b) 约定:省略多余括号 最外层 优先级递减:彐,V;v;∧,V;→,→ 《集合论与图论》第2讲

《集合论与图论》第2讲 8 合式公式（举例） ∃x(F(x)∧∀y(G(y)→H(x,y))) F(f(a,a),b) 约定：省略多余括号 最外层 优先级递减： ∃, ∀; ¬; ∧,∨; →,↔

命题符号化 个体域( scope):个体词的取值范围,缺省 (deau.用全总个体域 全总个体域:世界上的万事万物 特性谓词:表示所关注的对象的性质 两种模式 X(M(×)→>G(×) 彐x(M(X)^G(x) 其中M)是特性谓词。 《集合论与图论》第2讲

《集合论与图论》第2讲 9 命题符号化 个体域(scope): 个体词的取值范围, 缺省 (default)采用全总个体域. 全总个体域: 世界上的万事万物 特性谓词: 表示所关注的对象的性质 两种模式: ∀x(M(x)→G(x)) ∃x(M(x)∧G(x)) 其中M(x)是特性谓词。

命题符号化(举例 例:“有些人是要死的” 癱解1:采用全总个体域 设:F(x):X是人;G()X是要死的 原命题符号化成:彐X(F(×)AG(x) 解2:采用全体人作为个体域 设:G(x):X是要死的. 原命题符号化成:彐XG(x 《集合论与图论》第2讲

《集合论与图论》第2讲 10 命题符号化(举例) 例: “有些人是要死的”. 解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: ∃x(F(x)∧G(x)) 解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: ∃xG(x)