离散数学ch1讲义[2]命题演算

引言Discrete Math.离散数学研究离散对象及其相互间关系的一门数学学科。

研究离散结构的数学分支。

（辞海）计算机科学、信息科学、数字化科学的数学基础离散数学的内容：数理逻辑(Mathematics Logic)集合论(Sets)代数结构(Algebra Structure)图论(Graph Theory)组合论(Combination)线性代数(Linear Algebra)概率论(Probability Theory)……与高等数学的区别教学内容：数理逻辑(Mathematics Logic)集合论(Sets)代数结构(Algebra Structure)图论(Graph Theory)离散数学的由来与发展：一、古老历史：计数：自然数发展：图论：Konigsberg七桥问题二、年青新生：计算机：二进制运算离散数学课程设置：计算机系核心课程信息类专业必修课程其它类专业的重要选修课程离散数学的后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、……离散数学课程的学习方法：强调：逻辑性、抽象性；注重：概念、方法与应用参考教材：1、离散数学（耿素云，屈婉玲，北大版）2、离散数学（方世昌，西安电子科大版）3、离散数学结构（第三版、影印版）（Bernard Kolman、Robert C.Busby、Sharon Ross，清华版）4、离散数学提要与范例（阮传概、卢友清，北京广播学院版）第一章命题逻辑（Proposition Logic）1、命题符号化及联结词2、命题公式及分类3、等值演算4、联结词全功能集5、对偶与范式6、推理理论逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科——一套符号体系+ 一组规则数理逻辑的内容：古典数理逻辑：命题逻辑、谓词逻辑现代数理逻辑：逻辑演算、公理化集合论、递归论、模型论、证明论1、命题符号化及联结词命题(Proposition)：一个有确定真或假意义的语句。

第一章命题演算及其形式系统1.1 命题与联结词内容提要1.1.1 命题我们把对确定的对象作出判断的陈述句称作命题（propositions），当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。

“真、假”常被称为命题的真值。

自然语言中“并非、或者、并且、如果…，那么…、当且仅当” 这样的联结词称为逻辑联结词（logical connectives）。

通常把不含有逻辑联结词的命题称为原子命题或原子（atoms），而把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositive propositions）。

1.1.2 联结词否定词(negation)“并非”（not），用符号┐表示。

设p表示一命题，那么┐p表示命题p的否定。

p真时┐p假，而p假时┐p真。

┐p读作“并非p”或“非p”。

合取词(conjunction)“并且”（and），用符号∧表示。

设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即p和q同时为真时p∧q真，否则p∧q为假。

p∧q读作“p并且q”或“p且q”。

析取词(disjunction)“或”（or）用符号∨表示。

设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q 均假时p∨q为假。

p∨q读作“p或者q”、“p或q”。

蕴涵词(implication)“如果……，那么……”（if…then…），用符号→表示。

设p，q表示两命题，那么p→q表示命题“如果p，那么q”。

当p真而q假时，命题p→q为假，否则均认为p→q为真。

p→q中的p称为蕴涵前件，q称为蕴涵后件。

p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。

数学中还常把q→p，┐p→┐q，┐q→┐p分别叫做p→q的逆命题，否命题，逆否命题。

双向蕴涵词(two-way implication)“当且仅当”（if and only if），用符号表示之。