1. 1 形式系统--集合 复习.pptVIP

可推导性关系 演绎推理 由前提的真，可得结论的真 前提与结论存在可推导性关系 研究对象：怎样的前提和结论存在可推导性关系？ 可推导性关系的内因 表象：前提、结论的真值 语义范畴 内因：前提、结论的逻辑形式 语法范畴 数理逻辑的研究内容 形式语言 无二义性、精确的、普遍适用的符号语言 自然语言存在二义性、不精确 语义：涉及符号、表达式的具体涵义 语法：仅涉及表达式的形式结构 形式语言中用符号构成公式.公式来表示命题. 形式语言中的公式能够精确地表示命题的逻辑形式. 等价类 设R为S上的一个等价关系，则对于任意x∈S，称集 [x]R ={y ∈S |y,x∈R} 称为x的R等价类。 R等价类作为S的一个划分. R等价类两两不相交，他们的并是S. 等价类的性质 ∪[x]R=S [x1] R ∪ [x2] R ∪ ∪ [xn] R [x]R=[y]R iff xRy. [x]R≠Ф 归纳定义和归纳证明 一个集合的归纳定义(inductive definition)通常分为三步： 归纳基：一些基本的元素属于该集合； 归纳步：定义一些规则(或者说操作), 从该集合中已有的元 素来生成该集合的新的元素； 最小化：该集合中的所有元素都是通过基本元素以及所定义的规则生成的,换句话说,该集合是由基本元素及规则所生成的最小的集合. 自然数集 N 的归纳定义： 1. 归纳基：0 是一个自然数，即0∈N。 2. 归纳步：若n 是自然数，则n 的后继也是自然数。记n 的后继为succ(n)，即若n∈N，则succ(n)∈N。为方便起见，后面也记n 的后继为n+1。 3. 最小化：所有的自然都通过步骤1和2得到,或者说自 然数集是通过步骤1和2得到的最小集合。 * ·形式语言的语法(Syntax)与语义(Semantic)： · 形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。 ·形式语言的语义是关于形式系统的解释和意思。 ·形式语言本身没有含义，但我们在构造它们时是假想它们能代表某种意义的，特别的当我们在选择形式系统的公理时，总是选择所研究的问题域中那些最为明显或最容易公认为正确的性质。 *