Аннотация:
Исследуются некоторые свойства слабо положительных (антихорновских) и слабо отрицательных (хорновских) булевых функций. В частности, оценивается сложность задачи построения приведëнных представлений этих функций, показывается, что нет ограничений на вес таких функций, оценивается возможная длина записи рассматриваемых функций.
Ключевые слова:
слабо положительная (антихорновская) булева функция, слабо отрицательная (хорновская) булева функция, вычислительная сложность.
Полный текст:
PDF файл (578 kB)