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