Как найти двойственную функцию: решение по шагам

Дано: булева функция $f(x, y, z) = (x \vee y) \wedge \neg z$. Найти: двойственную функцию $f^{*}$, её формулу и ответ на вопрос, самодвойственна ли $f$.

Двойственная функция получается по определению $f^{*}(x, y, z) = \overline{f(\bar{x}, \bar{y}, \bar{z})}$: инвертируем все аргументы и инвертируем результат. Ответ: $f^{*} = (x \wedge y) \vee \neg z$, вектор значений 10101011, функция $f$ не самодвойственна. Калькулятор сверху строит обе таблицы для любой функции трёх переменных, а ниже тот же расчёт разобран по шагам.

Решение по шагам

Шаг 1. Таблица истинности исходной функции. Переменных три, значит наборов $2^3 = 8$. Перебираем их в стандартном порядке, читая набор как двоичную запись номера строки: 000, 001, 010 и так далее до 111. Сначала считаем дизъюнкцию $x \vee y$ и отрицание $\neg z$, потом их конъюнкцию.

Вектор значений $f$ записываем сверху вниз: 00101010. Если построение таблицы само по себе вызывает вопросы, порядок заполнения столбцов подробно разобран в задаче как построить таблицу истинности.

Шаг 2. Находим противоположные наборы. Инверсия всех переменных переводит набор 000 в 111, набор 001 в 110 и так далее. В нумерации строк это означает переход от строки $i$ к строке $7 - i$: противоположные наборы стоят симметрично относительно середины таблицы. Поэтому искать их не нужно, достаточно читать вектор $f$ снизу вверх.

Шаг 3. Инвертируем результат. По определению значение $f^{*}$ на наборе берётся со строки-зеркала и меняется на противоположное:

$$f^{*}(\alpha) = \overline{f(\bar{\alpha})}, \qquad \alpha = (x, y, z).$$

Вектор двойственной функции: 10101011. Короткое правило видно сразу: вектор $f$ переворачивается задом наперёд и каждый разряд инвертируется.

Шаг 4. Записываем формулу двойственной функции. Единицы $f^{*}$ стоят на наборах 000, 010, 100, 110 и 111. Первые четыре отличаются только значениями $x$ и $y$, а $z$ в них равен нулю, так что они склеиваются в одно слагаемое $\neg z$. Остаётся набор 111, то есть конъюнкция $xyz$, и она поглощается вместе с $\neg z$ по правилу $\neg z \vee xyz = \neg z \vee xy$:

$$f^{*} = \neg z \vee xyz = (x \wedge y) \vee \neg z.$$

Шаг 5. Проверяем самодвойственность. Сравниваем вектор $f$ = 00101010 и вектор $f^{*}$ = 10101011 разряд за разрядом. Совпадений шесть, расхождения два: строки 000 и 111. На этой паре противоположных наборов исходная функция даёт одно и то же значение, $f(0,0,0) = f(1,1,1) = 0$, а самодвойственность требует, чтобы значения были разными.

Ответ: $f^{*}(x, y, z) = (x \wedge y) \vee \neg z$ с вектором значений 10101011; функция $f$ не самодвойственна, контрпример - пара наборов 000 и 111.

Формула и откуда она берётся

Определение двойственной функции выглядит так: для булевой функции $f$ от $n$ переменных

$$f^{*}(x_1, \dots, x_n) = \overline{f(\bar{x}_1, \dots, \bar{x}_n)}.$$

Здесь черта над переменной означает её отрицание, а внешняя черта - отрицание всего результата. Операция ровно из двух шагов: сначала подменяем входы противоположными, потом переворачиваем выход.

Именно из этого определения и вытекает работа с вектором. Набор, противоположный набору с номером $i$, имеет номер $2^n - 1 - i$, потому что инверсия каждого бита равна дополнению числа до единиц во всех разрядах. Значит, значение $f^{*}$ в строке $i$ лежит в строке $2^n - 1 - i$ вектора $f$, остаётся только его инвертировать. Никаких вычислений по формуле при этом не требуется: достаточно готовой таблицы.

Двойственность обратима. Применим определение дважды: $f^{**}(\alpha) = \overline{f^{*}(\bar{\alpha})} = \overline{\overline{f(\alpha)}} = f(\alpha)$. То есть функция, двойственная к двойственной, совпадает с исходной, и пары функций всегда двойственны друг другу взаимно. Полезное следствие для самопроверки: если вы нашли $f^{*}$, примените ту же процедуру к ответу - должна вернуться $f$.

Двойственная формула без таблицы: замена операций

Когда функция задана формулой, таблицу можно не строить. Двойственная формула получается заменой каждой операции на двойственную ей: конъюнкция меняется на дизъюнкцию, дизъюнкция на конъюнкцию, константа 0 на 1 и наоборот. Отрицания и сами переменные остаются на своих местах, скобки сохраняются.

Проверим правило на нашем примере: в формуле $(x \vee y) \wedge \neg z$ меняем внешнюю конъюнкцию на дизъюнкцию, внутреннюю дизъюнкцию на конъюнкцию и получаем $(x \wedge y) \vee \neg z$ - ровно тот ответ, который дала таблица. Отрицание $\neg z$ не трогаем: двойственность меняет операции связывания, а не отрицание.

