Картинки из квадратов \ Презентация \

12.6. А теперь все вместе: алгебра

Начало см. здесь и здесь.
1. Новейшая теория базовых взаимоотношений между Эм и Жо
С целью формализации высказанных ранее интуиций предлагается следующая эквациональная теория из шести аксиом:
где p есть некоторая индивидная константа;
v, h, V, H есть некоторые унарные функциональные символы;
z есть некоторая индивидная переменная;
есть символ квантора всеобщности.
Конечно, эта теория имеет смысл и с точки зрения программиста, как об этом написано у Агафонова и др. По поводу понятий мат. логики: индивидных констант, функциональных и предикатных символов см., например, у Кейслера и Чэна (или, в программистском контексте, у Агафонова и др).
Интуитивный смысл индивидной константы p, унарных функциональных символов V, H в любимой модели см. здесь. Популярное объяснение смысла квантора всеобщности можно посмотреть у Нильсона.

2. Эндоморфизм детям не страшен
Первоначально унарные функциональные символы v и h обозначались символами эндоморфизмов φV и φH (см. об этом здесь, пункты 3 и 4). Возникает закономерный вопрос: а не сложно ли это понятие (эндоморфизм) для детей? Думается, что не сложно, поскольку (как это ни удивительно может показаться на первый взгляд) понятие гомеоморфизма не является для них сложным (разумеется не в его теоретических аспектах, а в интуитивно - наглядной форме). Соответствующий пример можно посмотреть у Звонкина.
В конце концов гомоморфизм (и, в частности, эндоморфизм) выражает некоторое отношение аналогии (список популярных примеров гомоморфизмов можно посмотреть здесь) Чтобы максимально упростить понимание эндоморфизмов в интересующем нас случае, мы прибегнем к использованию "польской" (или "бесскобочной") записи термов.

3. "Польская" запись термов
"Польскую" (или "бесскобочную") запись термов придумал и популяризовал польский логик Ян Лукасевич. Потом она нашла многочисленные применения в Computer Science (об одном из них см., например, у Ахо - Ульмана). Используя польскую запись термов, приведенную выше систему из шести аксиом можно записать следующим образом:
В этой записи мы опустили также квантор всеобщности; его присутствие обычно бывает ясно из контекста.

4. Удивительная вещь
Удивительной вещью является то, что абсолютно свободные алгебры оказываются самыми простыми алгебрами в мире. Мы последовательно раскроем этот тезис ниже. Пока же отметим, что он открывает путь к постижению конструкций логического программирования даже маленькими детьми. Это основывается на следующем факте, отмеченном, например, Л. Н. Шевриным: Исходные понятия теории полугрупп и простейшие свойства полугрупп достаточно элементарны и вполне доступны школьникам старших классов. Более того, можно сказать, что с полугруппами встречается, не подозревая этого, уже первоклассник, и затем они сопровождают учащихся на протяжении всех лет обучения в школе.
Нас будут интересовать специфические абсолютно свободные алгебры, которые во многих контекстах можно заменить свободными полугруппами, если воспользоваться упомянутой выше бесскобочной записью. Именно это обстоятельство и предопределяет элементарность рассмотрений, отмеченную Л. Н. Шевриным.
О нужном нам сочетании в использования абсолютно свободных алгебр и логики я упоминал здесь: "Абсолютно свободные алгебры являются объектами универсальной алгебры. Имея в виду дальнейшее развитие нашего изначального остова музыкальной гармонии, мы можем сделать еще один небольшой шаг и добавить к абсолютно свободной алгебре немного логики ..." (постинг от 08.12.2016 на странице по указанной ссылке).

5. Близость к лексикографическому упорядочению
Мы разберем эту близость на примере лексикографического упорядочения двоичных наборов длины 2:
(лексикографическое упорядочение двоичных наборов бОльшей длины рассматривалось ранее). Заменим 0 на букву V, а 1 — на букву H и будем считать, что на 2-х элементном множестве {V, H} задан линейный порядок, в котором буква V предшествует букве H. Тогда лексикографическое упорядочение двоичных наборов длины 2 в алфавите {0, 1} заменится лексикографическим упорядочением двоичных наборов длины 2 в алфавите {V, H}:
Теперь пометим этими цепочками длины 2 в алфавите {V, H} вершины 2-го уровня на Stern-Brocot Tree так, как это предписывает Великий Антанаиресис:
Как видим, эти метки расположились в лексикографическом порядке (если просматривать их слева направо). Мораль всего этого такова: давайте заменим дроби, обычным образом записанные в десятичной системе счисления, отвечающими им двоичными наборами. Тогда многие соотношения между дробями (например, их линейная упорядоченность) смогут быть объяснены гораздо проще. Это определенным образом выглядело бы как исполнение пожелания Лейбница:
"В конце 1600-х годов Лейбниц пришел к выводу, что существует необходимость в некоторой новой, более "чистой" арифметике, по сравнению с нашей обычной арифметикой, основанной на десятичной системе счисления. Лейбниц нашел прототип для этой новой арифметики в книге, написанной пять тысяч лет назад. В книге, которая лежит в основе китайской философии: И Цзин или Книга Перемен".
Как можно легко показать, Н. М. Бескин в начале своей статьи говорил, в принципе, о том же самом. Это не означает, конечно, что вообще не будет изучаться десятичная система счисления. Но начать, возможно, лучше с "двоичной", как наиболее простой.
Эта "двоичная арифметика" ближе к Computer Science. Что, наверное, и неплохо, если уж пошел такой тренд создания детских IT-академий. Ну, и, конечно, она идеально подходит для доходчивого объяснения сразу логического программирования, а не по отдельности логики и программирования.