@mo в общем, смотри.

Помимо формализма булевых формул (обычно использующих операнды "^", "V", "!"), есть формализм булевых схем. Булева схема - это ациклический граф, с одной/несколькими вершинами на выходе, и одной/несколькими вершинами (переменными) на входе. Промежуточным вершинам соответствуют булевы функции (в общем случае более чем унарные/бинарные, и входы у них в общем случае упорядочены - самый простой пример импликация).

Задача построения булевой схемы интересна тем, что является одним из формализмов для описания интегральных схем, и решение её задач (оптимизация булевой схемы по тому или иному параметру) позволяет оптимизировать интегральные схемы для получения лучших характеристик. Например, глубина (максимальное расстояние от входа до выхода) косвенно соответствует быстродействию, а количество промежуточных вершин (элементов) - размер. Также булева схема позволяет реализовать сразу несколько функций на основе одной схемы (т.е. несколько выходов).