- •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.6.1. Минимальные и максимальные элементы множества
Пусть А – частично упорядоченное множество: .
Элемент aA называется максимальным, если не существует больших элементов: из а х следует х = а.
Элемент аА называется наибольшим, если х а для .
Элемент аА называется минимальным, если не существует меньших элементов: из х а следует х = а.
Элемент аА называется наименьшим, если а х для .
Наибольший элемент часто называют единицей, а наименьший – нулём множества U.
Пример1. Пустое множество является минимальным элементом булеана по включению.
Пример2. Линейно упорядоченное множество имеет наименьший элемент 0, но не имеет наибольшего элемента.
Пусть – частично упорядоченное множество, B-подмножество А.
Элемент аА называется верхней гранью множества В, если b a для всех bB.
Элемент аА называется нижней гранью множества В, если a b для всех bB.
Пример3. Рассмотрим частично упорядоченное множество и интервал B=(0, 1]. Тогда любое число является верхней гранью, а любое число - нижней гранью множества B.
Элемент аА называется точной верхней гранью (супремумом) множества В (обозначается supB), если а – наименьшая из верхних граней множества В.
Элемент аА называется точной нижней гранью (инфимумом) множества В (обозначается infB), если а – наибольшая из нижних граней множества В.
В примере: supB=1, infB=0.
Теорема: Во всяком частично упорядоченном конечном не пустом множестве существует как минимальный элемент, так и максимальный (без док–ва),
Линейный порядок на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент. Пара , в которой отношение является полным порядком на множестве А, называется вполне упорядоченным множеством.
Пример1. Пара не является вполне упорядоченным множеством, т. к., например, полуоткрытый интервал , являющийся подмножеством [0, 1], не содержит наименьшего элемента.
Пример2. Пара является вполне упорядоченным множеством.
Замечание. В полне упорядоченное конечное множество содержит один минимальный элемент, а в произвольном частично упорядоченном конечном множестве их может быть несколько.
Теорема: Всякий частичный порядок на конечном множестве может быть дополнен до линейного (без док–ва).
Замечание: В данном случае «может быть дополнен» означает, что существует отношение полного порядка, которое является надмножеством заданного отношения частичного порядка.
Аксиомы частичного порядка могут быть записаны тогда привычным образом:
x ≤ x для всех x M
Если x ≤ y и y ≤ x, то x = y
Если x ≤ y и y ≤ z, то x ≤ z
Пример3. Обычное отношение ≤ является частичным упорядочением множества всех положительных целых чисел.
Пример4. Отношение (m дели n) – другое частичное упорядочение на множестве положительных целых чисел.
Пример5. Для любого множества Ω отношение является частичным порядком на множестве P(Ω) всех подмножеств множества Ω.
1.9.6.2. Диаграммы Хассе
Рассмотрим множество А с заданным на нём отношением частичного порядка .
Говорят, что элемент у покрывает элемент х, если х у и не существует такого элемента z, что x < z < y.
Если множество А конечно, то частично упорядоченное множество можно представить в виде схемы, называемой диаграммой Хассе. В ней каждый элемент
изображается точкой на плоскости. Если у покрывает х, то точки х и у соединяют отрезками, причём точку, соответствующую х, располагают ниже у.
Пример1. Рассмотрим частично упорядоченное множество , где A={1, 2, 3}. Множество P(А) содержит восемь элементов:
{0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. (рис. 5а)
Пример 2. Пусть А={1, 2, 3, 4, 5, 6, 10, 15, 30}. Отношение частного порядка на множестве А задаётся по правилу: делится на х (рис. 5б).
На рис.1в изображена диаграмма Хассе линейно упорядоченного множества {0, 1, 2, 3, 4, 5, 6, 7}.
Правило чтения диаграмм Хассе состоит в том, что , если можно прийти из точки х в точку у, следуя вдоль восходящих отрезков, соединяющих точки. Смена направления движения разрешается только в точках диаграммы.
в)
Р ис.5
Замечание. Диаграммы Хассе первых двух отношений совпадают. Это означает, что эти частично упорядоченные множества имеют одинаковую структуру, причём она отличается от структуры третьего множества, тоже имеющее восемь элементов.
Формально общность структур (рис. 5а и б) определяется понятием изоморфизма.
С помощью диаграмм Хассе поясним понятия верхней и нижней грани для элементов х и у из множества .
На языке диаграмм Хассе означает, что существует путь из х в у. Верхняя грань х и у – это вершина, в которую есть путь из х и у. нижняя грань – это вершина, из которой есть путь и в х, и в у.
Очевидно, что (рис. 5а) и {1, 2, 3} для , т. е. 0 есть наименьший элемент, а {1, 2, 3} – наибольший для частично упорядоченного множества P(A).
В общем случае для некоторых элементов верхняя и нижняя грань может быть не единственной, причём различные верхние (нижние грани) могут быть несравнимы.
Пример 3. На рис.6а изображена диаграмма Хассе множества
, у которого элементы x4 , x5 не имеют верхней грани, а элементы x2 и x3 - нижней грани.
Рис.6.
На рис.6б изображена диаграмма Хассе множества , у которого все элементы не имеют верхней и нижней грани, однако, например, x1 и x3 имеют несравнимые верхние грани.