Булевы графы и функции

В статье изучаются вложимые в $n$-мерный единичный куб ($n$-куб) графы, названные булевыми. Изучение таких графов представляет прикладной интерес, в частности, в связи с поиском оптимальных реализаций булевых функций в базисах, например в ДНФ и в виде дизъюнкций пороговых функций.
Доказан критерий вложимости графа в $n$-куб, описаны некоторые классы таких графов. Показано, что прямое произведение булевых графов является булевым графом.
Введено понятие $t$-типного булевого графа, допускающего $t$ различных вложений в $n$-куб и порождающего неоднотипные булевы функции. Установлено существование $t$-типных графов для любого $t$, рассмотрены некоторые классы $t$-типных графов, в том числе при $t=1$ – монотипных. Доказано, что монотипными являются графы связности полностью монотонных булевых функций, а также прямые произведения монотипных графов.