Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Независимая система функций и базис функционально замкнутого класса



Система функций независима, если ни какая функция из системы не может быть выражена с помощью суперпозиций через остальные функции системы. Система { , } независима, так как T , T , L, L. Для определения независимости функций надо найти два класса из пяти такие (можно по таблице Поста), что одна функция принадлежит первому классу и не принадлежит второму, а вторая функция наоборот принадлежит второму классу и не принадлежит первому. Система { , , } зависима, смотри выше законы Моргана.

Независимая система функций называется базисом функционально замкнутого класса, если всякая функция из этого класса есть суперпозиция функций из этой системы. Системы функций {&, } и { , } – базисы класса всех булевых функций.

Система функций {~, 0} – базис класса L. Это независимая система функций, так как 0 принадлежит классу M, а ~ не принадлежит классу M, 0 не принадлежит классу T , а ~ принадлежит классу T . Каждая линейная функция выражается суперпозициями функций + и , поскольку x = x + 1. Но эти функции в свою очередь выражаются через 0 и ~: x = x ~ 0, x + y = (x ~ y).





Дата публикования: 2014-11-29; Прочитано: 825 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...