Критерий Поста

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:50, 8 июня 2016.

Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию.[1]

Вспомогательные леммы

Прежде чем перейти непосредственно к критерию Поста, сформулируем и докажем несколько вспомогательных лемм.[2]

Лемма о несамодвойственной функции

TemplateTheoremIcon.svg Теорема Лемма о несамодвойственной функции

Если , то подставляя в функцию вместо переменных функции и , можно получить функцию, равную .

Доказательство

Если , то .

Если , то найдется набор .

Рассмотрим функцию , тогда

,


Но

Тогда


,
то есть


Лемма о немонотонной функции

TemplateTheoremIcon.svg Теорема Лемма о немонотонной функции

Если , то подставляя в функцию вместо переменных функции , и , можно получить функцию, равную .

Доказательство
Если , то найдутся наборы


Тогда обязательно найдется пара соседних наборов, на которых нарушается монотонность.


Если наборы и — соседние, то утверждение доказано.


Если расстояние между этими наборами равно , то рассматривая цепочку соседних наборов, соединяющих и , обязательно найдем среди них пару соседних наборов, на которых нарушается монотонность.


Если наборы и — соседние наборы, на которых нарушается монотонность, то пусть они различаются по -й координате: и .


При этом , .


Рассмотрим функцию .


Тогда
,

,

т.е. .


Лемма о нелинейной функции

TemplateTheoremIcon.svg Теорема Лемма о нелинейной функции

Если , то подставляя в функцию вместо переменных функции , , и и, при необходимости, инвертируя функцию , можно получить функцию конъюнкции.

Доказательство

Если , то в АНФ функции найдется хотя бы одно слагаемое, содержащее произведение каких-то двух переменных.


Пусть, например, это будут переменные и :
,

где — функция, не являющаяся тождественным 0.


Так как , то


Рассмотрим функцию
,

где , , .


Рассмотрим теперь функцию


Тогда функция[прим. 1]


Критерий Поста

TemplateTheoremIcon.svg Теорема Критерий Поста

Для того, чтобы система функций была функционально полной, необходимо и достаточно, чтобы она целиком не лежала ни в одном из 5 основных замкнутых классов: , , , , .

Доказательство

Необходимость.

Пусть , где — один из 5 основных замкнутых классов.


Тогда


Достаточность.

Пусть целиком не лежит ни в одном из 5 основных замкнутых классов. Тогда:

  • ;
  • ;
  • ;
  • ;
  • .


I. Покажем, что с помощью функций можно получить константы и .


a)
б)


По лемме о несамодвойственной функции, из функций и можно получить константу ; другую константу можно получить, применив к функцию инверсии.


II. C помощью полученных в п. I констант и и функции по лемме о немонотонной функции можно получить функцию инверсии: .


III. C помощью полученных в п.п. I, II констант и , функции инверсии и функции по лемме о нелинейной функции можно получить функцию конъюнкции


Таким образом, каждая функция функционально полной системы может быть выражена формулой в базисе . По доказанной ранее теореме — система сама является функционально полной системой.

Следствие

TemplateLemmaIcon.svg Лемма «Следствие»
Всякий отличный от замкнутый класс булевых функций целиком содержится по крайней мере в одном из 5 замкнутых классов: , , , , .


Пример

Рассмотрим множество


+ - - + +
- + - + +
+ + - + -
+ + + - +


По теореме, доказанной выше, множество является функционально полной системой, но никакое его подмножество функционально полной системой не является.

Примечания

  1. Инвертируем или не инвертируем функцию в зависимости от значения величины

Литература

  1. https://ru.wikipedia.org/wiki/Критерий_Поста
  2. Жуков А.Е. Лекции по булевым функциям