离散数学内容总结大纲
第一篇 数理逻辑
第1章 命题逻辑
求命题公式的主析取范式及主合取范式
例 求prqp的主析取范式及主合取范式。
例 求(P→Q)R的主析取范式及主合取范式。
例 求命题公式RQP)(的主析取范式和主合取范式。
例 求公式A=(pq)r的主析取范式与主合取范式。
例 求rqp的主析取范式。
判断公式类型
例 用等值演算法判断公式q (pq)的类型
例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。
(1)
(2)
证明
例 证明：rqrprqp
例 证明：rqprqp)()(
例 推证：Q∧(P→Q)P
例 前提：qpsqrp,,，结论：sr。该结论是否有效？请说明原因。
在命题逻辑中构造下面推理的证明：
例 如果小张守第一垒并且小李向B队投球，则A队获胜。或者A队未获胜，或者A队成为联赛的第一名。小张守第一垒。A队没有成为联赛的第一名。因此小李没有向B队投球。 解：先将简单命题符号化。P：小张守第一垒；Q：小李向B队投球；R：A队取胜；S：A队成为联赛第一名。
前提：(P∧Q)→R，R∨S，P，S
结论：Q
证明：
(1) R∨S 前提引入
(2) S 前提引入
(3) R (1)(2)析取三段论
(4) (P∧Q)→R 前提引入
(5) (P∧Q) (3)(4)拒取式
(6) P∨Q (5)置换
(7) P 前提引入
(8) Q (6)(7)析取三段论
例 一个公安人员审查一件盗窃案，已知下列事实：
（1）甲或乙盗窃了录像机；
（2）若甲盗窃了录像机，则作案时间不能发生在午夜前；
（3）若乙的证词正确，则午夜时屋里灯光未灭；
第 1 章 命题逻辑
数理逻辑是用数学方法研究思维规律和推理过程的科学，而推理的基本要素是命题，因此命题逻辑是数理逻辑最基本的研究内容之一，也是谓词逻辑的基础。由于数理逻辑使用了一套符号，简洁地表达出各种推理的逻辑关系，因此，一般又称之为符号逻辑。数理逻辑和电子计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计、逻辑电路、开关理论等计算机应用和理论研究提供了必要的理论基础。
一、命题与命题变量
在日常生活中，人们不仅使用语句描述一些客观事物和现象，陈述某些历史和现实事件，而且往往还要对陈述的事实加以判断，从而辨其真假。语句可以分为疑问句、祈使句、感叹句与陈述句等，其中只有陈述句能分辨真假，其他类型的语句无所谓真假。在数理逻辑中，我们把每个能分辨真假的陈述句称作为一个命题。陈述句的这种真或假性质称之为真值或值，这就是说真值包含“真”和“假”。因而命题有两个基本特征，一是它必须为陈述句：二是它所陈述的事情要么成立(真)，要么不成立(假)，不可能同时既成立又不成立，即它的真值是惟一的。
命题可按其真值分为两类。若一个命题是真的，则称其真值为真，用1或T表示，称该命题为真命题；若一个命题是假的，则称其真值为假，用0或F表示，称该命题为假命题。命题还可根据其复杂程度分类。只是由一个主语和一个谓语构成的最简单的陈述句，称为简单命题或原子命题或原始命题。简单命题不可能再分解成更简单的命题了，它是基本的，原始的。当然，也有一些命题并不是最基本的，它们还可以分解成若干个简单命题。由若干个简单命题通过联结词复合而成的更为复杂的新命题称为复合命题或分子命题。复合命题仍为陈述句。任意有限个简单或复合命题，还可用若干不同的联结词复合成极为复杂的复合命题。
简单命题和复合命题的真值是固定不变的，故又可称为命题常量或命题常元，简称为命题。而有些陈述句尽管不是命题，但可以将其变成命题，它的真值是不固定的、可变的，这种真值可变化的陈述句称为命题变量或命题变元。命题常元或命题变元用大写英文字母A，B，„，P，Q，„或Ai，Bi，„，Pi，Qi，„表示。一个简单命题，它的真值不是真就是假，因此，我们在命题逻辑中常常用1或T表示一个抽象的“真命题”，用0或F表示一个抽象的“假命题”。命题变元虽然没有确定的真值，但当我们用一个具体的命题常元代入时，它的真值就可确定了。
第一章 命题逻辑
逻辑学是研究推理过程规律一门科学。数理逻辑则是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁地表达出各种推理的逻辑关系，因此数理逻辑又称为符号逻辑或理论逻辑。
数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。
数理逻辑的主要分支包括公理化集合论、证明论、递归函数论、模型论等。从本章开始，我们用三章的篇幅介绍数理逻辑的基本内容：命题逻辑、谓词逻辑和非经典逻辑简介。
命题逻辑研究的是以原子命题为基本单位的推理演算，其特征在于，研究和考查逻辑形式时，我们把一个命题只分析到其中所含的原子命题成分为止。通过这样的分析可以显示出一些重要的逻辑形式，这种形式和有关的逻辑规律就是命题逻辑。
1.1 命题与联结词
1.1.1 命题与命题变元
语言的单位是句子。句子可以分为疑问句、祈使句、感叹句与陈述句等，其中只有陈述句能分辨真假，其他类型的句子无所谓真假。
定义1.1 能够分辨真假的陈述句叫做命题（Proposition）。
从这个定义可以看出命题有两层含义：(1)命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题；(2)这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。 作为命题的陈述句所表示的判断结果称为命题的真值，真值只取两个值：真或假。凡是与事实相符的陈述句是真命题，而与事实不符合的陈述句是假命题。通常用1（或大写字母T）表示真，用0（或大写字母F）表示假。
例1.1 判断下列语句是否为命题，并指出其真值。
(1) 北京是中国的首都。
（2）5可以被2整除。
（3）2+2=5。
（4）请勿吸烟。
（5）乌鸦是黑色的吗？
（6）这个小男孩多勇敢啊！
（7）地球外的星球上存在生物。
（8）我正在说谎。
解 （1）～（3）是命题，其中（1）是真命题，（2），（3）是假命题。值得注意的是，像2+2=5这样的数学公式也是一个命题，事实上，一个完整的数学公式与一个完整的陈述句并没有什么本质的差异。
数理逻辑
一、说明
(一) 课程性质
《数理逻辑》是数学与应用数学专业的方向选修课。数理逻辑又称符号逻辑、理论逻辑，是数学的一个分支，它是采用数学的方法来研究推理的形式结构和推理规律的数学学科，数理逻辑研究的中心问题是推理。所谓数学方法就是指数学采用的一般方法，包括使用符号和公式，已有的数学成果和方法，特别是使用形式的公理方法。用数学的方法研究逻辑的系统思想一般追溯到莱布尼茨，他认为经典的传统逻辑必须改造和发展，使之更为精确和便于演算。总的来说，数理逻辑就是精确化、数学化的形式逻辑，它是现代计算机技术的基础。
(二) 教学目的
本课程的教学应使得学生熟练掌握有关命题逻辑、一阶谓词逻辑的基本知识，理解并能初步运用形式化的逻辑推理和数学证明，训练学生的逻辑思维方式，提高其数学解题能力。
(三) 教学内容及学时数
本课程主要讲授命题逻辑的基本概念，命题逻辑的等值和推理演算，谓词逻辑的基本概念，谓词逻辑的等值和推理理论等内容，共计30学时。
序号 内容 学时数（ 30 ）
课堂学时数 实践学时数
1 命题逻辑的基本概念 6 0
2 命题逻辑的等值和推理演算 7 3
3 谓词逻辑的基本概念 6 0
4 谓词逻辑的等值和推理理论 6 2
合计 25 5
(四) 教学方式
数理逻辑是一门理论性课程，主要采用讲授法、研究探索法授课，讲授数理逻辑的内容时建议采用多媒体教学。
(五) 考核要求
1. 考核的方式及成绩评定
本课程的考核方式一般采用笔试，成绩评定100分制，其中平时成绩占50%，期末考试成绩占50%，其中平时成按数学系课堂“五个环节”评分细则进行评定。
2. 考题设计
(1) 考题设计原则：考题要全面，符合大纲要求，同时要做到体现重点，题量适度，难度适中，题量和难度的梯度按照教学的三个不同层次，并能够反映出数理逻辑的思想方法、解决基本问题能力的知识点来安排，不过分强调综合。
(2) 考题难度比例：基础知识（或基本概念）约35%、根据学生实际水平确定中等难度知识点约50%，稍有难度知识点15%范围以内。
