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

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

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

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

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

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

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

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

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

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

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

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

PuQ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 4.1

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

Свойства действий над множествами

Название

Законы логики

Коммутативность

А п В = В п А

пересечения

конъюнкции

АлВ&ВлА

Ли В = В и А

объединения

дизъюнкции

A v В <=> В v Л

Ассоциативность

(А п В) п С = А п (В п С)

пересечения

конъюнкции

(А л В) л С <=> А л (В л С)

и В) и С = А и и С)

объединения

дизъюнкции

(Av В) v С A v (В v С)

Идемпотентность

Л п Л = Л

пересечения

конъюнкции

А а Л <=> Л

А иЛ = Л

объединения

дизъюнкции

Л v А<=> А

Исключения констант

An U = A

для пересече-

для конъюнк-

А д 1 <=> Л

Л п 0 = 0

ния

ции

Л л 0 <=> 0

Akj U=U

для объедине-

для дизъюнк-

Л v 1 <=> 1

А и 0 = Л

ния

ции

Л v 0 <=> Л

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

Свойства действий над множествами

Название

Законы логики

Дистрибутивность

А п (В и С) =

= (Л п В) и (Л п С)

пересечения

относительно

объединения

конъюнкции

относительно

дизъюнкции

А л v С) <=>

<=> А В) V (Л А С)

А и (В п С) =

= (А и В) n (A u С)

объединения

относительно

пересечения

дизъюнкции

относительно

конъюнкции

A v а С) <=>

<=> (Л v В) а (Л v С)

Поглощ

ение

/1 п (Л и В) - А

для пересечения

для конъюнкции

А а (Л v В) <=> Л

Аи(АпВ)=А

для объединения

для дизъюнкции

Л v (Л а В) <=> Л

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >