第四章一阶逻辑基本概念.ppt

第四章:一阶逻辑基本概念 本章的主要内容 一阶逻辑命题符号化 一阶逻辑公式、解释及分类 本章与其他章的联系 克服命题逻辑的局限性 是第五章的先行准备 4.1 一阶逻辑命题符号化 例：将下列命题符号化并判断真假值 凡是学生都需要学习和考试 在北京工作的人未必是北京人 没有人登上过木星 4.1 一阶逻辑命题符号化 例：将下列命题符号化 不存在跑得同样快的两只兔子 有的兔子比所有的乌龟跑得快 尽管有些人聪明，未必所有人都聪明 4.1 一阶逻辑命题符号化 例子 凡是人都要死 苏格拉底是人 推出：苏格拉底要死？ F(x) : x是人；G(x) : x要死 a: 苏格拉底 ?x(F(x) ? G(x)) ? F(a) ? G(a) 4.2一阶逻辑公式及其解释 作业 1 4 5 10 11 * * * * * 例：?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 个体域为自然数集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一阶逻辑公式及其解释 给定解释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在任意的解释下为假 可满足式： 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) 对任意解释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 的代换实例 永真式 矛盾式 可满足式 4.2一阶逻辑公式及其解释 第四章 习题课 主要内容 个体词、谓词、量词 一阶逻辑命题符号化 一阶语言L 项、原子公式、合式公式 公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释 公式的类型 永真式(逻辑有效式)、矛盾式(永假式)、可满足式 基本要求 准确地将给定命题符号化 理解一阶语言的概念 深刻理解一阶语言的解释 熟练地给出公式的解释 深刻理解永真式、矛盾式、可满足式的概念, 会判断简