Embedded Files
Выражения, зависящие от небольшого количества переменных (обычно не более четырёх), удобно изображать в виде диаграмм, которые называют диаграммами Венна или кругами Эйлера.
На такой диаграмме каждой переменной соответствует круг, внутри которого она равна единице, а вне его — нулю. Круги могут пересекаться. Области, в которых рассматриваемое логическое выражение истинно, закрашиваются каким-либо цветом. На рисунке 3.14 приведены диаграммы для простейших операций с одной и двумя переменными. Серым цветом залиты области, где рассматриваемое выражение равно единице.
Такие диаграммы часто используются при работе с множествами: операция «И» соответствует пересечению двух множеств, а «ИЛИ» — объединению.
Для трёх переменных диаграмма будет немного сложнее. Для каждой из областей показанной на рис. диаграммы запишем логические выражения.
Для того чтобы найти выражение для объединения двух или нескольких областей, надо применить логическое сложение (операцию «ИЛИ») к выражениям для всех составляющих. Например, выражение для объединения областей 3 и 4 имеет вид
3 + 4: А В С +А В С.
Вместе с тем если не обращать внимания на область А, то можно заметить, что справедлива формула
3 + 4: В С.
Это означает, что логические выражения в некоторых случаях можно упростить. .
Диаграммы удобно применять для решения задач, в которых используются множества, например множества страниц, полученных от поисковой системы в ответ на какой-то запрос. Рассмотрим следующую задачу.
Задача 1. Известно количество страниц, которые находит поисковый сервер по следующим запросам (здесь символ «&» обозначает операцию «И», а «|» — операцию «ИЛИ»):
собаки | кошки 770
кошки 550
собаки & кошки 100
Сколько страниц будет выдано по запросу собаки?
Сначала попробуем рассмотреть задачу в общем виде и вывести формулу для её решения. Построим диаграмму с двумя областями А и В. Эти области могут быть разделены или пересекаться
Обозначим через Nх число страниц, которые выдаются по запросу X. В первом случае, когда области не пересекаются, получаем очевидную формулу:
. Это значит, что количество страниц, полученных по запросу А| В, будет равно сумме результатов по отдельным запросам.
Во втором случае сумма
дважды включает общую область, т. е. результат запроса А & В. Поэтому формула изменяется: Это более общий случай, где
=0- Для нашей задачи (область А — собаки, область В — кошки) получаем:
=770-550 + 100 = 320.
Рассмотрим теперь более сложную задачу, с тремя областями.
Задача 2. Известно количество страниц, которые находит поисковый сервер по следующим запросам (здесь символ «&» обозначает операцию «И», а «|» — операцию «ИЛИ»):
собаки 200
кошки 250
лемуры 450
кошки | собаки 450
кошки & лемуры 40
собаки & лемуры 50
Сколько страниц найдёт этот сервер по запросу (кошки | собаки) & лемуры?
Обозначим буквами С, К и Л области (группы сайтов), содержащие ключевые слова «собаки», «кошки» и «лемуры» соответственно. Построим диаграмму с тремя переменными и выделим интересующую область, которая соответствует запросу (кошки | собаки) & лемуры.
На рисунке эта область закрашена желтым цветом.
В общем виде задача очень сложна. Попробуем найти какое-нибудь упрощающее условие. Например, выделим три условия:
собаки 200
кошки 250
кошки | собаки 450
Это означает, что область «кошки ИЛИ собаки» равна сумме областей «кошки» и «собаки», т. е. эти области не пересекаются! Таким образом, в нашем случае диаграмма выглядит, как показано на рис.
Области 1 (собаки & лемуры) и 2 (кошки & лемуры) нам известны, они составляют соответственно 40 и 50 страниц, поэтому по запросу (кошки | собаки) & лемуры поисковый сервер выдаст 40 + 50 = 90 страниц
Подготовьте сообщение
Page updated
Google Sites
Report abuse