- •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.5. Отношение порядка
Отношение эквивалентности является обобщением отношения равенства: эквивалентные системы считаются «равными». Обобщением обычного отношения служит отношение порядка.
Рефлексивное, антисимметричное, транзитивное отношение R называется отношением нестрогого порядка и обозначается символом .
Антирефлексивное, антисимметричное, транзитивное отношение R называется отношением строгого порядка и обозначается символом <.
Отношения строгого и нестрогого порядка иначе называют отношениями упорядоченности.
Пример1. Нестрогим порядком является обычное отношение на множестве N. Действительно, это отношение рефлексивно (х х), транзитивно (х у, у z x = y) и антисимметрично (х у, у х х = у).
Пример2. Отношение включения на булеане P(U) образует нестрогий порядок.
Пример3. Отношение «х старше у» на некотором множестве людей является отношением строгого порядка.
Множество А с заданным в нём отношением порядка называется упорядоченным этим отношением.
Элементы a, bA сравнимы по отношению порядка R на М, если выполняется aRb или bRa. Во множестве М могут быть элементы, про которые нельзя сказать, что х у или у х. Такие элементы называются несравнимыми.
Пример4. Зададим отношение некоторого порядка рисунком:
Тогда элементы а и с – несравнимы.
М ножество А, на котором задано отношение порядка может быть:
а) полностью упорядоченным множеством (линейно упорядоченным или цепью), если любые два эле Рис.4.
мента a и b из А находятся между собой в отношении порядка. (Линейным является нестрогий порядок в примере 1).
б) в противном случае множество А является частично упорядоченным множеством. При этом говорят, что отношение R задаёт на множестве А частичный порядок.
В частично упорядоченном множестве можно выделить цепь.
Если между элементами a и b установлено отношение порядка, то они называются сравнимыми, в противном случае – несравнимыми.
Специальным типом частично упорядоченного множества является интервал
[x, y]={zX| x z y} (замкнутый) или (x, y)={zX| x < z < y} (открытый).
Антицепью (семейством Шернера) называется подмножество частично упорядоченного множества, в котором любые два элемента несравнимы.
Пример 1. К каким типам отношений относятся:
1. Отношение равносильности на множестве формул, описывающих элементарные функции (формулы равносильны, если они задают одну и туже функцию, например, (a + b)(a – b)=a² – b², sin²α + cos²α = 1);
2. Отношение, определяемое на множестве всех программ:{(a, b): a и b вычисляют одну и ту же функцию на определяемом множестве};
3. Отношения и < на множестве векторов длины n с компонентами из N, определяемые следующим образом:
а) , если ;
б) , если и хотя бы в одной координате i выполняется .
4. Отношением предшествования букв < конечного алфавита А (например, отношение предшествования букв русского алфавита, отношение предшествования чисел 0, 1, 2, …, 9 и т. п.), заданного фиксированным списком:
, если предшествует в списке букв.
Отношения, заданные в п. 1 и 2, являются отношениями эквивалентности на соответствующих множествах. Отношения 3 и 4 – отношения порядка (в п. 3 – отношение нестрогого порядка, а в п. 4 – строгого порядка).
Пример 2. Какой порядок на множестве задают отношения:
и , а также < и > для чисел множеств N и R;
и < на Rn , введённые в примере а, б п. 3; (пример 1);
и на системе подмножеств β(М) множества М;
подчиненности на предприятии;
предшествования < букв конечного алфавита А, определённого в примере 1 п. 4.
6) Отношения нестрогого порядка и , а также строгого порядка < и > полностью упорядочивают множества N и R.
7) Отношения и < на множестве векторов длины n c компонентами из R определяют частичный порядок на Rn:
и - не сравнимы.
8. Отношение на системе β(М) задаёт строгий частичный порядок, а отношение – нестрогий частичный порядок.
Например, {a, b} {a, b, c}, но {a, b} и {b, c ,d} несравнимы по отношения .
9. Отношение подчинённости на предприятии задаёт строгий порядок. В нём несравнимыми являются, например, сотрудники разных звеньев одного уровня организационной структуры.
10. Отношение предшествования < букв в алфавите А задают полное упорядочение множества букв в алфавите А.