Критерий Поста
Теорема 6.7 (критерий Поста). Множество булевых функций полно тогда и только тогда, когда оно не содержится целиком ни в одном из классов Поста.
Необходимость условия теоремы доказывается просто: если бы для некоторого класса Поста выполнялось , то всякая суперпозиция над , согласно теореме 6.5, снова лежала бы в . Между тем существуют функции, не содержащиеся ни в одном из классов Поста, например штрих Шеффера (см. пример 6.9). Таким образом, нашлась бы функция, которую нельзя представить в виде суперпозиции над , что противоречит предположению о полноте .
Переходим к доказательству достаточности условия теоремы. Для доказательства полноты множества , удовлетворяющего условию теоремы, построим формулы над для функций отрицания и конъюнкции, поскольку, как было замечено выше, множество, образованное этими функциями, полно. Тогда в силу теоремы 6.3 будет полным и множество .
Для немонотонной функции , согласно теореме 6.6, найдутся два таких набора и , что
а .
Тогда , т.е. отрицание может быть получено из немонотонной функции подстановкой вместо некоторого ее переменного переменного , а вместо остальных переменных констант , определяемых выбранными выше наборами и . Но, вообще говоря, система может и не содержать констант. Поэтому константы 0 и 1 необходимо представить некоторыми формулами над .
Рассмотрим два случая.
Первый случай. В существует функция , не сохраняющая константу 0, которая сохраняет константу 1; или существует функция , не сохраняющая константу 1, но сохраняющая константу 0.
Если существует функция и , то константа 1 представляется формулой , так как и . Чтобы выразить константу 0, используем любую функцию , не сохраняющую константу 1:
Если же указанная функция не существует, но найдется функция , to константы представляем формулами над аналогично (двойственным образом).
Второй случай. Любая функция из , не сохраняющая константу 0, не сохраняет и константу 1, и, наоборот, любая функция из , не сохраняющая константу 1, не сохраняет и константу 0.
Пусть и . Тогда мы получаем возможность представить отрицание следующей формулой:
Переходим к построению формул для констант, так как они потребуются нам далее при построении формулы для конъюнкции. Чтобы представить константы формулами над , воспользуемся несамодвойственной функцией из . Для этой функции найдется такой набор , что . Введем функцию от одного переменного (в предположении, что . Легко видеть, что , так как для любого имеем
Итак, значение есть константа. Если она равна 0, то константу 1 представляем через функцию, не сохраняющую константу 0; если же , то константу 0 представляем через функцию, не сохраняющую константу 1.
Опишем построение формулы для конъюнкции. Берем нелинейную функцию из . В полиноме Жегалкина для этой функции выберем произвольное нелинейное слагаемое, содержащее наименьшее число переменных; пусть это будет слагаемое при . Вместо каждого переменного функции , где , подставим константу 0, т.е. заменим нулем все переменные, которые не вошли в выбранную ранее конъюнкцию. Получим "редуцированную" функцию
Заметим, что коль скоро мы уже представили константы формулами над , то функция тоже представлена формулой над . Разобьем теперь множество переменных произвольно на две части: и , где , и заменим все переменные первой части переменным , а переменные второй части — переменным . В результате получим функцию от двух переменных
где .
Ясно также, что функция х может быть представлена такой формулой над
т.е. функция получена из нелинейной функции путем подстановки на место ее переменных с номерами переменного , на место переменных с номерами — переменного , а на место всех остальных переменных — константы 0, уже представленной формулой над (см. выше).
Определим функцию . Выразив эту функцию из полинома Жегалкина для получим
поскольку сумма по модулю 2 любого четного числа равных слагаемых равна 0. Итак, функция и есть конъюнкция. Так как прибавление к любой функции константы по модулю 2 есть либо сама исходная функция, либо ее отрицание, а отрицание уже представлено формулой над базисом , то тем самым и конъюнкция представлена такой формулой.
Чтобы исследовать полноту конкретного множества функций , нужно построить так называемую критериальную таблицу (табл. 6.6).
Строки таблицы соответствуют функциям исследуемого множества, а столбцы — классам Поста. В результате анализа функций множества клетки таблицы заполняются: если функция принадлежит некоторому классу Поста , то в соответствующей клетке критериальной таблицы ставится знак и "+" (плюс), а если нет, то — знак "–" (минус). Множество тогда полно, если и только если в каждом столбце таблицы стоит хотя бы один знак "–".
Пример 6.21. а. Пусть . Ниже приведены результаты исследования элементов этого множества на принадлежность к классам Поста, а также заполненная критериальная таблица (табл. 6.7).
При этом , так как функция (эквивалентность) не сохраняет константу 0, но сохраняет константу 1 (т.е. имеет место первый случай из доказательства достаточности условия теоремы Поста). Константа 0 принадлежит самому множеству . Поскольку , то ввиду полноты множества будет полным и рассматриваемое множество. Конъюнкцию можно представить формулой над , следуя доказательству теоремы Поста. Берем единственную нелинейную функцию данного множества, дизъюнкцию, и записываем для нее полином Жегалкина:
Видно, что этот полином есть не что иное, как функция при и . Следовательно,
Но так как , то . Этот же результат (в данном конкретном случае) можно получить и гораздо проще:
Итак, исходное множество является полным.
Заметим, что это полное множество двойственно к базису Жегалкина в том смысле, что каждая из его функций двойственна к соответствующей функции базиса Жегалкина: эквивалентность двойственна к сумме по модулю 2, дизъюнкция — к конъюнкции, константа 0 — к константе 1. Полезно заметить также, что никакое собственное подмножество заданного множества не будет полным.
б. Функция задана картой Карно (рис. 6.21), а вектор значений функции есть .
Для функции очень просто находятся ДНФ и полином Жегалкина:
откуда следует нелинейность функции . Легко показать также, что эта функция принадлежит лишь классу .
Так как , а , то функция не сохраняет ни константу 0, ни константу 1. Далее, эта функция несамодвойственна, поскольку ; немонотонность ее следует из того, что, например, , но . Вопрос о нелинейности функции оставим пока открытым, так как даже из частично заполненной критериальной таблицы (табл. 6.8) вытекает, что множество полно.
Формулы для отрицания и констант находятся легко:
Формулу для конъюнкции проще всего построить прямо по ДНФ для функции
Вернемся теперь к отложенному вопросу о нелинейности функции . По приведенной на рис. 6.21 карте Карно можно построить одну из минимальных ДНФ, представляющих эту функцию в виде
Подставляя в последнюю формулу 0 вместо , а вместо , 1 вместо и вместо , получаем , что доказывает нелинейность функции и одновременно полноту множества .
Константы же можно представить формулами над базисом , используя несамодвойственность функции (см. разбор второго случая в доказательстве достаточности условия теоремы Поста): мы уже видели, что , т.е. набор из упомянутого места в доказательстве теоремы Поста есть , и тогда функция , фигурирующая в том же месте доказательства и равная в данном случае константе 1, будет иметь вид . Но так как , то получаем
Подставив эти формулы в написанную выше формулу для конъюнкции, получим окончательно формулу над базисом для конъюнкции. Мы не выписываем эту формулу ввиду ее громоздкости.
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|