Prezentatsia10

Теорема Поста
Теорема. Система (набор) элементарных логических функций является (функционально) полной, если произвольную ПФ можно педставить в виде суперпозиции функций этой системы.
Чтобы система ПФ была полной, необходимо и достаточно, чтобы она содержала хотя бы одну функцию, не сохраняющую нуль, не сохраняющую единицу, не являющуюся линейной, не являющуюся монотонной, не являющуюся самодвойственной.

Особенности функционально полных систем.
Для удовлетворения критерию полноты необходимо и достаточно, чтобы среди функций системы имелись:
функция, не сохраняющая константу «0»;
функция, не сохраняющая константу «1»;
функция, не являющаяся самодвойственной;
функция, не являющаяся монотонно;
функция, не обладающая свойством линейности.
Если каждая из взятых функций не обладает лишь одним свойством, то для функциональной полноты необходима система из 5-ти функций.
Полная система называется несократимой, если исключение любой функции системы нарушает её полноту. В связи с тем, что каждая из функций не обладает несколькими свойствами, функционально полные системы могут быть построены с помощью одной, двух, трёх и четырёх функций. Наиболее распространённая система – система из трёх функций: И, ИЛИ, НЕ. С помощью этих функций могут быть описаны процессы управления любыми производствами, любая функция, описывающая работу любого устройства вычислительной техники.