Теорема

Пример.

Определение.

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

Рассмотрим примеры полных и неполных систем:

а) система - множество булевых функций, является полной системой;

б) система представляет полную систему;

в) система не является полной.

Пусть даны две системы функций и из , относительно которых известно, что является полной и каждая её функция выражается в виде формулы через функции системы . Тогда система также является полной.

Опираясь на эту теорему, можно установить полноту ряда систем следующим образом:

а) представить (задать) функции в виде формул;

б) все операции в заменить формулами над .

Дата добавления: 2014-10-22