ТЕОРИЯ МНОЖЕСТВ ОСНОВНЫЕ ПОНЯТИЯ

ХНУРЭ
ДИСКРЕТНАЯ МАТЕМАТИКА

проектирования
вычислительной техники (АПВТ),
ауд. 321, тел. 70-21-326,
консультации: среда, 4 пара, ауд.

319
Зачет – зимняя сессия, экзамен – весенний модуль
Оценка = текущая успеваемость + итоговое тестирование

множеств, законов алгебры множеств
Содержание:
Курс «Дискретная математика»: цель, структура

Теория множеств как раздел дискретной математики
Понятие множества
Способы задания множеств
Отношения принадлежности и включения
Мощность множества. Пустое и универсальное множества
Булеан и его мощность
Операции над множествами
Законы и тождества алгебры множеств Кантора

Тема: Основные понятия теории множеств

4-8 с.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств,

математической логике и теории алгоритмов. М.: Наука. Главная редакция физико-математической литературы, 1984. 4-10 с.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергия, 1980. 344 с.
Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовcкого ун-та, 1986. 240с.
Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001. С. 4-24.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 87с.

в области ДМ, необходимых для освоения методов анализа и синтеза

аппаратных и программных средств цифровых вычислительных систем и сетей различного назначения, изучения теоретической базы информационных технологий, математических способов представления дискретных информационных процессов

1845г.
В 1867 г. окончил Берлинский университет
В 1872-1913 гг.

– профессор университета в Галле
Сформулировал общее понятие мощности множества (1878)
Развил принципы сравнения мощностей множеств и
Систематически изложил принципы своего учения
Созданная Кантором теория множеств, некоторые идеи которой имелись у его предшественников, послужила причиной общего пересмотра логических основ математики и оказала влияние на всю современную ее структуру.

Георг Кантор
(XIX-XXвв.)

Историческая справка

современную математику из единого источника – теории множеств
Н. Бурбаки
Никто

не может изгнать нас из рая, который создал нам Кантор…
Д. Гильберт

Теория множеств как раздел дискретной математики

мощность
пустое множество
универсум
булеан
объединение
пересечение
дополнение
Базовые понятия:

множество
элемент
операции над множествами

иной природы
Объекты, которые образуют множество, называются его элементами
Понятие множества
Множество есть

многое, мыслимое как единое
Г. Кантор

• Точка

Информация

Множество

принадлежит множеству, если он является его элементом
Принадлежность элемента x множеству

X обозначается при помощи символа : xX
Пример

Отношение принадлежности

•m

M

•a

•s

m  M
s  M
a  M
d  M

•d

 – строгое включение;
 – нестрогое включение
А – подмножество

множества В
В – надмножество множества А
Множества равны, если они состоят из одних и тех же элементов

A  B

{3}, {4} }.
Какие из следующих утверждений верны?
2A верно, так

как в множестве А есть элемент 2;
{1,2}A верно, так как в множестве А есть элементы 1,2, т.е. 1A, 2A ;
3A верно, так как в множестве А имеется элемент 3;
{3}A верно, поскольку в множестве А есть элемент {3};
4A – неверно, так как в множестве А нет элемента 4;
{4}A – верно, так как в множестве А имеется элемент {4};
{4}A – неверно, поскольку в множестве А нет элемента 4.

A

• 2

• 1

• 3

•3

• 4

2A
{1,2}  A
3A
{3}A
4A
{4}A
{4}A

число определяет количество элементов данного множества
Обозначения: |M|, card M
Пустое множество

 не содержит ни одного элемента:
||=0
Универсальное множество U – надмножество всех множеств:
  М  U

множество A={a,b,c}. Найти В(А).

B(A)={ , {a}, {b},

{c}, {a,b}, {a,c}, {b,c}, {a,b,c} }

Мощность булеана определяется по формуле:
|B(M)|=2 |M|
Пустое множество и само множество являются несобственными подмножествами множества М
Остальные подмножества – собственные

Булеан. Мощность булеана

Обозначение: А=
Замкнутость относительно операций
Алгебра множеств Кантора:
носитель

– множества,
сигнатура – набор операций
Обозначение: Ak=

множество несобственным подмножеством самого себя?
а) да; б) нет
3. Множества равны, если

они содержат
а) одни и те же элементы;
б) одинаковое количество
элементов.

4. Являются ли понятия мощность и кардинальное число идентичными?
а) да; б) нет.
5. Определить мощность булеана множества F={a, {d, c} }:
|B(F)|= 2;
б) |B(F)|= 4;
в) |B(F)|= 0;
г) |B(F)|= 3.