一阶逻辑的语言和语义一些重要的元定理

Size: px

Start display at page:

Download "一阶逻辑的语言和语义一些重要的元定理"

徐管
5 years ago
Views:

1 一阶逻辑初步哲学数学计算机中的逻辑课程年秋王彦晶北大哲学系年月日

2 一阶逻辑的语言和语义一些重要的元定理

3 一阶逻辑的语言和语义

4 一阶逻辑的语言有很多个先确定一个符号表变元符号,... 常元符号,... 谓词符号,... 每个有一个相应的元数函数符号,... 每个有一个相应的元数给定这个符号表带等词的一阶逻辑的语言定义为项 ::= ( ) 公式 φ ::= φ (φ φ) φ 可以定义为例如 () () (, ) 等等有时也用!φ 表示 φ() (φ() φ() ) (() () (((() () (, ) ( () () (, )) 托尔斯泰

5 变元的约束一个公式里某个变元的某次出现不在任何一个量词的辖域里则称其是自由的 (, ()) (, ) 里第二个和第一个是自由的直观上讲该公式可以等价的写成 (, ()) (, ) 变元易字开公式有变元自由出现的闭公式没有自由出现的

6 年前为真的例子为了简化怎么让计算机理解和推理周迅的前男友窦鹏是窦唯的堂弟 ; 窦唯是王菲的前老公 ; 周迅的前男友宋宁是高原的表弟 ; 高原是窦唯的前任老婆 ; 周迅的前男友李亚鹏是王菲的现任老公 ; 周迅的前男友朴树的音乐制作人是张亚东 ; 张亚东是王菲的前老公窦唯的妹妹窦颖的前老公, 也是王菲的音乐制作人 ; 张亚东是李亚鹏前女友瞿颖的现男友请问下列说法不正确的是 : 王菲周迅是情敌关系 ; 瞿颖王菲是情敌关系 ; 窦颖周迅是情敌关系 ; 瞿颖周迅是情敌关系谓词前亲密关系现亲密关系一种情敌关系可被定义为 (, ) := (((, ) (, )) ((, ) (, )))

7 年前的例子为了简化贵圈真乱只能用父子关系谓词兄弟关系谓词前任函数父亲函数年纪函数以及大小谓词 < 怎么写周迅的前男友是王菲的前老公的堂弟 (((, (( ))) (, (( ))) (( )) < (( )) 进一步可以采用更基本的性别谓词手足谓词父母子女谓词年龄函数及大小谓词定义所有的关系如爸爸是你父母中的男性等

8 例子一阶算数的语言符号表 (, <,, +, ) 是一个常元 < 是二元谓词符号小于是后继函数符号表示自然数如表示 + 是二元函数符号加是二元函数符号乘能表达的举例不是任何自然数的后继任何数加还是其本身 ( + ) 一个数加另外一个数的后继等于这两个数的和的后继 (( + ) ( + )) 是素数 < ( < < )) 对 φ() 的数学归纳法 φ() (φ() φ(())) φ() 有谓词变元并对其做量化的是二阶语言可表达更一般的数学归纳法 (() (() (()) ())

9 定理的简单证明两个人的有穷深度的完美信息的总有输赢的博弈必有一个玩家有必胜策略我们之前是通过画出有穷树从底下一点点做标注证明的其实还有更简单的证明假设游戏深度为什么叫玩家有必胜策略 (,,, ) 什么叫第一个游戏者没有必胜策略 (,,, ) 根据和的关系等价于 : (,,, ) 因为这是输赢游戏游戏结束时不是你赢就是我赢所以 (,,, ) 这就在说玩家有必胜策略

10 一阶逻辑的结构与模型给定具体的一阶逻辑语言它的一个结构 A =, 是一个非空的个体域或论域也记为 A 是对常元符号谓词符号函数符号的解释给每个常元符号一个里的个体也记为 A 给每个元谓词符号一个上的元关系也记为 A 给每个元函数符号一个上的元函数也记为 A 一个模型 M 是一个结构加一个指派 A, σ 指派 σ 告诉我们变元们指的是个体域里的哪个东西如果我们只关心没有自由变元的句子的真假为啥还要指派用于语义定义

11 一阶逻辑的语义给定一个模型 M = A, σ 可以给所有的项解释了解释成个体可以推广 σ 的定义域到所有项本来只对们 σ() = A σ(( )) = A (σ( ),... σ( )) 语义定义在模型 M = A, σ 上 A, σ σ() = σ( ) A, σ ( ) (σ( ),, σ( )) A A, σ φ A, σ φ A, σ φ ψ A, σ φ 且 A, σ ψ A, σ φ 对所有的 A A, σ[ ] φ σ[ ] 就是改变 σ 对的解释为其他不变可以定义有效式为在任何模型上都为真的公式如 φ φ 但是反过来可不有效

12 给定结构和指派对一阶逻辑公式 φ 我们可以玩一个游戏给定结构 A 和指派 σ 游戏者支持者和反对者游戏的状态 η, ψ 其中 η 是一个指派 ψ 是 φ 的子公式初始状态是 σ, φ 游戏的规则首先断言公式 φ 在 A, σ 上是真的如果当前公式是 ψ ψ 则可以选择 ψ 或 ψ 其中一个继续如果当前公式是 ψ 则和的角色互换从 ψ 继续如果当前公式是 ψ 则选择一个 A 并且改变游戏状态为 σ[ ], ψ 继续游戏的输赢条件状态是 η, ψ ψ 是原子公式且 A, η ψ 则当前的赢反之则当前的赢可以证明 A, σ φ 在相应的游戏里有一个必胜策略

13 的非完美信息玩家不一定知道其所在的游戏状态 (, ) (, ) (, ) (, ) (, ) (, ) = 有效.. / = 不有效量词为啥一定要线性排序 / = 说的选择不依赖于可以用这样的游戏给这样的公式三值语义有必胜策略就是真有必胜策略就是假也可能两个人都没有必胜策略这时公式就既不真也不假

14 模态逻辑的真值游戏给定点模型和 φ 游戏者支持者和反对者游戏的状态, ψ 其中在 M 中 ψ 是 φ 的子公式初始状态是, φ 游戏的规则首先断言公式 φ 在 M, 上是真的如果当前公式是 ψ ψ 则可以选择 ψ 或 ψ 其中一个继续如果当前公式是 ψ 则和的角色互换从 ψ 继续如果当前公式是 ψ 则选择一个使得并且改变游戏状态为, ψ 继续游戏的输赢条件状态是若 () = 则当前的赢反之则当前的赢可以证明 M, φ 在相应的游戏里有一个必胜策略

15 从一阶逻辑的角度看模态逻辑 M, φ 对所有的如果则 M, φ 按照模态词的语义相对于可以看成一阶公式 ( ) 其中是一个二元谓词是一个一元谓词克里普克模型 {,, } 可以看成是特殊的一阶结构是个体域这个二元关系是的解释 () 是的解释可以证明所有模态逻辑公式 φ 都可以翻译成这样语言下的一阶逻辑公式 (φ) 使得对任意克里普克点模型 M, M, φ M, σ[ ] (φ) 证明了模态逻辑恰好是一阶逻辑在互模拟关系下保持真值的片段不过在谈论框架的意义上二者的表达能力不可比较为什么

16 一些重要的元定理

17 重要的元理论结果演绎定理紧致性定理相对于特定推理系统的可靠性与完全性定理与模态逻辑的区别没有有穷模型性只有无穷模型如 () ( ) 同构比互模拟严格得多保持一阶逻辑闭公式的真值但反过来很不对例如有与自然数算数结构 (N,,, <, +, ) 不同构的但满足同样一阶闭公式的非标准模型定理大致语句集有无穷模型则有任意大的无穷模型总可以加些东西 {,, N}

18 一阶逻辑的推理系统规则就是一条分离规则公理命题逻辑的三条公理模式 φ φ[/] 用统一替代 φ 的要对在 φ 中代入自由见下面的直观想法 φ φ 在 φ 中不自由的出现 (φ ψ) φ ψ 类似于模态逻辑公理 ( ) ( ) ( )) ( ) (( ) ( )) 对上面的公理模式 φ 做任意全称概括得到的 φ 类似模态逻辑必然化规则这与上面的 φ φ 不一样 ( ) 这时不能用去替换 ( ) 里的会得到 ( ) ( ) 对在里代入不自由

19 完全性定理的思路完全性 Γ φ = Γ φ 把完全性转化为一致的公式集可满足语形到语义给个一致的公式集补完它的信息极大一致集然后根据这个集合去造模型对 φ() 这样的公式找到实例在语言里加一堆新的常项补上公式 φ() φ() 扩充成极大一致集相对于新的大语言这本质上消去了不好处理的量词根据这个极大一致集造模型结构指派个体域是大语言里所有项的集合谓词解释成 {(, ) 类似处理函数符号常项解释成自己指派变元给自己处理等词相关的麻烦考虑项的等价类作为新的个体域证明我们造的东西是新语言极大一致集的模型证明新语言的极大一致集中的老语言的部分还是一致的忽略新语言相关的部分得到老语言一致集的模型

20 判定性问题问题任给一个公式是不是有一种一步步的机械可操作的办法一定在有穷步之内判定这个公式是不是有效式放之四海模型皆准对于有经典否定词的逻辑问这个问题等价于问任意一个公式是不是可以被满足 φ 有效 φ 不可被满足而且 φ 可满足 φ 不有效命题逻辑和模态逻辑公式的有效性或可满足性都是可判定的那一阶逻辑呢如果可以判定那很大多数数学家理论上就可以休息了用有穷多个公理表示数学理论然后判断这些公理是否蕴含某个特定结论可惜一阶逻辑是不可判定的但怎么证明不可判定性

21 要定义机械可操作的边界最直观的图灵机一个抽象的机器它有有穷多个内在的状态可以读写一个两边无穷长的纸带上的有穷多种符号并且根据一些规则该变读写头的位置改变内部状态等抽象的说, Σ, δ 是有穷多个状态的集合 Σ 有穷多个能读写的符号的集合 δ 是有穷多个状态转换的指令集具有如下形式, Σ 内在状态的时候如果读就擦掉写改变状态到以方式动作读写头可以是不动可以左移或者右移可要求至多只有一个指令以开头确定性图灵机除此之外有一个初始状态开始时读写头在左起第一个有字符的格子上如果到某个时候没有指令可做了就停了如果最后停在一些特殊状态称为接收状态上则称接收纸带上最开始的字符串

22 例子自己试试看

23 祝大家圣诞快乐

数理逻辑 I Mathematical Logic I

数理逻辑 I Mathematical Logic I 前情提要前情提要我们定义了两种可定义概念结构内的可定义性 : 给定结构关于该结构论域上的 k 元关系的性质由一个公式定义定义结构类 : 给定语言关于该语言的结构类的由一则闭语句定义 ( 初等类 ); 由一集闭语句定义 ( 广义初等类 ) 前情提要我们定义了两种可定义概念结构内的可定义性 : 给定结构关于该结构论域上的 k 元关系的性质由一个公式定义定义结构类 : 给定语言关于该语言的结构类的由一则闭语句定义

一阶逻辑的语言和语义 一些重要的元定理

一阶逻辑的语言和语义一些重要的元定理