- •Министерство образования и науки украины
- •Лекция1 множества Основные определения
- •Способы задания множеств
- •Отношения на множествах
- •Графическое представление множеств
- •Операции над множествами
- •Условные приоритеты операций над множествами
- •Алгебра множеств
- •Основные законы алгебры множеств
- •Лекция №2: Теория отношений
- •Способы задания отношений
- •Операции над отношениями
- •Отношение эквивалентности
- •Разбиения и покрытия множества
- •Лекция 3.Основные понятия комбинаторики.
- •Правило произведения Теоретико – множественная формулировка правила произведения
- •Комбинаторная формулировка правила произведения
- •Сложный выбор объектов
- •Соединения без повторений
- •Перестановки
- •Размещения из n элементов по m без повторений
- •Сочетания без повторений
- •Размещения с повторениями
- •Сочетания с повторениями.
- •1) В кондитерской продают 4 вида пирожных. Сколькими
- •Количество всевозможных, различных двоичных наборов длиной n равно 2n.
- •Табличный способ представления фал
- •Графическое представление фал Графическое представление фал
- •Функции алгебры логики одного аргумента
- •Функции алгебры логики двух аргументов
- •Условные приоритеты булевых функций
- •Фиктивные аргументы фал
- •Алгоритм нахождения фиктивных аргументов
- •Выражение одних элементарных функций через другие
Министерство образования и науки украины
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
"УТВЕРЖДАЮ"
Зав. кафедрою ПМИ
__________Е. А. Башков
д.т.н., професор
"__" ___________ 2009 р.
КОНСПЕКТ ЛЕКЦИЙ
ПО КУРСУ“ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ, часть1”
ДЛЯ СПЕЦИАЛЬНОСТИ ПО АСУ
очно-заочной формы обучения
ДОНЕЦК – 2009
Составитель: доцент кафедры ПМИ Назарова И.А.
Рецензенти: Губенко Н.Е.., доц. каф. ПМІ, к. т. н.,
Святный В. А., проф. каф. ЕОМ, д. т. н.
Рекомендовано ученым советом факультета КНТ ДонНТУ
Протокол № 1 від 30.09.2009г.
Лекция1 множества Основные определения
Множество относитсяк категории наиболее общих, основополагающих понятий математики, поэтому вместострогого определения обычно принимается некоторое основное положениео множествеи его элементах.
Синонимами слова "множество" являются слова "совокупность", "класс", "коллекция", "собрание", "список".
Основоположником теории множеств, как математической теории, считается немецкий математик Георг Кантор (конец 19 века).
Определение множества, данное Кантором.
Множество- это многое, мыслимоенами, как единое целое.
В качестве рабочего определения примем следующее утверждение.
Множество – совокупность определенныхи различимых между собой объектовтаких, чтодля любого объекта можноустановить принадлежитон данной совокупности или нет.
Для обозначения множеств и их элементов будем использовать латинские буквы, а именно: прописные буквы для обозначения множеств и строчные буквы для обозначения элементов. В случае необходимости при обозначении будем использовать индексы. Таким образом, будут использоваться следующие обозначения
для множеств:
и для элементов:
.
Известные математические множества:
N – множество натуральных чисел;
Z – множество целых чисел;
Q – множество рациональных чисел;
R – множество вещественных чисел;
C – множество комплексных чисел.
Тот факт, что множество A состоит из объектов и только из них условно записывается следующим образом:
.
Объекты называются элементами множестваA.
Утверждение "а является элементом множества А" записывается в виде аА (а принадлежит множеству А).
Утверждение "а не является элементом множества А" записывается в виде аА (а не принадлежит множеству А).
Способы задания множеств
1) Перечисление элементов.
А = {1,3,5,6,889,-10}
2) Задание определяющего свойства.
X = { x | 1 > х > 5, x є N };
А = {a2 | a - четное число}.
Множество, состоящее изконечного числа элементов, называется конечным, а множество, состоящее из бесконечногочисла элементов— бесконечным.
Число элементовконечного множества– мощность, норма, кардинальноечисло:|А|.
Пустое множество – множество, не содержащее ниодного элемента. Пустое множество обозначается или .
Универсальное множество – множествовсех, всевозможных, рассматриваемых в данном классе задач элементов. Универсальное множество обозначается U.