Чтобы составить таблицу Поста, нужно решить вопрос о принадлежности каждой из четырёх рассматриваемых функций к классам ( large P_0, P_1, S, L, M ). Если некоторая функция принадлежит тому или иному классу, то на пересечении соответствующей строки и соответствующего столбца ставится знак "плюс", если не принадлежит, то ставится знак "минус"
1) Представим все функции в полиномиальной форме и решим вопрос об их линейности. Используя основные тождества теории булевых функций, получим:
Сразу делаем вывод о нелинейности всех рассматриваемых в задаче функций.
Поскольку полином Жегалкина есть форма представления булевой функции (при переходе к полиномиальному виду сама функция не меняется), далее будем использовать полиномиальные представления рассматриваемых в задаче булевых функций.
2) Решим вопрос о принадлежности функций к классу ( large P_0 ). Имеем:
Итак, функции ( large f_2 ) и ( large f_3 ) сохраняют нуль, а функции ( large f_1 ) и ( large f_4 ) — не сохраняют.
3) Проверим, какие из функций принадлежат к классу ( large P_1 ). Имеем:
Вывод: все рассматриваемые функции, кроме ( large f_2 ), сохраняют единицу.
4) Выясним, какие функции принадлежат к классу ( large S ). Используя определение самодвойственной функции, получим:
Итак, ни одна из функций не принадлежит к классу самодвойственных функций.
5) Используя определения элементарных булевых функций, составим таблицы значений для функций ( large f_1, f_2, f_3, f_4 ) и выясним, являются ли они монотонными.
Рассмотрим первую и вторую строки таблицы. Функция ( large f_1 ) не является монотонной, так как
но
Рассмотрев третью и четвертую строки таблицы, делаем вывод, что функция ( large f_2 ) также не является монотонной, поскольку
но
Рассмотрим третью и седьмую строки таблицы. Функция ( large f_3 ) не является монотонной, так как
но
Рассмотрев первую и вторую строки таблицы, замечаем, что
но
Значит, функция ( large f_4 ) также не является монотонной.
Используя полученные выше данные, составим таблицу Поста:
Согласно теореме Поста, системы ( large { f_1,f_2,f_3,f_4 } ), ( large { f_1,f_2,f_3 } ), ( large { f_1,f_2,f_4 } ), ( large { f_2,f_3,f_4 } ), ( large { f_1,f_2 } ), ( large {f_2 ,f_4 } ) полны, поскольку в каждой из них есть функция, не сохраняющая нуль, есть функция, не сохраняющая единицу, есть функция, не являющаяся самодвойственной, есть нелинейная функция, есть немонотонная функция.
стемы ( large {f_1 ,f_3,f_4 } ), ( large { f_1,f_3 } ), ( large { f_1,f_4 } ), ( large { f_2,f_3 } ), ( large { f_3,f_4 } ), ( large { f_1 } ), ( large { f_2 } ), ( large { f_3 } ), ( large {f_4 } ), в силу той же теоремы, не являются полными. Но являются ли перечисленные выше полные системы базисами? Будем рассуждать, используя определение базиса булевых функций. Системы ( large { f_1,f_2 } ), ( large {f_2 ,f_4 } ) есть базисы, поскольку после удаления из них любой функции они превращаются в систему из одной функции, а все такие системы, как сказано выше, не полны. Удаляя из системы ( large { f_1,f_2,f_3 } ) функцию ( large f_3 ) получаем полную систему, удаляя из системы ( large { f_1,f_2,f_4 } ) функцию ( large f_1 ) получаем полную систему, удаляя из системы ( large { f_2,f_3,f_4 } ) функцию ( large f_3 ) получаем полную систему. Следовательно, системы ( large { f_1,f_2,f_3 } ), ( large { f_1,f_2,f_4 } ), ( large { f_2,f_3,f_4 } ) не являются базисами. Система ( large {f_1, f_2,f_3,f_4 } ) не базис, так как, например, удаление из неё функции ( large f_4 ) приводит к полной системе.
Итак, базисами являются только две системы: ( large { f_1,f_2 } ) и ( large {f_2 ,f_4 } ).
С другими вопросами теории, связанными с полнотой систем булевых функций, можно ознакомиться, перейдя в наш теоретический раздел
maths24.net
Система булевых функций F={f1,…,fn} называется полной, если любая булева функция представима в виде терма сигнатуры (f1,…,fn}, т.е в виде суперпозиции функций из F.
Классы Поста:
1) P0={f|f(0,…,0)=0} — класс булевых функций, сохраняющих ноль
2) P1={f|f(1,…,1)=1} – класс булевых функций, сохраняющих 1
3) S={f|f+=f} – класс самодвойственных функций
4) M – класс монотонных функций. Булева функция f(x1,…,xn) называется монотонной, если для любых наборов нулей и единиц (α1,…,αn) и (β1,…,βn) из условий αi≤βi следует f(α1,…,αn)≤f(β1,…,βn)
5) Класс I – это класс линейных функций. Булева функций f(x1,…,xn) называется линейной, если в булевом кольце функция f представима в виде
.
Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции.
Теорема Поста: Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P0, P1, S, M, L в системе F найдется функция, не принадлежащая этому классу..
Теорема: Каждый базис содержит не более четырех булевых функций
Доказательство: Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу P0. Тогда f(0,…,0)=1 и f(1,…,1)=1, но тогда f не принадлежит классу самодвойственных функций, а это противоречит предположения.
studopedia.ru