Представление конъюнкции и отрицания через данную функцию f (X, y, z) и её отрицание
Первый шаг в такой работе – вычисление
и
.
Получим две противоположные функции
от одной переменной.
Далее возможны два случая: или это 0 и
1, или это x и
.
(Например, для функции
получим
,
)
В общем случае для достижения конечного результат нам понадобятся и обе константы, и отрицание, поэтому рассмотрим оба случая.
Если есть две константы: по немонотонности найдутся два набора, на которых нарушается монотонность. Например, (0, 0, 1) < (0, 1, 1), но f (0, 0, 1) > f (0, 1, 1). Тогда поставим x на место разряда, на котором нарушается монотонность.
В данном случае обозначим h (x) = f (0, x, 1). Эта функция переводит 0 в 1, а 1 в 0, следовательно, h (x) – это отрицание.
Если есть отрицание, то по несамодвойственности найдутся два инверсных набора (наборы, получающиеся заменой 0 на 1 и 1 на 0), значения в которых одинаковы.
Тогда подставим в один из этих наборов
x вместо 1 и
вместо 0. Например, f (1, 0,
0) = f (0, 1, 1) = 0. Рассмотрим
функцию
.
Поскольку её значение не меняется при
инверсии набора, то значение равно
константе. В данном случае 0. Чтобы
получить 1, возьмём отрицание f.
Таким образом, в данном примере
.
Итак, мы получили две константы и отрицание. Теперь нужно получить дизъюнкцию. Получим её с помощью нелинейности. Многочлен Жегалкина содержит хотя бы одно произведение. Например, f (x, y, z) = z + xy + yz. Если мы получим выражение, целиком состоящее из произведения двух переменных, то наша цель достигнута.
В нашем примере можно принять z = 0 и получить: f (x, y, 0) = xy.
Осталось выразить 0, причём только через f и отрицание этой функции.
.
Подставим одно выражение в другое.
Теперь воспользуемся этим нулём.
Таким образом, можем записать ответ:
Обращаем ваше внимание на то, что в ответе не должно быть констант, в выражении для конъюнкции не должно быть отрицания х.
Для других многочленов Жегалкина могут потребоваться другие подстановки, одного метода на все случаи жизни не существует, поэтому ограничимся некоторыми общими рекомендациями.
Не обязательно получать произведение xy. Например, произведение xz, если вы его получите, тоже будет решением задачи.
Не обязательно одно из чисел принимать именно за 0. Можно принять его за 1. Например, в случае 1 + z + xy замена z = 1 быстрее приведёт к цели, чем замена z = 0.
Во многих случаях для получения конъюнкции
поможет отрицание. Например, для случая
f (x, y,
0) = x + xy можно
вынести x за скобку и
получить выражение x (y
+ 1) =
.
Тогда получим
.
Но нам нужно получить не
,
а xy.
Для этого мы возьмём отрицание от y
в обеих частях и получим:
,
а это и требовалось. Осталось только
записать произведение по правилам, то
есть без констант и отрицаний.
Наконец, иногда получается не xy,
а
.
Например,
.
В этом случае нужно взять
.
В целом, заключительная задача творческая, и её решение, вообще говоря, не однозначно определено.
Примечание
-
Конструктивно-исследовательские задачи. Например: существует ли булева функция линейная, но не монотонная. И так далее. (Ответ: да. например, отрицание или XOR).
-
Комбинаторные задачи про булевы функции. Например: сколько существует линейных функций от 5 переменных? (ответ: 64)
ДЛЯ СЕМИНАРОВ
(Задание для функции, формула которой приведена после номера варианта, с формулировками, разобранными в теоретическом материале.)
