Page 39 - 4496

Теорема Поста
Щоб система перемикальних функцій була повною,
необхідно і достатньо , щоб вона містила хоча б одну функцію
яка не зберігає нуль, одиницю, не є лінійною , монотонною та
самодвоїстою. Іншими словами для задоволення критерію
повноти необхідно й достатньо, щоб серед функцій системи
були:
- функція, що не зберігає константу нуль;
- функція, що не зберігає константу одиниця;
- функція, що не є само двоїстою;
- функція, що не є монотонною;
- функція, що не має властивості лінійності.
Якщо кожна із взятих функцій має лише одну
властивість (але відмінну від інших), то для повноти системи
необхідні 5 функцій.
У зв'язку з тим, що кожна із функцій має декілька
властивостей, функціонально повні системи можуть бути
побудовані за допомогою однієї, двох, трьох і чотирьох
функцій.
Найпоширенішою є система із трьох функцій (І, НЕ ,
АБО). За допомогою цієї системи функцій можна описати
роботу будь-якого логічного пристрою, наприклад , ЕОМ.

2.20 Канонічні форми перемикальних функцій

Проблема розв'язуваності.
Означення1. Формула називається тотожно істиною,
якщо вона при всіх можливих значеннях змінної , які входять
у неї, набуває значення одиниці і тотожно хибною, якщо при
всіх значеннях змінної набуває значення нуля.
Означення2. Формула називається здійсненою, якщо
набуває значення одиниці при деяких значеннях змінної і нуля
при інших значеннях цих же змінних.
Поставимо таку задачу: Знайти єдиний спосіб (алгоритм)
,який дає змогу для кожної формули з'ясувати чи вона є
здійсненою( не дорівнює тотожно 0 або 1).
Нехай задана деяка перемикальна функція
F (x 1 , x 2 ,..., x n ). Змінні можуть набувати значення із множини
n
n
2
2 .Всього значень функції буде М= 2 .Для кожної комбінації
36