Судоплатов С.В., Овчинникова Е.В. Дискретная математика. Учебник для дистанционного образования новосибирск 2011 Рецензенты А. Г. Пинус др физмат наук, проф
 Скачать 1.36 Mb.
|
|
) найти множество нижних и верхних граней множества {A, B}. Чему равен inf{A, B} и sup{A, B}? Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ. Построить линейный порядок на множестве комплексных чисел. Составить матрицу отношения полного порядка, при котором нумерация элементов ведется а) по возрастанию отношения б) по его убыванию. После изучения главы 1 выполняются задачи 1–5 контрольной работы. Задача 1 решается аналогично примеру 1.1.6 и предложению задача 2 — аналогично примеру 1.3.1, задача 3 — аналогично примерами утверждениям из §1.4, а задачи 4 и 5 — аналогично примерам из Глава АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Определения и примеры Рассмотрим непустое множество A. В § 1.2 было введено понятие местной операции на множестве A: f : A n → A. Отметим, что, поскольку операция f является функцией, для любого набора, . . . , x n ) ∈ A n результат применения операции f (x 1 , . . . , x n ) однозначно определен. Так как область значений операции f лежит в множестве, то будем говорить, что операция f замкнута на множестве Сигнатурой или языком Σ называется совокупность предикатных и функциональных символов с указанием их местности. Местный функциональный символ называется константным символом или просто константой. Если α — функциональный или предикатный символ, то его местность обозначается через µ(α). Местные предикатные и функциональные символы часто будем обозначать соответственно через и f (n) . Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, для отношения порядка, | для отношения делимости, для константного символа и другие, то мы просто пишем Σ = { }, Σ = { , +, ·, 0}, Σ = {+, −, |, 0, 1} и т.д. Алгебраической системой A = A; Σ сигнатуры Σ называется непустое множество A, где каждому местному предикатному (функциональному) символу из Σ поставлен в соответствие местный предикат (соответственно операция, определенный на множестве A. Множество называется носителем или универсумом алгебраической системы. Предикаты и функции, соответствующие символам из, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент (константа) из A. Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Алгебраические системы в дальнейшем будут обозначаться готическими буквами A, B, . . . (возможно, с индексами, а их носители — соответствующими латинскими буквами A, B, . . . (с соответствующими индексами. Иногда мы будем отождествлять носитель с алгебраической системой. Мощностью алгебраической системы A называется мощность ее носителя. В дальнейшем будем часто опускать слово “алгебраическая” и называть A системой или структурой. Сигнатура Σ называется функциональной (предикатной, если она не содержит предикатных (функциональных) символов. Система A называется алгеброй (моделью, если ее сигнатура функциональна (пре- дикатна). П р им ер. Набор ω; +, · является алгеброй с двумя двухместными операциями. Набор ω; , +, ·, , 0, 1 является системой с бинарным отношением, двухместными операциями +, · (µ(+) = µ(·) = одноместной операцией : n → n+1 (µ( ) = 1) и двумя нуль-местными операциями (константами) 0, 1 (µ(0) = µ(1) = 0). 3. Набор Z; +, :, √ 2 не образует алгебру, поскольку деление не является операцией на множестве Z (например, 2 : 3 / ∈ Z), а элемент √ 2 не принадлежит Z. 4. Набор P(U); ∩, ∪, , 0, 1 с двухместными операциями ∩, ∪, одноместной операцией A → A, константами 0 = ∅ и 1 = U является алгеброй, называемой алгеброй Кантора. Алгеброй является любое кольцо. Пара {f (x)|f : R → R}; d где d dx — операция дифференцирования) не является алгеброй, поскольку не всякая функция дифференцируема, но если рассмотреть множество A = {f (x) | f (x) дифференцируема бесконечное число раз, то отображение дифференцирования d dx : f → df dx является операцией на A и пара A; d dx образует алгебру. Заметим, что частичную операцию f , отображающую A n в A, можно рассматривать как (n + местное отношение, x 2 , . . . , x n , y)|(x 1 , . . . , x n ) ∈ A n и y = f (x 1 , . . . , x Поэтому в последнем примере пару {f (x)|f : R → R}; d dx можно считать алгебраической системой, если рассматривать d dx как бинарное отношение {(f, g)|g = df Алгебра A сигнатуры Σ = {f }, где µ(f ) = 2, называется группои- дом. Единственная здесь операция f обычно обозначается символом ·: 2.2. МОРФИЗМЫ 37 A = A; · . Если A — конечное множество, действия операции · можно задать квадратной таблицей, в которой для каждой пары (a i , a j ) ∈ записан результат действия ·(a i , a j ). Такая таблица называется таблицей Кэли группоида A. Группоид A называется полугруппой, если — ассоциативная операция, те. для всех элементов x, y, z ∈ A верно x·(y·z) = (x·y)·z. Полугруппа A называется моноидом, если существует элемент e ∈ A, называемый единицей, такой, что e·x = x·e = x для всех x ∈ A. Полугруппы и моноиды имеют особое значение в теории языков при обработке слов. П р им ер. Пусть W (X) — множество слов алфавита Определим на W (X) операцию конкатенации ˆ следующим образом: если α, β ∈ W (X), тот. е. результатом является слово, полученное соединением слови (например, xyzˆzx = xyzzx). Операцияˆ ассоциативна, те. для любых слов α, β, γ верно (αˆβ)ˆγ = Следовательно, система W (X);ˆ является полугруппой. Так как для всех α ∈ W (X) верно Λˆα = αˆΛ = α, где Λ — пустое слово, то удовлетворяет свойству единицы. Таким образом, система W (является моноидом. Моноид A = A; называется группой, если для любого элемента существует элемент x −1 ∈ A, называемый обратным к такой, что x · x −1 = x −1 · x = e. Группа A называется коммутативной или абелевой, если x · y = y · x для всех x, y ∈ Пример. Если K; +, · — кольцо, то K; + — абелева группа. Система GL n (K); · , где GL n (K) = {A|A — матрица порядка n над полем K, и det A = 0} является группой, которая некоммутативна при n 2. § 2.2. Морфизмы Пусть даны алгебраические системы A = A; Σ и B = B; Σ Отображение ϕ : A → B называется гомоморфизмом системы A в систему, если выполняются следующие условия) для любого функционального символа f (n) ∈ Σ, соответствующих функций ив системах A и B и любых a 1 , a 2 , . . . , a n ∈ выполняется, a 2 , . . . , a n )) = f B (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )); 2) для любого предикатного символа P (n) ∈ Σ, соответствующих предикатов ив системах A и B и любых a 1 , a 2 , . . . . . . , a n ∈ A Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ выполняется (a 1 , a 2 , . . . , a n ) ∈ P A ⇒ (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )) ∈ Если ϕ : A → B — гомоморфизм, то будем его обозначать через : A → При гомоморфизме сохраняются действия операций и отношения. Это позволяет переносить изучение свойств с одной системы на дру- гую. П р им ер. Рассмотрим системы A = Z; +и B = = Z 2 ; +, , где в системе B сложение задается по правилу, b 1 ) + (a 2 , b 2 ) = (a 1 + a 2 , b 1 + а отношение порядка — (a 1 , b 1 ) (a 2 , b 2 ) ⇔ и Отображение ϕ : Z → Z 2 , при котором ϕ(a) = (a, 0), является гомоморфизмом. Действительно, для любых a, b ∈ Z имеем + b) = (a + b, 0) = (a, 0) + (b, 0) = ϕ(a) + и если a b, тот. е. Гомоморфизм ϕ : A → B, являющийся инъекцией, называется мо- номорфизмом. Гомоморфизм ϕ : A → B, являющийся сюръекцией, называется эпиморфизмом, и при этом система B называется гомо- морфным образом системы A. Гомоморфизм ϕ : A → A называется эндоморфизмом. Сюръективный мономорфизм ϕ : A → B, для которого гомоморфизм, называется изоморфизмом A на B и обозначается через ϕ : A ∼ → B. Если существует изоморфизм ϕ : A ∼ → то системы A и B называются изоморфными и обозначается это так: A B. Таким образом, условие A B означает, что существует биекция ϕ : A ↔ B, удовлетворяющая следующим условиям) для любого функционального символа f (n) ∈ Σ, соответствующих функций ив системах A и B и любых a 1 , a 2 , . . . . . . , a n ∈ выполняется, a 2 , . . . , a n )) = f B (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )); 2) для любого предикатного символа P (n) ∈ Σ, соответствующих предикатов ив системах A и B и любых a 1 , a 2 , . . . . . . , a n ∈ выполняется, a 2 , . . . , a n ) ∈ P A ⇔ (ϕ(a 1 ), ϕ(a 2 ), . . . , ϕ(a n )) ∈ P B 2.2. МОРФИЗМЫ 39 Изоморфизм ϕ : A ∼ → A называется автоморфизмом системы Заметим, что, поскольку изоморфизм ϕ : A ∼ → B является биекцией A ↔ B, изоморфные системы равномощны. Утверждение 2.2.1. 1. id A : A ∼ → A. 2. Если ϕ : A ∼ → B, то ϕ −1 : B ∼ → A. 3. Если ϕ : A 1 ∼ → и ψ : A 2 ∼ → A 3 , то ϕ ◦ ψ : A 1 ∼ → Таким образом, отношение изоморфизма является эквивалентностью на любом множестве алгебраических систем (отметим, что класс всех алгебраических систем не является множеством, поскольку несу- ществует множества всех множеств. Это означает, что отношение изоморфизма разбивает множества алгебраических систем на классы эквивалентности, в каждом из которых содержатся системы, имеющие “одинаковое устройство. Это дает возможность переносить изучение свойств с одной системы на другую, изоморфную ей. Так, используя факт изоморфизма геометрического векторного пространства пространству строк, работу с геометрическими объектами можно свести к действиям с наборами чисел, что позволяет применять компьютеры. П р им ер. Рассмотрим множество векторов геометрического векторного пространства с операциями сложения векторов и умножения векторов на вещественные числа. Получим систему A = E 3 ; +, бесконечной сигнатуры, где одноместные функции ставят в соответствие вектору a вектор λa. Рассмотрим также систему, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умножения троек на число для всех вещественных чисел λ. Системы A и B являются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору a ∈ его координатную строку (x, y, z) в некотором фиксированном базисе e 1 , e 2 , e 3 , является биекцией (ϕ : E 3 ↔ R 3 ), при которой сохраняются действия операций ϕ(a + b) = ϕ(a) + ϕ(b) и · a) = λ · ϕ(a). Таким образом, ϕ — изоморфизм линейных пространств и B, и, следовательно, изучение геометрических векторов можно свести к изучению троек чисел и наоборот. Рассмотрим два равномощных алфавита X, X и алгебры A = W (X);ˆ , B = W (X );ˆ (см. пример 2.1.2). Покажем, что Так как |X| = |X |, то существует биекция ϕ : X ↔ X . Построим по ней биекцию ψ : W (X) ↔ W (X ), при которой слову α ∈ W (ставится в соответствие слово β ∈ W (X ), получающееся заменой каждого символа x в слове α на символ ϕ(x). Построенная биекция ψ дает Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ искомый изоморфизм A на B, поскольку ψ(α 1 ˆα 2 ) = ψ(α 1 )ˆψ(α 2 ) для любых α 1 , α 2 ∈ W (X). 3. Для заданного множества U система P(U); ∩, ∪, , 0, 1 изоморфна системе P(U); ∪, ∩, , 1, 0 с биекцией ϕ : A → A. Действительно, по законам де Моргана ϕ(B ∩ C) = B ∩ C = B ∪ C = ϕ(B) ∪ ϕ(C) и ∪ C) = B ∪ C = B ∩ C = ϕ(B) ∩ ϕ(C) для любых B, C ∈ Кроме того, ϕ(A) = A = ϕ(A), ϕ(0) = 0 = 1 и ϕ(1) = 1 = 0. 4. Рассмотрим группы A = (0, ∞); · , B = R; + и отображение ϕ : (0, ∞) → R по правилу ϕ(x) = log p (x) для некоторого фиксированного p ∈ (0, ∞), p = 1. Отображение ϕ является изоморфизмом систем и B, называемым логарифмом (по основанию p). Это позволяет производить умножение положительных чисел при помощи сложения вещественных чисел на основании тождества a · b = ϕ −1 (ϕ(a) + которое получается из равенства ϕ(a · b) = ϕ(a) + ϕ(b) применением отображения к обеим частям 2.3. Подсистемы Алгебраическая система A = A; Σ называется подсистемой системы (обозначается через A ⊆ B), если выполняются следующие условия: а) A ⊆ б) для любого функционального символа f (n) ∈ Σ, соответствующих функций и и любых элементов a 1 , a 2 , . . ., a n ∈ A выполняется равенство f A (a 1 , . . . , a n ) = f B (a 1 , . . . , a n ), те. интерпретации символа f действуют одинаково на элементах изв) для любого предикатного символа P (n) ∈ Σ, соответствующих предикатов и справедливо равенство P A = P B ∩ A n , те. предикат содержит в точности те кортежи отношения P B , которые состоят из элементов множества Если Σ — функциональная (предикатная) сигнатура, то подсистема алгебры (модели) B называется подалгеброй (подмоделью). П р им ер. Если V — подпространство линейного пространства, то V — подсистема (подалгебра) системы V . 2. Если Σ = {P (1) }, B = B; Σ — система, ∅ = A ⊆ B, то A = A; Σ является подсистемой системы B тогда и только тогда, когда Теорема 2.3.1. Если B — алгебраическая система, X ⊆ B, X = ∅, то существует единственная подсистема B(X) ⊆ B с носителем, такая, что X ⊆ B(X) и B(X) ⊆ A для любой подсистемы с условием X ⊆ A. 2.3. ПОДСИСТЕМЫ 41 Подсистема B(X) из теоремы 2.3.1 называется подсистемой, порожденной множеством X в B. Она является наименьшей подсистемой системы B, содержащей множество Пример. Если V — линейное пространство, S — некоторое непустое множество векторов пространства V , то линейная оболочка) множества S в V состоит из всевозможных линейных комбинаций векторов из S. Алгебра L(S) является подалгеброй пространства V порожденной множеством Для описания устройства подсистемы B(X) определим индукцией по построению понятие терма сигнатуры Σ: 1) переменные x, y, z, . . . и константные символы из Σ суть термы) если f ∈ Σ — местный функциональный символ, t 1 , t 2 , . . ., t термы, то f (t 1 , . . . , t n ) — терм) никаких термов, кроме построенных по пп. 1, 2, нет. Таким образом, термом является любое функциональное выражение, составленное с помощью переменных и (или) сигнатурных функциональных символов. Множество всех термов сигнатуры Σ обозначается через T Пример. Термами сигнатуры Σ = {+, ·, , 0} будут, например, 0, x, x + y, z · (x + z) + 0 · y, а x + y (0 + z) · x термом не является. Если Σ = {f, g, h} — функциональная сигнатура, где ) = 3, µ(g) = 1, µ(h) = 2, то выражения h(f (x 1 , x 2 , x 3 ), g(x 2 )), g(f (h(x 1 , x 2 ), x 1 , g(x 2 )) — термы, а h(x 1 , f (x 1 , x 3 )) не образует терма. В сигнатуре Σ = отец, Иван терм отец(отец(Иван)) можно проинтерпретировать как дедушка Ивана”. Пусть t(x 1 , x 2 , . . . , x k ) — терм из T (Σ), все переменные которого содержатся среди x 1 , x 2 , . . . , x k ; A = A; Σ — алгебраическая система. Значение терма t при значениях a 1 , a 2 , . . . , a k ∈ A переменных x 1 , x 2 , . . . , x k (t(a 1 , a 2 , . . . , a k )) определяется по индукции) если t есть переменная x константный символ c), то значение t есть a i (c); 2) если терм t есть f (t 1 , . . . , t n ), а значения t 1 , . . . , t суть b 1 , . . . , b то значение терма t есть f (b 1 , . . . , b Теорема 2.3.2. Если B = B; Σ — алгебраическая система = ∅ и X ⊆ B, то носитель подсистемы B(X) равен {t(a 1 , . . . , a n ) | t ∈ T (Σ), a 1 , . . . , a n ∈ Таким образом, носитель подсистемы B(X) состоит из всех элементов, которые получаются при подстановке элементов изв термы Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ П р им ер. Найдем носитель подсистемы B(X) системы = Q\{0}; · для множества X = { 1 2 }. Так как сигнатура Σ системы есть {·}, то T (Σ) = {x 1 , x 1 ·x 2 , (x 1 ·x 2 )·x 3 , x 1 ·(x 2 · ·x 3 ), . . .}. По теореме получаем B(X) = { 1 2 , 1 2 · 1 2 , 1 2 · 1 2 · 1 2 , . . .} = = { 1 2 , 1 4 , 1 8 , 1 16 , . . .} = { 1 2 n | n 1}. 2. Если B = Q \ {0}; ·, : , X = { 1 2 }, то, поскольку по сравнению с предыдущим примером сигнатура дополняется операцией деления x : y, множество B(X) содержит также числа 2 n : 1 2 m = 2 m−n , m, те. Так как множество C замкнуто относительно операций умножения и деления, те является подсистемой системы B и содержит множество X, то B(X) ⊆ C. Следовательно. Найдем носитель подсистемы B(X) системы B = C; +, ı для множества X = {−2, 2}. Так как все термы из T (Σ) являются переменными, константой или образуются из переменных и константы ı с помощью операции сложения, то каждый элемент из B(X) получается подстановкой элементов изв некоторый терм x 1 + x 2 + . . . + x m + ı + ı + . . . + ı. Следовательно, B(X) = {2m + n ı | m ∈ Z, n ∈ ω}. § 2.4. Конгруэнции. Фактор-алгебры. Теорема о гомоморфизме Конгруэнцией на алгебре A = A; Σ называется такое отношение эквивалентности θ ⊆ A 2 , при котором для любого n ∈ ω, любого местного символа f ∈ Σ (напомним, что сигнатура алгебры состоит только из функциональных символов, произвольных наборов, a 2 , . . . , a n ), (b 1 , b 2 , . . . , b n ) ∈ A n , если a 1 θ b 1 , a 2 θ b 2 , . . . , a n θ b n , то f (a 1 , a 2 , . . . , a n ) θ f (b 1 , b 2 , . . . , b Это означает, что все операции согласованы с отношением эквивалентности. Например, для операции сложения это выглядит так: для любых элементов x, y ∈ A, любых a ∈ θ(x), b ∈ θ(y) элемент a + b принадлежит классу θ(x + Рассмотрим фактор-множество множества A по конгруэнции θ: A/θ = {θ(x)|x ∈ A}. Определим на этом множестве алгебру сигнатуры. Константе c алгебры A поставим в соответствие элемент который в A/θ будет интерпретировать константный символ c. Если f — местный символ из Σ, то зададим на множестве A/θ действие функции f по правилу f (θ(x 1 ), . . . , θ(x n )) θ(f (x 1 , . . . , x Убедимся, что для любых x 1 , . . . , x n ∈ A это определение коррект- 2.5. РЕШЕТКИ И БУЛЕВЫ АЛГЕБРЫ Рис. ноте. не зависит от выбора представителей классов эквивалентности. Действительно, если θ(x i ) = θ(y i ), i = 1, 2, . . . , n, то x i θ y i , откуда в силу свойства конгруэнции имеем f (x 1 , . . . , x n ) θf (y 1 , . . . , y те Получившаяся алгебра A/θ A/θ; Σ называется фактор-алгеброй алгебры A по конгруэнции Очевидно, что отображение A → A/θ, при котором элементу x ∈ ставится в соответствие класс θ(x), является эпиморфизмом алгебры на фактор-алгебру A/θ. Этот эпиморфизм называется естественным гомоморфизмом. Если ϕ : A → B — гомоморфизм алгебр, то множество Ker ϕ {(a, a )|ϕ(a) = ϕ(a )} оказывается конгруэнцией на алгебре A и называется ядром гомоморфизма Следующая теорема утверждает, что гомоморфный образ алгебры изоморфен фактор-алгебре по ядру гомоморфизма. Теорема 2.4.1 (теорема о гомоморфизме. Если ϕ : A → → B — эпиморфизм, ψ : A → A/Ker ϕ — естественный гомоморфизм, то существует изоморфизм χ : B ∼ → A/Ker ϕ такой, что ϕ ◦ χ = Отображения ϕ, ψ и χ из теоремы 2.4.1 можно представить диаграммой, показанной на рис. 2.1. § Решетки и булевы алгебры Следующей нашей целью является определение и изучение понятия булевой алгебры, но сначала рассмотрим более общее понятие понятие решетки. Решеткой называется ч.у.м. A = A; , в котором каждая пара элементов имеет супремум и инфимум. Для заданных элементов Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ, y ∈ A элемент inf{x, y} называется пересечением элементов x и обозначается x ∧ y), а sup{x, y} называется объединением элементов x и y (обозначается x Заметим, что если в системе A введены операции и ∨, то отношение можно по этим операциям восстановить следующим образом y ⇔ x ∧ y = x, а также x y ⇔ x ∨ y = Наименьший (наибольший) элемент решетки, если он существует, называется нулем (единицей. Обозначаются эти элементы соответственно через 0 и 1. В конечных решетках всегда имеются нуль и еди- ница. П р им ер. Любое конечное линейно упорядоченное множество является решеткой. Рассмотрим ч.у.м. A = {a, b, c, d, e}; , в котором a < b, a < c, a < d, b < e, c < e, d < e, а элементы b, c, d попарно несравнимы. Система A образует решетку, показанную на d d d d d a e c Рис. рис. 2.2. В этой решетке a = 0, e = 1. 3. Если |A| > 1, то ч.у.м. A; не является решеткой, поскольку для любых различных элементов x и y не определены операции inf{x, y} и sup{x, y} по отношению Решетка A = A; называется дистрибутивной t t d Рис. если она подчиняется дистрибутивным законам x∨(y ∧ z) = (x ∨ y) ∧ (x ∨ z), x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) для всех x, y, z ∈ Не все решетки являются дистрибутивными. Решетка, изображенная на рис. 2.2, не дистрибутивна, поскольку, тогда как (b∧d)∨(b∧c) = a ∨ a = a. Недистрибутивной является также решетка P 5 , изображенная на рис. Теорема 2.5.1. Решетка A = A; , дистрибутивна тогда и только тогда, когда A не имеет подрешеток, изоморфных или Дистрибутивная решетка A = называется булевой алгеброй, если A имеет нуль 0, единицу 1, 0 = 1 и для любого элемента x ∈ найдется элемент x (называемый дополнением элемента x) такой, что x ∨ x = 1 и x ∧ x = Предложение 2.5.2. Если A — булева алгебра, то для любого элемента x дополнение x единственно. Таким образом, булеву алгебру можно представить в виде алгебры = B; ∧, ∨, , 0, 1 с двумя двухместными операциями пересечения 2.5. РЕШЕТКИ И БУЛЕВЫ АЛГЕБРЫ 45 ∧ и объединения ∨, одноместной операцией дополнения (x → x) и двумя константами 0 и Пример. Если на множестве {0, 1} задать линейный порядок с условием 0 < 1, то получим двухэлементную булеву алгебру, 1}; ∧, ∨, , 0, 1 . 2. Рассмотрим множество A = {0, a, b, 1} и зададим частичный порядок наследующим образом 0 < a, 0 < b, • • • • d d d d d d 0 0 a = b b = Риса элементы a и b несравнимы (рис. Система является булевой алгеброй, в которой a = b, b = a. 3. Алгебра Кантора ∩, ∪, , ∅, U является булевой алгеброй. Оказывается, что основные свойства операций ∩, из § 1.1 выполняются в любой булевой алгебре. Теорема 2.5.3. Если B = B; ∧, ∨, , 0, 1 — булева алгебра, тов выполняются следующие законы для любых x, y, z ∈ B: 1) ассоциативность операций и ∧: x ∨ (y ∨ z) = (x ∨ y) ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧ z; 2) коммутативность операций и ∧: x ∨ y = y ∨ x, x ∧ y = y ∧ x; 3) законы идемпотентности x ∨ x = x, x ∧ x = x; 4) законы дистрибутивности x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z), x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z); 5) законы поглощения x ∨ (x ∧ y) = x, x ∧ (x ∨ y) = x; 6) законы де Моргана x ∨ y = x ∧ y, x ∧ y = x ∨ y; 7) законы нуля и единицы x ∨ 0 = x, x ∧ 0 = 0, x ∨ 1 = 1, x ∧ 1 = x, x ∨ x = 1, x ∧ x = 0, 0 = 1; 8) закон двойного отрицания x = x. Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ В следующей теореме описываются все конечные булевы алгебры с точностью до изоморфизма. Теорема 2.5.4 (теорема Стоуна). Любая конечная булева алгебра изоморфна некоторой алгебре Кантора. Так как для любого множества U мощность множества P(U) равна | , то из теоремы Стоуна вытекает Следствие 2.5.5. Любые две конечные булевы алгебры, имеющие одинаковое число элементов, изоморфны. Число элементов конечной булевой алгебры равно 2 n для некоторого n ∈ ω \ Таким образом, конечная булева алгебра определяется однозначно с точностью до изоморфизма числом своих элементов. Аналогично примеру 2.2.2 булевы алгебры B; ∧, ∨, , 0, 1 и B; ∨, ∧, , 1, 0 изоморфны посредством изоморфизма ϕ : B → B, в котором) = x. На этом основан следующий принцип двойственности для булевых алгебр если в справедливом утверждении о булевых алгебрах, касающемся отношения и операций, всюду заменить на , ∧ — на ∨, ∨ — на ∧, 0 — на 1, 1 — на 0, то получится также справедливое утверждение. Образованное таким образом утверждение называется двойственным к исходному. П р им ер. Закон де Моргана x ∧ y = x ∨ y является двойственным по отношению к закону де Моргана x ∨ y = x ∧ y, а закон x ∧ x = 0 — к закону x ∨ x = Остановимся на связи булевых алгебр с кольцами. Кольцо R; +, называется булевым, если a 2 = a для всех a ∈ Предложение 2.5.6. Булево кольцо +, · коммутативно, и a + a = 0 для всех элементов a ∈ Напомним, что единицей кольца R называется такой элемент e, что a · e = e · a = a для всех a ∈ Пусть B = B; ∧, ∨, , 0, 1 — булева алгебра. Определим операции кольцевых сложения и умножения на B последующим правилам ⊕ y (x ∧ y) ∨ (x ∧ y), x y x ∧ y для всех x, y ∈ B. Операция соответствует кольцевой сумме множеств, операция пересечению множеств (см. § Теорема 2.5.7. Система B; является булевым кольцом с единицей Имея булево кольцо с единицей B; ⊕, , можно однозначно восстановить операции ∧, последующим правилам x ∧ y = = x y, x ∨ y = x ⊕ y ⊕ (x y), x = 1 ⊕ x. 2.6. АЛГЕБРЫ ОТНОШЕНИЯ И РЕЛЯЦИОННЫЕ АЛГЕБРЫ Алгебры отношений и реляционные алгебры Важным классом алгебраических систем являются алгебры отношений и их расширения — реляционные алгебры. Рассмотрим алгебру отношений, носителем которой является множество отношений R = {P 1 , P 2 , . . . , P m , . . .}, а сигнатура Σ состоит из символов частичных двухместных операций объединения ∪, пересечения, разности \ и декартова произведения × отношений. Отношения P i и P j называются совместимыми, если P i , P j ⊆ A n для некоторого множества A и числа n ∈ Объединением P i ∪ P j двух совместимых отношений P i и P j называется множество всех кортежей, каждый из которых принадлежит хотя бы одному из этих отношений P i ∪ P j = {X | X ∈ P i или X ∈ Пересечением P i ∩ P j двух совместимых отношений P i и P j называется множество всех кортежей, принадлежащих как отношению P i , таки отношению P j : P i ∩ P j = {X | X ∈ P i и X ∈ P j }. Разностью P j двух совместимых отношений P i и P j называется множество всех кортежей, принадлежащих отношению P i и не принадлежащих отношению P j : P i \ P j = {X | X ∈ P i и X / ∈ Пример. Если P = {(a, b, d), (b, c, e)}, Q = {(a, b, d), (b, d, то P ∪ Q = {(a, b, d), (b, c, e), (b, d, e)}, P ∩ Q = {(a, b, d)}, P \ Q = {(b, c, Декартовым произведением P i × P j двух отношений P i и P j называется множество всех кортежей Z таких, что Z — конкатенация Z = XˆY кортежей X ∈ P i и Y ∈ P j , где XˆY = = (x 1 , . . . , x r , y 1 , . . . , y если X = (x 1 , . . . , x r ), Y = (y 1 , . . . , y s ). Итак, P i × P j = {XˆY | X ∈ P i , Y ∈ Пример. Если P = {(a, b), (b, c)}, Q = {(b, c, a), (c, a, то P × Q = {(a, b, b, c, a), (a, b, c, a, a), (b, c, b, c, a), (b, c, c, a, Алгебры отношений находят применение при формализации реальных объектов. Рассмотрим, как используется алгебра отношений при создании информационного обеспечения — разработке реляционной базы данных. Основой построения реляционной базы данных является двумерная таблица, каждый й столбец которой соответствует i-му домену (если местное отношение R n содержится в D 1 × D 2 × . . . том доменом отношения R n , где i = 1, . . . , n, называется множество, строка — кортежу значений доменов, находящихся в отношении R n П р им ер. Рассмотрим местное отношение расписание экзаменов) (табл. 2.1). Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Таблица 2.1 R 4 D 1 D 2 D 3 D 4 Информатика января Ауд. 320 Физика января Ауд. 324 Анализ января Ауд. 324 Физика января Ауд. 320 Анализ января Ауд. 324 Информатика января Ауд. Таблица 2.2 R 4 D 1 D 2 D 3 D 4 Физика января Ауд. 324 Физика января Ауд. Отношение является подмножеством декартова произведения, и поэтому каждое из множеств D i является доменом домен группа) содержит значения A-1, A-2: D 1 = {A-1, A-2}; — домен дисциплина) — D 2 = Информатика, Физика, Анализ домен дата) — D 3 = {10 янв., 15 янв., 16 янв., 21 янв.}; — домен аудитория) — D 4 = {Ауд. 320, Ауд. Порядок столбцов в таблице фиксирован, строки в общем случае могут располагаться произвольно. Цифры первого столбца 1, 2, . . . , являются идентификаторами отношения Итак, каждому отношению можно поставить в соответствие табли- цу. Для преобразования отношений определим реляционную алгебру. Носитель реляционной алгебры представляет собой множество отношений, а набор операций кроме введенных операций ∪, ∩, \, × включает специальные операции над отношениями выбор, проекцию и со- единение. Операция выбора представляет собой процедуру построения горизонтального подмножества отношения, те. подмножества кортежей, обладающих заданным свойством. П р им ер. С помощью операции выбора построим из отношения расписание экзаменов) отношение расписание экзаменов по физике. Результатом операции выбора являются строки, в которых домен представлен значением Физика, это я и я строки (табл. 2.2). 2.6. АЛГЕБРЫ ОТНОШЕНИЯ И РЕЛЯЦИОННЫЕ АЛГЕБРЫ 49 Таблица 2.3 π R 4 2,3 D 2 D 3 Информатика января 2 Физика 10 января 3 Анализ 15 января 4 Физика 16 января 5 Анализ 21 января 6 Информатика 21 января Результатом операции проекции отношения R n ⊆ A 1 × A 2 × . . . × A n на A i 1 , A i 2 , . . . , A i m , где {i 1 , . . . , i m } ⊆ {1, 2, . . . , n}, i j < i при j < называется множество i 1 ,i 2 ,...,i m {(a i 1 , a i 2 , . . . , a i m ) | (a 1 , a 2 , . . . , a n ) ∈ Например, π R n 1 {a 1 | (a 1 , a 2 , . . . , a n ) ∈ Операция проекции определяет построение вертикального подмножества отношения, те. из кортежей удаляются координаты, соответствующие невыделенным доменам. П р им ер. Проекция π R 4 отношения из примера определяет множество пар, каждая из которых содержит название дисциплины и дату (табл. Операция соединения по двум таблицам, имеющим общий домен, позволяет построить одну таблицу, каждая строка которой образуется соединением двух строк исходных таблиц. Из заданных таблиц берут строки, содержащие одно и тоже значение общего домена общему домену ставится в соответствие один столбец. Таблица 2.4 R 4 D 1 D 2 D 3 D 4 Информатика января Ауд. 320 Физика января Ауд. Таблица 2.5 R 4 D 1 D 2 D 3 D 4 Анализ января Ауд. 324 Физика января Ауд. 320 Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ Таблица 2.6 R 7 D 1 D 2 D 3 D 4 D 2 D 3 D 4 1 A-1 Информатика 10 янв. Ауд.320 Физика 16 янв. Ауд.320 Физика янв. Ауд.324 Анализ 15 янв. Ауд.324 П р им ер. Найдем по двум заданным таблицам (табл. 2.4, 2.5) результат соединения по домену табл. 2.6). § Задачи и упражнения. Установить, образуют ли алгебры следующие системы: а) ω; +, − , б) Z; :, · , в) R; ·, −, 1 − 2 ı . 2. Обозначим через F множество функций, действующих на множестве A. Образует ли система F; ◦ : а) полугруппу, б) моноид, в) группу. Построить изоморфизм систем {1, 2, 3, 4}; {(1, 3), (1, 4), (4, 2), (3, 2)} и {a, b, c, d}; {(b, a), (c, b), (c, d), (d, a)} . Построить все гомоморфные образы указанных систем. Построить всевозможные попарно неизоморфные группы с двухэлементным носителем. Рассмотрим алгебру A = {a, b, c, d}; · , определенную следующей таблицей Кэли: · a b c d a a a b a b |