Информатика. Упрощение логических выражений

Введение

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

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

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

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

Упрощение логических выражений

Все законы алгебры логики выводятся для главных логических операций следующим образом:

• НЕ является инверсией, то есть, отрицанием.
• ИЛИ является дизъюнкцией, то есть, логическим сложением.
• И является конъюнкцией, то есть, логическим умножением.

Правило двойного отрицания заключается в том, что операция НЕ является обратимой, то есть, если ее применить два раза, логический итог в результате останется неизменным.

Смысл правила исключенного третьего заключается в том, что каждое логическое выражение при всех условиях может быть или истинным, или ложным. Если A=1, тогда A=0, а также наоборот. Конъюнкция данных величин всегда равняется 0, дизъюнкция равна 1.

Закон повторения и операции с константами может быть просто проверен путём применения таблицы истинности операций ИЛИ и И.

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

Для дизъюнкции распределительный закон заключается просто в раскрытии скобок. Для конъюнкции выражение неизвестно, в математике подобное равенство является неверным. Приведём доказательство, начиная с правой части. В начале следует раскрыть скобки:

(A + B) ⋅ (A + C) = A ⋅ A + A ⋅ C + B ⋅ A + B ⋅ C

Применим закон повторения, который гласит, что A ⋅ A = A. Далее:

A ⋅ A + C ⋅ A = A + C ⋅ A = A ⋅ (1 + C) = A ⋅ 1 = A

A + A ⋅ B =A⋅ (1 + B) = A ⋅ 1 = A, следовательно, (A + B) ⋅ (A + C) = A + B ⋅ C.

Таким образом, равенство доказано.

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

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

Введём следующие обозначения:

• X является логическим высказыванием.
• x̅ является инверсией.
• & является конъюнкцией.
• V является дизъюнкцией.
• → является импликацией.
• ↔ является логической эквивалентностью.

Рассмотрим конкретный пример. Необходимо упростить следующее логическое выражение:

X & Y V X & Y ̅& ZV Y ̅& X& Z ̅ V X & Z ̅

Запишем данное выражение при помощи наиболее привычных действий умножения и сложения:

XY + XY ̅ Z +Y ̅X Z ̅ + X Z ̅ =

Далее следует воспользоваться распределительным законом и вынести за скобки общий множитель, затем операцией переменной с ее инверсией:

XY + X Y ̅ (Z + Z ̅) + X Z ̅ = XY + X Y ̅ + X * Z ̅ =

Затем следует снова воспользоваться распределительным законом и вынести за скобки общий множитель, а далее операцией переменной с ее инверсией, затем операцией с константами:

X (Y + Y ̅ + Z ̅) = X (1+ Z ̅) = X* 1 = X

Подводя итог, можем сделать следующий вывод, что:

X & Y V X & Y ̅& ZV Y ̅& X& Z ̅ V X & Z ̅= X

Рассмотрим ещё один пример. Требуется определить, кто из рабочих, условно обозначаемых, как A, B, C, D работает на заводе, а кто не работает, если имеются следующие начальные условия:

• Когда работает A или работает B, то в этом случае не работает C.
• Когда не работает B, тогда работает D, а также работает C.

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

• A рабочий A работает на заводе.
• B рабочий B работает на заводе.
• C рабочий C работает на заводе.
• D рабочий D работает на заводе.

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

((A + B) → C) ⋅ (B → C ⋅ D) ⋅ C.

Если упростить данную формулу, то можно получить, что A равняется 0, B равняется 1, C равняется 1, D равняется 1. Следовательно, это означает, что рабочий A на заводе не работает, а работники B, C, D работают.

В данном примере использовано правило де Моргана, далее применён распределительный закон, после этого использован закон исключенного третьего, а затем использовался переместительный закон. За ним осуществлён закон повторения, потом снова использован переместительный закон и в конце использовался закон поглощения.