ИСТИНА

Рассматривается задача реализации булевых функций с помощью информационных графов. В работе делается акцент на базовое множество, состоящее только из монотонных функций, в простейшем случае — множество всех переменных. Приведены основные оценки сложности реализации, такие как оценка функции Шеннона сложности реализации монотонных булевых функции в классе информационных графов и информационных деревьев с монотонным базовым множеством. Также для почти всех монотонных булевых функций получен порядок сложности реализации их информационными деревьями с монотонным базовым множеством.