4.3 Логические формулы

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

Логическая формула:

1. Элементарные формулы: любая логическая переменная и символы «1» («истина») и «0» («ложь») – формулы.

2. Правило образования новых формул: если А и В – формулы, то Ā, (А  В), (А v В), (А  B) , (АВ) – формулы.

Других формул в алгебре логики нет.

В качестве примера рассмотрим высказывание «если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог». Это высказывание формализуется в виде (A v B)  C.

Такая же формула соответствует высказыванию «если Игорь знает английский или японский язык, то он получит место переводчика».

Как показывает анализ формулы (A v B)  C, при определённых сочетаниях значений переменных A, B и C она принимает значение «истина», а при некоторых других – «ложь». Такие формулы называются выполнимыми.

Некоторые формулы принимают значение «истина» при любых значениях входящих в них переменных. Таковой будет, например, формула А v Ā, соответствующая высказыванию «Этот треугольник прямоугольный или косоугольный».

Эта формула истинна, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными или тавтологиями.

Высказывания, которые формализуются тавтологиями, называются логически истинными.

Высказыванию «Катя самая высокая девочка в классе, и в классе есть девочки выше Кати» соответствует формула А  Ā. Очевидно, формула будет ложной, так как либо значение А, либо Ā обязательно ложно. Такие формулы называются тождественно ложными или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными.

Если две формулы А и В при одинаковых наборах значений, входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

Равносильность двух формул алгебры логики обозначается символом «=» или символом «». Замена формулы другой, равносильной ей, называется равносильным преобразованием данной формулы.

4.4 Упрощение логических формул

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

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

1. содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции либо меньшее число вхождений переменных;

2. не содержит отрицаний неэлементарных формул.

Основные законы алгебры логики приведены в таблице 12.

Таблица 12 – Основные законы алгебры логики

Закон	Для ИЛИ	Для И
Коммутативный (переместительный)
Ассоциативный (сочетательный)
Дистрибутивный (распределительный)
Правила де Моргана
Идемпотенции
Поглощения
Закон Порецкого
Склеивания
Операция переменной с ее инверсией
Операция с константами
Двойного отрицания

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

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

Пример 4.4.1 ,

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

Пример 4.4.2 ,

использовали правило де Моргана для дизъюнкции, вынесли за скобки общий множитель, использовали правило операций переменной с её инверсией.

Пример 4.4.3 ,

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

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

Пример 4.4.4 Для какого из указанных значений числа X истинно выражение

?

1. 1 2) 2 3) 4 4) 7

Решение: преобразуем выражение таким образом, чтобы левая часть каждого неравенства содержала только X. Получим:

.

Выполним инверсию:

Выполним конъюнкцию:

,

Она будет истинной только в том случае, когда оба неравенства примут значение «истина», т.е. при

Рассмотрим дизъюнкцию:

.

Дизъюнкция истинна только в том случае, когда истинно хотя бы одно из входящих в нее высказываний. Высказывание при данных вариантах ответа истинным быть не может. Следовательно, ищем такое значение X, при котором будет истинно первое высказывание . Такое значение 7. Правильный ответ – 4.

Пример 4.4.5 Чему равно наименьшее целое значение числа X, при котором истинно выражение

.

Преобразуем выражение, используя формулу (19):

.

Инверсией выражения будет .

Отсюда:

Для того чтобы дизъюнкция была истинной, должно быть истинным хотя бы одно из выражений.

Первое неравенство будет истинным при Второе при . Ответ: –16.

Пример 4.4.6 Какое из перечисленных выражений является тождественно-ложным:

1) 2)

3) 4)

Решение. Упростим логические выражения:

1) – формула не является тождественно-ложной;

2) – формула не является тождественно ложной;

3) – формула не является тождественно-ложной;

4) – формула является тождественно-ложной.

Ответ: 4.

Пример 4.4.7 Какое из приведенных имен удовлетворяет логическому условию

1) Ирина 2) Олег 3) Степан 4) Илона

Решение: введем условные обозначения. Пусть

А – первая буква гласная;

B – последняя буква гласная;

С – вторая буква согласная.

Тогда

Это значит, что значения логических переменных А и С должно быть истинно, а значение В – ложно.

Проверяем ответы:

1. Ирина.

Первая буква гласная – 1;

Последняя буква гласная – 1;

Вторая буква согласная – 1.

Следовательно: Ответ неверный.

2. Олег.

Первая буква гласная – 1;

Последняя буква согласная – 0;

Вторая буква согласная – 1.

Следовательно: Ответ верный.

Таким образом ответ 2 (Олег).