离散数学引论.doc

离散数学引论
《离散数学》是现代数学的一个重要分支,是计算机科学基础理论的核心课程,其内容一直随着计算机科学的发展而不断地扩充与更新。它所研究的对象是离散数据结构及相互关系。由于数字电子计算机是一个离散结构,它只能处理离散的或离散化了的数量关系,因此,无论计算机科学本身,还是与计算机科学及其应用密切相关的现代科学研究领域,都面临着对离散结构建立相应的数学模型、将已用连续数量关系建立起来的数学模型离散化问题。在计算机科学中由于普遍采用了离散数学中的基本概念、基本思想和方法,从而使得离散数学成了不可少的理论工具。
离散数学的主要内容为:集合论、数理逻辑、近世代数、图论和组合数学等。离散数学不仅为数据结构、操作系统、编译原理、算法分析、人工智能、形式语言与自动机提供了重要的数学理论基础,而且通过对它的学习可以使我们熟悉和习惯抽象的符号表示和演算形式,培养和训练我们掌握使用数学语言或符号系统处理问题的基本方法,提高我们的抽象思维和逻辑推理的能力。
参考书目:
《离散数学》,耿素云等著,清华大学出版社;
《离散数学》,陈莉等著,高等教育出版社;
《离散数学》,孙吉贵等著,高等教育出版社;
《离散数学及其应用》,傅彦等著,电子工业出版社;
第一章数理逻辑
数理逻辑又称符号逻辑,是逻辑学的一个重要分支。逻辑学是研究人的思维形式的科学。数理逻辑是用数学方法研究推理、利用符号体系研究推理过程中前提和结论之间的关系。
命题符号化及联结词

命题是一个非真即假的陈述句。因此不能判断真假的陈述句、疑问句、祈使句和感叹句都不是命题。
(1) 一个命题的真或假称为命题的真值。真用T或1表示,假用F或0表示;
(2)原子命题(简单命题):最简单的命题,通常用大写字母p,q,r表示;几个简单命题用联结词连接起来得到的命题叫复合命题。
(3)一个陈述句有真值与是否知道它的真假是两回事。
[]判断下列语句是不是命题?若是,给出命题的真值:
(1)2是素数。(2)雪是黑色的
(3)给我一块钱吧! (4)2007年元旦下雨
(5)x>y。
数理逻辑的特点是并不关心具体某个命题的真假,而是将逻辑推理变成类似数学演算的形式化了的过程,它关心的是命题之间的关联性。因此需要进行命题符号化:
原子(简单)命题就是简单陈述句,用大写字母(或带下标)表示;
命题常元:T(1)或F(0),或者表示一个确定的命题;
命题变元:以T(1)或F(0)为值的变元;
指派(解释):用一个具体命题代替一个命题变元。
而不是简单命题的复合命题需要使用称为命题联结词的运算符来进行符号化。命题联结词的作用是为了将原子命题组合成复合命题。常用的有五种:
(1) 否定联结词
P(否定式):非P
: 不,非,没有
规定P是T当且仅当P是F。
合取联结词
PQ(合取式) :P 并且Q,P合取Q
: 并且,且,既…又…,不仅…而且…
规定PQ是T当且仅当P和Q都是T。
析取联结词
PQ(析取式):P或者Q,P析取Q
: 或,或者说,不是…就是,要么…要么
规定PQ是T当且仅当P,Q中至少一个是T(或者PQ是F当且仅当P,Q都是F)。
蕴含联结词→
P→Q(条件式、命题):如果P则Q
P称为条件式的前件(前提),Q称为条件式的后件(结论)
→:如果(若)…就(则),只要…就,若…才能
规定P→Q是F当且仅当P是T,Q是F。
等价(双条件)联结词
PQ (双条件式、命题) :P当且仅当Q
规定PQ是T当且仅当P,Q或者都是T,或者都是F。
命题符号化的目的在于用五个联结词将日常语言中的命题转化为数理逻辑中的形式命题,其关键在于使用适当的联结词。对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解:
确定语句是否是一个命题;
找出句中连词,用适当的命题联结词表示。
[]试将下列命题符号化:
若你不看电影,则我也不看电影。
小王一边吃饭,一边看书。
命题公式及分类

一个命题越复杂,符号化该命题所需的命题变元和联结词就越来越多。如何安排这么多的东西使之有意义呢?
一个(合式)公式是由下列方式递归定义的:
命题常元或命题变元是一个公式;
若A是一个公式,则(A)也是一个公式;
若A、B是公式,则(AB)、(AB)、(A→B)和(AB)均为公式;
只有经过有限次地应用(1)、(2)、(3)所得的结果才是公式。
注:1、公式一般无真值,只有对其所有的变元进行解释后,它才有真值;
2、公式无限多;
3、在一个复杂的公式中,常常有许多括号,为了简便起见,规定下列运算顺序:,