В чем заключается важность теоремы Поста для теории булевых функций?

Важность теоремы Поста для теории булевых функций заключается в том, что она формулирует необходимое и достаточное условие полноты системы булевых функций. neerc.ifmo.ru

Согласно критерию Поста, система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из определённых замкнутых классов функций. neerc.ifmo.ru intuit.ru Иными словами, если в наборе имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция. neerc.ifmo.ru intuit.ru

Также теорема Поста позволяет строить базисы из элементарных функций. momathcollege.ucoz.org Для этого нужно выбрать любую элементарную булеву функцию и дополнить её при необходимости другими функциями так, чтобы все они вместе удовлетворяли теореме о функциональной полноте. momathcollege.ucoz.org Через функции этого базиса можно выразить все другие булевы функции. momathcollege.ucoz.org