Решетка как универсальная алгебра

Решетка может быть также определена как универсальная алгебра с двумя бинарными операциями (они обозначаются + и × или È и Ç, а также Ú и Ù), удовлетворяющая следующим тождествам

(1) a + a = a, (1¢) a × a = a { идемпотентность },

(2) a + b = b + a, (2¢) a × b = b × a { коммутативность },

(3) (a + b) + c = a +(b + c), (3¢) (a × b)× c = a × (b × c) { ассоциативность },

(4) a (a + b) = a, (4¢) a + a × b = a { поглощение }.

Связь между этими двумя определениями устанавливается при помощи формул:

a + b = sup { a, b }, a × b = inf { a, b },

и обратно. При этом для любых элементов a и b эквивалентны следующие утверждения: (а) a £ b; (б) a b = a; (в) a + b = b. Понятия изоморфизма решеток как универсальных алгебр и как частично упорядоченных множеств совпадают.

 

 

25. Алгебраическая система (алгебра). Носитель, основное множество алгебры. Сигнатура алгебры. Универсальная алгебра (собственно алгебра) и реляционная система (модель) как разновидности алгебраической системы (алгебры).

Алгебраическая система (алгебра) определяется как S = (A,O,R), где A — непустое множество, O — семейство операций, R — семейство отношений на множестве A. При этом A называется носителем, или основным множеством; операции из O и отношения из R называются основными или главными. Множество W = O È R называется сигнатурой алгебры S. Система S называется собственно алгеброй, или универсальной алгеброй, если множество R основных отношений пусто; и называется реляционной системой или моделью, если множество O основных операций пусто. Сигнатура любой алгебры должна быть полной, независимой и непротиворечивой. Сигнатура является полной, если любая другая формула может быть представлена в виде пропозициональной формы с помощью ее элементов. Сигнатура называется независимой, если в ней не найдется элемента, выводимого с помощью правил вывода из других элементов сигнатуры. Сигнатура непротиворечива, если не найдется формулы F, которая одновременно справедлива с формулой Ø F.

 

Отображения. Изоморфизм. Автоморфизм. Гомоморфизм. Эпиморфизм. Эндоморфизм. Мономорфизм. Биморфизм.

Функцией или отображением называются всюду определенные функциональные соответствия.

Для любого (а1,а2,..,аn) сущ. единств bÎ B, такой что: (a1,a2..,an) R B.

Записывают: f:A->B; b=f(a).

Представим, что есть отображение одной алг. системы в другую:

<M1,O1,R1> ---> <M2,O2,R2>. Отображение 2х алг систем, сохраняющее операции, наз-ся гомоморфизмом.

Взаимообратный гомоморфизм наз-ся изоморфизмом (в обе стороны будет гомоморфизм) x -> ln(x), y -> ln(y), xy -> ln(xy) = ln(x) + ln(y). Обратно – e^ln(x)…

· Автоморфизм – изоморфизм некоторой системы объектов на себя.

· Эндоморфизм – гомоморфизм алгебраической системы в (в том числе и на) себя.

· Эпиморфизм – или, что то же самое, сюръективное отображение (сюръекция) множества A на множество B – отображение f такое, что образ A есть все B, т.е. f (A)= B (все y должны быть заняты).

· Мономорфизм множества A в множество B – отображение, при котором различные элементы из A имеют различные образы в B. Инъективное отображение называют также взаимно однозначным отображением множества A в множество B или вложением. (от одного x не больше одной стрелки и к каждому Y не больше одной стрелки, не все x и y могут быть заняты)

· Биморфизм, или, что то же самое, биективное отображение (биекция) – мономорфизм и эпиморфизм одновременно.

 

Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф). Кратные ребра (дуги). Петли. Смежные вершины, смежные дуги. Степень вершины. Инцидентные ребро и вершина, дуга и вершина.

Граф — множество V вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно граф обозначают как G (V, E). Неупорядоченная пара вершин называется ребром, упорядоченная пара — дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги — ориентированным (или орграфом). Пара вершин может быть соединена двумя или более ребрами (или, соответственно, дугами одного направления), такие ребра (или дуги) называются кратными. Дуга (или ребро) может начинаться и заканчиваться в одной и той же вершине. В этом случае соотв. дуга (или ребро) называется петлей. Вершины, соединенные ребром или дугой, называются смежными. Ребра, имеющие общую вершину, тоже называются смежными. Степень вершины – количество рёбер, выходящих из вершины. Ребро (или дуга) и любая из его вершин называются инцидентными. Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга (u, v) начинается в вершине u и кончается в вершине v.