лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4

• Название: Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
• Анкор: лекции по дм
• Дата: 08.02.2021
• Размер: 1.51 Mb.
• Имя файла: лекции.docx
• Тип: Документы; #174835
• страница: 13 из 40

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

Алгебраическая система

Определение 6.1. Множество Μ вместе с заданными на нем операциями {φ1, φ2,...,φ n} называется алгеброй. Обозначение алгебры: , где М называется основным множеством (несущим множеством, носителем), а - сигнатурой алгебры A.

Примером алгебры является полугруппа - множество Μ с заданной на нем одной бинарной ассоциативной операцией (обозначается: · ), т.е. A= {М; ·}, например множество натуральных чисел N с операцией сложения + на нем, т.е. A= {Ν; +} является полугруппой.

Типом алгебры A называется вектор парностей операций сигнатуры. Например, в алгебре A= {R; +, χ}, где R - множество действительных чисел, + и χ - соответственно операции сложения и умножения (такая алгебра называется полем действительных чисел), сигнатура Σ = {+, χ} включает две бинарные операции - сложение и умножение. Поэтому тип данной алгебры (2,2).

Определение 6.2. Алгебраическую систему , где множество состоит из одной двухместной операции, называется группоидом.

Определение 6.2. кольцом называется алгебра с двумя операциями , если обладает следующими свойствами:

• 
  - Авелева группа
  
• 
  - полугруппа
  
• 
  Операция умножения дистрибутивна относительно сложения ( ).
  

Определение 6.3. Множество Μ вместе с заданными на нем отношениями {R₁ R₂, ..., R_n} называется моделью. Обозначение модели: , где М - несущее множество (универсум), – сигнатура модели V. Например, моделью V₁| является мно­жество М₁, чисел с отношениями: "быть больше" (>) и "быть равным" (=), т.е. V₁ = (M₁; >, =), или некоторое множество M_г людей с отношением R - "быть руководителем", т.е. V_г = (М₂; R), и т.д.

Определение 6.4. Множество Μ вместе с заданными на нем операциями {φ₁, φ₂, ..., _n} и отношениями {R_1, R₂, ···,R_n} называется алгебра­ической системой, или алгебраической структурой. Обозначение алгебраической структуры:

V= (Μ; φ₁, φ₂,..., φ_n; R₁, R₂,..., R_n).

Если полугруппа обладает коммутативным свойством ( ), то её называют Авелевой группой.

Примером алгебраической структуры является так назы­ваемая решетка - множество Μ с заданными на нем: одним бинарным отношением частичного порядка (обозначение ≤) и двумя бинарными операциями ( ∩ и U ): {М;≤; ∩, U }.

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

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

Пусть между множествами А и В установлено соответствие Г - отображение А в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. Нечеткие множества. Основные понятия и определения. Основные характеристики. Теоретико-множественные операции над нечеткими множествами. Графическое представление операций.