1.1. Множества и отношения. Множества и элементы множеств
1.5. Табличный способ задания множеств
2.2. Логические связки (операции) над высказываниями
2.3. Пропозициональные формулы
2.4. Булевы функции. Таблицы истинности
2.5. Булевы функции одной переменной
2.6. Булевы функции двух переменных
2.7. Существенные и несущественные переменные
2.8. Равносильные формулы. Основные равносильности
2.11. Понятие двойственной функции
2.12. Некоторые двойственные функции
2.13. Элементарные канонические формы
2.15. Приведение формул к нормальным формам
2.17. Полные системы функций. Полином Жегалкина
3.1. Основные понятия и определения
3.2. Смежность, инцидентность, степени
3.4. Подграфы. Операции на графах
3.5. Связность. Компоненты связности. Маршруты и пути
3.6. Эйлеровы и гамильтоновы графы
3.8. Цикломатическое число графа. Построение остовного дерева связного графа
4.1. Понятие конечного детерминированного автомата
4.2. Способы задания автоматов
4.3. Эквивалентные состояния. Минимизация к.д.а
4.4. Алгоритм минимизации конечного автомата
4.5. Каноническая таблица. Канонические уравнения
4.6. Функциональные и логические элементы. Проектирование дискретных устройств
1. Теория множеств
1.1. Множества и отношения
Множества и элементы множеств
Определение. Множество – любая определенная совокупность объектов произвольной природы. Обозначают множества прописными латинскими буквами: A, B, ¼ , а его элементы обозначаются строчными латинскими буквами: a, b, ¼.
Например:
(
является элементом множества 
(«
принадлежит A«)),
( не является элементом множества A).
Определение. Пустое множество – это множество, не содержащее ни одного элемента, обозначается оно символом: Æ.
Определение. 
– универсальное множество (универсум) – множество, из которого берутся элементы в конкретном рассуждении. – множество, рассматриваемое как наиболее общее в данной ситуации.
Множество элементов 
, удовлетворяющих свойству P(x) обозначается 
.
Примеры.
– множество натуральных чисел;
– множество вещественных чисел.
– множество комплексных чисел.
1.2. Сравнение множеств
Определение. 
(А содержится в В или В включает А), если 
. А называется подмножеством В. Если и 
, то А называется строгим (собственным) подмножеством В. Обозначается это 
.
Определение. 
если они являются подмножествами друг друга, то есть 
или 
Определение. Мощность конечного множества 
– число его элементов. Мощность бесконечного множества равна ¥.
1.3. Операции над множествами
Определение. Объединением множеств А и В (
) называется множество, состоящее из элементов, принадлежащих хотя бы одному из них. 
Определение. Пересечением множеств А и В (
) называется множество, состоящее из элементов, принадлежащих и первому и второму одновременно. 
Определение. Разностью множеств А и В (
) называется множество, состоящее из элементов множества А, не принадлежащих множеству В. 
Определение. Симметрической разностью множеств А и В (
) называется множество, состоящее из элементов множества А, не являющихся элементами множества В и элементов множества В, не являющихся элементами множества А. 
Определение. Дополнением множества А (
) называется множество, состоящее из элементов множества U, не принадлежащих множеству А.
Пример: 
зависит от того, какое U. Если 
, то 
, если 
, то 
.
1.4. Диаграммы Эйлера-Венна
Диаграммы Эйлера-Венна – это геометрическое представление множеств. Множество U изображается прямоугольником, рассматриваемые множества – фигурами (окружностями). Для выделения результата применяется штриховка.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
