- •Теория множеств.
- •Свойства подмножеств.
- •Операции над множествами.
- •Алгебра теории множеств.
- •Решение уравнений алгебры множеств.
- •Кортеж.
- •Проекция множества.
- •График и свойства графика
- •Свойства графиков.
- •Прямое (декартовое) произведение множество.
- •Соответствия.
- •Отношения.
- •Операции над отношениями.
- •Основные свойства отношений.
- •Решетки. Диаграммы Хассе.
- •Математическая логика Высказывания и операции над высказываниями.
- •Операции над высказываниями.
- •Формулы математической логики.
- •Формулы равносильности.
- •Различные формы представления высказываний
- •Выполнимость формулы алгебры логики
- •Применение математической логики.
- •Минимизация сложных высказываний.
- •Метод Квайна.
- •Метод минимизирующих карт.
- •Метод минимизации с помощью карт Вейча.
- •Булевые функции и их свойства.
- •Функциональная полнота. Теорема Поста.
- •Логика предикат.
- •Логические операции над предикатами.
- •Квантовые операции.
- •Равносильные формулы логики предикатов.
- •Предваренная нормальная форма предиката
- •Теория графов
- •Основные понятия теории графов
- •Эйлеров граф.
- •Множество внутренней устойчивости графа
- •Алгоритм Магу для определения множества внутренней устойчивости графа
- •Множество внешней устойчивости графа
- •Алгоритм Магу для определения множества внешней устойчивости.
- •Множество путей в графе
- •Алгоритм фронта волны. Поиск минимального пути в графе.
- •Алгоритм фронта волны.
- •Ярусно-параллельная форма графов
- •Деревья и леса
- •Алгоритм получения дерева из графа
- •Теория алгоритмов
- •Рекурсивная функция
- •Пусть даны функции:
- •Машина Тьюринга
- •Работа машины Тьюринга:
- •Нормальные алгоритмы Маркова
- •Теория автоматов
- •Законы функционирования автоматов.
- •Задание автоматов
- •Минимизация автоматов
- •Алгоритм минимизации автомата Мили
- •Особенности минимизации автомата Мура. :
- •Минимизация частичных автоматов.
- •Переход от автомата Мили к автомату Мура
- •Переход от автомата Мура к автомату Мили
Алгебра теории множеств.
Для любых множеств А, В и С выполнимы следующие тождества:
Коммутативный закон
(9)
Ассоциативный закон
(10)
Дистрибутивный закон
(11)
Закон поглощения
(12)
Закон идемпотентности
(13)
Закон де Моргана
(14)
Закон исключенного третьего
(15)
Закон противоречия
(16)
Операции с универсумом:
(17)
Операции с пустым множеством:
(18)
(19)
Закон двойного дополнения
(20)
(21)
(22)
При преобразованиях выражений над множествами по законам алгебры логики существуют следующие приоритеты: самой приоритетной операцией является дополнение, затем пересечение и в последнюю очередь объединение.
Решение уравнений алгебры множеств.
Пусть дано уравнение вида:
(23)
где X - неизвестное множество. Необходимо определить это неизвестное множество.
Алгоритм решения уравнений алгебры множеств имеет следующий алгоритм:
Представляем данное уравнение в следующем виде:
(24)
2. Используя алгебру множеств, преобразуем данное уравнение к виду:
(25)
где C и D - некоторые множества, не содержащие множество X и его дополнение.
3. Решением уравнения является следующее выражение:
(26)
Рис 2. Диаграмма Эйлера-Венна для решения уравнения алгебры множеств.
ПРИМЕР.
Необходимо решить уравнение:
1. Преобразуем данное уравнение:
2. С помощью алгебры множеств преобразуем данное выражение следующим образом:
В данном выражении присутствует множество , в котором не содержится ни множество X , ни его дополнение, поэтому к этому множеству применяем следующие преобразования:
C учетом данных преобразований имеем:
Таким образом, имеем множества C и D в следующем виде:
.
Решением уравнения будет множество:
.
Решение уравнения (один из вариантов) может быть представлено на диаграмме Эйлера-Венна
Рис 3 Диаграмма Эйлера-Венна для решения уравнения алгебры множеств.
При изображении решения уравнения алгебры множеств следует иметь в виду, что два множества могут иметь следующие диаграммы Эйлера-Венна
Рис 4 Диаграмма Эйлера-Венна для решения уравнения алгебры множеств.
Кортеж.
Кортеж - это упорядоченный набор элементов. Кортеж характеризуется элементами и их порядком расположения. Элементы кортежа называются компонентами. Компоненты нумеруют слева направо. Число компонент определяет длину кортежа. Кортеж обозначается а1, а2, ..., аn.
Кортеж длиной в две компоненты называется парой, кортеж длиной в три компоненты - тройка, длиной в n - n-ка.
Проекцией кортежа на i-тую ось называется его i-тая компонента.
Проекцией кортежа на оси i1, i2, ..., iq оси называется кортеж, состоящий из i1, i2, ... , iq компонент, где .
Проекцией кортежа на пустое множество осей является пустой кортеж.
ПРИМЕР
Пусть дан кортеж А=< ,,,>. Найти проекции на 1 ось, 3 ось, 5 ось, 1 и 4 оси, 4 и 2 оси.
Пр А1=<>
Пр А3=<>
Пр А5 не определена
Пр А1,4=<>
Пр А4,2 не определена.