Теория: Эквивалентность

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

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

Логическая эквивалентность

Возьмем для примера такое предложение:

Если Вася получит прибавку к зарплате, то он пойдет в театр

С точки зрения логики в этом высказывании есть и такой смысл:

Если Вася не пошел в театр, значит он не получил прибавку к зарплате

Эти высказывания логически эквивалентны — одно можно заменить на другое без потери смысла. В этом и заключается логическая эквивалентность — два выражения считаются эквивалентными, если они имеют одинаковое истинностное значение во всех случаях.

Как эквивалентность помогает доказывать

Основная польза эквивалентности в том, что она помогает доказывать математические результаты. Допустим, мы знаем, что 2+3=5. Попробуем это доказать.

Можно заменить выражение 2+3 на другое эквивалентное выражение 3+2, которое также будет равно 5.

Как видите, значение составной пропозиции не изменилось. Значит, эквивалентность помогла нам доказать первоначальное высказывание — 2+3=5.

Как эквивалентность помогает рассуждать

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

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

В логической функции есть три основные операции:

• НЕ (Инверсия или отрицание, обозначается как ¬)
• ИЛИ (Дизъюнкция или сложение, обозначается как ∨)
• И (Конъюнкция или умножение, обозначается как ∧)

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

Таблица истинности выглядит так:

Рассмотрим ее подробнее:

• Тавтология (T) — высказывание, которое всегда истинно независимо от того, истинны ли значения переменных внутри него. По таблице вся колонка истинна
• Противоречие или абсурд (F) — высказывание, которое всегда ложно
• Случайность — составное предложение, которое не является ни тавтологией, ни противоречием.

Тавтологии и противоречия помогают доказывать и проверять математические аргументы, а также объяснить пропозициональные эквивалентности — утверждения, которые равны в логическом аргументе. В этом случае самый простой способ — создать таблицу истинности и посмотреть, идентичны ли столбцы.

По такой таблице мы можем проверить, эквивалентны ли высказывания a и b.

Иногда в математике полезно заменить одно утверждение другим, но эквивалентным. Возьмем такой пример:

Если `n` четное, то `n/2` — это целое число

Эквивалентное утверждение звучит так:

Если `n/2` не целое число, то `n` — это нечетное число

Первое высказывание имело вид «Если A, то B», а второе — «Если не B, то не A». Это эквивалентные высказывания, о которых мы подробнее поговорим ниже.

Законы логической эквивалентности (Законы Моргана)

Ниже приведен список важных законов эквивалентности — также их называют законами алгебры высказываний. На протяжение всего курса мы будем использовать такие законы:

Применим некоторые из этих законов на практике.

Возьмем для примера составное предложение:

Я обедаю в ресторане и иду на танцы

Используем законы де Моргана — они связывают с помощью отрицания конъюнкцию и дизъюн­кцию. Можно выразить отрицание так:

Я не буду есть в ресторане или не пойду танцевать

Обратите внимание, что мы отрицаем оба простых предложения и заменили «и» на «или».

В качестве еще одного примера рассмотрим следующее утверждение:

Неверно, что Глеб — доктор, а Вася — инженер

Это переводится на математический язык как:

¬(доктор ∧ инженер)

Пусть:

• доктор — означает "Глеб — доктор"
• инженер — означает "Вася — инженер"

Эквивалентная форма по закону де Моргана:

¬(доктор ∧ инженер) ≡ ¬доктор ∨ ¬инженер

Следовательно, мы можем сказать, что: Либо Глеб — не доктор, либо Вася — не инженер (или оба сразу).

Приведенные выше примеры можно легко решить с помощью таблицы истинности. Но это можно сделать только для предложения с небольшим числом переменных — здесь их всего две.

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

Но если переменных будет больше 1000, вычисление на компьютере будет очень долгим.

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

• Высказывание: Если n четное, то n/2 — целое число
• И его эквивалент: Если n/2 не целое число, то n не четное
• При этом преобразование справедливо для любого n

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