7.2. Изоморфизм алгебраических систем

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

Определение 7.13. Алгебраические системы A, B одной и той же сигнатуры типа <n₁, …, n_k; m₁, …, m_l> называются изоморфными, если существует биективное отображение :A  B, такое, что:

1) для любой операции и любых элементовA выполняется равенство: ;

2) для любого отношения и любых элементовA:

.

При этом само отображение называется изоморфизмом системы A на систему B.

Пример 7.14. Пусть B₁ — булева алгебра всех подмножеств множества M = {a₁, …, a_n}, B₂ — булева алгебра всех делителей числа m = p₁ p₂ … p_n, где p₁ p₂ … p_n — различные простые числа. Определим отображение :B₁  B_2, положив и. Легко видеть, что,;, а также,, для любых подмножествA, B множества M. Это и означает, что есть изоморфизм булевой алгебры B₁ на булеву алгебру B₂.

Замечание 7.15. Легко видеть, что отношение изоморфизма является отношением эквивалентности на любом множестве алгебраических систем одной сигнатуры и потому все такие системы разбиваются на классы изоморфных систем. Из определения 7.13 видно, что изоморфные алгебраические системы сигнатуры с точки зрения свойств операций и отношений отличаются лишь обозначениями элементов. Отождествив в системах из определения 7.13 элементыa и (a), мы получим одну и ту же алгебраическую систему. Тем самым достигается существенная экономия сил и времени при изучении всего многообразия алгебраических систем.

Замечание 7.16. Понятие изоморфизма естественным образом распространяется на алгебраические системы различных, но однотипных сигнатур. При этом необходимо только предварительно установить между операциями (а также между отношениями) систем взаимно однозначное соответствие, сохраняющее арности. Так, если операции f_i соответствует операция , то условие 1 определения 7.13 запишется в виде:

.

В частности, если f_i — бинарная операция «», аf — бинарная «», то последнее равенство будет иметь вид:

.

Пример 7.17. Рассмотрим алгебры R⁺()и R(+), где R⁺ — множество всех положительных действительных чисел; R — множество всех действительных чисел. Положим , для любогоx  R⁺, где a — некоторое положительное число, a1. Тогда условие 1 определения 7.13 гарантируется в этом случае известным свойством логарифмов: .

Замечание 7.18. Пример 7.17 показывает, что в некоторых случаях переход к изоморфной алгебре позволяет существенно упростить вычисления. В этом проявляется ещё одна положительная роль понятия изоморфизма.

Л е к ц и я 8

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

8.1. Основные логические операции и их свойства

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

Если высказывание а истинно или ложно, то говорят, что оно имеет значение «и» или «л» и пишут

а  и или а  л.

Высказывания а и b, имеющие одинаковые значения, называются равносильными, что обозначается в виде

а  b.

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

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

a  b (a  b), a  b, a  b, a ( a)

и называются конъюнкцией, дизъюнкцией, импликацией и отрицанием высказывания а (табл.8.1).

В высказываниях a  b, a  b, a и b называются членами, или компонентами, соответственно конъюнкции и дизъюнкции; в высказывании а -> b а называют посылкой, b — заключением импликации.

Обозначим через  = {и, л}. Тогда табл.8.1 может служить определением операций , , , на множестве .

Таблица 8.1

a	b	a  b	a  b	a  b	a
и	и	и	и	и	л
и	л	л	и	л	л
л	и	л	и	и	и
л	л	л	л	и	и

При этом операции , , обладают следующими свойствами:

1) операции ,  коммутативны, ассоциативны, идемпотентны, дистрибутивны одна относительно другой и связаны законами поглощения: a  (a  b)  a, a  (a  b)  a;

2) операция отрицания — инволютивна (т.е. ) и связана с операциями,  законами де Моргана: и соотношениями а  а  л, а  а  и.

Отсюда следует, что алгебра (, , ) является булевой алгеброй. В ней роль 1 и 0 играют соответственно элементы и, л.

Определение 8.1. Двухэлементная булева алгебра (, , ) называется алгеброй высказываний.

Из табл.8.1 видно, что импликация (->) также является операцией на множестве  и обладает рядом свойств, связывающих её с другими операциями:

a  b b a (закон контрапозиции),

a  (b  a)  и,

ab  b  и,

a  b a  b и другие.