- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
1.9. Отношения
1.9.1.Определения
Отношения – один из способов задания взаимосвязей между элементами множества. Наиболее изученными и чаще всего используемыми являются так называемые унарные и бинарные отношения.
Отношением называется некоторые свойства, которым могут обладать или не обладать элементы данного множества.
Унарные (одномерные) отношения отражают наличие какого-то определённого признака R (свойства и т. п.) у элементов множества М.
Примеры:
1) «быть белым» на множестве шаров в урне. Тогда все такие элементы а из множества М, которые отличаются данным признаком R, образуют некоторое подмножество в М, называемое унарным отношением R, т. е.
аR и RM
2)унарные операции: –1 или –2; Бинарные 4 – 3; 2 + 1.
Если свойство связывается два элемента, то отклонение называется бинарным и двухместным.
Бинарные (двухместные) отношения используются для определения взаимосвязей, которыми характеризуются пары элементов в множестве М. Все пары (a, b) элементов из множества М, между которыми имеет место данное отношение R, образуют подмножество пар из множества всех возможных элементов ММ=М².
Это подмножество называется бинарным отношением R,
т. е. (a, b)R, при этом RMM.
В общем случае могут рассматриваться n-местные (n-арные) отношения. Между тройками элементов -трехместные (тернарные) отношения и т. д.
Под n-местным отношениям на множествах понимают любое подмножество R прямого произведения множеств: .
Говорят, что элементы
(где ) находится в отношении R, если . Если , то .
1.9.2 Бинарные отношения
Наибольшее значение имеют бинарные отношения.
Пусть имеется универсальное множество U. Составим декартово произведение U само на себя:
U²=UU.
Любое подмножество R множества U² называется бинарным отношением на множестве U.
Пусть aU и bU. Если (a, b)R, то говорят, что элемент а находится в отношении R к элементу b: aRb.
Диагональю Δ множества U² называется множество всех элементов вида (a, a), где aU.
Областью определения D(R) некоторого бинарного отношения R называется множество
D(R) = {a| (a, b)R для некоторого b}.
Область значений отношения R – множество
Q(R)= {b| (a, b)R для некоторого a}.
1.9.3. Способы задания бинарных отношений
Так как отклонения, по определению, есть подмножества некоторых множеств – прямых произведений, то для задания бинарных отношений используются любые способы задания множеств. Отношения, определённые на конечных множествах, обычно задаются:
1. Списком (перечислением) пар, для которых это отклонение выполняется.
Пример 1. Если U={2, 3, 4, 5, 6, 7, 8}, то отклонение aRb, где R={(a, b)| a, bU, a делит b и a3} можно записать в виде
R={(2, 2); (2, 4), (2, 6), (2, 8), (3, 3), (3, 6)}.
2. Матрицей – бинарному отношению RUU, где , соответствует квадратная матрица порядка n, элементы которой Cij , определяются следующим правилом:
(*)
Пример 2. Пусть U={1, 2, 3, 4, 5}. Задать матрицей отношение RUU, если R означает – «быть строго меньше».
R |
1 2 3 4 5 |
|
|
1 2 3 4 5 |
0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 |
Т. о., каждому отношению можно поставить в соответствие матрицу данного вида. Обратно: любая матрица из нулей и единиц определяет отношение R по формуле (*) (используется для представления отношений в ЭВМ).
3 . Стрелочный. Элементы множества U располагаются по кругу и стрелками соединяются два элемента, находящиеся в отношение R: от первого элемента ко второму. Стрелка будет двусторонней, если aRb и bRa. Например,
Обобщение понятия отношения
n-местным (n-арным)отношением
R называется множество упорядо Рис.3. ченных наборов (кортежей):
При этом множества не обязательно различны.
Таким образом, n-арное отношение – любое подмножество прямого произведения множеств (i=1, 2, …, n).
Многоместные отношения используются, например, в теории баз данных («реляционные» базы данных). Бинарные отношения используются в теории графов.