离散数学入门：奥斯卡·莱文的开放教程

需积分: 9 181 浏览量更新于2024-07-17 收藏 1.43MB PDF 举报

"离散数学与开放式引导" 《离散数学：开放性介绍》是一本英文教材，由Oscar Levin撰写，适用于对离散数学感兴趣的学习者。这本书是第二版，作者是University of Northern Colorado的数学科学学院教授。Oscar Levin以其幽默的语言风格和丰富的习题设计，使得学习离散数学的过程更具吸引力。该书遵循创作共享 Attribution-ShareAlike 4.0 国际许可协议，允许自由使用和分享，同时也有ISBN编号以便于正式出版和引用。最新版本可以在http://discretetext.oscarlevin.com/免费获取。离散数学是计算机科学和数学领域的重要基础，主要研究不连续或个体化的数学结构，如集合、图、逻辑、组合数学和数理逻辑等。这本教材涵盖的基本离散数学内容可能包括以下几个方面： 1. **逻辑与证明**：介绍形式逻辑的基础，包括命题逻辑和一阶逻辑，以及如何构建和评估逻辑推理，学习如何书写严谨的数学证明。 2. **集合论**：讲述集合的基本概念，如集合的定义、集合的运算（并、交、差），以及笛卡尔积和幂集等。 3. **图论**：研究点与点之间连接关系的图形结构，涉及图的基本概念（如顶点、边、路径、环和连通性），以及图的分类（如简单图、有向图、加权图等）。 4. **关系与函数**：探讨关系（如等价关系和偏序关系）及其性质，以及函数的概念，包括一对一、一对多和多对一的映射。 5. **组合数学**：讲解组合计数的基本原理，如组合公式、排列组合、二项式定理，以及鸽巢原理等。 6. **数理逻辑**：深入讨论命题和一阶逻辑的推理规则，包括量词（全称量词和存在量词）和蕴含、等价等逻辑连接词。 7. **递归与归纳**：介绍递归定义和归纳法，这些在算法设计和分析中非常关键。 8. **基本的算法分析**：可能会涉及简单的算法分析技术，如时间复杂度和空间复杂度的计算，为计算机科学中的算法设计奠定基础。 9. **编码理论**：可能涵盖信息编码和错误检测与纠正的概念，如汉明码。 10. **概率与信息理论**：虽然不是离散数学的核心部分，但可能会涉及到概率论的基础知识，特别是与离散数据相关的概率计算。《离散数学：开放性介绍》不仅提供了理论知识，还通过丰富的习题集帮助读者巩固和应用所学知识。习题的设计鼓励探索和思考，有助于提升问题解决能力。此外，由于它源于Richard Grassland Tabitha Mingus的《离散和组合数学》，因此继承了其探究式教学法，使学习过程更加生动有趣。对于计算机科学专业的学生、数学爱好者或是需要提高离散数学素养的读者来说，这是一本极好的学习资源。通过阅读和实践，读者可以深入理解离散数学的概念，为后续的计算机科学课程，如算法、数据结构、计算理论等打下坚实的基础。

2 0. Introduction and Preliminaries

Investigate!

Note: Throughout the text you will see Investigate! activities like this one.

Answer the questions in these as best you can to give yourself a feel for what

is coming next.

1. The most popular mathematician in the world is throwing a

party for all of his friends. As a way to kick things oﬀ, they decide

that everyone should shake hands. Assuming all 10 people at

the party each shake hands with every other person (but not

themselves, obviously) exactly once, how many handshakes take

place?

2. At the warm-up event for Oscar’s All Star Hot Dog Eating Con-

test, Al ate one hot dog. Bob then showed him up by eating

three hot dogs. Not to be outdone, Carl ate ﬁve. This continued

with each contestant eating two more hot dogs than the previ-

ous contestant. How many hot dogs did Zeno (the 26th and ﬁnal

contestant) eat? How many hot dogs were eaten all together?

3. After excavating for weeks, you ﬁnally arrive at the burial cham-

ber. The room is empty except for two large chests. On each is

carved a message (strangely in English):

If this chest is empty,

then the other chest’s

message is true.

This chest is ﬁlled

with treasure or the

other chest contains

deadly scorpions.

You know exactly one of these messages is true. What should

you do?

4. Back in the days of yore, ﬁve small towns decided they wanted

to build roads directly connecting each pair of towns. While

the towns had plenty of money to build roads as long and as

