Критерій поста, математика, fandom powered by wikia

Критерій Посту - одна з центральних теорем в теорії булевих функцій. встановлює необхідна і достатня умова для того, щоб певний набір булевих функцій володів достатньою виразністю, щоб представити будь-яку булеву функцію. Вперше сформульовано американським математиком Емілем Постом.

В середині 60-х років майже одночасно в СРСР і у Франції з'явилися роботи, де з інших позицій і в більш доступній формі викладалися результати Посту. У 80-ті роки відразу цілої низки дослідників з використанням різних підходів і різної техніки вдалося отримати досить компактні докази результатів Посту. Алгебраїчний підхід у вивченні замкнутих класів булевих функцій (подалгебр итеративной алгебри Посту над безліччю) належить А. І. Мальцеву.

Попередні відомості Правити

Булева функція - це функція типу, де, а - арность. Кількість різних функцій арності одно, загальна ж кількість різних булевих функцій нескінченно. Разом з тим, очевидно, що багато функцій можуть бути виражені через інші, з використанням оператора суперпозиції. Наприклад, давно відомо, що з диз'юнкції і заперечення можна, використовуючи закони де Моргана. отримати кон'юнкцію. Крім того, будь-яка булева функція (за винятком тотожної одиниці) може бути представлена у вигляді ДНФ тобто в термінах кон'юнкції, диз'юнкції і заперечення. Виникає природне запитання: як визначити, чи буде даний набір функцій достатнім, щоб представити будь-яку булеву функцію. Такі набори називаються функціонально повними. Теорема Поста дає відповідь на це питання. Оскільки умова теореми є необхідними і достатнім, її називають також критерієм.

Ідея теореми полягає в тому, щоб розглядати безліч всіх булевих функцій як алгебру щодо операції суперпозиції. Зараз вона носить ім'я алгебра Посту. Ця алгебра містить, як своїх подалгебр, безлічі функцій, замкнутих. щодо суперпозиції. Їх називають ще замкнутими класами. Нехай - деяка підмножина. Замиканням множини називається мінімальна подалгебра, що містить. Іншими словами, замикання складається з усіх функцій, які є суперпозиціями. Очевидно, що буде функціонально повно тоді і тільки тоді, коли. Таким чином, питання, чи буде даний клас функціонально повний зводиться до перевірки того, чи збігається його замикання с.

Оператор, є оператором замикання. Іншими словами, він володіє (серед інших) властивостями:

Кажуть, що безліч функцій породжує замкнуте клас (або клас породжується безліччю функцій), якщо. Безліч функцій називається базисом замкнутого класу, якщо і для будь-якої підмножини множини, відмінного від.

Якщо до подалгебре, яка не співпадає з додати один елемент, їй не належить, і утворити замикання, результатом буде нова подалгебра, що містить дану. При цьому, вона співпаде з, в тому і тільки в тому випадку, якщо між вихідної подалгебру, і немає ніяких інших подалгебр, тобто, якщо вихідна подалгебра була максимальною. Таким чином, для того, щоб перевірити, що дане безліч функцій функціонально повно, досить переконається, що воно не входить цілком ні в одну з максимальних подалгебр. Виявляється, що таких подалгебр всього п'ять, і питання приналежності до них може бути вирішене просто і ефективно.

Двоїстість, монотонність, лінійність. Критерій повноти Правити

Нижче наведені деякі наслідки, що випливають з теорем про двоїстих функціях.

Якщо - замкнутий клас. то - також замкнутий клас.
Безліч утворює замкнутий клас.
Якщо безліч породжує замкнуте клас, то безліч породжує замкнуте клас. Зокрема, якщо - базис класу, то - базис класу.

Перейдемо тепер до з'ясування повноти конкретних наборів функцій.

Основні класи функцій Правити

** Функція змінних називається самодвоїстих. якщо на протилежних наборах вона приймає протилежні значення, тобто самодвоїстих функція задовольняє умові Наприклад, функції, - є самодвоїстих. а функції, - не є.

Теорема про замкнутості основних класів функцій Правити

Відзначимо, що жоден з замкнутих класів цілком не міститься в об'єднанні інших чотирьох. Це випливає з таких співвідношень:

Всякий замкнутийклас булевих функцій, відмінний від, цілком міститься хоча б в одному з класів.

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

Критерій Посту - теорема. яка дозволяє визначити, чи є повним набір булевих функцій (повний набір значить, що будь-яка [інша] булева функція записується у вигляді формули, де зв'язками служать функції набору). Запропонований американським математиком Емілем Постом.

Набір булевих функцій тоді і тільки тоді є повним, коли він не міститься ні в одному з п'яти класів ( «предполних»):

монотонні функції (функція монотонно не убуває по кожному зі своїх аргументів);
функції, що зберігають нуль (функція від нуля дає нуль);
функції, що зберігають одиницю (функція від одиниці дає одиницю);
лінійні функції (функція представима многочленом, в якому кожен член складається з однієї змінної);
самодвоїстих функції (функція двоїста сама собі).

література Правити

С. С. Марченков, «Замкнуті класи булевих функцій»
Освітній сайт MiniSoft