L - клас усіх лінійних перемикальних функцій

Передповними називають класи перемикальних функцiй Р₀, Р₁, 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й { Ú, &, ¯ }, { Å, &, ¯ }, { Ú, ¯ }, { &, ¯ }, { Þ, ¯ }, { | }; { }.

Теорема про власність і замкненість класів Р₀, Р₁, S, M і L:класи P₀, P₁, S, M, L є власними та замкненими класами перемикальних функцiй.

Теорема Поста про функціональну повноту:. система перемикальних функцiй F={f₁, f₂, …, f_k,…} є функціонально повною тоді і тільки тоді, коли в ній існує:

1) хоча б одна функція, що не зберігає константу 0;

2) хоча б одна функція, що не зберігає константу 1;

3) хоча б одна не самодвоїста функцiя;

4) хоча б одна не лінійна функцiя;

5) хоча б одна немонотонна функція.

Наслідок 1 теореми Поста про функціональну повноту: у результаті суперпозиції немонотонної перемикальної функції f(x₁,…,x_n) iз константами 0 і 1, може бути отримана функція заперечення`x_i одного з її аргументів.

Система перемикальних функц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в.