Оценить:
 Рейтинг: 0

Discrete Math. Practice. For students of technical specialties

Автор
Год написания книги
2020
1 2 3 4 5 ... 8 >>
На страницу:
1 из 8
Настройки чтения
Размер шрифта
Высота строк
Поля
Discrete Math. Practice. For students of technical specialties
Ivan Treschev

The manual is intended for students of the specialty information security of automated systems when studying the practice course “Discrete mathematics”, and can also be used by students of other specialties studying similar courses.The author would like to express gratitude to his supervisor A. Khusainov and Mikhailova N.N.

Discrete Math. Practice

For students of technical specialties

Ivan Treschev

Assistnt Anastasiya Sergeevna Vatolina

© Ivan Treschev, 2020

ISBN 978-5-4498-7599-0

Created with Ridero smart publishing system

Introduction

This paper presents some of the tasks that can be used in preparation for the Discrete Mathematics course.

The author will be grateful for indicating shortcomings, typos, etc.

1 Examples of completing tasks

Task Problem 1: let A and B be finite sets, | A | = m, | B | = n. How many binary relations exist between A and B?

Solution: the Cartesian product will contain a total of (n*m) pairs, therefore, a total of 2

 subsets. Each subset is a binary relation on the set of Cartesian products, which means that there are 2

 relations

Problem No. 2: prove that the comparability relation modulo a positive integer n on the set Z: x = y (modn) is an equivalence relation.

Proof: non the definition of x is comparable with y modulo n if and only if x – y is divisible by n without remainder. It is an equivalence relation, since it holds:

1) Reflexivity – since x – x = 0 is divided by n, then x ≡ x (mod n).

2) Symmetry – if x ≡ y (mod n), then x – y is divided by n, then y – x is divided by n, that is, y ≡ x (mod n).

3) Transitivity – if x – y is divisible by n, then x – y = t

n (t

 is an integer), and if y – z is divisible by n, then y – z = t

n.

Adding these equalities, we have: x – y + y – z = t

n + t

n, whence x – z = (t

 + t

) n, that is, x – z is divided by n. Thus, from x ≡ y (mod n) and y ≡ z (mod n) it follows that x ≡ z (mod n).

Problem No. 3: a partition of a set X is a collection of pairwise disjoint subsets of X such that each element of the set X belongs to one and only one of these subsets.

Proof: such a partition, by definition, defines the relation of belonging to a subset of the partition. Therefore, it remains to prove that this relation is equivalence.

1) reflexivity: if for any element x from X xRx performed.

2) Symmetry: Let x, y belong to the same subset, whereas

if for all x, y from X in xRy yRx follows.

3) Transitivity: If for any x,y,z X from xRy, and yRz follows xRz.

A partition of a set X is a collection of pairwise disjoint subsets of X such that each element of the set X belongs to one and only one of these subsets.

Examples.

– X= {1,2,3,4,5}. Partition: {{1,2}, {3,5}, {4}}.

– The partition of many students of the institute can be a set of groups.

In other words, a partition of a set X is a family: X= ∪

X

 ∀i,j X

 ⋂ X

=0,X

 ⊆X is an element of the partition.

The set of equivalence classes of elements of any set of X by the equivalence relation R sets the quotient of the set X with respect R denoted and X/R. For example, a plurality of student groups of a given university is a factor in a plurality of a plurality of university students in relation to belonging to one group.

Examples.

– (x, ≤) x ≤ y (x,y) ∈ ≤ – are comparable;

– (x,y) ∉ ≤ – are not comparable.
1 2 3 4 5 ... 8 >>
На страницу:
1 из 8