Арифметическое разложение булевых функций

Если в некотором выражении булевой функции F заменить логические операции арифметическими на множестве вещественных чисел {0, 1} по следующим правилам:

, (7)

, (8)

, (9)

, если , (10)

, (11)

, если , (12)

, (13)

, (14)

, (15)

то полученное в результате такой замены, раскрытия скобок и приведения подобных, выражение называется арифметическим разложением (или арифметическим полиномом) булевой функции и обозначается черев G(F) .

Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) арифметический полином G(F) имеет вид:

Отметим некоторые свойства арифметического полинома G(F) булевой функции n переменных .

1. Полином G(F) является для функции F единственным.

2. Полином G(F) имеет степень n, если вектор w(F) содержит нечетное

число единиц.

3. Сумма коэффициентов полинома G(F) равна значению булевой функции

F на наборе переменных (1,1,…,1) в таблице истинности.

Некоторые из методов разложения булевых функций F в канонический полином Жегалкина после соответствующей модификации могут быть применимы для разложения F в полином G(F).

К таким методам относятся, в частности, рассмотренный выше метод преобразования СДНФ.

При использовании метода преобразования СДНФ необходимо в СДНФ функции F заменить логическую операцию «дизъюнкция» на операцию "арифметическое сложение", поскольку из (12) следует, что , если . Затем в полученном выражении необходимо избавиться от отрицания переменных по (7). После раскрытия скобок и приведения подобных получается искомый полином.

Пример. Составить арифметический полином G(F) СПНФ булевой функции, если СДНФ данной булевой функции, имеет вид: .

Решение. Заменим операцию дизъюнкции на операцию "арифметическое сложение" по формуле (10). При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю: