- •Дискретная математика. Теория и практика
- •Оглавление
- •Глава 1. Множества 6
- •Глава 2. Комбинаторика 24
- •Глава 3. Отношения. Отображения 34
- •Глава 4. Алгебраические структуры 55
- •Предисловие
- •Введение
- •Глава 1. Множества
- •1.1. Множества и их элементы. Способы задания множеств
- •1.2. Подмножества
- •1.3. Операции над множествами
- •1.4. Диаграммы Эйлера – Венна
- •1.5. Прямое произведение множеств
- •1.6. Метод математической индукции
- •1.7. Соответствия
- •1.8. Задачи, связанные с определением мощности конечного множества
- •Задачи и упражнения к главе 1
- •Глава 2. Комбинаторика
- •2.1. Правила суммы и произведения
- •2.2. Размещения и сочетания
- •2.3. Примеры решения задач
- •2.4. Бином Ньютона
- •2.5. Свойства биномиальных коэффициентов. Треугольник Паскаля
- •Задачи и упражнения к главе 2
- •Глава 3. Отношения. Отображения
- •3.1. Понятие отношения
- •3.2. Способы задания бинарных отношений
- •Характеристическим свойством.
- •3.3. Операции над бинарными отношениями
- •3.4. Свойства матриц бинарных отношений
- •3.5. Свойства бинарных отношений
- •3.6. Определение свойств бинарного отношения по его матрице
- •3.7. Отношение эквивалентности
- •3.8. Счетные и несчетные множества
- •3.9. Отношение порядка. Диаграммы Хассе
- •3.10. Функции
- •Задачи и упражнения к главе 3
- •Глава 4. Алгебраические структуры
- •4.1. Алгебраические операции и их свойства
- •4.2. Понятие алгебраической структуры
- •4.3. Алгебры с одной бинарной алгебраической операцией
- •4.4. Алгебры с двумя бинарными алгебраическими операциями
- •4.5. Конечные поля
- •4.6. Булевы алгебры
- •4.7. Гомоморфизмы алгебр
- •4.8. Алгебраические системы. Решетки
- •Задачи к главе 4
- •Список литературы
4.6. Булевы алгебры
Рассмотрим понятие булевой алгебры, имеющее большое число приложений в программировании и вычислительной технике. Оно возникло в трудах ирландского математика и логика Джорджа Буля (1815 – 1864) как аппарат символической логики.
Определение 4.29. Алгебра А = < А, Å, *, > типа (2, 2, 1) называется булевой алгеброй, если выполняются следующие условия (аксиомы):
А1. Существуют различные элементы Î А, являющиеся нейтральными относительно бинарных операций Å, * соответственно, то есть
(" a Î A) $ e1, e2 Î A: a Å e1 = e1 Å a = a Ù a e2 = e2 a = a.
А2. Операции ассоциативны, то есть
Ù .
A3. Операции коммутативны, то есть
Ù .
А4. Операции дистрибутивны относительно друг друга, то есть
Ù .
A5. , .
Замечание 4.6. Аксиома А5 может побудить к ошибочному заключению о том, что элемент является симметричным к элементу а, однако это неверно. Если бы был симметричным элементом к а , то и . Сравнивая с аксиомой А5, заключаем, что не является симметричным элементом к а ни для одной из бинарных операций.
Бинарную операцию называют сложением, бинарную операцию * – умножением, элементы a b и a * b – суммой и произведением, соответственно. Унарную операцию «» называют дополнением, а элемент – дополнением к элементу a.
Существует несколько альтернативных способов записи бинарных операций сложения и умножения:
Определение 4.30. Для любого выражения булевой алгебры двойственным выражением (или дуализмом) называется выражение, полученное из исходного, заменой на , на , на , на .
Заметим, что каждая из аксиом булевой алгебры – это пара аксиом. Внутри каждой пары каждая аксиома является двойственным выражением по отношению к другой.
Пример 4.20. Наиболее простой из булевых алгебр является алгебра
<{0, 1}, Ú, Ù, >, в которой две бинарные операции Ú (дизъюнкция), Ù (конъюнкция) и одна унарная операция (отрицание) задаются таблицами Кэли:
Эта булева алгебра носит название двоичной алгебры логики. В ней роль операции сложения играет дизъюнкция, роль операции умножения – конъюнкция, роль операции дополнения – отрицание. Элемент 0 является нейтральным элементом относительно дизъюнкции, а элемент 1 – нейтральным элементом относительно конъюнкции.
Пример 4.21. Пусть А – непустое множество. Тогда < P(A), È, Ç, > есть булева алгебра, носящая название алгебры множеств (или алгебры Кантора). Носителем ее является булеан множества А, сигнатурой – операции объединения, пересечения подмножеств множества А, дополнения данного подмножества до множества А, играющих соответственно роли сложения, умножения и дополнения. Пустое множество является нейтральным элементом относительно объединения, а само множество А – нейтральным элементом относительно пересечения.
Свойства булевой алгебры
Утверждение 4.2 (принцип двойственности). Для любой теоремы булевой алгебры двойственная теорема также верна.
Теорема 4.5. Нейтральные элементы и относительно Å и * соответственно единственны.
Теорема 4.6. , .
Замечание 4.7. Знак «!» означает слово «единственный».
Теорема 4.7 (закон идемпотентности).
, .
Теорема 4.8 (закон идентичности).
, .
Теорема 4.9 (закон абсорбции или поглощения).
, .
Теорема 4.10 (закон инволюции).
.
Теорема 4.11 (законы де Моргана).
, .
Теорема 4.12. , .
Докажем, например, теорему 4.11, в частности, .
Из аксиомы A5 следует, что для этого достаточно показать выполнение равенства . Действительно, = = = = = = .
Второй закон де Моргана верен по принципу двойственности.