Дискретно-непрерывная математика (стр. 25 )

Доказательство. Очевидпо, что φ інъективно и сюръективно. Если

В, С Р(А), то

φ (В С) = (В С)' = В' С′ = φ (В) φ(С),

φ (В С) = (В С)′ = В' С′ = φ (В) φ (С).

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

Микромодуль 3

Примеры решения типовых задач

1.1) Алгебра (R; +, •) называется полем действительных чисел. Обе операции — бинарные, поэтому тип этой алгебры (2, 2). Все конечные подмножества R, кроме {0}, не замкнуты относительно обеих операций. Подалгеброй этой алгебры является, например, поле рациональных чисел.

2) Пусть Np = {0, 1, 2, ..., р— 1}. Определим на Np операции («сложение по модулю р») и («умножение по модулю р») таким образом: а b = с, а b= d, где c и d — остатки от деления на р чисел а + b и а ∙ b соответственно. Например, если р=7, то Np = {0, 1, ..., 6}, 3 4 = 0, 3 4 = 5, 4 6 = 3. Часто операции и обозначают как а + b ≡ с (mod р), а b =d(modp). Если р — простое число, то алгебра {Nр, , } называется конечным полем характеристики р.

3) Пусть задано множество U. Множество всех его подмножеств называется булеаном U и обозначается через B(U). Алгебра

В = (B (U); , ,-) называется булевой алгеброй множеств над U, ее тип (2, 2, 1). Элементами основного множества этой алгебры являются множества (подмножества U). Для любого U'U В' = (B (U′);,,-) является подалгеброй В. Например, если U= {а, b, c, d}, то основное множество алгебры В содержит 16 элементов; алгебра В' = { B ({а, с}); , ,- } — подалгебра В; ее основное множество содержит четыре элемента.

4) Множество F одноместных функций на R, т. е. функций f :R → R, вместе с операцией дифференцирования является алгеброй. Элементы основного множества — функции типа R → R, единственной операцией этой алгебры служит дифференцирование — унарная операция типа F → F (производной функции на R является снова функция на R). Множество элементарных функций, как мы знаем, замкнуто относительно дифференцирования - производные элементарных функций элементарны - и, следовательно, образуют подалгебру данной алгебры.

5) Рассмотрим квадрат с вершинами в точках а1, а2, а3, а4 и повороты квадрата вокруг центра (против часовой стрелки), переводящие вершины в вершины. Таких поворотов — бесконечное множество: на углы 0, π/2, π, 3π/2, 2π, 5π/2..., однако они задают всего четыре различных отображения множества вершин в себя, соответствующих первым четырем поворотам. Таким образом, получаем алгебру с основным множеством {а1 а2, а3, а4} и четырьмя унарными операциями α, β, γ, δ. Их можно задать табл. 1.17, в которой на пересечении, например, строки а3 и столбца γ написано значение функции γ(а3).

Таблица 1.17

Операция α, отображающая любой элемент в себя, называется тождественной операцией. Она соответствует нулевому повороту. Подалгебр в этой алгебре нет.

6) Множество О={ α, β, γ, δ } отображений вершин в себя из предыдущего примера вместе с бинарной операцией композиции отображений образует алгебру {О; }. Элементами множества О являются отображения (повороты). Композиция отображений — это последовательное выполнение двух поворотов. Она задается табл. 1.18 (в ней на пересечении строки α и столбца γ написан результат композиции αγ).

Таблица 1.18

Такая таблица, задающая бинарную операцию, как мы занем, называется таблицей Кели. Множество { α,γ }, т. е. повороты 0, π, образует подалгебру алгебры (О; }.

2. 1) Пусть QN — множество всех целых чисел, Q2N — множество всех четных чисел. Алгебры (QN; +) и (Q2N; +) изоморфны; изоморфизмом являются отображения Г2п : п → 2п, причем условие (1.1) здесь имеет вид 2(а +b) = 2а + 2b. Поскольку Q2n Qn, то Г2n — изоморфизм (QN; +) в себя. Отображение Г-п : п→(-п) является для алгебры (Qn; +) автоморфизмом; условие (1.1) имеет вид (-а)+ (-b) = —(а + b). Для алгебры (Qn; ∙) Г-п не является автоморфизмом, так как (-а) (—b)≠-(аb).

2) Рассмотрим алгебры (N; +; •) и (N7; , ) (см. пример 1) и определим отображение Г7 : N → N7 следующим образом: Г(п) равно остатку от деления п на 7; иначе говоря, если п = 7a + b (b < 7), то Г(п)= b. Пусть п1 = 7a1 + b1, п2 = 7а2 + b2. Проверим условие (1.1). Для сложения имеем

Г (п1 + п2) = Г (b1 + b2) = b1 b 2 = Г (п1) Г (п2).

Для умножения имеем

Г (п1п2) = = Г (b1 b2) = b1 b2 = Г (п1) Г (п2).

Таким образом, условие (1.1) выполненная и Г7 — гомоморфизм. Очевидно, Г7 не является изоморфизмом, так как нет взаимной однозначности. Этот пример показывает, что возможен гомоморфизм бесконечной алгебры (т. е. алгебры с бесконечным основным множеством) в конечную алгебру. При этом N разбивается на семь классов эквивалентности по отношению Е7 : аЕ7b, если и только если Г7 (а) = Г7 (b).

3) Изоморфизмом между алгебрами (R+, •) и (R, +), где R+ — положительная часть R, является отображения а → log а. Условие (1.1) имеет вид равенства log (ab) = log a + log b.

4) Рассмотрим алгебры (К, φ) и (М, ψ), где К={а1 ,а2, а3, a4};

M = {b1, b2, b3, b 4}, а бинарные операции φ и ψ заданы следующими таблицами (табл. 1. 19, а, б):

Таблица 1. 19