7. О минимизации R-функций

В гл. 2,5 было показано, что система функций

является полной по отношению к классу -функций. Это означает, что с помощью функций (2.89) и правил построения сложных функций может быть построена по крайней мере одна -функция, соответствующая любой наперед заданной булевой функции.

Пусть есть произвольная булева функция. Приведем эту функцию к дизъюнктивной нормальной форме. Затем произведем формальную замену знаков конъюнкции, дизъюнкции и отрицания знаками -конъюнкции, -дизъюнкции и -отрицания, а булевых переменных непрерывными переменными соответственно. Получим -функцию соответствующую булевой функции Если затем воспользоваться формулами (2.65) и (2.66), положив для простоты получим формулу, не содержащую других операций, кроме сложения, умножения и извлечения квадратного корня.

Так как каждая булева функция имеет бесчисленное множество эквивалентных ей различных дизъюнктивных нормальных форм, то имеется также бесчисленное множество -реализуемых -функций, соответствующих данной булевой операции. Поэтому может быть поставлена следующая задача.

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

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

Пусть есть некоторая -реализуемая -функция. Формула упрощается следующим образом.

Во-первых, можно производить тождественные преобразования, не выводящие формулу за пределы реализуемых функций.

Во-вторых, если функция может быть представлена в виде

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

Пример 1. -функция соответствующая отрицанию равнозначности определяется формулой

С помощью тождественных преобразований эта формула может быть приведена к виду

Опуская положительный множитель, получим