Читать онлайн
Discrete Math. For students of technical specialties
For students of technical specialties
Ivan Treshchev
Assistnt Anastasiya Sergeevna Vatolina
© Ivan Treshchev, 2020
ISBN 978-5-4498-7601-0
Created with Ridero smart publishing system
Introduction
The tutorial is devoted to the consideration of theoretical issues in the framework of the course «Discrete Mathematics». The basic theoretical information on finite mathematics for students in the study of relevant courses, the principles of constructing mathematical models and methods for their analysis are presented. The manual can be useful not only to students of technical specialties and specialties associated with the design of information systems and the development of software modules, but also to students of humanitarian specialties. The sections discussed in the manual fully reflect the necessary material.
The main focus of the manual is on the set-theoretic approach. The basic information on combinatorics, coding theory and mathematical modeling, graph theory is presented. Many theses are illustrated clearly.
1. PLURALITY
1.1. Definitions and examples
The concept of set is one of the fundamental concepts of mathematics. The set is known, at least, that it consists of elements.
By the set S we mean any collection of defined and distinguishable objects, conceivable as a whole. These objects are called elements of the set S. As examples of the sets, one can cite: the set of students present at the lecture, the set of even numbers, etc. Usually, sets are indicated in capital letters of the Latin alphabet: A, B, C, …; and the elements of sets are in lower case: a, b, c,…
If the object x is an element of the set M, then they say that x belongs to M: x∈M. Otherwise, they say that x does not belong to M: x∉M.
A set A is called a subset of B if every element of A is an element of B. If A is a subset of B and B is not a subset of A, then they say that A is a strict (proper) subset of B. In the first case, denote: A⊆B, in the second: A⊂B.
Note that the symbol ∈ defines the relationship between some element and the set, and the symbol ⊆ defines the relationship between the sets, one of which is a subset of the other. So, it is not true that 1∈ {{1}, {2}}, or that {1} ⊆ {{1}, {2}}; it is true that {1} ∈ {{1}, {2}} and {{1}} ⊆ {{1}, {2}}. This example illustrates the difference between membership and inclusion.
For arbitrary sets X, Y, Z the following relations are true:
– X⊆X;
– if X⊆Y, Y⊆Z, then X⊆Z;
– if X⊆Y, Y⊆X, then X = Y.
A set containing no elements is called empty, denoted as: ∅. It is a subset of any set. The set U is called universal, that is, all the sets under consideration are its subset.