Условие:
Дана функции f, зависящая от 4-х переменных.
Известно, что она принимает значение 1 только на векторе с номером 13. Действуя строго по алгоритму, используемому при доказательстве леммы о немонотонной функции, составьте формулу над множеством \{f, 0,1\}, реализующую отрицание.
Формула имеет вид f(A, B, C, D), где:
Решение:
Мы знаем, что функция f от четырёх переменных принимает значение 1 только на векторе с номером 13. Напомним, что при 4‑х переменных номера векторов соответствуют их двоичным представлениям (при фиксированном порядке аргументов), и вектор с номером 13 имеет вид (1, 1, 0, 1). Наша цель — составить формулу, использующую лишь операции f, 0 и 1, которая реализует логическое отрицание (¬). То есть нам надо получить формулу, зависящую от некоторой переменной, скажем, x, и удо...