- •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.11.5. Алгебры с двумя бинарными операциями
Рассматриваются алгебры с двумя бинарными операциями: , которые условно называются "сложением" и "умножением".
1. Кольца.
Алгебра , которая по умножению является мультипликативным группоидом, а по сложению - абелевой группой, причем операции связаны между собой законами дистрибутивности, называется кольцом.
Таким образом, кольцо обладает, по определению, следующими свойствами:
1. - сложение ассоциативно.
2. - существует нуль.
3. - существует обратный элемент
4. - сложение коммутативно, т.е. кольцо – абелева группа по сложению.
5. - умножение ассоциативно, т.е. кольцо полугруппа по умножению.
6. - умножение дистрибутивно слева и справа.
7. - если умножение коммутативно, то кольцо коммутативное
8. - если существует единица, то кольцо называется кольцом с единицей. Кольцо с единицей – моноид по умножению.
Пример 1.
- множество целых чисел относительно обычных операций сложения и умножения образует коммутативное кольцо с единицей.
Пример 2.
В частности, машинная арифметика целых чисел - коммутативное кольцо с единицей.
Пример 3.
Множество числовых матриц заданного порядка относительно операций сложения и умножения матриц, определенных обычным образом, предоставляет собой некоммутативное кольцо.
Теорема: В кольце выполняются следующие соотношения:
Доказательство:
1.
2.
3.
Если в кольце существует и такие, что , то называется левым, а y – правым делителем нуля.
Пример4: В машинной арифметике целых чисел имеем 256128=0.
2. Тело и поле
Кольцо, в котором все отличные от нуля элементы составляют группу по умножению, называется телом.
Тело, у которого мультипликативная группа абелева, называется полем.
Таким образом, поле - алгебра с такими операциями и , что
(ab)c=a(bc) – сложение ассоциативно;
- существует нуль;
- существует обратный элемент по сложению;
- сложение коммутативно (абелева группа по сложению);
- умножение ассоциативно;
- существует единица;
- существует обратный элемент по умножению;
8. - умножение коммутативно, т.е. поле – абелева группа по умножению.
- умножение дистрибутивно относительно сложения.
Примеры:
Алгебра - множество всех действительных чисел, в котором определены обычные операции сложения и умножения, является полем.
Алгебра - поле рациональных чисел.
Схема образования некоторых понятий для алгебры с двумя операциями показана на рис.13.
Теорема: В поле выполняются следующие соотношения:
Доказательство:
и и
и
Алгебра
рис.13
1.11.6.Решетки
Решетки сами по себе чисто встречается в задачах программирования. Но еще важнее то, что понятие решетки подводит нас к понятию булевой алгебры, которая имеет множество приложений в программировании и вычислительной технике.
Определение. Решетка - это любая алгебра с двумя бинарными операциями и : такими, что выполнены следующие условия (аксиомы решетки):
Идемпотентность: ;
Коммутативность: ;
Ассоциативность:
4. Поглощение:
Решетка называется дистрибутивной, если она подчиняется дистрибутивным законам:
для всех a, b, c M.
Замечание. Если на множестве М введены операции и , то отношение можно установить следующим образом: , а так же .
Таким образом, можно сказать, что решетка – это алгебра
< М, ≤, , > с одним бинарным отношением (≤) и двумя бинарными операциями ( и ).
Примеры:
1. Любое конечное линейноупорядоченное множество является решеткой.
2. Семейство подмножеств Р(А) множества А частично упорядочено отношениям ≤, поэтому < Р(А), ≤ , , > - решетка, элементами которой являются множества, а операции – обычные – теоретико-множественные операции объединения и пересечения.
3. Рассмотрим частично упорядоченное множество , в котором a<b, a<c, a<d; b<e, c<e, d<e, а элементы b, c, d попарно не сравнимы. Система U обращает решетку, показанную на рисунке 14. (М3)
Не все решетки являются дистрибутивными. Решетка М3 не дистрибутивна, так как , тогда как .
Не дистрибутивна так же решетка P5 (Рис.15)
Теорема: Решетка <M, , > дистрибутивна тогда и только тогда, когда она не имеет подрешеток, изоморфных М3 и Р5.
Ограниченные решетки
Решетка, в которой объединение и пересечение существуют для любого подмножества элементов, называется полной решеткой.
О бъединение всех элементов полной решетки – это максимальный элемент решетки, называемый единицей решетки (или верхней гранью решетки):
Рис.14. Рис.15.
Объединение всех элементов полной решетки – это максимальный элемент решетки, называемый единицей решетки (или верхней гранью решетки):
Пересечение всех элементов полной решетки – это минимальный элемент решетки, называемый нулем решетки (или нижней гранью решетки):
В конечных решетках всегда имеются нуль и единица.
Пример: в решетке М3 (рис.11) а = 0; е =1.
Решетка с верхней и нижней гранью называется ограниченной.
Теорема: Если нижняя (верхняя) грань существует, то она единственная.
Доказательство: Пусть имеется два нуля 0 и 0′ решетки. Тогда и . Следовательно, 0 = 0|.
Теорема: <=> .
Доказательство: Пусть . Тогда . <= Пусть . Тогда .
Следствие: <=> ; <=> .
Решетка с дополнением
В ограниченной решетке элемент (или а|) называется дополнением элемента а, если и .
Вообще говоря, в произвольной решетке дополнение не обязано существовать и не обязано быть единственным. Однако в ограниченной решетке дополнение элемента единственно.
Если решетка обладает нулем и такой унарной операцией , определяющей отрицание, что
,
, ,
,
то она называется решеткой с дополнением.
Согласно законам де Моргана и двойного отрицания, одна из операций и может быть выражена через другую. Следовательно, решетку с дополнением можно определить как алгебру с операциями .
Замечание: упорядоченное множество, двойственное решетке, так же является решеткой, в которой пересечение и объединение меняются местами.