Двойственные формулы — в алгебре логики — это такие формулы, которые получаются одна из другой путём замены в них каждого знака конъюнкции на знаки дизъюнкции и наоборот. При этом предполагается, что формулы построены лишь с помощью операций ∧, ∨, ~.
Определение. Формула F* называется двойственной формуле F, если она получена из F заменой символов функций на символы двойственных им функций. Пример. Теорема (принцип двойственности).
Функция самодвойственна, если и только если на противоположных наборах принимает противоположые значения. Достаточное условие несамодвойственности булевой функции. Если число единиц в столбце значений функции не совпадает с числом нулей, то функция не является самодвойственной.
Булева функция называется линейной (принадлежит классу L), если ее полином Жегалкина линеен. Утверждение о числе булевых функций класса L. Число различных линейных булевых функций, зависящих от n переменных, равно 2n+1.