绪论
一、数理逻辑研究什么？
★ 研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的
二、数理逻辑如何研究？ ★ 形式语言
第一章 预备知识
第一节 集合
一、集合
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、 符号的省略：最外层括号＋其它形式的括号＋联结符号的优先级
五、习题解析 ?
第四节 语义
一、基本概念
1、 概念：真假赋值
2、 概念：公式的真假值AV（真假赋值v给公式A指派的真假值＋递归定义） 3、 定理：对于任何A∈Form（LP）和任何真假赋值V，AV∈{0，1} ★ 关键：如何证明LP的所有公式都满足R性质？
二、基本概念
1、 概念：∑V（∑表示公式集）
2、 概念：∑是可满足的（存在V，使得∑V＝1）
★ 注意：∑是可满足的蕴涵∑中的所有公式都是可满足的，但逆命题不成立 3、 概念：A是重言式、A是矛盾式
4、 概念：A的真假值表（真假赋值V给公式A指派的值，仅涉及V给A中出现的不同的命题符号所指派的值）
5、 性质：简化公式（熟练掌握简化公式）
三、习题解析
1、 性质：联结符号?满足交换律和结合律
2、 性质：A是重言式，则A?B是重言式当且仅当B是重言式
第五节 逻辑推论
一、逻辑推论
1、 符号：∑╞A（A是∑的逻辑推论，读作∑逻辑地蕴涵A）
2、 概念：∑╞A，当且仅当对于任何的逻辑赋值V，如果∑V＝1，则AV＝1 3、 概念：∑|≠A（存在逻辑赋值V，使得∑V＝1，AV＝0） 4、 特殊情况：?╞A（这时存在着性质：A是重言式） 5、 概念：逻辑等值公式A|＝|B 6、 例题分析：注意找到捷径和方法
⑴、如何证明一个逻辑推论是成立的（直接证明或者反证法）
⑵、如何证明一个逻辑推论是不成立的（构造出这样的真假赋值V，使得∑V＝1，AV＝0）
二、定理
1、 性质：合取符号和析取符号都满足交换律和结合律 2、 定理：
⑴、A1，…，An╞A，当且仅当?╞A1∧…∧An→A
⑵、A1，…，An╞A，当且仅当?╞A1→（…→（An→A）…） 3、 引理：如果A|＝|A’并且B|＝|B’，则有?A|＝|?A’等5条性质
4、 等值替换定理：设B|＝|C并且在A中把B的某些出现替换为C而得到A’，则A|＝|A’ 5、 对偶性定理：A’|＝|?A（其中A’是A的对偶）
面向计算机科学的数理逻辑复习文档
