Урок №22. Логические операции и операции над множествами.
Любое множество можно задать с помощью некоторого логического выражения (условия), которое истинно для каждого элемента множества и ложно для всех объектов, не входящих в это множество. Например, множество чётных чисел задаётся условием «число делится на 2 без остатка». Поэтому для выполнения операций со множествами можно успешно применять аппарат алгебры логики.
Пусть А — это логическое выражение, определяющее некоторое множество. Для того чтобы не вводить лишние обозначения, мы будем говорить «множество А», имея в виду «множество элементов, для которых выражение А истинно».
Множество ¬А — это множество всех объектов, которые не входят в А (для них выражение А ложно). Такое множество называется дополнением множества А до некоторого универсального множества U, из которого мы выделяем множество А. Например, если А — это множество чётных чисел, то в качестве универсального множества U можно взять множество всех целых чисел. Тогда ¬А — это множество всех нечётных чисел.
Множество А • В включает общие элементы множеств А и В и называется их пересечением. Множество А + В — это объединение множеств А и B, т. е. все элементы, которые входят хотя бы в одно из двух множеств.
Все перечисленные множества удобно изображать с помощью диаграмм Эйлера-Венна (рис. 3.18).
Рис. 3.18
Логические выражения, зависящие от небольшого количества переменных (обычно не более четырёх), удобно изображать в виде диаграмм, которые называют диаграммами Эйлера-Венна. На такой диаграмме каждой переменной соответствует круг, внутри которого её значение истинно, а вне его — ложно. Круги могут пересекаться.
Диаграмма Эйлера-Венна для трёх переменных содержит 8 областей. Для каждой из них запишем логические выражения (рис. 3.13).
Рис. 3.13
Для того чтобы найти логическое выражение для объединения двух или нескольких областей, надо сложить (используя логическое сложение — операцию ИЛИ) выражения для всех составляющих. Например, выражение для объединения областей 3 и 4 имеет вид
Вместе с тем если не обращать внимания на область А, то можно заметить, что справедлива формула
Это означает, что логические выражения в некоторых случаях можно упростить. Как это делается, вы узнаете в следующем параграфе.
Диаграммы Эйлера-Венна удобно применять для решения задач, в которых используются множества, например множества страниц, полученных от поисковой системы в ответ на какой-то запрос.