Исследуются некоторые свойства слабо положительных (антихорновских) и слабо отрицательных (хорновских) булевых функций. В частности, оценивается сложность задачи построения приведённых представлений этих функций, показывается, что нет ограничений на вес таких функций, оценивается возможная длина записи рассматриваемых функций.
Скачать электронную версию публикации
Загружен, раз: 121
- Title О некоторых свойствах слабо положительных и слабо отрицательных булевых функций
- Headline О некоторых свойствах слабо положительных и слабо отрицательных булевых функций
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(20)
- Date:
- DOI
Ключевые слова
computing complexity, weakly negative (Horn) Boolean function, weakly positive (anti-Horn) Boolean function, вычислительная сложность, слабо отрицательная (хорновская) булева функция, слабо положительная (антихорновская) булева функцияАвторы
Ссылки
Горшков С. П. О пересечении классов мультиаффинных, биюнктивных, слабо положительных и слабо отрицательных булевых функций // Обозрение прикладной промышленной математики. Сер. дискретной математики. 1997. Т. 4. Вып. 2. С. 238-259.
Тарасов А. В. О свойствах функций, представимых в виде 2-КНФ // Дискретная математика. 2001. Т. 13. Вып. 4. С. 99-115.
Schaefer T. Complexity of satisfiability problems // Proc. 10 Annual ACM Symposium on Theory of Computing Machinery. New York, NY, USA: ACM, 1978. P. 216-226.
Горшков С. П., Тарасов А. В. О максимальных группах инвариантных преобразований мультиаффинных, биюнктивных, слабо положительных и слабо отрицательных булевых функций // Дискретная математика. 2009. Т. 21. Вып. 2. С. 94-101.
Горшков С. П. Применение теории NP-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикладной промышленной математики. Сер. дискретной математики. 1995. Т. 2. Вып.3. С. 325-398.
Горшков С. П. О сложности распознавания мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности булевых функций // Обозрение прикладной промышленной математики. Сер. дискретной математики. 1997. Т. 4. Вып. 2. С. 440-467.
Коршунов А. Д. О числе монотонных булевых функций. Проблемы кибернетики. Вып. 38. М.: Наука, 1981. С. 5-108.
Гретцер Г. Общая теория решёток. М.: Мир, 1982. 456 с.
Алексеев В. Б. О числе семейств подмножеств, замкнутых относительно пересечения // Дискретная математика. 1989. Т. 1. Вып. 2. С. 129-136.
Гизунов С. А., Носов В. А. О классификации всех булевых функций четырёх переменных по классам Шеффера // Обозрение прикладной промышленной математики. Сер. дискретной математики. 1995. Т. 2. Вып.3. С. 440-467.
Горшков С. П. О сложности нахождения приведённых представлений слабо положительных и слабо отрицательных булевых функций // Прикладная дискретная математика. 2008. Т. 1. Вып. 1. С. 7-9.
О некоторых свойствах слабо положительных и слабо отрицательных булевых функций | Прикладная дискретная математика. 2013. № 2(20).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 190