L - клас усіх лінійних перемикальних функцій
Передповними називають класи перемикальних функцiй Р0, Р1, S, M, L, якi зберігають константи 0 і 1, є самодвоїстими, монотонними та лінійними.
Iснують функції, які належать кожному із п’яти класів, наприклад: f(x)=x.
Теорема про функціональну повноту: для того, щоб система пере-микальних функцій була повною, необхідно та достатньо, щоб вона цілком не мiстилася в жодному з п'яти класів T0,T1, S, L, M .
У задачах, де потрібно з'ясувати, чи є повною система перемикальних функцій, складають таблиці Поста, в кожну клітинку яких заносять символ плюс або мінус, залежно від того, чи входить перемикальна функція, що стоїть у вiдповiдному рядку, до класу, що знаходиться у вiдповiдному стовпцi.
Виходячи з теореми про повноту, одержуємо наступне правило: для повноти системи перемикальних функцій, необхідно та достатньо, щоб у кожному стовпці таблицi Поста знаходився хоча б один мінус.
Теорема про подання перемикальних функцiй через диз’юнкцію, кон’юнкцію та заперечення:будь-яка перемикальна функцiя може бути пред-ставлена у вигляді суперпозиції перемикальних функцій із множини {Ú, &, ¯}, де знак “¯” ставиться лише безпосередньо над деякими зi змінних і не ставиться над внутрішніми функціями.
Теорема про функціональну повноту деяких поширених систем перемикальних функцiй: функціонально повними є системи перемикальних функцiй { Ú, &, ¯ }, { Å, &, ¯ }, { Ú, ¯ }, { &, ¯ }, { Þ, ¯ }, { | }; { 
}.
Теорема про власність і замкненість класів Р0, Р1, S, M і L:класи P0, P1, S, M, L є власними та замкненими класами перемикальних функцiй.
Теорема Поста про функціональну повноту:. система перемикальних функцiй F={f1, f2, …, fk,…} є функціонально повною тоді і тільки тоді, коли в ній існує:
1) хоча б одна функція, що не зберігає константу 0;
2) хоча б одна функція, що не зберігає константу 1;
3) хоча б одна не самодвоїста функцiя;
4) хоча б одна не лінійна функцiя;
5) хоча б одна немонотонна функція.
Наслідок 1 теореми Поста про функціональну повноту: у результаті суперпозиції немонотонної перемикальної функції f(x1,…,xn) iз константами 0 і 1, може бути отримана функція заперечення`xi одного з її аргументів.
Система перемикальних функцiй називається ослаблено функціонально повною, якщо дана система містить у собі константи 0 і 1.
Наслідок 2 теореми Поста про ослаблену функціональну повноту: для того, щоб система перемикальних функцiй була ослаблено функціонально повною, необхідно та достатньо, щоб вона містила хоча б одну нелінійну та одну немонотонну функцію.
Функціонально повну систему перемикальних функцiй називають нескоротною, якщо будь-яка її частина не є функціонально повною.
Будь-яку функціонально повну систему перемикальних функцiй можна привести до нескоротного виду, видаляючи з неї зайві функції.
Наслідок 3 теореми Поста про ослаблену функціональну повноту: максимально можливе число перемикальних функцiй у нескоротній функціонально повній системі перемикальних функцiй дорівнює чотирьом.
Наслідок 4 теореми Поста про функціональну повноту: на практиці, для знаходження функцiонально повних систем перемикальних функцiй, зручно користуватися таблицями, подібними наведеній нижче.
Критерієм функціональної повноти буде наявність символу «+» у п’ятьох стовпчиках категорiї «Групи елементів» указаної таблиці.
| Тип елементу | Функція | Групи елементів | ||||
| Немоно-тонні | Нелінійні | Несамо- двоїсті | Не збері-гають 0 | Не збері-гають 1 | ||
| Тривіальний | x | - | - | - | - | - |
| Нулевий | 0 | - | - | - | - | + |
| Одиничний | 1 | - | - | - | + | - |
| Інвертор | `х | + | - | - | + | + |
| Кон’юнкція | хÙy | - | + | + | - | - |
| Диз’юнкція | хÚy | - | + | + | - | - |
| Співпадання з забороною | `хÙy º
º 
| + | + | + | - | + |
| Розділення з забороною (імплікація) | `хÚy º º x®y | + | + | + | + | - |
| Співпадiння з подвійною забороною (стрілка Пірса) | `хÙ`y º º x¯y | + | + | + | + | + |
| Розділення з подвійною забороною (штрих Шефера) | `хÚ`y º º x½y | + | + | + | + | + |
| Елемент рівнознач-ності | хуÚ`х`у º х«у | + | - | + | + | - |
| Елемент нерівнознач-ності | хÅу | + | - | + | - | + |
КОНТРОЛЬНІ ПИТАННЯ
1. Що розуміють під елементарною перемикальною функцією ?
2. Сформулювати поняття логічного елементу.
3. Що являє собою комбінаційна схема ?
4. Чим вирізняється поняття цифрового автомату ?
5. За якою технологією здійснюється побудова тих комбінаційних схем, які реалізують перемикальні функції, задані аналітичними виразами ?
6. Охарактеризувати метод побудови комбінаційних схем, які реалізують перемикальні функції, задані таблицями істинності.
7. Чим вирiзняються функцiонально повнi системи перемикальних функцій ?
8. Яку роль вiдiграє теорема про подання перемикальних функцiй через диз`юнкцiю, кон`юнкцiю та заперечення ?
9. Сформулювати теорему про функцiональну повноту деяких поширених систем перемикальних функцiй
10. Охарактеризувати перемикальнi функцiї, що зберiгають константу 0 (клас P0) i константу 1 (клас P1), самодвоїстi (клас S), монотоннi (клас M) i лiнiйнi (клас L) перемикальнi функції.
11. Пояснити поняття власних i замкнених класiв перемикальних функцiй (класiв Поста).
12. Сформулювати теорему про власнiсть i замкненiсть класiв перемикальних функцiй P0, P1, S, M, i L.
13. Охарактеризувати роль теореми Поста про функiональну повноту та її наслiдкiв.