Эквиваленция (логическое тождество)

Операция, выражаемая связками "тогда и только тогда, когда", "необходимо и достаточно", "... равносильно...", называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или ~.

Высказывание A↔B истинно тогда и только тогда, когда значения А и В совпадают. Например, высказывания:

 

"24 делится на 6 тогда и только тогда, когда 24 делится на 3",

" 23 делится на 6 тогда и только тогда, когда 23 делится на 3" истинны,

 

а высказывания

"24 делится на 6 тогда и только тогда, когда 24 делится на 5",

"21 делится на 6 тогда и только тогда, когда 21 делится на 3" ложны.

 

Высказывания А и В, образующие составное высказывание A↔B, могут быть совершенно не связаны по содержанию, например:

 

" три больше двух" (А), "пингвины живут в Антарктиде" (В).

 

Отрицаниями этих высказываний являются высказывания

"три не больше двух" (­­­A),

"пингвины не живут в Антарктиде" (B).

 

Образованные из высказываний А и В составные высказывания A↔B и A↔B истинны, а высказывания A↔ B и A↔B — ложны.

 

ТАБЛИЦЫ ИСТИННОСТИ

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

 

При построении таких таблиц целесообразно пользоваться определенной последовательностью действий:

1. Определить количество строк таблицы по формуле:

Количество строк = 2ⁿ, где n – число логических переменных.

2. Количество столбцов = n + число логических операций.

3. Первые n столбцов нумеруем, начиная с нуля.

4. Заполняем столбец №0 нулями и единицами, чередуя их через 1 знак (номер столбца = 0, 2⁰ = 1);

Столбец №1, 2¹ = 2, чередуем через два знака;

Столбец №2, 2² = 4, чередуем через четыре знака и т.д.

5. Заполняем остальные столбцы таблицы истинности, в соответствии с определенным порядком очереди выполнения логических операций:

1. Инверсия
2. Конъюнкция
3. Дизъюнкция
4. Импликация
5. Эквивалентность
6. Для изменения указанного порядка выполнения операций используются скобки.

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

§ 8. ЛОГИЧЕСКИЕ ФОМУЛЫ. ЗАКОНЫ ЛОГИКИ

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

В качестве примера рассмотрим высказывание

"Если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог"

"Если Игорь знает английский или японский язык, то он получит место переводчика".

Оба эти высказывания формализуются в виде (A v B) C.

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

Некоторые формулы принимают значение "истина" при любых значениях истинности входящих в них переменных. Таковой будет, например, формула А v A, соответствующая высказыванию

"Этот треугольник прямоугольный или косоугольный".

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

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

В качестве другого примера рассмотрим формулу А &A, которой соответствует, например, высказывание

"Катя самая высокая девочка в классе, и в классе есть девочки выше Кати".

Очевидно, что эта формула ложна, так как либо А, либо A, обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями.

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

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

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

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

Перечислим наиболее важные из них:

Поясним некоторые из них:

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия (непротиворечия) говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием.
“Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание.
“ Неверно, что 2 2 4”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

XÙ Xº X,

XÚ Xº C

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана

(Август де Морган (1806-1871) - шотландский математик и логик) выразил эти законы в кратких словесных формулировках:

- отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

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

Доказать законы логики можно:

1) с помощью таблиц истинности;
2) с помощью равносильностей.

Докажем законы склеивания и поглощения с помощью равносильностей:

Закон склеивания:

(C Ú U) Ù ( Ú U) º

º (C + U) × ( + U) º C × + U × + U × U + C × U º

º U × + U + C × U º U × + U (1 + C) º U × + U º

º U ( + 1) º U

Закон поглощения:

C Ù (C Ú U) º C × C +C × U º C +C × U º C (1 + U) º C

 

Законы логики отражают в сознании человека свойства, связи и отношения окружающих объектов.

 

ТОЖДЕСТВЕННЫЕ ПРЕОБРАЗОВАНИЯ

Упрощение формул.

Пример 1. Упростить формулу (А+В)· (А+С)
Решение. а) Раскроем скобки
(A + B) · (A + C) º A · A + A · C + B · A + B · C
б) По закону идемпотентности,
A · A + A · C + B · A + B · C º A + A · C + B · A + B · C
в) В высказываниях А и А· C вынесем за скобки А и используя свойство А+1º 1, получим
А+А· С+ B · A + B · C º A ·(1 + С) + B · A + B · Сº A + B · A + B· С
г) Аналогично пункту в) вынесем за скобки высказывание А.
A + B · A + B · С º A (1 + B) + B · С º A + B · С
Таким образом, мы доказали закон дистрибутивности.

2. Преобразования “поглощение” и “склеивание”

Пример 2. А) Упростить выражение А+ A · B
Решение. A + A · B º A (1 + B) º A - поглощение

В) Упростить выражение A · B + A ·
Решение. A · B + A · º A (B + ) º A - склеивание