Основные равносильности алгебры высказываний

Формулы и законы логики

 

На вводном уроке, посвящённом основам математической логики, мы познакомились с базовыми понятиями этого раздела математики, и сейчас тема получает закономерное продолжение. Помимо нового теоретического, а точнее даже не теоретического – а общеобразовательного материала нас ожидают практические задания, и поэтому если вы зашли на данную страницу с поисковика и/или плохо ориентируетесь в материале, то, пожалуйста, пройдите по вышеуказанной ссылке и начните с предыдущей статьи. Кроме того, для практики нам потребуется 5 таблиц истинности логических операций, которые я настоятельно рекомендую переписать от руки.

НЕ запомнить, НЕ распечатать, а именно ещё раз осмыслить и собственноручно переписать на бумагу – чтобы они были перед глазами:

– таблица НЕ;
– таблица И;
– таблица ИЛИ;
– импликационная таблица;
– таблица эквиваленции.

Это очень важно. В принципе, их было бы удобно занумеровать «Таблица 1», «Таблица 2» и т.д., но я неоднократно подчёркивал изъян такого подхода – как говорится, в одном источнике таблица окажется первой, а в другом – сто первой. Поэтому будем использовать «натуральные» названия. Продолжаем:

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

1) любые элементарные (простые) высказывания ;

2) если и – формулы, то формулами также являются выражения вида
.

Никаких других формул нет.

В частности формулой является любая логическая операция, например логическое умножение . Обратите внимание на второй пункт – он позволяет рекурсивным образом «создать» сколь угодно длинную формулу. Поскольку – формулы, то – тоже формула; так как и – формулы, то – тоже формула и т.д. Любое элементарное высказывание (опять же согласно определению) может входить в формулу неоднократно.

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

Логическую формулу можно рассматривать, как логическую функцию. Запишем в функциональном виде ту же конъюнкцию:

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

Таблица, описывающая логическую формулу (функцию) называется, как уже было озвучено, таблицей истинности. Пожалуйста – знакомая картинка:

Принцип формирования таблицы истинности таков: «на входе» нужно перечислить все возможные комбинации истины и лжи, которые могут принимать элементарные высказывания (аргументы). В данном случае в формулу входят два высказывания, и нетрудно выяснить, что таких комбинаций четыре. «На выходе» же получаем соответствующие логические значения всей формулы (функции).

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

– в первую очередь выполняется отрицание ;
– во вторую очередь – конъюнкция ;
– затем – дизъюнкция ;
– потом импликация ;
– и, наконец, низший приоритет имеет эквиваленция .

Так, например, запись подразумевает, что сначала нужно осуществить логическое умножение , а затем – логическое сложение: . Прямо как в «обычной» алгебре – «сначала умножаем, а затем складываем».

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

Наверное, все понимают, но на всякий пожарный: и – это две разные формулы! (как в формальном, так и в содержательном плане)

Составим таблицу истинности для формулы . В данную формулу входят два элементарных высказывания и «на входе» нам нужно перечислить все возможные комбинации единиц и нулей. Чтобы избежать путаницы и разночтений договоримся перечислять комбинации строго в таком порядке (который я, собственно, де-факто использую с самого начала):

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

На втором шаге смотрим на столбцы и и применяем к ним операцию ИЛИ. Немного забегая вперёд, скажу, что дизъюнкция перестановочна ( и – это одно и то же), и поэтому столбцы можно анализировать в привычном порядке – слева направо. При выполнении логического сложения удобно использовать следующее прикладное рассуждение: «Если два нуля – ставим ноль, если хотя бы одна единица – единицу»:

Таблица истинности построена. А теперь вспомним старую-добрую импликацию:

…внимательно-внимательно… смотрим на итоговые колонки…. В алгебре высказываний такие формулы называются равносильными или тождественными:

(три горизонтальные чёрточки – это значок тождества)

В 1-й части урока я обещал выразить импликацию через базовые логические операции, и выполнение обещания не заставило себя ждать! Желающие могут вложить в импликацию содержательный смысл (например, «Если идёт дождь, то на улице сыро») и самостоятельно проанализировать равносильное утверждение .

Сформулируем общее определение: две формулы называются равносильными (тождественными), если они принимают одинаковые значения при любом наборе значений, входящих в эти формулы переменных (элементарных высказываний). Также говорят, что «формулы равносильны, если совпадают их таблицы истинности», но мне не очень нравится эта фраза.

Задание 1

Составить таблицу истинности для формулы и убедиться в справедливости знакомого вам тождества .

Ещё раз повторим порядок решения задачи:

1) Так как в формулу входят две переменные, то всего будет 4 возможных набора нулей и единиц. Записываем их в оговорённом выше порядке.

2) Импликации «слабее» конъюнкции, но они располагаются в скобках. Заполняем столбец , при этом удобно использовать следующее прикладное рассуждение: «если из единицы следует ноль, то ставим ноль, во всех других случаях – единицу». Далее заполняем столбец для импликации , и при этом, внимание! – столбцы и следует анализировать «справа налево»!

3) И на завершающем этапе заполняем итоговый столбец . А здесь удобно рассуждать так: «если в столбцах и две единицы, то ставим единицу, во всех остальных случаях – ноль».

И, наконец, сверяемся с таблицей истинности эквиваленции .

 

Основные равносильности алгебры высказываний

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