Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.

Множество – это совокупность объектов, рассматриваемых как единое целое.

Способы задания множеств:

1. Перечисление элементов: М={0,1,2,…,9}

2. Указание свойств Р(х), которым элементы множества должны удовлетворять: М={x | P(x)}.

Неправильное заданные свойства могут привести к противоречию!

Парадокс Рассела:

Рассмотрим множество всех множеств, которые не являются своими собственными элементами: . Является ли тогда множество К своим элементом. Если КєК, то должно выполняться свойство, задающее множество К, т.е. К¢К, что приводит к противоречию. Если же К¢К, то, поскольку выполняется свойство, задающее К, то КєК, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмысленному заданию множества.

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

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

Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью и обозначается Р(А), т.е. . Если |U|=n (множество U содержит n элементов), то |P(U)|=2ⁿ.

Множество, не содержащее ни одного элемента называется пустым ø.

Множество, содержащее все элементы, находящиеся в рассмотрении, называется универсальным или универсумом U.

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

1) объединение

2 ) пересечение

3) вычитание

4) кольцевая сумма (симметрическая разность)

5) дополнение

Свойства основных операций над множествами:

1. Ассоциативность:

2. Коммутативность:

3. Идемпотентность:

4. Дистрибутивность:

5. Поглощение:

6. Законы де Моргана:

7. Законы нуля и единицы: 0=ø, 1=U

8. Закон двойного отрицания:

Упорядоченную последовательность (х₁, х₂,…,х_n) называют кортежем длины n.

Декартовым (прямым) произведением множеств А₁, А₂,…, А_n называется множество {(x₁, x₂,…, x_n) | x₁ є A₁,…, x_n є A_n}.

Если А₁=А₂=…=А_n, то – n-ная декартова степень множества А.

А⁰ = ø

2. Yandex.RTB R-A-252273-3
   Содержание

   • Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.
   • Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.
   • Функции. Инъекции, сюръекции, биекции. Понятие последовательности.
   • Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.
   • Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
   • Конечные, счетные, континуальные множества. Мощность булеана.
   • Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
   • Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.
   • Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества.
   • Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.
   • Морфизмы алгебраических систем.
   • Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
   • Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
   • 17.Многообразия. Теорема Биркгофа.
   • Решетки. Дистрибутивные решетки. Критерий дистрибутивности.
   • Булевы алгебры. Теорема Стоуна. Принцип двойственности для булевых алгебр.
   • Булево кольцо.
   • 18. Алгебры отношений. Реляционные алгебры.
   • 27. Виды и способы задания графов.
   • 28. Подграфы и части графа. Операции над графами. N-Мерные кубы.
   • Объединение: .
   • 29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).
   • 30. Расстояние в графах. Центральные и периферийные вершины.
   • 31. Взвешенное расстояние. Алгоритм Форда-Беллмана.
   • 32. Степени вершин. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.
   • 33. Гамильтоновы графы. Постановка задачи коммивояжера.
   • 34. Деревья, леса. Остовы графов. Цикломатическое число, коранг. Алгоритм построения остова минимального веса. Обходы графов по глубине и ширине.
   • 35. Упорядоченные и бинарные деревья. Соответствия между ними.
   • 36. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов.
   • 37. Раскраска графов. Планарные графы.
   • 38. Формулы алгебры логики, их таблицы истинности.
   • 39. Булевы функции, способы их задания. Представления булевых функций формулами.
   • 40. Эквивалентность формул.
   • 41. Двухэлементная булева алгебра. Алгебра булевых функций. Фактор-алгебра алгебры формул.
   • 42. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.
   • 43. Теорема Шеннона. Теорема о функциональной полноте. Способы построения сднф и скнф.
   • 44. Импликанты, простые импликанты. Сокращенные, тупиковые, минимальные нормальные формы. Алгоритм Квайна построения мднф.
   • 45. Карты Карно. Построение мднф с помощью карт Карно.
   • 46. Принцип двойственности. Самодвойственные функции.
   • 47. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции.
   • 48. Классы Поста. Полные системы булевых функций. Теорема Поста. Базисы.
   • 49. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов.

   Yandex.RTB R-A-252273-4