Функция Шеннона

Пусть задана булева функция f и соответствующее множество схемных реализаций Для того, чтобы подобрать лучшую реализацию с точки зрения простоты, нужно ввести индекс сложности схемы S. При решении задачи синтеза мы должны выбрать такую схему на которой достигается Решение этой задачи даже для достаточно простых реализаций связано с большими трудностями. Существует несколько ослабленных постановок этой задачи. Постановка Шеннона заключается в том, что каждой булевой функции ставится в соответствие множество схем Выберем среди всех схем с , т.е. среди самых простых схем, такую схему, которая обладала бы наибольшим индексом простоты Функция называется функцией Шеннона. Если, например, – это количество элементов, затраченных на реализацию схемы то – минимальное количество элементов, на которых можно построить любую булеву функцию от n переменных. Для синтеза схем с помощью функции Шеннона необходимо: а) построить эту схему для заданного класса схем, б) уметь строить схему, сложность которой не превышала бы