Some properties of weakly positive (anti-Horn) and weakly-negative (Horn) Boolean functions are investigated. Particularly, estimates are given for the complexity of constructing reduced form and for the possible lengths of expressions of considered functions, and it is shown that there are no limits for the weight of such functions.
Download file
Counter downloads: 123
- Title About some properties of Horn and anti-Horn functions
- Headline About some properties of Horn and anti-Horn functions
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(20)
- Date:
- DOI
Keywords
computing complexity, weakly negative (Horn) Boolean function, weakly positive (anti-Horn) Boolean function, вычислительная сложность, слабо отрицательная (хорновская) булева функция, слабо положительная (антихорновская) булева функцияAuthors
References
Горшков С. П. О пересечении классов мультиаффинных, биюнктивных, слабо положительных и слабо отрицательных булевых функций // Обозрение прикладной промышленной математики. Сер. дискретной математики. 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.
About some properties of Horn and anti-Horn functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 2(20).
Download full-text version
Download fileCounter downloads: 192