- •1.Основные понятия теории множеств.
- •2.Операции над множествами.
- •3.Соответствия, отображения и функции.
- •4. Отношения на множествах
- •5. Операции на множествах, понятие алгебры
- •6. Алгебра Кантора. Законы алгебры Кантора
- •7. Алгебраические системы. Решетка Хассэ
- •8.Задание множеств конституентами (числом)
- •9. Основные понятия комбинаторики
- •10. Размещения
- •11. Перестановки
- •12. Сочетания
- •13. Треугольник Паскаля
- •14. Бином Ньютона
- •15. Задание графов
- •16. Свойства графов
- •17. Понятие о задачах на графа
- •18. Понятие о переключательных функциях
- •19. Двоичные переключательные функции и способы их задания
- •20. Основные логические операции
- •21. Элементарные переключательные функции
- •22. Определение свойств переключательных функций
- •23. Функциональная полнота систем переключательных функций. Теорема Поста о функциональной полноте систем пф
- •24. Переключательные схемы - техническая реализация пф
- •25. Основные законы булевой алгебры пф
- •26.27. Формы представления переключательных функций. Сднф. Скнф
- •28. Цели минимизации пф
- •29. Основные понятия минимизации пф
- •30. Метод Квайна-Мак-Класки
- •31.32. Задание пф картой Карно. Карта Карно на три и четыре переменных
- •33. Минимизация на кубе соседних чисел
- •35. Основные определения теории автоматов
- •36. Описание конечных автоматов таблицами переходов-выходов и графами
- •37. Техническая интерпретация конечного автомата
- •38. Синтез комбинационных автоматов в заданном базисе
- •39. Элементарные автоматы памяти
- •40. Системы счисления - основа различных кодов
- •41. Представление информации в эвм
6. Алгебра Кантора. Законы алгебры Кантора
Алгебра Кантора: <B(I),,,–>. Носителем ее является булеан универсального множества I, сигнатурой – операции объединения , пересечения и дополнения –[9].
Для операций алгебры Кантора выполняются следующие законы:
1) коммутативности объединения и пересечения:
МаМb=МbМа, МаМb=МbМа;
2) ассоциативности объединения и пересечения:
Ма(Мb Мс)=(МаМb)Мс, Ма(МbМс)=(МаМb)Мс;
3) дистрибутивности пересечения относительно объединения и объединения относительно пересечения:
Ма(МbМс)=(МаМb)(МаМс),
Ма(МbМс)=(МаМb)(МаМс),
причем последнее соотношение не имеет аналога в обычной алгебре;
4) идемпотентности объединения и пересечения:
МаМа=Ма, МаМа=Ма,
поэтому в алгебре Кантора нет ни степеней, ни коэффициентов;
5) де Моргана:
, ;
6) двойного дополнения:
.
Выполнимы также следующие действия с универсальным I и пустым множествами:
7) М=М, М=, МI=I, МI=М, ,.
Все эти соотношения могут быть доказаны с использованием кругов Эйлера. Видны двойственность соотношений: они справедливы как относительно объединения, так и относительно пересечения.
Рассмотрим дополнительные законы:
8) склеивания:
9) поглощения:
М(МА)=М;
10) Порецкого – по фамилии российского логика, математика и астронома, профессора Казанского университета Платона Сергеевича Порецкого (1846-1907 гг.):
.
Алгебра Кантора по аддитивной операции объединения и мультипликативной операции пересечения является абелевой полугруппой, так как для этих операций выполняются законы коммутативности и ассоциативности, но она не является группой, поскольку уравнения МаХ=Мb, МаХ=Мb не имеют решения, например, для случая, когда множества не пересекаются: МаМb= [9]. Поэтому алгебра Кантора по двухместным операциям и не является кольцом. Эта алгебра принадлежит к другому классу фундаментальных алгебр – к классу решеток.
7. Алгебраические системы. Решетка Хассэ
Выше рассматривались алгебры, т.е. множества, на которых заданы операции [19].
Множества, на которых кроме операций заданы отношения, называются алгебраическими системами [19]. Таким образом, алгебры можно считать частным случаем алгебраических систем. Другим частным случаем алгебраических систем являются модели – множества, на которых заданы только отношения.
Рассмотрим пример алгебраической системы, который наиболее часто встречается в теоретической алгебре и ее применениях [19]. Этот пример – решетка.
Рассмотрим алгебраическую систему из множества М, отношения порядка (будем обозначать ) и некоторых операций. Говорят, что множество М линейно упорядочено, если любые два элемента находятся в отношении упорядоченности, иначе – частично упорядочено. Для элементов а и b из М их верхней гранью (мажорантой) называется любой элемент сМ такой, что са, сb, а их нижней гранью (минорантой) – любой элемент dМ такой, что dа, db. В общем случае для некоторых элементов а и b верхняя или нижняя грань может не существовать или быть не единственной, причем различные верхние (или нижние) грани могут быть несравнимыми. Во множестве верхних и нижних границ вводится понятие точной верхней (нижней) границы множества.
Такая верхняя граница множества обозначается supМ («супремум»), такая нижняя граница – обозначается infМ («инфинум»).
Частично упорядоченное множество называется решеткой, если у каждой пары его элементов а,b необходимо имеются единственная точная верхняя граница sup(а,b) или пересечение аb и точная нижняя граница inf(а,b) или объединение аb. Здесь операции , пока понимаются как абстрактные операции алгебраической системы и отличаются от теоретико-множественных операций объединения и пересечения. Для алгебры множеств соответствует , соответствует .
Рассмотрим пример частично упорядоченного множества – диаграмму (решетку) Хассе [9], известную с конца XIX века и применяемую в генеалогии для задания родства (рис. 8).
Рис. 8. Диаграмма (решетка) Хассэ для множества всех
подмножеств универсального множества I={y,x,z}
На рис. 8 множество всех подмножеств данного множества упорядочено по отношению включения, а операции объединения и пересечения элементов связаны дистрибутивными законами. Нулем и единицей частично упорядоченного множества называются, соответственно, его наименьший и наибольший элементы, обычно применяются традиционные обозначения 0,1.
Так, на рис. 8 нулем и единицей будут, соответственно, пустое множество и данное множество (I).
На решетке Хассе обычно не изображаются линии транзитивности и рефлексивности.
В частично упорядоченных множествах с нулем и единицей, вводится операция дополнения элементов.
Элементы а и в частично упорядоченного множества с нулем 0 и единицей 1 называются дополнительными друг для друга, если их пересечение равно нулевому элементу 0, а объединение дает единичный элемент 1: аb=0, аb=1.
Так, {y}{x,z}=, {y}{x,z}=I на рис. 8.
Дистрибутивная решетка с отличными друг от друга нулем и единицей, в которой каждый элемент имеет дополнение, называется булевой алгеброй.
Пример булевой алгебры – совокупность множества всех подмножеств данного множества и теоретико-множественных операций объединения, пересечения и дополнения, т.е. алгебра Кантора (алгебра множеств), рассмотренная выше. Операции объединения и пересечения являются бинарными (двухместными), а операция дополнения – унарной (одноместной).
Далее мы рассмотрим другой пример булевой алгебры – булеву алгебру логических (переключательных) функций.