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

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

Если в некотором выражении булевой функции 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)  СПНФ булевой функции, если СДНФ данной булевой функции, имеет вид: .

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

.

Все переменные с отрицанием заменяем по формуле (2), затем раскрываем скобки и из полученного выражения удаляем попарно одинаковые слагаемые в соответствии с (1):

Ответ: G(F) 

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

Решение.

Если Вам понравилась эта лекция, то понравится и эта - Закономерности размещения населения.

.

Ответ: G(F) .