Алгебраические структуры

Содержание

Слайд 2

Алгебраические методы описания моделей находят самое широкое применение при формализации различных предметных

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

1

Слайд 3

Владение алгебраической терминологией, таким образом, входит в арсенал средств, необходимых для абстрактного

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

2

Слайд 4

Операции и алгебры

Всюду определенная (тотальная) функция
f: Мn → М называется n-арной

Операции и алгебры Всюду определенная (тотальная) функция f: Мn → М называется
(n-местной) операцией на М.
Если операция f— бинарная (то есть f: М х М -> М), то будем писать afb вместо f(а, b) или a о b, где о — знак операции.

3

Слайд 5

множество М вместе с набором операций
∑ = {f1,. . . ,fm},

множество М вместе с набором операций ∑ = {f1,. . . ,fm},
fi :Mni→ M, где ni — арность операции fi , называется алгебраической структурой, универсальной алгеброй или просто алгеброй.
множество М называется основным (несущим) множеством, или основой (носителем);
вектор арностей (ni,...,nm) называется типом;
множество операций ∑ называется сигнатурой;
запись: <М; ∑>

4

Слайд 7

Многоосновная алгебра имеет несколько носителей, а каждая операция сигнатуры действует из прямого

Многоосновная алгебра имеет несколько носителей, а каждая операция сигнатуры действует из прямого
произведения некоторых носителей в некоторый носитель.

Другими словами

6

Слайд 8

Замыкания и подалгебры

Подмножество X ⊂ M называется замкнутым относительно операции f, если

Замыкания и подалгебры Подмножество X ⊂ M называется замкнутым относительно операции f,
∀ x1, …, xn ∈ X, если X замкнуто относительно всех X f∈ X, то называется подалгеброй

Пример

Алгебра - поле действительных чисел. Тип – (2,2). Все конечные подмножества, кроме {0}, не замкнуты относительно обеих операция. Поле рациональных чисел образует подалгебру.

7

Слайд 10

Непустое пересечение подалгебр образует подалгебру.

 

ТЕОРЕМА

9

Непустое пересечение подалгебр образует подалгебру. ТЕОРЕМА 9

Слайд 11

Замыканием множества X включенного в М относительно сигнатуры ∑ (обозначается [X]∑ )

Замыканием множества X включенного в М относительно сигнатуры ∑ (обозначается [X]∑ )
называется множество всех элементов (включая сами элементы X), которые можно получить из X, применяя операции из ∑. Если сигнатура подразумевается, ее можно не указывать.

ТЕОРЕМА

Непустое пересечение подалгебр образует, подалгебру.

10

Слайд 12

В алгебре целых чисел замыканием числа 2 являются четные

В алгебре целых чисел замыканием числа 2 являются четные числа. I. X
числа.
I. X ⊂ Y=[X] ⊂ [Y]; .
2. Х ⊂ [X];
3. [[X]] = [X];
4. [Х] ∪ [Y] ⊂ [X ∪ Y].

Свойства замыкания:

Пример

11

Слайд 13

