Примеры алгебраических систем

1.Модели ‹D,£ › и ‹D,³ › изоморфны, т.к. é _{f (x)} = -x есть биекция и é _{(x) ³} é _{(y) ~} -x ³ -y ~ x £ y.

2.Алгебра ‹Q,+› и ‹Z,+› - неизоморфна. Действительно поля ú Qú =ú Zú (что означает биективные отображения из Q на Z) и многие свойства операций + в ‹Q,+› ‹Z,+› совпадают (т.е. имеют нейтральный элемент, коммутативен, ассоциативен, и т.д.), но свойства операции + в ‹Z,+›, связанные с 1, не выполняются в ‹Q,+› (это даёт возможность доказать отсутствие изоморфизма).

3.Автоморфизмы модели ‹{2,3,4,5,6,7}›, где R={‹x,y› Î M: x,y имеют общий делитель, отличный от 1} сведём в таблицу:

Действительно, R={‹2,4›, ‹4,2›, ‹2,6›, ‹6,2›, ‹3,6›, ‹6,3›, ‹4,6›, ‹6,4›, ‹2,2›, ‹3,3›, ‹4,4›, ‹5,5›, ‹6,6›, ‹7,7› }.

Графовое представление рассматриваемой модели ‹M,R› есть:

‹A,Q,B› гомоморфизмы детерминированных конечных автоматов U₁=‹A,Q,B,d,l ›, U₂=‹A,Q,B,d,l › называется совокупность трёх однозначных отображений ‹é _{f 1} , é _{f 2}, é _{f 3}› (é _{f 1}: Q® Q^’, é _{f 2}: A® A^’, é _{f 3}: B® B^’ ) удовлетворяющих для всех qÎ Q и aÎ A соотношениям:

é _{f 1} (d (q,a))=d ^’(é _{f 1}(q), é _{f 2} (a)), ^é _{f 3} (l (q,a))=l ^’(é _{f 1}(q), é _{f 2} (a)).

Автономный автомат Мура ‹Q,d › осуществляет отображение множество состояний Q в себя, т.е. d: Q® Q (в этом плане, рассматриваемую ‹Q,d › как универсальную алгебру, можно говорить об изоморфизме.

Булева алгебра ‹B_(m), Ù, Ú,- ›, где ç M=n изоморфизм булевой алгебры ‹B_n, Ú, Ù, ù ›, где B_n – множество двоичных векторов длины n.

Действительно, каждому элементу B_(m) (в этом случае элементом является подмножество M_e множества M) взаимно однозначно соответствует двоичный вектор из B_n (т.е. ‹x₁,x₂,…,x_n›; x_i =1, если a_iÎ M_e, и x_i=0, если a_iÏ M_e) т.е. é (M_i)=x, xÎ M_n. Поскольку операции булевой алгебры ‹B_n, Ú, Ù, ù › на множестве B_n определяется для любых x,yÎ B_n тождествами: xÚ y=‹x₁,x₂,…,x_n› Ú ‹y₁,y₂,…,y_n› = ‹x_1Ú y₁, x_2Ú y₂,…, x_nÚ y_n ›,

xÙ y=‹x_1Ù y₁, x_2Ù y₂,…, x_nÙ y_n ›, (*)

x=‹x₁,x₂,…x_n›, то

é (M_iÚ M_j) = é (M₁)Ú é (M₂)=xÚ y

é (M_iÙ M_j) =xÙ y (**)

é (M_i)=x

Справедливость последних трёх выражений вытекает непосредственно из (*): если a_iÎ M_eÚ M_j, то i – ый разряд вектора é (M_eÚ M_k)=1; с другой стороны, это означает, что a_iÎ M_e или a_iÎ M_k, т.е. x_i=1 или y_i=1, и следовательно, i - ый разряд вектора xÚ y равен 1. Если же a_iÏ M_eÚ M_k, то i - ый разряд é (M_eÚ M_k) равен 0. Но тогда a_iÏ M_e и a_iÏ M_k, следовательно, i - ый разряд xÚ y также равен 0. Аналогично доказывается и остальные два равенства (**).

Примечание: В рассматриваемых булевых алгебрах M={a,a,…,a}, ê B(m)ê =2ⁿ, ê B_nê =2ⁿ.

Дата добавления: 2014-01-06