Принцип двойственности

3.7 Принцип двойственности

Если в формуле алгебры логики F заменить знаки всех логических функций на знаки двойственных функций, то получится двойственная формула F ^*, реализующая функцию, двойственную той, которая реализуется формулой F. При этом, если формулы равны F ₁ = F ₂, то верно равенство двойственных формул , которое называется двойственным предыдущему. Например, равенства, являющиеся двойственными друг другу:

 и ;

 и ;

 и ;

 и ;

 и .

3.8 Полнота функций алгебры логики

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

Например, суперпозицию функций f₁, f₂, f₃ можно задать формулой

.

Если f₁ обозначает дизъюнкцию, f₂ – конъюнкцию, а f₃ – сложение по mod 2, то последняя формула примет вид:

.

Если рассматривается произвольная система функций, то возникает вопрос: всякая ли логическая функция из этой системы представима формулой, содержащей символы только этой системы функций.

Система функций алгебры логики (ФАЛ) называется функционально полной, если любая функция алгебры логики может быть реализована формулой, содержащей лишь символы функций из этой системы ФАЛ, т.е. является суперпозицией функций из этой системы.

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

3.9 Теорема Поста – Яблонского (критерий функциональной полноты)

Для того, чтобы система ФАЛ  была полной необходимо и достаточно, чтобы она содержала функцию:

1) не сохраняющую ноль;

2) не сохраняющую единицу;

3) нелинейную;

4) немонотонную;

5) несамодвойственную.

Примерами функционально полных систем являются, например, системы:

.

Все названные выше классы функций обладают свойством: любая ФАЛ, полученная с помощью операции суперпозиции и подстановки из функций одного класса, обязательно будет принадлежать этому же классу.

Полная система ФАЛ называется базисом,если теряется полнота Ф при удалении хотя бы одной функции системы.

К базису относятся системы функций:

базис 1: ;

базис 2: ;

базис 3: ;

базис 4: функция Шеффера: x₁ | x₂;

базис 5: функция Пирса (Вебба): x₁ ↓ x₂.

Базис 1 – избыточный, базисы 4 и 5 – минимальные (удаление хотя бы одной функции превращает систему ФАЛ в неполную).

При исследовании полноты систем функций удобно пользоваться таблицей, которую называют критериальной. Эта таблица имеет пять столбцов, каждый из которых соответствует одному из пяти классов, а строки таблицы соответствуют функциям исследуемой системы. На пересечении строки таблицы, соответствующей функции f, и столбца, соответствующего классу К, ставится знак плюс, если функция , и минус, если . Система функций полна тогда и только тогда, когда в каждом столбце содержится хотя бы один знак минус.

Пример.

Является ли система булевых функций  полной? Если является, то выписать все возможные базисы.

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

1. Исследуем ее принадлежность к классу К₀:

.

Следовательно, .

2. Исследуем принадлежность функции к классу К₁:

.

Следовательно, .

3. Установим, является ли функция f₁ линейной. Используем метод неопределенных коэффициентов. Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:

.

Найдем коэффициенты , исходя из предположения линейности этой функции. Зафиксируем набор 000:

, , .

Следовательно, .

Зафиксируем набор 100:

,

,

.

Следовательно, .

Фиксируем набор 010:

,

Фиксируем набор 001:

.

Следовательно, функция (по нашему предположению) может быть представлена полиномом первой степени вида:

.

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