最经典最简约的面向计算机科学的数理逻辑复习笔记

《最经典最简约的面向计算机科学的数理逻辑复习笔记》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、该笔记适用于任何版本的数理逻辑！绪论一、数理逻辑研究什么？★研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的二、数理逻辑如何研究？★形式语言第一章预备知识第一节集合一、集合1、集合的内涵和外延（所有元素的共同性质/构成集合的所有元素）2、有序偶和笛卡儿集二、关系1、概念：集合S上的n元关系R2、特殊情况：集合S上的一元关系R（集合S上的性质R）三、函数（映射）1、概念：函数（集合＋有序偶＋性质）、定义域dom（f）、值域ran（f）2、概念：f（x）（函数f在x处的值）3、概念：f：S－>T（函数f是由S到T的映射）、满射、一

2、一映射四、等价1、概念：关系R是集合S上的等价关系（自反＋对称＋传递）2、概念：元素x的R等价类3、性质：R等价类对集合S的一个划分（两两不相交，且并为S）五、基数1、概念：S～T（两个集合S和T是等势的）2、概念：集合S的基数

3、S

4、（集合中的元素个数）3、概念：可数无限集第二节归纳定义和归纳证明一、归纳定义1、集合的归纳定义⑴、直接生成某些元素⑵、给出运算，将其作用在已有元素上，以产生新的元素⑶、只有这样才是集合中的元素，除此之外，再也没有了2、典例：自然数集N的两个归纳定义二、归纳证明1、归纳定理：设R是一个性质，如果⑴、R（0）⑵、对于任

5、何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、小结：只考虑复合命题的真假是如何

6、确定的二、联结词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）（经典归纳定义及其两种变形）★

7、经典定义容易理解，然而两种变形更容易使用3、定理：如何证明LP的所有公式都满足R性质？★关键：假设S={A∈Form（LP）

8、R（A）}4、概念：对公式的结构做归纳（上述归纳证明）三、习题解析1、关键：利用二叉树表示公式的生成过程2、关键：蕴涵有多种不同的叙述方式（关键：分清楚充分条件和必要条件）⑴、◆如果p，则q⑵、◆只要p，则q⑶、◆p仅当q⑷、◆只有p，才q⑸、◆除非p，否则q（思路：想方设法转化为上述情形）第三节公式的结构一、引理1、引理1：LP的公式是非空的表达式2、引理2：在LP的每个公式中，左括号和右括号出现的数目相同3、引理3：

9、真初始段不是公式（在LP的公式的任何非空的真初始段中，左括号出现的次数比右括号多。因此，LP的公式的非空的真初始段不是LP的公式（同理分析真结尾段））二、定理1、定理：LP的每个公式恰好具有以下6种形式之一；并且在各种情形中，公式所具有的那种形式是唯一的★注意：仔细分析其证明过程2、推论：LP的公式的生成过程是唯一的3、概念：否定式、合取式、析取式、蕴涵式、等值式三、辖域1、概念：辖域、左辖域、右辖域2、定理：任何A中的任何辖域存在并且唯一3、性质：如果A是B中的段，则A中的任何联结符号在A中的辖域和它在B中的辖域是相同的4、定理：如果A是（¬

10、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）★注

11、意：∑是可满足的蕴涵∑中的所有公式都是可满足的，但逆命题不成立3、概念：A是重言式、A是矛盾式4、概念：A的真假值表（真假赋值V给公式A指派的值，仅涉