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

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

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

Мощным аппаратом для таких равносильных преобразований помимо рассмотренных законов алгебры логики являются так называемые основные формулы равносильных преобразований, полученные с использованием этих законов [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)]}=