Приналежність фал двох змінних до «чудових» класів функцій

Аргументи і тип ФАЛ		f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
a	b
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
Зберігає «0»		+	+	+	+	+	+	+	+
Зберігає «1»			+		+		+		+		+		+		+		+
Самоподвійна					+		+					+		+
Монотонна		+	+		+		+		+								+
Лінійна		+			+		+	+			+	+		+			+

Відповідно до теореми Поста-Яблонського, для того щоб ФАЛ була функціонально повною, необхідно і достатньо, щоб вона містила хоча б одну функцію, що не зберігає константу «0», хоча б одну функцію, що не зберігає константу «1», хоча б одну несамоподвійну функцію, хоча б одну нелінійну функцію, хоча б одну немонотонну функцію. Отже, у функціонально повну систему ФАЛ двох змінних повинні входити функції, спільно перекриваючі колонки табл. 2.1 клітками, не поміченими символом «+».

Існують різні функціонально повні системи ФАЛ: заперечення диз'юнкції (АБО-НІ); заперечення кон’юнкції (І-НІ); константа нуль і імплікація; заперечення і кон’юнкція; заперечення і диз’юнкція і т.д. Функціонально повний набір ФАЛ, що використовується для реалізації логічних схем, називається базисом. Найзручнішим для зображення ФАЛ є базис, що містить кон’юнкцію, диз’юнкцію і інверсію («І», «АБО», «НІ»). Використання трьох функцій спрощує описання схем, проте, як видно з табл. 2.1, будь-яку ФАЛ можна побудувати, використовуючи і лише одну функцію «І-НІ» або функцію «АБО-НІ». Базиси «І-НІ» «АБО-НІ» також отримали широке розповсюдження завдяки можливості істотно зменшити число уніфікованих логічних елементів.

Для перетворення ФАЛ з одного базису в інший використовується закон подвійного заперечення і закон подвійності (правило де Моргана), використання яких ілюструє такий приклад:

у базисі «І», «АБО», «НІ»: ; (2)

у базисі «І-НІ»: ; (3)

у базисі «АБО-НІ»: . (4)