Основание у правила - законы де Моргана. Раскроем определение для дизъюнкции: $(x \vee y)^{*} = \overline{\bar{x} \vee \bar{y}} = x \wedge y$. Для конъюнкции симметрично: $(x \wedge y)^{*} = x \vee y$. А отрицание двойственно само себе, потому что $(\bar{x})^{*} = \overline{\overline{\bar{x}}} = \bar{x}$. Дальше работает индукция по построению формулы: двойственная к суперпозиции есть суперпозиция двойственных.

Отсюда же следует принцип двойственности: если две формулы равносильны, то равносильны и двойственные к ним. Поэтому в алгебре логики законы идут парами - распределительный закон для конъюнкции и для дизъюнкции, два закона поглощения, два закона де Моргана. Выводить вторую половину каждой пары не нужно, она получается автоматически. Этим удобно пользоваться при упрощении логических выражений: доказав одно тождество, вы бесплатно получаете двойственное.

Самодвойственные функции и класс S

Функцию называют самодвойственной, если $f^{*} = f$, то есть векторы значений совпали. Развернём условие: на любой паре противоположных наборов функция обязана принимать противоположные значения, $f(\bar{\alpha}) = \overline{f(\alpha)}$. Проверка сводится к четырём сравнениям для трёх переменных: строка 0 против строки 7, строка 1 против строки 6, строка 2 против строки 5, строка 3 против строки 4.

Такое описание сразу даёт и счёт. Вектор длины $2^n$ разбивается на $2^{n-1}$ зеркальных пар, в каждой верхнее значение выбирается свободно, а нижнее определено однозначно. Значит, самодвойственных функций от $n$ переменных ровно $2^{2^{n-1}}$: для трёх переменных это 16 функций из 256.

Классические представители - отрицание $\neg x$, тождественная функция $x$, медиана $xy \vee yz \vee zx$ и сумма по модулю два от нечётного числа переменных. Все они есть среди готовых чипов калькулятора сверху: выберите медиану, и подсветка расхождений пропадёт, а счётчик покажет ноль. Самодвойственные функции образуют замкнутый класс $S$ - один из пяти предполных классов в критерии полноты, о которых подробно написано в статье про классы Поста.

Частые ошибки

• Инвертируют только аргументы и забывают внешнее отрицание. Получается не $f^{*}$, а функция $f(\bar{x})$, у которой вектор просто перевёрнут. Внешняя черта обязательна.
• Меняют отрицания над переменными. При переходе к двойственной формуле заменяются только конъюнкции, дизъюнкции и константы. Запись $\neg z$ остаётся как есть.
• Забывают про константы. Если в формуле есть 0 или 1, они тоже меняются местами: например, двойственная к $x \wedge 1$ будет $x \vee 0$.
• Считают самодвойственной любую функцию с равным числом нулей и единиц. Баланс необходим, но не достаточен: важно, чтобы противоположные значения стояли именно в зеркальных парах строк.
• Переносят свойство с нечётного числа переменных на чётное. Сумма по модулю два от трёх переменных самодвойственна, а от двух нет: двойственной к $x \oplus y$ оказывается эквивалентность $x \leftrightarrow y$.
• Сбивают порядок наборов. Если таблица заполнена не в порядке двоичных чисел, зеркальные строки перестают быть симметричными, и переворот вектора даёт неверный ответ.

FAQ

Чем двойственная функция отличается от отрицания функции? Отрицание меняет только выход: $\bar{f}$ имеет вектор с инвертированными разрядами в тех же строках. Двойственная функция дополнительно переставляет строки зеркально. Совпадают эти операции лишь тогда, когда $f$ не зависит от переменных по существу.

Как быстро найти двойственную функцию, если дан только вектор значений? Прочитайте вектор справа налево и инвертируйте каждый разряд. Для вектора 00101010 обратный порядок даёт 01010100, после инверсии получается 10101011 - это и есть вектор $f^{*}$.

Сколько единиц у двойственной функции? Столько же, сколько нулей у исходной. Перестановка строк количество значений не меняет, а инверсия меняет нули на единицы: в примере у $f$ три единицы, у $f^{*}$ их пять.

Двойственна ли функция сама себе, если она задана СДНФ? Форма записи роли не играет, самодвойственность - свойство самой функции. Но по совершенной дизъюнктивной нормальной форме её видно быстро: наборы с единицами не должны содержать ни одной зеркальной пары, при этом их ровно половина от общего числа. Как строится сама форма, разобрано в материале про СДНФ.

Коротко

1. По определению $f^{*}(x_1, \dots, x_n) = \overline{f(\bar{x}_1, \dots, \bar{x}_n)}$: инвертировать аргументы и инвертировать результат.
2. На векторе значений это переворот вектора задом наперёд плюс инверсия каждого разряда; строка $i$ берётся из строки $2^n - 1 - i$.
3. По формуле - замена конъюнкции на дизъюнкцию, дизъюнкции на конъюнкцию, 0 на 1 и обратно; переменные и отрицания не трогаем.
4. Для $f = (x \vee y) \wedge \neg z$ вектор 00101010 даёт 10101011, то есть $f^{*} = (x \wedge y) \vee \neg z$.
5. Функция самодвойственна, когда $f^{*} = f$, то есть на каждой паре противоположных наборов значения разные; у нашей $f$ пара 000 и 111 даёт одинаковые нули, поэтому она не самодвойственна.