ebook Discrete mathematics for computer science students Renata Kawa

Wydawca: Uniwersytet Jana Długosza w Częstochowie

Rok wydania: 2024

Preface
Discrete mathematics is a part of mathematics that deals with discrete structures.
The term "discrete" should be understood here in the sense of "not continuous" or "separated
from each other" (as opposed to "discreet" meaning "unobtrusive"). In a more
restrictive sense, the term "discrete" is also understood as "finite", indicating that the objects
of interest in discrete mathematics are finite structures and processes. Thus, discrete
mathematics is fundamentally different from calculus, theory of differential equations, or
topology, which are mainly concerned with continuous concepts and infinite objects.
More specifically, discrete mathematics is based on logic, set theory, and number
theory, with its main branches including combinatorics and graph theory. It is applied
in areas at the intersection of mathematics and computer science such as algorithms,
cryptography, coding theory, and computational theory. Discrete mathematics is essential
for understanding the theoretical foundations of computer science. A deep understanding
of discrete mathematics allows for efficient solving of complex computing problems and
the creation of effective algorithms.
This textbook aims to introduce the key concepts of discrete mathematics to all those
interested in this field, particularly first-year undergraduate students in computer science.
By learning the fundamentals of discrete mathematics, students develop problem-solving
skills applicable in various real-life scenarios.
The material for the script "Discrete Mathematics for Computer Science Students"
is selected to organize knowledge in this field acquired in high school and to supplement
it with topics necessary for further studies in computer science. This script covers the
basics of logic (Chapter 1), elements of number theory (Chapter 2), and an introduction to
combinatorics (Chapter 3). Each chapter is supplemented with a set of exercises, most of
which also include answers. The entire work is complemented by sample exam questions
(Chapter 4).

Spis treści ebooka Discrete mathematics for computer science students

Contents
Notations 4
Preface 5
1. Elements of Logic 6
1.1. Basics of Propositional Calculus . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2. Basics of Quantifier Calculus . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3. Elements of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4. Elements of Relation Theory . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5. Notation for Sums and Products . . . . . . . . . . . . . . . . . . . . . . . 20
1.6. Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7. Integer-Valued Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8. Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.9. Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2. Elements of Number Theory 37
2.1. Divisibility of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2. Prime and Composite Numbers . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3. Greatest Common Divisor and Least Common Multiple . . . . . . . . . . 41
2.4. Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.5. Relatively Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.6. Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.7. Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3. Elements of Combinatorics 53
3.1. Factorial and Binomial Coefficient . . . . . . . . . . . . . . . . . . . . . . 53
3.2. Variations, Permutations, and Combinations . . . . . . . . . . . . . . . . . 56
3.3. The Multiplication and Addition Principles . . . . . . . . . . . . . . . . . 59
3.4. Various Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5. Inclusion-Exclusion Principle and Dirichlet’s Box Principle . . . . . . . . . 64
3.6. Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.7. Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4. Sample Exam Questions 88
The bibliography 92
3