Образовательный блог – всё для учебы

Определение: Решетка L=(A, ?, ?) есть множество А с двумя определенными на нем бинарными операциями x ? y: A x A ? A; x?y: A?*A?A удовлетворяющее следующим аксиомам:
? a,b,c ? A:

L1) x ? x = x, x ? x=y – идемпотентность.
L2) x ? y = y ? x, x ? y = y ? x – коммутативность.
L3) x ? (y ? z)= (x ? y) ? z, x ? (y ? z) = (x ? y) ? z – ассоциативность.
L4) x ? (x ? y)= x, x ? (x ? y) = x – поглощение.

Замечание: Иногда вместо x?y пишут x&y, x?y, xy.

Определение: Решетка называется дистрибутивной, если для нее выполняются аксиомы L1 – L4 и равенство L5:
x ? (y ? z) = (x ? y) ? (x ? z)
x ? (y ? z) = (x ? y) ? (x ? z)

Определение: Решетка называется модулярной, если для нее выполняются аксиомы L1 – L4 и равенство L6:
a ? (b ? (a ? c)) = (a ? b) ? (a ? c)
a ? (b ? (a ? c)) = (a ? b) ? (a ? c)

Замечание: (Принцип двойственности): если в верном в решетке L равенстве заменить «?» на «?», а «?» на «?» с сохранением скобок, то получим снова верное равенство.

Лемма: в решетке L = (A, ?, ?) справедливо соотношение a?b = a ? a?b = b
Без доказательства.

Введем отношение a ? b, положив a ? b ? a?b = a, тогда по лемме a ? b ? a?b =b.

Теорема: в решетке L= (A, ?, ?) отношение a ? b – есть отношение частичного порядка.
Без доказательства.

Следствие: решетка L=(A, ?, ?) есть частично упорядоченное множество (A, ?) c отношением частичного порядка a ? b ? ab = a.

Замечание: Во всяком ЧУМе можно определить функции:
x ? y = sup(x,y)
x ? y = inf(x,y)

Теорема: в ЧУМе справедливы аксиомы L1 – L4 для решетки.

Следствие: Если в ЧУМ (A, ?) операции sup(x,y) и inf(x,y) всюду определены, то по отношению к этим операциям ЧУМ есть решетка.

Решетки имеющие наименьшее O и наибольшее I элементы называются решетками с универсальными границами. Возможны решетки только с одной универсальной границей, возможны без обеих.

Всякая конечная решетка имеет универсальные границы O и I.
Универсальные границы имеют свойства L7:
a?I = I
a?O = a
a?I = a
a?O = O

Определение: Дополнение элемента а решетки L есть такой элемент a ?L, что а?а = I, и a?a=O.

Определение: Решетка в которой каждый элемент имеет дополнение, называется решеткой с дополнениями.

1. Булевы решетки и булевы алгебры
2. Отношение частичного порядка
3. Графы и группы подстановок, орбита группы подстановок
4. отношения. Отношение эквивалентности, фактор-множество
5. Мощность множества. Кардинальные числа.
6. Планарные и плоские графы
7. Конгруенции и фактор-алгебры, теоремы о гомоморфизме
8. СДНФ и СКНФ
9. Дизъюнктивная и Конъюнктивная нормальные формы. Разложение функции по компонентам
10. Суперпозиция функций. Функционально замкнутые классы
11. Рекуррентные уравнения, порядок уравнения, частное и общее решение
12. Функции и отношения, их свойства
13. Графы, мультиграфы, псевдографы, орграфы. Изоморфизм графов
14. Фундаментальная система решений, общее решение однородного и неоднородного ЛРУ с помощью ФСР
15. Целые числа, сравнения – дискретная математика
16. Теорема Поста о функциональной полноте
17. Способы задания графов и операции над графами