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в.