绪论_第一章课件.ppt

高级数理逻辑 计算机学院 曲日 quri@tju.edu.cn 涉及的数学分支 证明论 模型论 递归论 集合论 推演系统 概述 数理逻辑的含义 用数学的方法研究逻辑问题 逻辑的核心内容 推理理论：本书仅仅研究演绎（有效）推理 演绎推理 前提与结论存在可推导性关系 由前提的真，可得结论的真 怎样的前提和结论存在可推导性关系？ 例子 所有3的倍数的数字之和是3的倍数。 1010的数字之和不是3的倍数。 1010不是3的倍数。 所有中学生打网球。 王君不打网球。 王君不是中学生。 可推导性关系的内因 表象：前提、结论的真值 语义范畴 内因：前提、结论的逻辑形式 语法范畴 两个例子的逻辑形式相同 S中的所有元有R性质。 a没有R性质。 a不是S中的元。 数理逻辑的研究内容 形式语言 无二义性、精确的、普遍适用的符号语言 自然语言存在二义性、不精确 语义：涉及符号、表达式的具体涵义 语法：仅涉及表达式的形式结构 推理演算 历史 公元前3世纪，Aristotle创立了逻辑学。 数理逻辑是数学的基础问题。 17世纪，Leibniz提出建立形式语言、推理方法的思想，以解决数学证明等问题的一致性问题。 1847年，Bool发表了《逻辑的数学分析》，建立了布尔代数，初步创建了符号系统。 1887年，Frege出版了《数论基础》，成功的实现了Leibniz的思想。 1928年，Hilbert提出4个急需解决的数理逻辑问题。 从1929年开始的短时期内，Godel全部解决了这四个问题。 课程的主要内容 经典逻辑 命题逻辑 谓词（一阶）逻辑 非经典逻辑 构造型逻辑 模态逻辑 集合论 19世纪下半叶，Cantor提出朴素集合论 1903年，Russel提出集合论悖论，产生数学的第三次危机 1908年，Zermelo提出公理化集合论(ZF体系) 集合论 集合论是数学的基石之一 基本概念 集合元素 序偶笛卡尔积 关系 映射 等价关系 相容关系 序关系 集合元素 若干事物组成的整体被称为集合，集合中的每个事物被称为元素。 元素a属于集合A，记为 在确定性数学中， 集合的表示方法 枚举法 谓词法 归纳法 元素的一些说明 无序性 {a, b} = {b, a} 可区分 {a, b} = {a, a, b} 或具体或抽象 {1, 2, , *, 天津大学, CMU} 或有联系或无联系 特别的，集合的元素可以是一个集合 {{1, 2}, 1, 2} 集合悖论 Russel（理发师）悖论 某城市中有一位理发师，他的招牌是这样写的：“本人将为本城所有不给自己刮脸的人刮脸，且只给这些人刮脸。” 这位理发师能不能给他自己刮脸呢？ 如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。 ZF公理体系 外延公理 子集公理 空集存在公理 存在一个没有任何元素的集合 幂集公理 集A的幂集P(A) = {a | a为A的子集} 集合的运算 对于集S，T 并 交 差补 E为全集 对称差 序偶笛卡尔积 序偶 集合{a, {a, b}}称为元素a与b构成的序偶，简记为a, b。 a, b = x, y iff a=x且b=y 笛卡尔积 扩展(n2) 有序n元组 a1, a2, …, an= a1, a2, …, an-1 , an n阶笛卡尔积 关系 R是从集S到集T的一个二元关系 iff R是集S上的一个二元关系 iff 几个特殊关系 从集S到集T的全域关系 空关系 集S上的恒等关系 关系的表示 关系矩阵 关系图 关系的运算 定义域（前域）、值域、域 设R是由A到B的一个二元关系，则 dom(R) = {x|存在y∈B，使得x,y∈R}称为R的定义域； ran(R) = {y|存在x ∈A，使得x,y∈R}称为R的值域； FLD(R) = dom(R) ∪ran(R)称为R的域。 复合关系 设R是由A到B的一个二元关系，S是由B到C的一个二元关系，则 R?S={x,z|存在y ∈B，使得x,y∈R且y,z∈S}称为R与S的复合关系 逆关系 设R是由A到B的一个二元关系，则 R-1= {y,x|x,y∈R} 称为R的逆关系。 关系的性质 设R是A上的一个二元关系 自反 R在A上自反，iff 对于任何x ∈A，xRx。 对称 R在A上对称，iff 对于任何x ,y∈A，若xRy，则yRx。 传递 R在A上传递，iff 对于任何x ,y,z∈A，若xRy且yRz，则xRz。 反自反 反对称 等价关系 等价关系 若R在A上自反、对称、传递，则称R为A上的一