Имеется множество A = {0, 1}. Нужно вычислить, чему равно максимальное количество попарно неизоморфных алгебраических систем с носителем A и одной бинарной операцией. Понятно, что существует всего 16 отображений, действующих из AxA в A, значит, и систем можно построить столько же. Но как посчитать, какое максимальное количество систем мы можем выбрать, чтобы они все были попарно неизоморфны?

задан 9 Сен 20:22

10|600 символов нужно символов осталось
0

Здесь нужно аккуратно перебирать и классифицировать по какому-то признаку. Возьмём свойство быть идемпотентом. Оно сохраняется при изоморфизме.

1) Пусть идемпотентов нет. Тогда 00=1, 11=0 (операцию обозначаем как умножение). Система или коммутативна, или нет. Если коммутативна, то 01=10. Это или 0, или 1, и оба элемента равноправны. Поэтому имеем одну систему с таким свойством. Для определённости, 01=10=0. Это стрелка Пирса (отрицание дизъюнкции)

Допустим, что система не коммутативна. Тогда 01=0, 10=1 или наоборот: 01=1, 10=0. В первом случае операция задаётся как ab=not(b), во втором как ab=not(a). Такие системы антиизоморфны, но не изоморфны. Действительно, изоморфизм первой системы на вторую, если он не тождественный, должен иметь вид ф(0)=1, ф(1)=0, то есть ф(x)=not(x). Тогда ф(ab)=not(ab)=not(not(b))=b, но ф(a)ф(b)=not(ф(a)) [во второй системе!] =not(not(a))=a.

Итого получили 3 попарно не изоморфные системы.

2) Пусть идемпотентов два. Тогда 00=0, 11=1. В коммутативном случае 01=10; элементы можно переставлять. Полагаем 01=10=0. Эта операция -- обычное произведение. Систем стало 4. Для некоммутативного случая 01=0, 10=1 или наоборот: 01=1, 10=0. Здесь операции задаются формулами ab=a и ab=b соответственно. Это полугруппа левых нулей и полугруппа правых нулей. Они не изоморфны. Систем стало 6.

3) Пусть идемпотент один. Будем считать, что это 0. Тогда 00=0, 11=0. Коммутативный случай даёт 01=10. Если это 0, то умножение в системе нулевое. Если 1, то получается сложение по модулю 2. Системы не изоморфны, получается 8 штук.

Наконец, некоммутативный случай. Если 01=0, 10=1, то перед нами отрицание импликации : not(a->b). Для случая 01=1, 10=0 операция имеет вид not(b->a). Видно, что ф(0)=1, ф(1)=0 не будет изоморфизмом первой системы на вторую, так как ф(ab)=a->b, но ф(a)ф(b) во второй системе есть not(ф(b)->ф(a))=not(not(b)->not(a))=not(a->b), то есть одно другому не равно.

Итого 10 попарно не изоморфных систем. Этот же ответ можно получить быстрее, используя понятие двойственности булевых функций. Известно, что среди 16 функций двух переменных, есть ровно 4 самодвойственных (тождественные функции одной переменной и их отрицания). Здесь замена 0 на 1 и обратно приводит к той же системе. Для остальных 12 функций происходит разбиение на 6 пар различных изоморфных (типа, конъюнкция перешла в дизъюнкцию). Итого 4+6=10.

ссылка

отвечен 9 Сен 21:57

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×386
×44
×10

задан
9 Сен 20:22

показан
27 раз

обновлен
9 Сен 21:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru