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

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

Так как всякая формула может быть представлена приведенной формулой, то система å ₀ = {Ù, Ú, } - полна.

Система å сводится к å ^*, обозначается å ®å ^*, если все операции системы å ^* представимы формулами над системой å. Если å ^* полна, то и å полна.

Последнее утверждение даёт один из способов доказательства полноты системы операций – сведение её к известной полной системе, например к å ₀. То есть полной будет система å, через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание.

Так в силу законов де Моргана, полными будут и системы å ₁ = {Ù, } и å ₂ = {Ú, }.

Алгебра над множеством логических функций с двумя операциями Ù и Å называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:

, ,

, ,

а также ассоциативность, коммутативность, идемпотентность конъюнкции и свойства констант.

Задание. Доказать полноту системы å ₅ = {Ù, Å }.

Решение. Сведем систему å ₅ к полной системе å ₀.

.

Если в произвольной формуле алгебры Жегалкина, реализующей булеву функцию f, раскрыть скобки и произвести все возможные упрощения, то получится формула, имеющая вид суммы произведений, то есть полинома по mod 2. Такая формула называется полиномом Жегалкина для данной функции. Линейной называется функция, полином Жегалкина которой линеен.

Сводимость к полной системе операций является необходимым условием полноты системы операций. Необходимое и достаточное условие полноты системы операций формулируется в терминах булевых функций.

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

Замыканием множества F (обозначается [F]) называется множество всех булевых функций, реализуемых формулами над F. Класс функций называется замкнутым, если [F] = F.

Примеры замкнутых классов.

1. Класс функций, сохраняющих 0.

.

2. Класс функций, сохраняющих 1.

.

3. Класс самодвойственных функций.

.

4. Класс монотонных функций.

, где

.

5. Класс линейных функций.

.

Принадлежность некоторых функций этим классам оформим в виде таблицы.

Функция	Принадлежность классу
T 0	T 1	T *	T £	TL
	+ - - +	- + - +	- - + -	+ + - +	+ + + -

Замкнутые классы попарно различны, не пусты и не совпадают с .

Теорема 6.1 (Поста). Система булевых функций полна тогда и только тогда, когда она содержит хотя бы одну функцию, не сохраняющую 0, хотя бы одну функцию, не сохраняющую 1, хотя бы одну несамодвойственную функцию, хотя бы одну немонотонную функцию и хотя бы одну нелинейную функцию.

Доказательство.

Необходимость. Предположим противное, т.е. система булевых функций F полна ([F] = ) и входит в один из замкнутых классов (F Ú F Ú Ú F Ú F Ú F ). Обозначим через T_i тот класс, для которого справедливо включение F . Тогда [F] = , что противоречит тому, что ни один из классов не совпадает с .

Достаточность. Пусть система булевых функций F содержит хотя бы по одной функции, не принадлежащих каждому из замкнутых классов. Т.е. $ F¢ = , причем функции не обязательно различны и не обязательно исчерпывают F. Покажем, что отрицание и конъюнкция, которые образуют полную систему булевых функций, реализуются формулами над F¢.

1) Проведем вначале построение вспомогательных формул над F¢. Реализуем константы 0 и 1, которые будут использоваться в формуле для конъюнкции.

Для реализации 1 воспользуемся функцией . Обозначим . Так как , то . Если , то возможны 2 случая:

a) и тогда реализует 1;

b) . В этом случае реализует отрицание, для построения формулы 1 воспользуемся функцией . Так как она несамосопряженная, то существует набор , на котором значение функции отличается от значения двойственной функции , тогда . Рассмотрим функцию , для которой . Следовательно, является константой, если , то она реализует 1, если , то реализацией 1 будет функция .

Константа 0 строится аналогично с использованием функции .

2) Для построения формулы, реализующей функцию отрицания, воспользуемся немонотонной функцией . Так как , то , такие что . Неравенство означает, что либо соответствующие координаты векторов , совпадают, либо и . Так как , то , а, следовательно, найдутся такие индексы, что . Обозначим через I множество таких индексов. Определим функцию , где , если , и , если . Вычислим значение функции в 0 и 1: , . Так как , то , а это означает, что .

3) Для построения формулы, реализующей конъюнкцию, будем использовать нелинейную функцию . Так как , то её полином Жегалкина содержит слагаемое, являющееся конъюнкцией, по крайней мере, двух переменных. Выберем произвольное слагаемое, содержащее наименьшее число переменных пусть это . Рассмотрим функцию, полученную заменой всех переменных, не вошедших в этот набор, нулями, т.е. . Её полином Жегалкина имеет вид

. Рассмотрим функцию

, где , , . Определим функцию

,

Такое представление корректно, так как являются константами 0 или 1, определенными ранее формулами над F¢, а сложение по модулю 2 с константой дает либо функцию, либо её отрицание, которое также выражено формулой над F¢. Преобразуем , воспользовавшись представлением c,

. Таким образом, функция реализует конъюнкцию.