Функция Линдона: пример Линдона и решение уравнений

Функция Линдона в курсе — бинарная операция · на множестве E₇={0,1,2,3,4,5,6}. Она принимает ненулевые значения только когда первый аргумент принадлежит A={1,5,6}, а второй B={2,3,4}. Полная таблица операции задаёт конечную алгебру, для которой рассматривается бесконечная полная система тождеств.¹

При решении уравнений удобно сначала установить, когда x·y=0. Это происходит тогда и только тогда, когда x∉A или y∉B. После этого вложенные произведения сводятся к проверке принадлежности A и B, и уравнения решаются по случаям.¹

Что важно запомнить

E₇={0,1,2,3,4,5,6}, A={1,5,6}, B={2,3,4}.
x·y≠0 возможно только при x∈A и y∈B.¹
В задачнике функция Линдона сопровождается тождествами A₁,A₂,A₃ и семействами \(B_m,C_m\). Их бесконечная система полна.¹
Для уравнений сначала анализируют область нулевого значения операции, затем оставшиеся ненулевые случаи.
Не путать эту функцию Линдона с разложением Линдона слов в комбинаторике.

Таблица функции Линдона

Обозначим φ(x,y)=x·y. В задачнике курса операция задаётся таблицей:¹

x\y	2	3	4
0	0	0	0
1	1	5	6
2	0	0	0
3	0	0	0
4	0	0	0
5	5	5	5
6	6	6	6

Отсюда сразу видно ключевое свойство: x·y≠0 только при x∈A={1,5,6} и y∈B={2,3,4}. Результат ненулевого произведения снова лежит в A. Поэтому если результат одного произведения попадает во второй аргумент следующего произведения, оно автоматически обнуляется.

Зачем нужен пример Линдона

В задачнике для этой алгебры вводятся основные тождества A₁,A₂,A₃ и бесконечные семейства \(B_m,C_m\). Они образуют полную бесконечную систему тождеств, тогда как конечной полной системы для данного примера нет. Поэтому функция Линдона служит модельным примером того, что конечная алгебра не обязана иметь конечный базис тождеств.¹

Решение типовых уравнений

В задаче 3.11 предлагаются четыре уравнения. Их решения удобно записать через A и B.¹

Уравнение	Все решения
(x·y)·z=x·(y·z)	Все тройки, кроме x∈A, y∈B, z∈B. Правая часть всегда 0. Левая ненулевая ровно в исключённом случае.
x·y=y·x	x=0 или y=0, либо x,y∈A, либо x,y∈B.
(y·x)·y=(x·y)·x	Все пары x,y∈E₇. Обе части всегда равны 0.
x·y=z·x	Если x=0 — любые y,z. Если x∈A — y∉B, z любое. Если x∈B — y любое, z∉A.

Такая запись показывает общий метод: не перебирают 49 или 343 набора вслепую, а используют форму ненулевой области A×B.

Пример простыми словами

Для уравнения x·y=y·x ненулевые левая и правая части одновременно возникнуть не могут: слева требуется x∈A,y∈B, а справа y∈A,x∈B. Поэтому равенство означает, что обе части равны нулю. Отсюда сразу получаются случаи x=0, y=0, оба аргумента в A или оба в B.

Частые ошибки

Искать «функцию Линдона» в теории строк. В этом курсе речь о конкретной 7-значной логической операции.
Решать уравнения полным перебором, не используя A×B. Структура таблицы сокращает решение до нескольких случаев.
Считать, что x·y не равно нулю при любых ненулевых x и y. Ненулевая область очень узкая: только A×B.

Другие вопросы

Источники

1 Задачи по курсу «Основы кибернетики» М.: МАКС Пресс, 2011 г., раздел 3, задачи 3.10–3.11