ИСТИНА

Правильным семейством булевых функций называется упорядоченный набор булевых функций(𝑓1,...,𝑓𝑛) от переменных 𝑥1,...,𝑥𝑛,такой что для любых двух различных двоичных наборов 𝛼= (𝛼1,...,𝛼𝑛), 𝛽= (𝛽1,...,𝛽𝑛) найдется индекс 𝑖 со свойством 𝛼𝑖̸ != 𝛽𝑖, но 𝑓𝑖(𝛼) = 𝑓𝑖(𝛽). Правильные семейства изучались применительно к построению параметрических семейств латинских квадратов для синтеза поточных шифров. Ориентация рёбер булева куба B называется ориентацией с единственным стоком (unique sink orientation), если каждый подкуб в B имеет единственный сток. С помощью семейства булевых функций (𝑓1,...,𝑓𝑛) можно определенным образом задавать ориентации на рёбрах булева куба.Оказывается, что при таком отображении правильным семействам(𝑓1,...,𝑓𝑛)взаимно-однозначно соответствуют реберные ориентации кубов с единственным стоком. Данное свойство связано с неподвижными точками отображения (𝑥1,...,𝑥𝑛)→(𝑓1(𝑥),...,𝑓𝑛(𝑥)) и позволяет получить дополнительные свойства для правильных семейств, в частности получить оценки на число правильных семейств длины 𝑛≥5 и показать, что задача распознавания правильности семейства является coNP-полной.