Система функций называется функционально полной системой, если любая логическая функция может быть представлена формулой над системой (является суперпозицией функций этой системы).
Из теоремы 1 (из предыдущей лекции) следует, что система является функционально полной. Равным образом, функционально полна любая система , через функции которой можно выразить конъюнкцию, дизъюнкцию и отрицание. Действительно, для любой логической функции из такой системы следует составить булеву формулу (а она обязательно существует согласно теореме 1 (из предыдущей лекции)) и потом выразить в ней конъюнкцию, дизъюнкцию и отрицание через функции системы . Аналогично обосновывается более общее утверждение.
Теорема 1. Если все функции функционально полной системы представимы формулами над системой , то система также функционально полна.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2025) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление