Раздел 2. Дискретная математика

Тема 4. Элементы дискретной математики (8 часов)

Литература:

1. Баврин И.И. Высшая математика: Учебник для вузов. – М.: «Академия», 2008.

2. Шипачев В.С. Высшая математика: Учебник для вузов. – М.: Высшая школа, 2010.

3. Хаггарти Р. Дискретная математика для программистов. – М.: Техносфера, 2003. – 320с. – (сер. Мир программирования).

4. Яблонский С.В. Введение в дискретную математику. - М.: Наука, 1979.

5. Шипачев В.С. Задачник по высшей математике: Учебное пособие для вузов/ В.С. Шипачев. – 3-е изд., стер. – М.: Высшая школа, 2003. – 304 с

Вопросы для самостоятельного изучения

1. Теория множеств и отношений

При изучении данных учебного вопроса основное внимание следует обратить на следующее.

Теория, в которой изучаются множества (классы) элементов произвольной природы. Созданная, прежде всего, трудами Кантора (а также Р. Дедекинда и К. Вейерштрасса), теория множеств к концу 19 в. стала основой построения сложившихся к тому времени математических теорий; в терминах теории множеств были определены важнейшие понятия классической математики: отношение, функция и др..

Самым "элементарным" разделом Т. м. является алгебра множеств, т.е. теория операций над абстрактными множествами, являющаяся, по существу, переформулировкой алгебры логики. Естественным развитием "абстрактной" теории множеств, (изучающей множества, элементы которых не индивидуализируются, не фиксируются), явилась теория "бесконечных чисел": кардинальных чисел - мощностей множеств и ординальных (порядковых) чисел. Мощность множества - это его количественная (см. Количество в математике) характеристика: мощность конечного множества есть число его элементов, мощность же бесконечного множества определялась Кантором как "то общее, что присуще всем эквивалентным ему множествам" (эквивалентными называют множества, между элементами которых можно установить взаимно-однозначное соответствие). Минимальной бесконечной мощностью является мощность натурального ряда чисел. Множества, эквивалентные натуральному ряду, называются счетными, или перечислимыми (т.к. их элементы можно "пересчитать", "перенумеровать" числами натурального ряда).

1. Объединением множеств X и Y называется множество, состоящее из тех элементов, которые принадлежат хотя бы одному из множеств X или Y:

.

2. Пересечением множеств X и Y называется множество, состоящее из тех элементов, каждый из которых принадлежит и множеству X, и множеству Y:

.

3. Разностью множеств X и Y называется множество, состоящее из тех и только тех элементов, которые принадлежат X и не принадлежат Y:

.

X\Y Y\X.

Множество , определяемое из соотношения называется дополнением множества X (до универсального множества I).

(Под универсальным понимается множество, которое содержит в качестве подмножеств все множества, участвующие в рассматриваемой задаче.)

Стоит отметить, что универсальное множество в алгебре множеств играет роль единицы. Действительно, для такого множества справедливо:

(аналогично тому, что в алгебре чисел).

В то же время пустое множество играет роль нуля в алгебре множеств. Действительно,

(аналогично тому, что в алгебре чисел);

(аналогично тому, что в алгебре чисел).

Пример 1.1. Даны два множества X ={1; 2; 3; 4; 5; 6; 7} и Y ={2; 3; 5; 6; 8; 9} и универсальное множество, включающее в себя целые числа от 0 до 10:

Найти: 1) ; 2) ; 3) ; 4) ; 5) ;

6) ; 7) ; 8) ; 9) ; 10) .

Решение

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) .

Пример 1.2. Запишите элементы множеств, которые заданы с помощью характеристических свойств:

1) ;

2) ;

3) .

Решение

1) ;

2) ;

3) (корни квадратного уравнения: , , из них только является натуральным числом).

Пример 1.3. Дано множество . Запишите все его подмножества.

Решение. , , , , , , , Æ.

Пример 1.4. Даны два множества: и . Верно ли, что ?

Решение. Нет, множество А не является подмножеством множества В.

Пример 1.5. Даны множества: , , и .

Найти множества:

1) ; 2) ; 3) ; 4) ; 5) .

Решение

1) ;

2) ;

3) ;

4) ;

5) .

Поиск по сайту: