Дана функции f=(10000110), зависящая от 3 -х переменных. Действуя по алгоритму, используемому при доказательстве леммы о несамодвойственной функции, составьте формулу над множеством \{f, ≠g x\}, реализующую константу 0 . Если формул несколько, приведите формулу с наименьшим количеством отрицаний.
Формула имеет вид f(A, B, C), где
Наша цель – построить формулу на базисе {f, ¬x} (при этом f – функция трёх аргументов, заданная таблицей значений (10000110)) такую, что полученная функция равна константе 0. При этом нужно использовать наименьшее число отрицаний.
Мы знаем, что функция f имеет значения (при порядке аргументов (x, y, z) согласно 000, 001, 010, 011, 100, 101, 110, 111):
f(0,0,0) = 1 f(0,0,1) = 0 f(0,1,0) = 0 f(0,1,1) = 0 f(1,0,0) = 0 f(1,0,1) = 1 f(1,1,0) = 1 ...