Гомоморфизмы. Проверка условия гомоморфизма. Изоморфизмы. Изоморфные алгебры. Изоморфизм модели. Примеры изоморфных алгебр.
Пусть между множествами А и В установлено соответствие Г - отображение А в 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,...,αη) и β=(β1,β2,...,βη): α)α&β=(α1&β1,α2&β2,...,αη&βη), при этом α1&β1=1, если αi= βi=1, и αi&βi=Ο - в любом другом случае, т.е. если αi=1 и βi=1, αi&βi=1, αi&βi=Ο - в противном случае;
Изоморфизм булевых алгебр широко используется в компьютерных вычислениях, например при необходимости выполнения операций над множествами с применением соответствующих и легко реализуемых на компьютере поразрядных операций над соответствующими двоичными векторами.
Пример.Пусть Μ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; просмотров: 402;