ЖЕГАЛКИНА АЛГЕБРА

— одна из разновидностей алгебры логики. Названа по имени советского математика И. И. Жегалкина. В Ж. а. используются следующие теоретико-высказывательные связки: логич. умножение (конъюнкция, знак ), сложение по модулю 2 (исключающее «или», знак +) и константа 1 («истина»). Набор этих операций полный, т. е. всякая ф-ция алгебры логики может быть представлена суперпозицией указанных операций. Более того, в Ж. а. всякая ф-ция алгебры логики однозначно представима как многочлен, в котором каждая переменная входит не выше чем в 1-й степени, а коэфф. явл. элементами поля из двух элементов, т. е. либо нулем, либо единицей. Возможность такого представления «приведенными» многочленами вытекает из существования интерполяционной ф-лы Лагранжа, которая в данном случае приобретает простой вид:

Булевы связки, дизъюнкция и отрицание в Ж. а. записываются как

Ж. а. наз. иногда булевым кольцом (не смешивать с термином «булева алгебра»). Операции над приведенными многочленами производятся, как над обычными многочленами с целочисленными коэфф., затем в полученном результате все переменные , которых , заменяются на а коэфф. при одночленах заменяются их наименьшими вычетами по модулю 2. Именно эта близость Ж. а. к привычной элементарной алгебре многочленов объясняет ее преимущество с методической точки зрения. Некоторые авторы использовали Ж. а. в исследованиях по матем. логике и в вычисл. технике. В частности, сам И. И. Жегалкин применил ее в исследованиях исчисления предикатов узкого. Он распространил положения этой алгебры на исчисление матриц с коэфф. 0 и 1 и нашел решение проблемы разрешения на конечных классах для некоторых типов формул узкого исчисления предикатов. Ж. а. с успехом применяют в релейно-контактных схем теории. Ж. а. допускает естественное обобщение на случай А-значных логик, если к — степень простого числа. Действительно, в этом случае ф-ции соответствующей алгебры логики согласно интерполяционной формуле Лагранжа допускают однозначное представление приведенными полиномами (т. е. такими, в которых каждая переменная входит в степени, не выше чем с коэфф. из конечного поля (поля Галуа) с к элементами. Это позволяет применить аппарат теории полиномов над конечными полями к исследованиям по логикам многозначным.

Лит.: Жегалкин И. И. Арифметизация символической логики. «Математический сборник Московского математического общества», 1929, т. 36, в. 3—4; Жегалкин И. И. К проблеме разрешимости. «Математический сборник. Новая серия», 1939, т. 6, в. 2; Жегалкин И. И. Проблема разрешимости на конечных классах. «Ученые записки Московского государственного университета», 1946. т. 1, в. 100; Костырко В. Ф. Об ошибке в статье И. И. Жегалкина «Проблема разрешимости на конечных классах». В кн.: Алгебра и логина. Семинар т. 1, в. 5. Новосибирск, 1962.

Л. А. Калужнин.