§ 20. Диаграммы Венна
Диаграммы Венна
Выражения, зависящие от небольшого количества переменных (обычно не более четырёх), удобно изображать в виде диаграмм, которые называют диаграммами Венна или кругами Эйлера. На такой диаграмме каждой переменной соответствует круг, внутри которого её значение истинно, а вне его — ложно. Круги могут пересекаться. Области, в которых рассматриваемое логическое выражение истинно, закрашиваются каким-либо цветом. На рисунке приведены диаграммы для простейших операций с одной и двумя переменными. Серым цветом залиты области, где рассматриваемое выражение равно единице. Такие диаграммы часто используются при работе с множествами: операция «И» соответствует пересечению двух множеств, а «ИЛИ» — объединению.
Для трёх переменных диаграмма будет немного сложнее. Для каждой из областей показанной на диаграммы запишем логические выражения.
Для того чтобы найти выражение для объединения двух или нескольких областей, надо применить логическое сложение (операцию «ИЛИ») к выражениям для всех составляющих. Например, выражение для объединения областей 3 и 4 имеет вид
3 + 4: А•В•С + А•В•С.
Вместе с тем если не обращать внимания на область А, то можно заметить, что справедлива формула 3 + 4: В•С.
Это означает, что логические выражения в некоторых случаях можно упростить. Как это делается, вы узнаете в следующем параграфе.
Диаграммы удобно применять для решения задач, в которых используются множества, например, множества страниц, полученных от поисковой системы в ответ на какой-то запрос. Рассмотрим следующую задачу.
Задача 1. Известно количество страниц, которые находит поисковый сервер по следующим запросам (здесь символ «&» обозначает операцию «И», а «|» — операцию «ИЛИ»):
Собаки |кошки 770
Кошки 550
Собаки и кошки 100
Сколько страниц будет выдано по запросу собаки?
Сначала попробуем рассмотреть задачу в общем виде и вывести формулу для её решения. Построим диаграмму с двумя областями А и В. Эти области могут быть разделены (рис. 3.16, а) или пересекаться (рис. 3.16, б).
Обозначим через Nx число страниц, которые выдаются по запросу X. В первом случае, когда области не пересекаются, получаем очевидную формулу: NA,S = NA + NB- Это значит, что количество страниц, полученных по запросу А \ В, будет равно сумме результатов по отдельным запросам.
Во втором случае (рис. 3.16, б) сумма NA + NB дважды включает общую область, т. е. результат запроса А &В. Поэтому формула изменяется:
^a\b-Na+Nb-Na&b.
Это более общий случай, справедливый и для рис. 3.16, а, где NA&B =0. Для нашей задачи {область А — собаки, область В — кошки) получаем:
NA =NA.B -NB +NA&B =770-550 + 100 = 320.
Рассмотрим теперь более сложную задачу, с тремя областями.
Задача 2. Известно количество страниц, которые находит поисковый сервер по следующим запросам (здесь символ «&» обозначает операцию «И», а «|» — операцию «ИЛИ»):
собаки 200
кошки 250
лемуры 450
кошки | собаки 450
кошки s лемуры 40
собаки & лемуры 50
Сколько страниц найдёт этот сервер по запросу (кошки | собаки) & лемуры?
Обозначим буквами С, К и Л области (группы сайтов), содержащие ключевые слова «собаки», «кошки» и «лемуры» соответственно (рис. 3.17). Построим диаграмму с тремя переменными и выделим интересующую область, которая соответствует запросу
(кошки | собаки) & лемуры. На рисунке 3.17 эта область закрашена серым цветом.
В общем виде задача очень сложна. Попробуем найти какое-нибудь упрощающее условие. Например, выделим три усло-I собаки
200 250 450Это означает, что область «кошки ИЛИ собаки» равна сумме областей «кошки» и «собаки», т. е. эти области не пересекаются! Таким образом, в нашем случае диаграмма выглядит, как показано на рис. 3.18.
Области 1 (собаки & лемуры) и 2 (кошки S лемуры) нам известны, они составляют соответственно 40 и 50 страниц, поэтому по запросу
(кошки I собаки) & лемуры поисковый сервер выдаст 40 + 50 = 90 страниц.
Подготовьте сообщение
а) «Диаграммы Венна и теория множеств»
б) «Язык запросов поисковых систем»