Условие:
Выберите функцию, для которой верно утверждение: любая булева функция может быть представлена формулой, использующей только эту функцию.
(00011111)
(10001000)
(00111100)
(10101010)
Решение:
Нам дано четыре булевы функции (заданные таблицами истинности для трёх переменных). Надо выбрать ту функцию f, что класс формул, составленный только из неё, функционально полный – то есть каждая булева функция может быть выражена формулой, использующей только f.
Чтобы функция f была функционально полной (то есть самим оператором f можно было выразить все булевы функции), она не должна принадлежать ни одному из классов, закрытых по Посту. В частности, она не должна:
- Сохранять ноль: f(0,0,0)=0
- Сохранять единицу: f(1,1,1)=1
- Быть монотонной
- Быть самодвойственной
- Быть линей...