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

ХНУРЭ

Лектор – д.т.н., проф. Хаханов Владимир Иванович
ДИСКРЕТНАЯ МАТЕМАТИКА

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

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

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

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

математической логике и теории алгоритмов. М.: Наука, 1984. C. 4-10.
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергия, 1980. 344 с.
Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001. С. 4-24.
Тевяшев А.Д., Гусарова И.Г. Основы дискретной математики в примерах и задачах. Харьков: ХТУРЭ, 2001. С. 4-7.
Бондаренко М.Ф., Белоус Н.В., Руткас А.Г. Компьютерная дискретная математика. – Харьков: СМИТ, 2004. – 480 с.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 87с.
Хаханов В.И., Чумаченко С.В. Дискретная математика. Электронный учебник. ХНУРЭ: Электронная библиотека кафедры АПВТ (ауд. 320) NSERV\Library\Чумаченко\Дискретная математика\...

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

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

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

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

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

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

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

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

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

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

множество/ совокупность/набор

элемент/объект

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

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

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

• Точка

Информация

Множество

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

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

Пример

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

•m

M

•a

•s

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

•d

mB)
Обозначение:
 – строгое включение;
 – нестрогое включение
А –

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

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, т.е. 4A.

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.

булеан,
в) любой элемент булеана,
г) пустое множество,
д) универсальное множество?
7. Какие формулы

определяют закон элиминации?
а) (АВ)А=А, (АВ)А=А;
б) AB=BA, AB=BA.
8. Как определяется дополнение множества
а) A=U\A; б) А=U∆А ?

9. Мощность множества вычисляется по формуле:
а) |B(M)|=2·|M|;
б) |B(M)|=2|M|.
10. Какие подмножества являются собственными для множества
F={a, {d, c} }:
А) {a, {d, c} },
Б) {a},
В) {d, c},
Г) {{d, c}},
Д) ?