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

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

Для того чтобы получить ответ на этот вопрос, рассмотрим два предиката Р (х) и Q (x). Пусть Р и Q — множества истинности этих предикатов соответственно.

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

Если мы изобразим с помощью диаграмм Эйлера — Венна множества истинности данных предикатов и их конъюнкции, то получим следующий результат (рис. 4.1).

Рис. 4.1. Множество истинности для конъюнкции.

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

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

Изобразим эти множества истинности с помощью диаграммы Эйлера — Венна (рис. 4.2).

Рис. 4.2. Множество истинности для дизъюнкции.

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

3. Отрицанием предиката является предикат (-> Р (х))_у зависящий от той же переменной, что и данный предикат, который обращается в истинное высказывание в том и только в том случае, когда данный предикат становится ложным высказыванием. В связи с этим множества истинности данного предиката (Р) и его отрицания (—Р) можно изобразить так (рис. 4.3).

Рис. 43. Множество истинности для отрицания.

Операция отрицания соответствует дополнению множества до универсального множества.

4. Следующая логическая операция — импликация. Импликацией предикатов Р (х) —> Q (x) является предикат, зависящий от той же переменной, что и данные, и превращающийся в ложное высказывание при тех и только тех значениях переменной, при которых первый предикат (Р (х)) обращается в истинное высказывание, а второй (Q (x)) — в ложное. В остальных случаях полученное высказывание является истинным. Другими словами, из истинности первого высказывания должна следовать истинность второго высказывания. Например, если есть любой ромб (Р)_у то он является параллелограммом (Q).

Если мы изобразим с помощью диаграмм Эйлера — Венна множества истинности данных предикатов и их импликацию, то получим следующий результат (рис. 4.4).

Рис. 4.4. Множество истинности для импликации.

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

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

Рис. 4.5. Множество истинности для конъюнкции.

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

Таблица 4.1

Соответствие действий над множествами и законов логики

Окончание табл. 4.1