Тема 11. Бинарные алгебры с одной операцией: Отношение изоморфизма для бинарных алгебр.

Бинарной алгеброй с одной операцией на множестве Aназывают упорядоченную паруA, f, гдеf– функция, ставящая в соответствие упорядоченной паре элементовAзначение из этого же множества:fA^AA.

Выражения с бинарными операциями удобнее записывать в инфиксной форме. Символ бинарной операции будем обозначать звёздочкой «» между операндами:

xy = f(x, y)

Алгебру будем аналогично обозначать таким же символом в упорядоченной паре:

A, =A, f (fA^AA & (xA yA xy = f(x, y)))

Если необходимо рассмотреть несколько таких алгебр, будем использовать различные инфиксные символы: , ▫,⋄ ….

Алгебры удобно представлять в виде двумерных таблиц, в которых записаны значения результатов операции для всех возможных комбинаций значений левых и правых операндов. Такие таблицы называют таблицами Кэли. Мы уже использовали такую форму представления при рассмотрении логических операций и алгебр классов вычетов по модулю некоторого числа. Теперь такие таблицы будем применять к алгебрам с произвольными множествами элементов. Например, дляA={a, b, c, d} зададим алгебруA, таблицей

	a	b	c	d
a	a	b	c	d
b	b	a	d	c
c	c	d	b	a
d	d	c	a	b

Такие алгебры с дискретным, но уже возможно не двоичным набором значений являются обобщением двоичных функциональных преобразований, реализуемых логическими элементами в различных технических и информационных системах. Подобно тому, как из логических элементов можно строить схемы (моделью схем являются формулы с логическими операциями), можно представить и недвоичные преобразователи информации. Это может быть более общим подходом, чем сразу переходить к работе с символьной информацией, представленной двоичными или числовыми кодами.

Так же, как для бинарных отношений рассматривается отношение подобия, для алгебр вводят отношение изоморфизма. Обозначается символом ~, как и равномощность множеств, так как для изоморфных алгебр множества действительно равномощны:

A,  ~ B, ▫  ( f  B^A  ( f ^-1  A^B ) & (xA yA ( f(xy)=f(x)▫f(y) ))

Как и для других подобных отношений, связанных с установлением соответствий между множествами, будем надписывать обозначение устанавливающей соответствие функции над символом ~: A, B, ▫.

То, что две алгебры изоморфны, означает, что одна может быть получена из другой при помощи замены обозначений элементов и операций. Структура у изоморфных алгебр одинакова. Рассмотрим это на примере алгебр логических бинарных операций. Возьмём, например, бинарные операции ЛОГИЧЕСКОЕ И (символ &) и ЛОГИЧЕСКОЕ ИЛИ (символ ). Обе операции заданы на множестве логических значенийℬ={0, 1}. Обозначим задаваемые этими операциями алгебры какℬ, &иℬ, .

Таблицы для этих алгебр будут иметь вид

Покажем, что структура этих алгебр одинакова. Рассмотрим формулу де Моргана:

xV yV( (x &y) =x  y )

Рассматривая унарную логическую операцию НЕ (символ ) как биективную функциюfV^V, видим совпадение структуры этой формулы с определением отношения изоморфизма.

Разберемся, что это именно замена обозначений. Заменим в таблице для алгебры V, &все вхождения символа 0 на символ 1 и наоборот, все вхождения символа 1 на символ 1. Заменим обозначение операции& операцией. Получим таблицу

	1	0
1	1	1
0	1	0

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

Общая схема получения изоморфных пар логических операций может быть пояснена следующей парой таблиц, отражающих выражение второй операции через первую  x ▫ y = (x  y), когда заданы двоичные значенияa,b,c,dдля всех возможных сочетаний значений операндов операции:

Такие операции в алгебре логики называются двойственными.

Следующий пример взят из математики действительных чисел. Множество вещественных чисел обозначают символом ℝ. Обозначим множество действительных положительных чисел символомP={x | xℝ & x>0}. Символы + иобозначают соответственно сложение и умножение действительных чисел. Тогда имеем две алгебрыℝ, +иP,. Можно записатьℝ, +P,, так как экспонента по любому основанию (функцияExp) устанавливает взаимнооднозначное соответствие между множествамиℝиP. При этом выполняется соотношение

(xℝ yℝ ( Exp(x+y) = Exp(x)Exp(y) )

Аналогично логарифм (функция Log) по любому основанию устанавливает соотношениеP,ℝ, +: (xP yP( Log(xy) = Log(x)+Log(y) ). На основе этого изоморфизма основан принцип действия логарифмической линейки: умножение чисел заменяют суммой длинной отрезков, отложенных на неподвижной и перемещаемой части по логарифмической шкале. С этой же шкалы снимают показания в виде результата умножения.

Как и равномощность множеств, отношение изоморфизма алгебр является отношением эквивалентности:

Рефлексивность: A, A, 

Симметричность: A, B, ▫  B, ▫A, 

Транзитивность: A, B, ▫ & B, ▫C, ⋄  A, C, ⋄

Класс эквивалентности по отношению изоморфизма некоторой алгебры [A, ]_~называютабстрактной(свободной) алгеброй.

Например, все бинарные алгебры логических операций

M = {A,  | A, =A, f & (fA^AA) & (A= {0, 1})}

(всего их 16) можно разбить на 10 классов свободных алгебр M/~. Изоморфными окажутся следующие пары операций: & и,и ↔, ↓ и |, → и↚,и↛, функция-константа 0 и функция-константа 1. Еще 4 операции в данных обозначениях операндов (0, 1) не имеют изоморфных пар, то есть являются одноэлементными классами. Они не очень интересны с практической точки зрения, так как имеют фиктивные аргументы. Но сам пример интересен тем, что, будучи подвергнуты преобразованию получения двойственной операции, такие алгебры переходят в себя, например, дляxy = y ℬ,  = ℬ, ▫:

Такие логические операции называются самодвойственными.