ОПРЕДЕЛЕНИЕ. Конъюнкцией ранга r называется всякая формула K, имеющая вид:

Конъюнкцией ранга r называется всякая формула K, имеющая вид: .

Булевскую функцию, представляемую конъюнкцией некоторого ранга, будем также называть конъюнкцией этого ранга, или просто конъюнкцией.

Очевидно, что K = принимает значение 1на единственном наборе значений своих переменных, для которого выполнены условия: . Поэтому для всякого конкретного набора значений переменных x₁, . . . , x_n однозначно определяется конъюнкция ранга n, принимающая значение 1 только на этом наборе. Например, для набора
(0,0,1,0,1) значений переменных x₁, . . ., x₅ соответствующая конъюнкция имеет вид

. (1)

Тогда, если булевская функция f(x₁, . . . , x_n) принимает значение 1 лишь на двух наборах значений переменных
(s₁, . . . , s_n) и (d₁, . . . , d_n), то справедливо равенство:
f (x₁, . . . , x_n) =

Ú . (2)

Подобным образом можно выписать формулу, представляющую произвольную булевскую функции f, если заданы все наборы, на которых она равна 1.

Приведенные два примера (1) и (2) представлений булевских функций формулами являются частными случаями следующей общей теоремы.

Дата добавления: 2014-11-15; просмотров: 224; Нарушение авторских прав

Мы поможем в написании ваших работ!