第2讲 一阶逻辑基础 北京大学计算机系离散数学讲义(ppt版)幻灯片课件.pptVIP

《集合论与图论》第2讲 量词否定等值式(举例) ? ?? ?N ?n ( nN → |an-a|? ) a1,a2,a3,…,aN ,aN+1,aN+2 ,…,an ,… ? ? a ? ? 量词否定等值式(举例、续) ? ? ???? ?N ?n ( nN → |an-a|? ) ? ????N ?n ( nN → |an-a|? ) ? ?? ?N??n ( nN → |an-a|? ) ? ?? ?N ?n?( nN → |an-a|? ) ? ?? ?N ?n?( ?nN∨ |an-a|? ) ? ?? ?N ?n ( nN ∧ ? |an-a|? ) ? ?? ?N ?n ( nN ∧ |an-a|?? ) 量词辖域收缩与扩张(?) ?x(A(x)∨B) ? ?xA(x)∨B ?x(A(x)∧B) ? ?xA(x)∧B ?x(A(x)→B) ? ?xA(x)→B ?x(B→A(x)) ? B→?xA(x) 说明: B中不含x的出现 例1: ?x(F(x)∨G(y)) ? ?xF(x)∨G(y) 例2: ?x?y(F(x)∧G(y)) ??x(F(x)∧?yG(y)) ? ?xF(x)∧?yG(y) * * 第2讲 一阶逻辑基础 内容提要 1. 量词、谓词、个体词、命题符号化 2. 合式公式、解释、永真式 3. 一阶逻辑等值式 4. 一阶逻辑推理规则 一阶逻辑的字母表 个体常项: 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(x,y): x与y是兄弟。 n元谓词：含有n个变元。例如： F(x)是一元谓词， G(x,y)是二元谓词 量词(quantifier) 全称(universal)量词: ? “所有的”, “全部的”,… 存在(existential)量词: ? “有一些的”, “某些的”,… 唯一(unique)存在量词: ?! “恰好存在一个” 量词(举例) 设：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)) 合式公式（举例） ?x(F(x)??y(G(y)?H(x,y))) F(f(a,a),b) 约定：省略多余括号 最外层 优先级递减： ?, ?; ?; ∧,∨; →,? 命题符号化 个体域(scope): 个体词的取值范围, 缺省(default)采用全总个体域. 全总个体域: 世界上的万事万物 特性谓词: 表示所关注的对象的性质 两种模式: ?x(M(x)?G(x)) ?x(M(x)?G(x)) 其中M(x)是特性谓词。 命题符号化(举例) 例: “有些人是要死的”. 解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: ?x(F(x)?G(x)) 解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: ?xG(x) 命题符号化(举例、续) 例: “凡人都是要死的”. 解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: ?x(F(x)?G(x)) 解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: ?xG(x) 命题符号化(举例、续) 例: “存在最小