Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр.

Пусть между множествами А и В установлено соответствие Г - отображение А в B, т.е. . Это означает, что каждому элементу а из А поставлен в соответствие Г един­ственный элемент α из В, т.е. Г(а) = α. Пусть также на мно­жестве А задана операция φ, на множестве В - операция ψ, обе одинаковой арности, например обе бинарные, так что , где а,b,с €А, и , где α,β,γ€В. Таким образом, имеем две алгебры <Α;φ> и <B;ψ>.

Определение 6. 5. Тогда отображение называется гомоморфизмом алгебры <Α;φ> в алгебру <B;ψ>, если выполняется условие: . (Рисунок 6.1)

Рисунок 6.1.

Условие гомоморфизма требует (см. рис. 6,1), чтобы отображение Г результата с=аφb выполнения на множестве А операции φ над элементами α и b, т.е. Г(с)=Г(aφb), совпадало с результатом γ выполнения на множестве В операции ψ над отображениями этих элементов, т.е. над Γ(α)=α и Γ(b)=β.

Проверка уcловия гомоморфизма заключается в следующем. В соответствии с левой частью сна­чала над элементами а и b из А должна быть выполнена опе­рация φ, а затем результат с=αφb выполнения операции φ отображается из А в множество В. В соответствии с правой частью условия Γ(α)=α и Γ(b)=β требуется сначала выполнить отобра­жения элементов α и b из множества А в В, т.е. найти Г(а)=а и Г(b)=β, а затем над α и β выполнить операцию ψ (задан­ную на множестве В), т.е. Γ(α) ψ Г(&), или α ψ β = γ. Условие будет выполнено, если результат отображения элемен­та с=αφb из А в В совпадает с элементом γ из В, т.е. если Г(с)=у.

Определение 6. 6. Если при этом отображение является взаимно однозначным соответствием, оно называется изоморфизмом алгебры <Α;φ> на алгебру <B;ψ>. В этом случае существует и обратное отображение , также взаимно однозначно: .

Определение 6. 7. Отображение Г^-1 - это, в свою очередь, изоморфизм В на А. Итак, если существует изоморфизм А на В, то существует изоморфизм В на А. При этом алгебры <Α;φ> и <B;ψ> назы­ваются изоморфными.

В более общем случае, если на множествах А и В заданы несколько операций соответственно <Α; {φ₁ φ₂,..., φ_n}> и <В; {ψ_1, ψ₂.....ψ_n}>, отображение является гомоморфиз­мом алгебры <Α; {φ₁ φ₂,..., φ_n}> в алгебру <В; {ψ_1, ψ₂.....ψ_n}>, если условия, аналогичные , выполняются для каждой пары операций φ₁ и ψ₁ ... ,φ_n и φ_n.

В силу взаимной однозначности соответствия при изоморфизме мощности основных множеств изоморфных алгебр равны. Поэтому проверка алгебр на изоморфизм сводится к проверке условия гомоморфизма для каждой пары операций и установления взаимной однозначности соответствия Г (равной мощности множеств А и В).

Аналогично определяется гомоморфизм (изоморфизм) множеств с отношениями - моделей и .

Пусть, например, на множестве А задано бинарное отно­шение R(а,b) а,b € А, и на множестве В—бинарное отношение R'(α,β), α,β € В. Тогда отображение является гомоморфизмом модели в модель , если для любой пары элементов а,b из А такой, что а и b находятся в отношении R, следует, что их отображения Г(а)=α и Г(b)=β находятся в отношении R' (см. рис. 6.2.), т.е.

(аRb влечет Г(а)RГ(b) для любых а,bÎА).

Рисунок 6.2.

Определение 6. 7. Если при этом отображение является взаимно однозначным соответствием, оно называется изомор­физмом модели на модель . В этом случае существует и обратное отображение , также являющееся изоморфизмом: αR'β влечет Г^-1(α)RГ^-1(β) для любых α,βÎВ. При этом модели и называются изоморфными.

Понятие гомоморфизма (изоморфизма) для алгебраических структур вводится аналогично тому, как это сделано для алгебр и моделей, при этом должны выполняться условия сохранения и операций, и отношений.

Понятие изоморфизма - одно из важнейших понятий в современной математике. Так, из условия изоморфизма следует, например, что любое эквивалентное соотношение в алгебре A сохраняется в любой изоморфной ей алгебре A. Это позволяет, получив такие соотношения в алгебре A автоматически распространить их на все алгебры, изоморфные A. В частности, изоморфизм сохраняет свойства ассоциативности, коммутативности и дистрибутивности операций, а также рассматриваемые выше свойства отношений.

Важным примером изоморфных алгебр являются так называемые булевы алгебры, в том числе:

1) β(U), {∩, U, -} - булева алгебра множеств.

Здесь β(U) - множество всех подмножеств (булеан) множества U;

{∩, U, -} - соответственно операции пересечения, объединения, дополнения над множествам

2) {Β_η; &, ν, -} - булева алгебра двоичных векторов дли­ны η.

Здесь Β_η - множество всех двоичных векторов длины η, т.е. Β_η=В´В´...´В=Вⁿ, где В={0,1};

3) {&, ν, -} - операции логического (покомпонентного) ум­ножения, сложения и дополнения соответственно, опреде­ленные следующим образом: для любых векторов α=(α_1,α₂,...,α_η) и β=(β₁,β₂,...,β_η): α)α&β=(α₁&β₁,α₂&β₂,...,α_η&β_η), при этом α₁&β₁=1, если α_i= β_i=1, и α_i&β_i=Ο - в любом другом случае, т.е. если α_i=1 и β_i=1, α_i&β_i=1, α_i&β_i=Ο - в противном случае;

Изоморфизм булевых алгебр широко используется в ком­пьютерных вычислениях, например при необходимости вы­полнения операций над множествами с применением соот­ветствующих и легко реализуемых на компьютере поразряд­ных операций над соответствующими двоичными векторами.

Пример.Пусть Μ₁ - множество сотрудников организации и R₁, - заданное на нем отношение "быть старше" (~); М₂ - конечное множество натуральных чисел (ограни­ченное, например, числом 100) и R₂ - заданное на нем от­ношение "быть больше" (>). Гомоморфные (изоморфны) ли модели:

A = (M;~) и B=(М₂;>)?

1. Определим отображение Г: Μ₁,-> М₂ следующим образом: каждому сотруднику организации из Μ₁ поставим в соответствие Г число из М₂, соответствующее его возрасту (в годах). Установленное таким образом отображение Г: М₁, →М₂ является гомоморфизмом моделей A= (М₁, ~) и B= (М₂; >), так как очевидно выполняется условие (3.2). Действительно, если 'Иванов', 37 лет, старше 'Петрова', 26 лет, т.е. 'Иванов' ~ 'Петрова' и Г( 'Иванов") = 37, Г( 'Петров') = 26, то и 37 > 26.

2. Однако установленное отображение Г: М₁ → М₂ не является изоморфизмом моделей A=(М₁; ~) на B=(М₂;>), так как не является в общем случае взаимно однозначным (если в организации имеются сотрудники одного возраста, например 'Петров' 26 лет и 'Сидоров' 26 лет. В этом случае обратное соответствие Г ^-1 не является отображением, поскольку не функционально (отсутствует единственность образа 26 на множество сотрудников организации).

Таким образом, заданные модели A= (M₁; ~) и B = (М₂;>) гомоморфны, но не изоморфны.

Тема 7. Нечеткие множества. Основные понятия и определения. Основные характеристики. Теоретико-множественные операции над нечеткими множествами. Графическое представление операций.