内容发布更新时间 : 2024/4/28 8:22:06星期一 下面是文章的全部内容请认真阅读。

该笔记适用于任何版本的数理逻辑！

绪论

一、数理逻辑研究什么？

★ 研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的

二、数理逻辑如何研究？ ★ 形式语言

第一章 预备知识

第一节 集合

一、集合

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（思路：想方设法转化为上述情形）