Как упростить логическую формулу?

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1)
(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);

2)
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

3)
(повторяетсявторойсомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);

4)
(вводится вспомогательный логический сомножитель ( ); затем комбинируются два крайних и два средних логических слагаемых и используется закон поглощения);

5)
(сначаладобиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);

6)
(выносятся за скобки общие множители; применяется правило операций с константами);

7)
(к отрицаниям неэлементарных формул применяется правило де Моргана; используются законы двойного отрицания и склеивания);

8)
(общий множитель x выносится за скобки, комбинируются слагаемые в скобках — первое с третьим и второе с четвертым, к дизъюнкции применяется правило операции переменной с её инверсией);

9)
(используются распределительный закон для дизъюнкции, правило операции переменной с ее инверсией, правило операций с константами, переместительный закон и распределительный закон для конъюнкции);

10)
(используются правило де Моргана, закон двойного отрицания и закон поглощения).

Из этих примеров видно, что при упрощении логических формул не всегда очевидно, какой из законов алгебры логики следует применить на том или ином шаге. Навыки приходят с опытом.

Задача нахождения среди равносильных схем наиболее простых является очень важной. Большой вклад в ее решение внесли российские учёные Ю.И. Журавлев, С.В. Яблонский и др.

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работысводится к следующим трём этапам:

1. составлению функции проводимости по таблице истинности, отражающей эти условия;
2. упрощению этой функции;
3. построению соответствующей схемы.

АНАЛИЗ СХЕМЫ сводится к

1. определению значений её функции проводимости при всех возможных наборах входящих в эту функцию переменных.
2. получению упрощённой формулы.

Примеры.

1. Построим схему, содержащую 4 переключателя x, y, z и t, такую, чтобы она проводила ток тогда и только тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных трёх контактов.

Решение. В этом случае можно обойтись без построения таблицы истинности. Очевидно, что функция проводимости имеет вид F(x, y, z, t) = t × (x v y v z), а схема выглядит так:

2. Построим схему с пятью переключателями, которая проводит ток в том и только в том случае, когда замкнуты ровно четыре из этих переключателей.

Схема имеет вид:

3. Найдем функцию проводимости схемы:

Решение. Имеется четыре возможных пути прохождения тока при замкнутых переключателях a, b, c, d, e : через переключатели a, b; через переключатели a, e, d; через переключатели c, d и через переключатели c, e, b. Функция проводимости F(a, b, c, d, e) = a×b v a× e×d v c×d v c×e×b.

4. Упростим переключательные схемы:

а)

Решение:

Упрощенная схема:

б)

.

Здесь первое логическое слагаемое является отрицанием второго логического слагаемого , а дизъюнкция переменной с ее инверсией равна 1.

Упрощенная схема :

в)

Упрощенная схема:

г)

Упрощенная схема:

д)

(по закону склеивания)

Упрощенная схема:

е)

Решение:

Упрощенная схема: