7.2. Равносильные преобразования. Упрощение формул алгебры переключательных функций

Равносильные преобразования – это замена одной формулы другой, равносильной формулой. Если в равносильные формулы всюду вместо какой-нибудь переменной подставить одну и ту же формулу, то вновь полученные формулы также окажутся равносильными.

Под упрощением формулы будем понимать равносильные преобразования, приводящие к формуле, содержащей меньшее число переменных, чем исходная. Такие преобразования формул логики необходимы при синтезе, анализе, контроле дискретных устройств, а в последнее время – в системах искусственного интеллекта (логического вывода).

Мощным аппаратом для таких равносильных преобразований помимо рассмотренных законов алгебры логики являются так называемые основные формулы равносильных преобразований, полученные с использованием этих законов [34].

Пусть – некоторая переменная, причем символ ~ означает, что неважно, инверсная они или нет, т.е.; тогда.

Пусть – некоторая функция, зависящая как от переменной х и ее инверсии, так и от других переменных. Под одноименностью будем понимать и соответствие знаков инверсии (т.е. одновременное наличие или отсутствие). Тогда, если переменнаянаходится в конъюнкции с некоторой функцией, зависящей от данной переменной и от других переменных, то в этой функции все одноименныепеременные заменяются на константу 1, а все переменные, инверсные одноименной, – на константу 0. Сама же переменная перед функцией остается без изменения. Таким образом:

Такая запись означает, что:

Условно замену переменных на константу в функции f обозначаем стрелками.

Примеры.

Для облегчения запоминания рекомендуется мнемоническое правило [34]. Представим формулу равносильного преобразования относительно конъюнкции из вида переключательной схемы, в которой конъюнкции и функцииf соответствует их последовательное соединение. Такое соединение напоминает символ 1 (рис. 39). Для простоты на рис. 1 не указаны переменные функции f. Это значит, что одноименные переменные вf заменяются на константу 1. Соответственно переменные вf заменяются на константу 0.

Рис. 39. Иллюстрация мнемонического правила для формулы равносильных преобразований относительно конъюнкции

Рассмотрим формулу равносильных преобразований относительно дизъюнкции. Если переменная находится в дизъюнкции с функцией, зависящей от данной переменной и от других переменных, то в этой функции все одноименныепеременные заменяются на константу 0, а все переменные, инверсные одноименной, заменяются на константу 1. Сама же переменная остается без изменения:

Это означает, что:

Примеры.

f(аbс)=

В этой функции в явном виде нет отдельной переменной (), однако нетрудно заметить, что. Поэтому обозначим аb, например, х:

Отсюда:

Имеется соответствующее мнемоническое правило. Представим формулу равносильного преобразования относительно дизъюнкции в виде переключательной схемы, в которой дизъюнкции и функцииf соответствует их параллельное соединение. Такое соединение напоминает символ 0 (рис. 40). Это значит, что одноименные переменные вf заменяются на константу 0. Соответственно переменные вf заменяются на константу 1.

Рис. 40. Иллюстрация мнемонического правила для формулы равносильных преобразований относительно дизъюнкции

Основные формулы равносильных преобразований можно доказать методом подстановки в них вместо переменной х ее возможных значений 0, 1 и сравнения правой и левой частей уравнения.

Докажем, например, формулу:

Пусть х=0; тогда левая часть формулы:

а правая:

т.е. равенство справедливо.

Пусть х=1; тогда левая часть формулы

а правая часть формулы

Равенство также справедливо, несмотря на отличия в функции f.

Аналогично доказывается формула для конъюнкции, например:

При х=0:

равенство справедливо, несмотря на отличия в функции f.

При х=1:

равенство также справедливо.

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

Следствие 1.

Следствие может быть доказано путем конъюнкции функции с тождественно истинной формулой и последующего применения формул равносильного преобразования:

.

Это известное разложение Шеннона.

Пример 1. Разложить логическую функцию по переменной b:

f(аbсd)=а(b)с[аd(b)]=

=b{а0(1)с[а0d(1)]} {а1(0)с[а1d(0)]}=

Следствие 2.

.

Доказательство:

f=f0=fх=(fх)(f)=.

Пример 2. Разложим ту же функцию f(авсd) (пример 1) по переменной а с помощью следствия 2:

f(аbсd)={а0(1b)с[0d(1b)]}{1(0b)с[1d(0b)]}=