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


Пусть между множествами А и В установлено соответствие Г - отображение А в 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;ψ> назы­ваются изоморфными.

В более общем случае, если на множествах А и В заданы несколько операций соответственно <Α; {φ1 φ2,..., φn}> и <В; {ψ1, ψ2.....ψn}>, отображение является гомоморфиз­мом алгебры <Α; {φ1 φ2,..., φn}> в алгебру <В; {ψ1, ψ2.....ψn}>, если условия, аналогичные , выполняются для каждой пары операций φ1 и ψ1 ... ,φ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) {Βη; &, ν, -} - булева алгебра двоичных векторов дли­ны η.

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

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

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

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

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

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

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

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

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

Нечеткие множества. Основные понятия и определения.

Пусть E- универсальное множество, x - элемент E, а R - некоторое свойство. Обычное (четкое) подмножество A универсального множества E, элементы которого удовлетворяют свойству R, определяется как множество упорядоченных пар , где , µA(х)- характеристическая функция, принимающая значение 1, если x удовлетворяет свойству R, и 0 - в противном случае.

Определение 7.1. Нечеткое подмножество отличается от обычного тем, что для элементов x из E нет однозначного ответа "да-нет" относительно свойства R. В связи с этим, нечеткое подмножество A универсального множества E определяется как множество упорядоченных пар , где

µA(х) - характеристическая функция принадлежности (или просто функция принадлежности), принимающая значения в некотором вполне упорядоченном множестве M (например, M=[0,1]). Функция принадлежности указывает степень (или уровень) принадлежности элемента x подмножеству A.

Определение 7.2. Множество M называют множеством принадлежностей. Если M={0,1}, то нечеткое подмножество A может рассматриваться как обычное или четкое множество.



Дата добавления: 2021-07-22; просмотров: 395;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.014 сек.