Геометрическое представление логических функций

Обозначим через Еⁿ множество всех наборов (α₁,..., α_η), состоящих из чисел ноль и единица. Множество Еⁿ называется n -мерным кубом, а набор (α₁, ..., α_η) - вершинами куба.

Пусть σ₁, ..., σ_r- фиксированный набор чисел из 0 и 1. Множество всех вершин (α₁,..., α_η) куба Еⁿ таких, что α_i1 = σ₁, α_i2 = σ₂, ... , α_ir = σ_r, 1 < i₁ < i₂ < ...< i_r, называется (n – r)- мерной гранью. Очевидно, что (n – r)-мерная грань является (n – r) - подкубом куба Еⁿ.

Например, в трехмерном кубе Е³ наборы (0,0,1) и (0,0,0) образуют одномерную ( n = 3, r = 2) грань (ребро), а наборы (1,0,0), (1,0,1), (1,1,0), (1,1,1) - двухмерную грань.

Пусть f(X₁,X₂,…,X_n) - произвольная булева функция. Ей сопоставляется в соответствие подмножество Ν_f вершин куба Еⁿ, таких что (α₁, ..., α_η)  N_f тогда и только тогда, когда f(α₁, ..., α_η) = l Очевидно, что по подмножеству N_f исходная функция f(X₁, X₂., ... , Χ_n) восстанавливается однозначно. Таким образом геометрический способ задания булевой функции заключается в задании множества вершин n -мерного куба Еⁿ, в которых данная функция истинна.

Пример 8. Пусть функция f(X₁, X₂, Х₃) задана табл. 4. Составить для нее множество N_f.

Таблица 4

Решение. Очевидно, что N_f = {(0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}. Множество N_f  изображено на рис. 3.

Напомним [1], что для любой булевой функции существует ее представление в СДНФ. Причём в алгоритме построения СДНФ используется только те наборы значений, при которых функция равна единице [3]. Это позволяет проинтерпретировать геометрическое представление функции следующим образом. Рассмотрим трёхмерный куб и занумеруем вершины так, как показано на рис. 4.

Тогда его грани (двумерные подкубы) можно рассматривать как

Ребрами данного куба ( одномерными подкубами) будут, например, , и т.д.

Пример 9. Построитьмодель куба, соответствующего функции:

.

Решение. Первому слагаемому соответствует вершина 2, второму – вершина 6, третьему – вершина 3, четвертому – вершина 8, пятому – вершина 4 (рис. 5).

Пример 10. Дана модель куба с помеченными вершинами (рис. 6). Составить СДНФ для данной булевой функции

Решение. Вершине 1 соответствует конъюнкция , вершинам 3 и 4 конъюнкция  и  соответственно; вершинам 5 и 6 - конъюнкции  и . Следовательно, искомая СДНФ имеет вид

    .

Заметим, что для функций, зависящих от четырёх и более переменных, геометрическое представление применяется очень редко, т.к. трудно построить наглядную модель n-мерного куба при n > 3. Поэтому в этом и следующих параграфах мы будем рассматривать только булевы функции трех аргументов, хотя все изложенное справедливо для других функций, зависящих от большого числа аргументов.

Перейдем теперь к геометрической постановке задачи минимизации булевых функций.