Классы поста

Чтобы составить таблицу Поста, нужно решить вопрос о принадлежности каждой из четырёх рассматриваемых функций к классам (  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={f₁,…,f_n} называется полной, если любая булева функция представима в виде терма сигнатуры (f₁,…,f_n}, т.е в виде суперпозиции функций из F.

Классы Поста:

1) P₀={f|f(0,…,0)=0} — класс булевых функций, сохраняющих ноль

2) P₁={f|f(1,…,1)=1} – класс булевых функций, сохраняющих 1

3) S={f|f⁺=f} – класс самодвойственных функций

4) M – класс монотонных функций. Булева функция f(x₁,…,x_n) называется монотонной, если для любых наборов нулей и единиц (α₁,…,α_n) и (β₁,…,β_n) из условий α_i≤β_i следует f(α₁,…,α_n)≤f(β₁,…,β_n)

5) Класс I – это класс линейных функций. Булева функций f(x₁,…,x_n) называется линейной, если в булевом кольце функция f представима в виде .

Каждый класс Поста замкнут относительно операций замены переменных и суперпозиции.

Теорема Поста: Система F булевых функций тогда и только тогда является полной, когда для каждого из классов P₀, P₁, S, M, L в системе F найдется функция, не принадлежащая этому классу..

Теорема: Каждый базис содержит не более четырех булевых функций

Доказательство: Предположим, что существует базис F, состоящий более чем из четырех функций. По теореме Поста тогда получаем, что F состоит ровно из пяти функций, каждая из которых не принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классу P₀. Тогда f(0,…,0)=1 и f(1,…,1)=1, но тогда f не принадлежит классу самодвойственных функций, а это противоречит предположения.

studopedia.ru