Преобразование логических выражений

Логическая информация и основы логики

Высказывание (суждение) – это повествовательное предложение, в котором что-либо утверждается или отрицается.

Логические величины – понятия, выражаемые словами: ИСТИНА, ЛОЖЬ (true, false).

Логическая константа: ИСТИНА или ЛОЖЬ.

Логическая переменная – символически обозначенная логическая величина.

Логические операции

Конъюнкция (логическое умножение). В русском языке она выражается союзом И. В математической логике используются знаки Ù, × или &. Конъюнкция – двуместная операция; записывается в виде А Ù В или А & В, или А × В.

Дизъюнкция (логическое сложение). В русском языке этой операции соответствует союз ИЛИ. В математической логике она обозначается знаком Ú или +. Дизъюнкция – двуместная операция; записывается в виде А Ú В или А + В.

Примечание. Выделяют еще строгую дизъюнкцию (исключающее ИЛИ). В русском языке ей соответствует союз ЛИБО. Она обозначается знаком Å. Эту операцию также называют сложением по модулю 2.

Отрицание. В русском языке этой операции соответствует частица НЕ. Отрицание – унарная (одноместная) операция; записывается в виде Ø А или А.

Импликация (условное высказывание). В русском языке этой логической операции соответствуют слова если …, то; когда …, тогда; коль скоро …, то и т.п. В логических формулах операция импликации обозначается знаком ®. Импликация – двуместная операция; записывается так: А ® В.

Эквивалентность (тождественность). Языковой аналог – если и только если; тогда и только тогда, когда … Эквивалентность обозначается знаком º или «. Эквивалентность – двуместная операция; записывается так: А «В или А º В.

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

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

Результаты каждой логической операции приведены в таблице истинности (табл. 3).

Таблица 3

Таблица истинности логических операций

А	В	А	А × В	А + В	А ® В	А «В	А Å В
и	и	л	и	и	и	и	л
и	л	л	л	и	л	л	и
л	и	и	л	и	и	л	и
л	л	и	л	л	и	и	л

Задача. Определить истинность логической формулы:

F =((C + B)® B) × (A × B) ® B.

Определим порядок выполнения действий с учетом приоритета логических операций (см. выше):

_{1 2 4 3 5}

F =((C + B)® B) × (A × B) ® B.

Для решения задачи составим таблицу истинности этой формулы, перебрав все варианты значений логических переменных А, В и С.

1 2 3 4 5

А	В	С	C + В	(С + В)® В	А × В	((С + В)® В) × (А × В)	F

Здесь числовые обозначения для логических величин: 1 – истина, 0 – ложь.

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

Преобразование логических выражений

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

Основные формулы преобразования логических выражений:

1. А º А.