winding as they wished, it was very important that the roads

not intersect with each other (as stop signs had not yet been

invented). Also, tunnels and bridges were not allowed. Is it

possible for each of these towns to build a road to each of the

four other towns without creating any intersections?

! Attempt the above activity before proceeding !

0.2. Mathematical Statements 5

only if” (Sam is a man if and only if Chris is a woman), and “not” (Sam is not a

man). The ﬁrst four are called binary connectives (because they connect two

statements) while “not” is an example of a unary connective (since it applies

to a single statement).

Which connective we use to modify statement(s) will determine the truth

value of the molecular statement (that is, whether the statement is true or

false), based on the truth values of the statements being modiﬁed. It is

important to realize that we do not need to know what the parts actually say,

only whether those parts are true or false. So to analyze logical connectives,

it is enough to consider propositional variables (sometimes called sentential

variables), usually capital letters in the middle of the alphabet: P, Q, R, S, . . ..

These are variables that can take on one of two values: T or F. We also have

symbols for the logical connectives: ∧, ∨, →, ↔, ¬.

Logical Connectives

• P ∧Q means P and Q, called a conjunction.

• P ∨Q means P or Q, called a disjunction.

• P → Q means if P then Q, called an implication or conditional.

• P ↔ Q means P if and only if Q, called a biconditional.

• ¬P means not P, called a negation.

The truth value of a statement is determined by the truth value(s) of its

part(s), depending on the connectives:

Truth Conditions for Connectives

• P ∧Q is true when both P and Q are true

• P ∨Q is true when P or Q or both are true.

• P → Q is true when P is false or Q is true or both.

• P ↔ Q is true when P and Q are both true, or both false.

• ¬P is true when P is false.

Note that for us, or is the inclusive or (and not the sometimes used exclusive

or) meaning that P ∨ Q is in fact true when both P and Q are true. As for

the other connectives, “and” behaves as you would expect, as does negation.

The biconditional (if and only if) might seem a little strange, but you should

think of this as saying the two parts of the statements are equivalent. This

leaves only the conditional P → Q which has a slightly diﬀerent meaning in

6 0. Introduction and Preliminaries

mathematics than it does in ordinary usage. However, implications are so

common and useful in mathematics, that we must develop ﬂuency with their

use, and as such, they deserve their own subsection.

Implications

An implication or conditional is a molecular statement of the form

P → Q

where P and Q are statements. We say that

• P is the hypothesis (or antecedent).

• Q is the conclusion (or consequent).

An implication is true provided P is false or Q is true (or both), and

false otherwise. In particualr, the only way for P → Q to be false is for P

to be true and Q to be false.

Easily the most common type of statement in mathematics is the condi-

tional, or implication. Even statements that do not at ﬁrst look like they have

this form conceal an implication at their heart. Consider the Pythagorean The-

orem. Many a college freshman would quote this theorem as “a

+ b

 c

.”

This is absolutely not correct. For one thing, that is not a statement since it

has three variables in it. Perhaps they imply that this should be true for any

values of the variables? So 1

+ 5

 2

??? How can we ﬁx this? Well, the

equation is true as long as a and b are the legs or a right triangle and c is the

hypotenuse. In other words:

If a and b are the legs of a right triangle with hypotenuse c, thena

 c

This is a reasonable way to think about implications: our claim is that the

conclusion (“then” part) is true, but on the assumption that the hypothesis

(“if” part) is true. We make no claim about the conclusion in situations when

the hypothesis is false.

Still, it is important to remember that an implication is a statement, and

therefore is either true or false. The truth value of the implication is deter-

mined by the truth values of its two parts. To agree with the usage above, we

say that an implication is true either when the hypothesis is false, or when

the conclusion is true. This leaves only one way for an implication to be false:

when the hypothesis is true and the conclusion is false.

剩余344页未读，继续阅读

smallchan

粉丝: 0
资源: 1

离散数学入门：奥斯卡·莱文的开放教程

SUMS29 A First Course in Discrete Mathematics, Ian Anderson (2002) .pdf

A first course in discrete mathematics（离散数学引论）

discrete mathematics and its applications 第八版答案

discrete mathematics and its applications

discrete mathematics第七版

discrete differential geometry an applied introduction csdn下载

discrete mathematics and its applications seventh edition

discrete mathematics and its applications, 8th edition

discrete mathematics and its applications kenneth h. rosen

discrete mathematics

最新资源