О существовании минимальной, но не кратчайшей ортогональной дизъюнктивной нормальной формы

Рассматриваются представления булевых функций в виде дизъюнктивных нормальных форм (ДНФ), элементарные конъюнкции у которых попарно ортогональны. Для таких ДНФ, названных ортогональными (ОДНФ), вводятся понятия минимальной (МОДНФ), содержащей минимальное число букв в записи, и кратчайшей (КОДНФ), состоящей из наименьшего числа элементарных конъюнкций. В ряде работ (см. [7, 8]) была выдвинута гипотеза о том, что любая МОДНФ является и КОДНФ. В данной статье эта гипотеза опровергается путем построения контрпримера функции 12 переменных и проведения соответствующего доказательства.