Пусть заданы сигнатура ∑ = (ϕ1, …, ϕm) типа N = (n1,

Пусть заданы сигнатура ∑ = (ϕ1, …, ϕm) типа N = (n1,
…, nm) и множество переменных V = {x1, x2, …}. Определим множество термов Т в сигнатуре ∑ следующим образом:
V ⊂ T;
t1, …, tni ∈ T & ϕi ∈ ∑ ⇒ ϕ( t1, …, tni) ∈ T.
Алгебра 〈T; ∑〉 называется свободной алгеброй термов, или ∑-алгеброй.
Носителем ∑-алгебры является множество термов, то есть формальных выражений, построенных с помощью знаков операция сигнатуры ∑. Таким образом, с ∑-алгеброй не связано никакое конкретное множество, являющееся носителем. Поэтому ∑-алгебры используются в программировании для определения абстрактных типов данных.

12

Слайд 14

Ассоциативность: (a○b)○c = a○(b○c);
Коммутативность: a○b = b○a;
Дистрибутивность слева: a◊(b○c) = (a◊b)○(a◊c);
Дистрибутивность справа:

Ассоциативность: (a○b)○c = a○(b○c); Коммутативность: a○b = b○a; Дистрибутивность слева: a◊(b○c) =
(a○b) ◊c = (a◊c)○(b◊c);
Поглощение: (a○b) ◊a = a;
Идемпотентность: a○a = a.

Свойства операций

Некоторые часто встречающиеся свойства операция имеют специальные названия. Пусть задана алгебра 〈М;∑〉 и a, b, c ∈ M; ○,◊ ∈ ∑; ○,◊: М × М → М.
Тогда:

13

Слайд 15

Понятие изоморфизма, введенное в этом разделе, является одним из ключевых.

Алгебры с различными

Понятие изоморфизма, введенное в этом разделе, является одним из ключевых. Алгебры с
типами имеют различное строение.

А = 〈N; +〉, B = 〈N10;+10〉, где N10 = {0,1,2,3,4,5,6,7,8,9}, а +10 сложение по модулю 10.
Тогда f: = а mod 10 – гомоморфизм из А в В.

Морфизмы

Гомоморфизм

Пример

Пусть А = 〈A; ϕ1, …, ϕm〉 и В = 〈В; ψ1, …, ψm〉 - две алгебры одинакового типа. Если существует функция f: A→B, такая что ∀ i ∈ 1..m f(ϕi (a1, …, an)) = ψI (f(a1), …, f(an)), то говорят,
что f – гомоморфизм из А в В.

14

Слайд 16

Гомоморфизмы, обладающие дополнительными свойствами, имеют специальные названия:
Гомоморфизм, который является инъекцией, называется мономорфизмом.
Гомоморфизм,

Гомоморфизмы, обладающие дополнительными свойствами, имеют специальные названия: Гомоморфизм, который является инъекцией, называется
который является сюръекцией, называется эпиморфизмом (или эпиоморфизмом).
Гомоморфизм, который является биекцией, называется изоморфизмом.
Если А=В,
то гомоморфизм называется эндоморфизмом,
а изоморфизм называется автоморфизмом.

15

Слайд 17

Изоморфизм

Пусть А = 〈A; ϕ1, …, ϕm〉 и В = 〈В; ψ1,

Изоморфизм Пусть А = 〈A; ϕ1, …, ϕm〉 и В = 〈В;
…, ψm〉 - две алгебры одинакового типа., и f: А→В – изоморфизм.

f

Если f: А→В – изоморфизм, то алгебры А и В называют изоморфными и обозначают так А ~ В.

Если f: А→В – изоморфизм, то f-1: В→А тоже изоморфизм.

ТЕОРЕМА

16

Слайд 18

ТЕОРЕМА

Отношение изоморфизма на множестве однотипных алгебр является эквивалентностью.

17

ТЕОРЕМА Отношение изоморфизма на множестве однотипных алгебр является эквивалентностью. 17

Слайд 19

 

x2

f

ln

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

x2 f ln Понятие изоморфизма является одним из центральных понятий, обеспечивающих применимость
различных областях.
Алгебраические структуры принято рассматривать с точностью до изоморфизма, то есть рассматривать классы эквивалентности по отношению изоморфизма.

Пример

18

Слайд 20

Алгебры с одной операцией

Естественно начать изучение алгебраических структур с наиболее простых.

Алгебры с одной операцией Естественно начать изучение алгебраических структур с наиболее простых.

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

○: M × M → M

19

Слайд 21

Полугруппы

Полугруппа — это алгебра с одной ассоциативной бинарной операцией:
a○(b○c) = (a○b)○c.

Множество слов

Полугруппы Полугруппа — это алгебра с одной ассоциативной бинарной операцией: a○(b○c) =
А+ в алфавите А образует полугруппу относительно операции конкатенации.
Всякое множество функций, замкнутое относительно суперпозиции, является полугруппой.

Пример

20

Слайд 22

Если в полугруппе существует система образующих, состоящая из одного элемента, то такая

Если в полугруппе существует система образующих, состоящая из одного элемента, то такая
полугруппа называется циклической.

(N; +) является циклической полугруппой, поскольку {1} является системой образующих.

Пример

21

Слайд 23

Моноиды

Моноид — это полугруппа с единицей:

∃ e ∀ a a○e = e○a

Моноиды Моноид — это полугруппа с единицей: ∃ e ∀ a a○e
= a.

Множество слов A* в алфавите А вместе с пустым словом Λ образуют моноид.
Пусть Т – множество термов над множеством переменных V и сигнатурой Σ. Подстановкой, или заменой переменных, называется множество пар
σ = {ti//vi}i∈I,
где ti – термы, а vi – переменные, причем vi ∉ ti. Результатом применения подстановки σ к терму t (обозначается tσ) называется терм, который получается заменой всех вхождений переменных vi на соответствующие термы ti.

Пример

22

Слайд 24

 

Пусть ∃ e1 , e2 ∀ a a ○ e1 = e1

Пусть ∃ e1 , e2 ∀ a a ○ e1 = e1
○ a = a & a ○ e2 = e2 ○ a = а. Тогда e1 ○ e2 = e1 & e1 ○ e2 = e2 ⇒ e1 = e2.

ТЕОРЕМА

Единица единственна.

Доказательство

23

Слайд 25

Группы

Группа — это моноид, в котором
Элемент a -1 называется обратным.

∀ a ∃

Группы Группа — это моноид, в котором Элемент a -1 называется обратным.
a-1 a ○ a-1 = a-1○ a = e

24

Слайд 26

Множество невырожденных квадратных матриц порядка n образует группу относительно операции умножения матриц.

Множество невырожденных квадратных матриц порядка n образует группу относительно операции умножения матриц.
Единицей группы является единичная матрица. Обратным элементом является обратная матрица.
Множество подстановок на множестве М, то есть множество взаимно однозначных функций f: M→ M является группой относительно операции суперпозиции. Единицей группы является тождественная функция, а обратным элементом – обратная функция.

25

Слайд 27

Пусть a ○ a-1 = a-1○ a = e & a ○

Пусть a ○ a-1 = a-1○ a = e & a ○
b = b ○ a = e.
Тогда a-1 = a-1○ e = a-1○ (a ○ b) = (a-1○ a) ○ b = e ○ b = b.

ТЕОРЕМА

Обратный элемент единственен.

Доказательство

ТЕОРЕМА

В группе выполняются следующие соотношения:

(a ○ b) -1= b-1 ○ a-1;
a ○ b = a ○ с ⇒ b = с;
b ○ a = с ○ а ⇒ b = с;
(a-1)-1 = а.

26

Слайд 28

(a ○ b)○(b-1○ a-1) = a ○(b ○ b-1) ○ a-1 =

(a ○ b)○(b-1○ a-1) = a ○(b ○ b-1) ○ a-1 =
a ○ e ○ a-1 = a ○ a-1 = e.
а ○ b = a ○ с ⇒ a-1○(a ○ b) = a-1○(a ○ c) ⇒ (a-1○ a) ○ b = (a-1○ a) ○ c ⇒ e ○b = e ○ c ⇒ b = c.
b ○ a = с ○ а ⇒ (b ○ a) ○ a-1 = (с ○ а) ○ a-1 ⇒ b ○ (a ○ a-1) = с ○ (а ○ a-1) ⇒ b ○ e = c ○ e ⇒ b = с.
(a-1) ○ a = a-1 ○ a =e.

Доказательство

27

Слайд 29

a ○ x = b ⇒ a-1 ○ (a ○ x) =

a ○ x = b ⇒ a-1 ○ (a ○ x) =
a-1 ○ b ⇒ (a-1 ○ a) ○ x = a-1 ○ b ⇒ e ○ x = a-1 ○ b ⇒ x = a-1 ○ b

Коммутативная группа, то есть группа, в которой
a ○ b =b ○ a,
называется абелевой. В абелевых группах приняты следующие обозначения: групповая операция обозначается + или ⊕, обратный элемент к а обозначается -а, единица группы обозначается 0 и называется нулем.

ТЕОРЕМА

В группе можно однозначно решить уравнение a ○ x = b , (решение: x = a-1 ○ b).

Доказательство

28

Слайд 30

〈Z; +〉 - множество целых чисел образует абелеву группу относительно сложения. Нулем

〈Z; +〉 - множество целых чисел образует абелеву группу относительно сложения. Нулем
группы является число 0. Обратным элементом является число с противоположным знаком: x-1= -x.
〈Q+; ⋅〉 - множество положительных рациональных чисел образует абелеву группу относительно умножения. Нулем группы является число 1. Обратным элементом является обратное число: (m/n)-1: = n/m.
〈2M; Δ〉 - булеан образует абелеву группу относительно симметрической разности. Нулем группы является пустое множество ∅. Обратным элементом является дополнение: X-1: = M\X.

29

Слайд 31

Алгебры с двумя операциями

В этом разделе рассматриваются алгебры с двумя бинарными операциями:
которые

Алгебры с двумя операциями В этом разделе рассматриваются алгебры с двумя бинарными
условно называются «сложением» и «умножением», соответственно.

⊕, ⊗: M × M → M,

30

Слайд 32

Кольца

Кольцо – это множество М с двумя бинарными операциями ⊕ и ⊗,

Кольца Кольцо – это множество М с двумя бинарными операциями ⊕ и
в котором:
(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) сложение ассоциативно;
∃ 0 ∈M ∀ a a ⊕ 0 = 0 ⊕ a = a существует нуль;
∀ a ∃ - a a ⊕ - a = 0 существует обратный элемент;
A ⊕ b = b ⊕ a сложение коммутативно, то есть кольцо – абелева группа по сложению;
a⊗( b ⊗ c) = (a ⊗ b) ⊗ c умножение ассоциативно, то есть кольцо – полугруппа по умножению;
a⊗(b ⊕ c) = (a ⊗ b) ⊕ ( a ⊗ c) умножение дистрибутивно
(a ⊕ b) ⊗ c = (a ⊗ с) ⊕ ( b ⊗ c) слева и справа.
Кольцо называется коммутативным, если
a ⊗ b = b ⊗ a умножение коммутативно.
Коммутативное кольцо называется кольцом с единицей, если
∃ 1 ∈ M a ⊗ 1 = 1 ⊗a = a существует единица, то есть кольцо с единицей – моноид по умножению.

31

Слайд 33

 
0 ⊗ a = (0 ⊕ 0) ⊗ a = (0 ⊗

0 ⊗ a = (0 ⊕ 0) ⊗ a = (0 ⊗
a) ⊕ (0 ⊗ a) ⇒ -(0 ⊗ a) ⊕ (0 ⊗ a) = -(0 ⊗ a) ⊕ ((0 ⊗ a) ⊕ (0 ⊗ a)) = (-(0 ⊗ a) ⊕ (0 ⊗ a)) ⊕ (0 ⊗ a) ⇒ 0 = 0 ⊕ (0 ⊗ a) = 0 ⊗ a.
(a ⊗ (-b)) ⊕ (a ⊗ b) = a ⊗ (-b ⊕ b) = a ⊗ 0 = 0 ⇒ a ⊗ (-b) = -( a ⊗ b), (a ⊗ b) ⊕((-a) ⊗ b) = (a ⊕ (-a)) ⊗ b = 0 ⊗ b = 0 ⇒ (-a) ⊗ b = -( a ⊗ b).
(-a) ⊗ (-b) = -(a ⊗ ( -b)) = -(-( a ⊗ b)) = a ⊗ b.

ТЕОРЕМА

В кольце выполняются следующие соотношения:
0 ⊗ a = a ⊗ 0 = 0;
a ⊗ (-b) = (-a) ⊗ b = -( a ⊗ b);
(-a) ⊗ (-b) = a ⊗ b.

Доказательство

32

Слайд 34

Если в кольце ∃x ≠ 0 ∃y ≠ 0 x ⊗ y

Если в кольце ∃x ≠ 0 ∃y ≠ 0 x ⊗ y
= 0, то x называется левым, а у – правым делителем нуля.

 

Пример

 

Пример

33

Слайд 35

 
⇒: От противного. Пусть x ⊗ y = 0. Тогда x ≠

⇒: От противного. Пусть x ⊗ y = 0. Тогда x ≠
0 & x ⊗ y = 0 & x ⊗ 0 = 0 ⇒ y = 0, y ≠ 0 & x ⊗ y = 0 & 0 ⊗ y = 0 ⇒ x = 0.
⇐: 0 = (a ⊗ b) ⊕ (-(a ⊗ b)) = (a ⊗ b) ⊕ (-(a ⊗ с)) = (a ⊗ b) ⊕ (a ⊗ (-с)) = a ⊗ (b ⊕ (-с)), a ⊗ (b ⊕ (-с)) = 0 & a ≠ 0 ⇒ b ⊕ (-с) = 0 ⇒ b = c.

ТЕОРЕМА

 

Доказательство

34

Слайд 36

Коммутативное кольцо с единицей, не имеющее делителей нуля, называется областью целостности.

 

Пример

35

Коммутативное кольцо с единицей, не имеющее делителей нуля, называется областью целостности. Пример 35

Слайд 37

Поле – это множество М с двумя бинарными операциями ⊕ и ⊗,

Поле – это множество М с двумя бинарными операциями ⊕ и ⊗,
такими что:
(a ⊕b) ⊕ c = a ⊕ (b ⊕ c) сложение ассоциативно;
∃ 0 ∈M a ⊕ 0 = 0 ⊕ a = a существует нуль;
∀ a ∃ - a a ⊕ - a = 0 существует обратный элемент по сложению;
а ⊕ b = b ⊕ a сложение коммутативно, то есть поле – абелева группа по сложению;
a⊗( b ⊗ c) = (a ⊗ b) ⊗ c умножение ассоциативно;
∃ 1 ∈ M a ⊗ 1 = 1 ⊗a = a существует единица;
∀ a ≠ 0 ∃ a-1 a-1 ⊗ a = 1 существует обратный элемент по умножению;
a ⊗ b = b ⊗ a умножение коммутативно, то есть поле – абелева группа по умножению;
a⊗(b ⊕ c) = (a ⊗ b) ⊕ ( a ⊗ c) умножение дистрибутивно относительно сложения

Поля

36

Слайд 38

〈R; +, ⋅〉 - поле вещественных чисел.
〈Q; +, ⋅〉 - поле рациональных

〈R; +, ⋅〉 - поле вещественных чисел. 〈Q; +, ⋅〉 - поле
чисел.
Пусть E2 : = {0, 1}. Определим операции ⊕, ⋅: E2 × E2→ E2 следующим образом: 0⋅0 = 0, 0⋅1 = 0, 1⋅0 = 0, 1⋅1 = 1, 0⊕0 = 0, 0⊕1 = 1, 1⊕0 = 1, 1⊕1=0. Тогда ε2: = 〈 E2; ⊕, ⋅〉 является полем и называется двоичной арифметикой.

Пример

37

Слайд 39

(a ⊗ (-1)) ⊕ a = (a ⊗ (-1)) ⊕ (a ⊗

(a ⊗ (-1)) ⊕ a = (a ⊗ (-1)) ⊕ (a ⊗
1) = a ⊗ (-1 ⊕ 1) = a ⊗ 0 = 0.
(а ⊕ b) ⊕ ((-а) ⊕ (-b)) = (а ⊕ b) ⊕ ((-b) ⊕ (-а)) = а ⊕ (b ⊕ (-b)) ⊕ (-а) = а ⊕ 0 ⊕ (-а) = а ⊕ (-а) = 0.
а-1 ⊗ a = 1.
а ⊗ b = 0 & а ≠ 0 ⇒ b =1 ⊗ b = (а-1 ⊗ a) ⊗ b = а-1 ⊗ (a ⊗ b) = а-1 ⊗ 0 = 0, а ⊗ b = 0 & b ≠ 0 ⇒ a = 1 ⊗ a = (b-1 ⊗ b) ⊗ a = b-1 ⊗ (b ⊗ a) = b-1 ⊗ (а ⊗ b) = b-1 ⊗ 0 = 0.

ТЕОРЕМА

В поле выполняются следующие соотношения:
(-а) = а ⊗ (-1);
–(а ⊕ b) = (-а) ⊕ (-b);
а ≠ 0 ⇒ (a-1)-1 = a;
a ⊗ b = 0 ⇒ a = 0 ∨ b = 0.

Доказательство

38

Слайд 40

а ⊗ x ⊕ b = 0 ⇒ а ⊗ x ⊕

а ⊗ x ⊕ b = 0 ⇒ а ⊗ x ⊕
b ⊕ (-b) = 0 ⊕ (-b)а ⊗ x ⊕ (b ⊕ (-b)) = -b ⇒ а ⊗ x + 0 = -b ⇒ а ⊗ x = -b ⇒ а-1 ⊗ (а ⊗ x) = а-1 ⊗ (-b) ⇒ (а-1 ⊗ а) ⊗ x = -( а-1⊗ b) ⇒ 1 ⊗ x = -( а-1 ⊗ b) ⇒ x = -( а-1 ⊗ b).

ТЕОРЕМА

Если а ≠ 0, то в поле единственным образом разрешимо уравнение
а ⊗ x ⊕ b = 0, (х = -( а-1) ⊗ b).

Доказательство

391

Слайд 41

Решетки иногда называют «структурами», но слово «структура» перегружено, и мы не будем

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

Решётки

40

Слайд 42

⇒: Пусть a ∩ b = b. Тогда a ∪ b =

⇒: Пусть a ∩ b = b. Тогда a ∪ b =
a ∪ (a ∩ b) = (a ∩ b) ∪ a = a.
⇐: Пусть a ∪ b = a. Тогда a ∩ b = (a ∩ b) ∩ b = (b ∪ a) ∩ b = b.

ТЕОРЕМА

Если нижняя (верхняя) грань существует, то она единственна

ТЕОРЕМА

a ∩ b = b ⇔ a ∪ b = a.

Доказательство

Если в решетке ∃0 ∈M ∀ a 0 ∩ a = 0, то 0 называется нулем (или нижней гранью) решетки. Если в решетке ∃1 ∈M ∀ a 1 ∪ a = 1, то 1 называется единицей (или верхней гранью) решетки. Решетка с верхней и нижней гранями называется ограниченной.
Пусть 0’ – еще один нуль решетки. Тогда 0 ∩ 0’ = 0’ и 0’ ∩ 0 = 0.
Следовательно 0 = 0’.

Доказательство

41

Слайд 43

В ограниченной решетке элемент а’ называется дополнением элемента а, если a ∩

В ограниченной решетке элемент а’ называется дополнением элемента а, если a ∩
а’ = 0 и a ∪ а’ = 1.
Если ∀ а ∈M ∃ а’ ∈M a ∩ а’ = 0 & a ∪ а’ = 1, то ограниченная решетка называется решеткой с дополнением. Вообще говоря, дополнение не обязано существовать и не обязано быть единственным.

ТЕОРЕМА

(о свойствах дополнения) В ограниченной дистрибутивной решетке с дополнением выполняется следующее:
дополнение а’ единственно;
дополнение инволютивно: а” = а;
грани дополняют друг друга: 1’ = 0, 0’ = 1;
выполняются законы де Моргана: (a ∪ b)’ = а’ ∩ b’, (a ∩ b)’ = а’ ∪ b’.

42

Слайд 44

Частичный порядок в решётке

 

ТЕОРЕМА

 

Доказательство

 

43

Частичный порядок в решётке ТЕОРЕМА Доказательство 43

Слайд 46

 

ТЕОРЕМА

Если в частично упорядоченном множестве для любых двух элементов существуют нижняя

ТЕОРЕМА Если в частично упорядоченном множестве для любых двух элементов существуют нижняя
и верхняя грани, то это множество образует решетку относительно inf u sup (то есть x ∩ y: inf(x, y), x ∪y: sup(x, y)).

ТЕОРЕМА

Если нижняя(верхняя) грань существует, то она единственна.

Доказательство

45

Слайд 47

Булевы алгебры

Дистрибутивная ограниченная решетка, в которой для каждого элемента существует дополнение, называется

Булевы алгебры Дистрибутивная ограниченная решетка, в которой для каждого элемента существует дополнение,
булевой алгеброй.

 

Пример

46

Слайд 48

a ∪ a = a, a ∩ a = a
по определению решетки;
2. a

a ∪ a = a, a ∩ a = a по определению
∪ b = b ∪ a, a ∩ b = b ∩ a,
по определению решетки;
a ∪ (b ∪ c) = (a ∪ b) ∪ c, a ∩ (b ∩ c) = (a ∩ b) ∩ c
по определению решетки;
(a ∩ b) ∪ a = a, (a ∪ b) ∩ a =a
по определению решетки;
a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c), a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c)
по свойству дистрибутивности;
a ∪ 1 = 1, a ∩ 0 = 0
по свойству ограниченности;
a ∪ 0 = a, a ∩ 1 = a
по следствию из теоремы ограниченности;
a’’ = a
по теореме о свойствах дополнения;
(a ∩ b)’ = a’ ∪ b’, (a ∪ b)’ = a’ ∩ b’
по теореме о свойствах дополнения;
a ∪ a’ = 1, a ∩ a’ = 0
так как дополнение существует.

47

Имя файла: Алгебраические-структуры.pptx
Количество просмотров: 45
Количество скачиваний: 0