面向计算机科学的数理逻辑复习.doc

绪论 一、数理逻辑研究什么？ ★ 研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的 二、数理逻辑如何研究？ ★ 形式语言 第一章 预备知识 第一节 集合 一、集合 1、 集合的内涵和外延（所有元素的共同性质/构成集合的所有元素） 2、 有序偶和笛卡儿集 二、关系 1、 概念：集合S上的n元关系R 2、 特殊情况：集合S上的一元关系R（集合S上的性质R） 三、函数（映射） 1、 概念：函数（集合＋有序偶＋性质）、定义域dom（f）、值域ran（f） 2、 概念：f（x）（函数f在x处的值） 3、 概念：f：S－T（函数f是由S到T的映射）、满射、一一映射 四、等价 1、 概念：关系R是集合S上的等价关系（自反＋对称＋传递） 2、 概念：元素x的R等价类 3、 性质：R等价类对集合S的一个划分（两两不相交，且并为S） 五、基数 1、 概念：S～T（两个集合S和T是等势的） 2、 概念：集合S的基数|S|（集合中的元素个数） 3、 概念：可数无限集  第二节 归纳定义和归纳证明 一、归纳定义 1、 集合的归纳定义 ⑴、直接生成某些元素 ⑵、给出运算，将其作用在已有元素上，以产生新的元素 ⑶、只有这样才是集合中的元素，除此之外，再也没有了 2、 典例：自然数集N的两个归纳定义 二、归纳证明 1、 归纳定理：设R是一个性质，如果 ⑴、R（0） ⑵、对于任何n∈N，如果R（n），则R（n’） 那么，对于任何n∈N，都有R（n） 2、概念：归纳基础、归纳步骤（包括归纳变元和归纳假设）、归纳命题、归纳证明 3、概念：串值归纳法及其变形 三、递归定义 1、 递归定义（在归纳定义的集合上，定义函数） 在自然数集N上定义一个这样的函数f：g，h是N上的已知函数 f（0） ＝g（0） f（n’）＝h（f（n）） 2、 递归定义原理（这样的函数是存在而且唯一的） 第二章 经典命题逻辑 第一节 联结词 一、基本概念 1、 概念：命题（陈述句+确定值）（要么是真，要么是假） 2、 概念：简单命题和复合命题（区分的关键） 3、 小结：只考虑复合命题的真假是如何确定的 二、联结词 1、 非A： 2、 A与B：A为真并且B为真 3、 A或B：A为真或B为真（A为真或B为真或AB同时为真） 4、 A蕴涵B：如果A真，则B真（并非A假B真） 5、 A等值于B：如果A蕴涵B，同时B蕴涵A 第二节 命题语言 一、基本概念 1、 概念：命题语言（命题逻辑使用的形式语言） 2、 归纳：命题语言的三类符号（命题符号＋联结符号＋标点符号） 3、 概念：表达式、长度、空表达式、两个表达式相等 4、 概念：段、真段、初始段、结尾段 二、基本概念 1、 定义：原子公式，记为Atom（LP）（单独一个命题符号） 2、 定义：公式，记为Form（LP）（经典归纳定义及其两种变形） ★ 经典定义容易理解，然而两种变形更容易使用 3、 定理：如何证明LP的所有公式都满足R性质？ ★ 关键：假设S={A∈Form（LP）| R（A）} 4、 概念：对公式的结构做归纳（上述归纳证明） 三、习题解析 1、 关键：利用二叉树表示公式的生成过程 2、 关键：蕴涵有多种不同的叙述方式（关键：分清楚充分条件和必要条件） ⑴、◆如果p，则q ⑵、◆只要p，则q ⑶、◆p仅当q ⑷、◆只有p，才q ⑸、◆除非p，否则q（思路：想方设法转化为上述情形） 第三节 公式的结构 一、引理 1、 引理1：LP的公式是非空的表达式 2、 引理2：在LP的每个公式中，左括号和右括号出现的数目相同 3、 引理3：真初始段不是公式（在LP的公式的任何非空的真初始段中，左括号出现的次数比右括号多。因此，LP的公式的非空的真初始段不是LP的公式（同理分析真结尾段）） 二、定理 1、 定理：LP的每个公式恰好具有以下6种形式之一；并且在各种情形中，公式所具有的那种形式是唯一的 ★ 注意：仔细分析其证明过程 2、 推论：LP的公式的生成过程是唯一的 3、 概念：否定式、合取式、析取式、蕴涵式、等值式 三、辖域 1、 概念：辖域、左辖域、右辖域 2、 定理：任何A中的任何辖域存在并且唯一 3、 性质：如果A是B中的段，则A中的任何联结符号在A中的辖域和它在B中的辖域是相同的 4、 定理：如果A是（?B）的段，则A＝（?B）或者A是B中的段；如果A是（B*C）中的段，则A＝（B*C）或者A是B或C中的段 四、其它 1、 算法：判断一个LP的表达式是不是公式的算法 2、 符号的省略：最外层括号＋其它形式的括号＋联结符号的优先级 五、习题解析 ?  第四节 语义 一、基本概