Еще пример задания:
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент:
Ключевое слово | Количество сайтов, для которых данное слово является ключевым |
сканер | 200 |
принтер | 250 |
монитор | 450 |
Сколько сайтов будет найдено по запросу
(принтер | сканер) & монитор
если по запросу принтер | сканер было найдено 450 сайтов, по запросу принтер & монитор – 40, а по запросу сканер & монитор – 50.
Решение (вариант 1, использованием свойств операций «И» и «ИЛИ»):
обратим внимание на такой факт1 (справа указано количество сайтов по каждому запросу)
сканер 200
принтер 250
принтер | сканер 450
п оскольку последнее число равно сумме двух предыдущих, можно сразу же придти к выводу, что в этом сегменте сети нет сайтов, на которых ключевыми словами являются одновременно принтер и сканер:
принтер & сканер 0
диаграмма Эйлера для этого случая показана на рисунке справа:
с этого момента все просто: для того, чтобы определить, сколько сайтов удовлетворяют заданному условию
достаточно просто сложить числа, соответствующие запросам принтер & монитор и
сканер & монитор
таким образом, правильный ответ: 40 + 50 = 90.
Возможные проблемы: обратите внимание, что в условии была лишняя информация: мы нигде не использовали количество сайтов в данном сегменте Интернета (1000) и количество сайтов с ключевым словом монитор (450) не всегда удается «раскрутить» задачу в уме, здесь это несложно благодаря «удачному» условию |
Решение (вариант 3, таблицы истинности):
для сокращения записи обозначим через C, П, М высказывания «ключевое слово на сайте – сканер» (соответственно принтер, монитор)
если рассматривать задачу с точки зрения математической логики, здесь есть три переменных, с помощью которых можно составить всего 8 запросов, выдающих различные результаты
| С | П | М |
? | 0 | 0 | 0 |
? | 0 | 0 | 1 |
? | 0 | 1 | 0 |
? | 0 | 1 | 1 |
? | 1 | 0 | 0 |
? | 1 | 0 | 1 |
? | 1 | 1 | 0 |
? | 1 | 1 | 1 |
всего | 200 | 250 | 450 |
составим таблицу истинности, в которую добавим левый столбец и последнюю строку, где будем записывать количество сайтов, удовлетворяющих условиям строки и столбца (см. рисунок справа); например, первая строка соответствует сайтам, на которых нет ни одного из заданных ключевых слов; такая схема непривычна, но она существенно упрощает дело сумма в последней строчке получается в результате сложения всех чисел из тех строк первого столбца, где в данном столбце стоят единицы. Например, сумма в столбце С – складывается из четырех чисел в последних четырех строчках первого столбца. Мы пока не знаем, сколько результатов возвращает каждый из восьми запросов отдельно, поэтому в первом столбце стоят знаки вопроса
добавим в таблицу истинности остальные запросы, которые есть в условии, в том числе и тот, который нас интересует:
П | С = принтер | сканер 450
П & М = принтер & монитор 40
C & М = сканер & монитор 50
(П | C) & М = (принтер | сканер) & монитор ?
| С | П | М | П | С | П & М | C & М | (П | C) & М |
? | 0 | 0 | 0 | 0 | | | |
? | 0 | 0 | 1 | 0 | | | |
? | 0 | 1 | 0 | 1 | | | |
? | 0 | 1 | 1 | 1 | | | |
? | 1 | 0 | 0 | 1 | | | |
? | 1 | 0 | 1 | 1 | | | |
0 | 1 | 1 | 0 | 1 | | | |
0 | 1 | 1 | 1 | 1 | | | |
всего | 200 | 250 | 450 | 450 | | | |
проанализируем столбец П | С в этой таблице: его сумма (450) складывается из суммы столбцов С (200) и П (250) – выделены ярким зеленым цветом – плюс последние две строчки (голубой фон), то есть, 450 = 200 + 250 + X, откуда сразу получаем, что X = 0, то есть, последним двум строчкам (запросам) не удовлетворяет ни одного сайта
теперь составим таблицы истинности для остальных запросов, отбросив заведомо «нулевые» варианты:
| С | П | М | П | С | П & М | C & М | (П | C) & М |
? | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
? | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
? | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
40 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
? | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
50 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
всего | 200 | 250 | 450 | 450 | 40 | 50 | 90 |
из оставшихся шести строк таблицы запросы П & М и С & М затрагивают только по одной строчке, поэтому сразу можем вписать соответствующие числа в первый столбец; в последнем запросе, который нас интересует, присутствуют именно эти две строки, то есть, для получения нужно сложить 40 и 50
таким образом, правильный ответ: 40 + 50 = 90.
Р ешение (вариант 3, через диаграммы и систему уравнений):
для сокращения записи обозначим через C, П, М высказывания «ключевое слово на сайте – сканер» (соответственно принтер, монитор) и нарисуем эти области виде диаграммы (кругов Эйлера); интересующему нас запросу (П | C) & M соответствует объединение областей 4, 5 и 6 («зеленая зона» на рисунке)
количество сайтов, удовлетворяющих запросу в области i, будем обозначать через Ni
составляем уравнения, которые определяют запросы, заданные в условии:
сканер N1 + N2 + N4 + N5 = 200
принтер N2 + N3 + N5 + N6 = 250
принтер | сканер N1 + N2 + N4 + N5 + N3 + N6 = 450
из первого и третьего уравнений сразу следует
200 + N3 + N6 = 450 N3 + N6 = 250
далее из второго уравнения
N2 + N5 + 250 = 250 N2 + N5 = 0
поскольку количество сайтов не может быть отрицательной величиной, N2 = N5 = 0
посмотрим, что еще мы знаем (учитываем, что N5 = 0):
принтер & монитор N5 + N6 = 40 N6 = 40
сканер & монитор N4 + N5 = 50 N4 = 50
окончательный результат:
(принтер | сканер) & монитор N4 + N5 + N6 = N4 + N6 = 40 + 50 = 90
таким образом, правильный ответ 90.
Возможные проблемы: внимательнее с индексами переменных, очень легко по невнимательности написать N5 вместо N6 и получить совершенно другой результат этот метод ярко демонстрирует, что в общем случае мы получаем систему уравнения с семью неизвестными (или даже с восемью, если задействована еще и область вне всех кругов); решать такую систему вручную достаточно сложно, поэтому на экзамене всегда будет какое-то условие, сильно упрощающее дело, ищите его |
1 Как мы увидим далее, при использовании других методов решения, это условие принципиально облегчает решение данной задачи. Во всех известных автору вариантах подобных задач такое упрощающее условие было.