Нахождение таблицы значений функции, двойственной к данной булевой функции

Это действие сводится к композиции инвертирования и переворота.

Например, для функции со значениями (0, 1, 0, 0, 0, 1, 1, 1) значения двойственной можно получить следующим образом.

Инвертирование (1, 0, 1, 1, 1, 0, 0, 0).

Переворот (0, 0, 0, 1, 1, 1, 0, 1).

То есть значения двойственной функции будут такими: (0, 0, 0, 1, 1, 1, 0, 1).

Гораздо более творческое задание – получить формулу для функции, двойственной к данной булевой функции, используя теорему о двойственной к суперпозиции функций.

При этом используется следующая идея.

Если α и β – две булевы функции, то, например, . Аналогично вычисляется двойственная для других выражений, например, XOR заменяют эквивалентностью, а эквивалентность – XOR.

Например, если , то

Для самопроверки следует построить таблицу значений этой функции и сравнить с таблицей для f *, полученной композицией инверсии и переворота.