Использование логических связок в поисковых запросах

1. Введение

В курсе Информатики и ИКТ основной и старшейшколы рассматриваются такие важные темы как“Основы логики” и “Поиск информации вИнтернет”. При решении определенного типа задачудобно использовать круги Эйлера (диаграммыЭйлера-Венна).

Математическая справка. Диаграммы Эйлера-Веннаиспользуются прежде всего в теории множеств каксхематичное изображение всех возможныхпересечений нескольких множеств. В общем случаеони изображают все 2n комбинаций n свойств.Например, при n=3 диаграмма Эйлера-Венна обычноизображается в виде трех кругов с центрами ввершинах равностороннего треугольника иодинаковым радиусом, приблизительно равнымдлине стороны треугольника.

2. Представление логических связок в поисковыхзапросах

При изучении темы “Поиск информации вИнтернет” рассматриваются примеры поисковыхзапросов с использованием логических связок,аналогичным по смыслу союзам “и”, “или”русского языка. Смысл логических связокстановится более понятным, еслипроиллюстрировать их с помощью графическойсхемы – кругов Эйлера (диаграмм Эйлера-Венна).

3. Связь логических операций с теорией множеств

С помощью диаграмм Эйлера-Венна можно нагляднопредставить связь логических операций с теориеймножеств. Для демонстрации можновоспользоваться слайдами в Приложение1.

Логические операции задаются своими таблицамиистинности. В Приложении 2подробно рассматриваются графическиеиллюстрации логических операций вместе с ихтаблицами истинности. Поясним принциппостроения диаграммы в общем случае. Надиаграмме – область круга с именем А отображаетистинность высказывания А (в теории множествкруг А – обозначение всех элементов, входящих вданное множество). Соответственно, область внекруга отображает значение “ложь”соответствующего высказывания. Что бы понятькакая область диаграммы будет отображениемлогической операции нужно заштриховать толькоте области, в которых значения логическойоперации на наборах A и B равны “истина”.

Например, значение импликации равно “истина”в трех случаях (00, 01 и 11). Заштрихуемпоследовательно: 1) область вне двухпересекающихся кругов, которая соответствуетзначениям А=0, В=0; 2) область, относящуюся только ккругу В (полумесяц), которая соответствуетзначениям А=0, В=1; 3) область, относящуюся и к кругуА и к кругу В (пересечение) – соответствуетзначениям А=1, В=1. Объединение этих трех областейи будет графическим представлением логическойоперации импликации.

4. Использование кругов Эйлера придоказательстве логических равенств (законов)

Для того, чтобы доказать логические равенстваможно применить метод диаграмм Эйлера-Венна.Докажем следующее равенство ¬(АvВ) = ¬А&¬В (законде Моргана).

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

Рис.3 Рис.4

Для визуального представления правой частиравенства выполним последовательно:заштрихуем область для отображения инверсии (¬А)серым цветом и аналогично область ¬В также серымцветом; затем для отображения конъюнкции нужновзять пересечение этих серых областей (результатналожения представлен черным цветом):

Рис.5 Рис.6 Рис.7

Видим, что области для отображения левой иправой части равны. Что и требовалось доказать.

5. Задачи в формате ГИА и ЕГЭ по теме: “Поискинформации в Интернет”

Задача №18 из демо-версии ГИА 2013.

В таблице приведены запросы к поисковомусерверу. Для каждого запроса указан его код –соответствующая буква от А до Г. Расположите кодызапросов слева направо в порядке убывания количествастраниц, которые найдет поисковый сервер покаждому запросу.

Решение:

Для каждого запроса построим диаграммуЭйлера-Венна:

Ответ: ВАГБ.

Задача В12 из демо-версии ЕГЭ-2013.

В таблице приведены запросы и количествонайденных по ним страниц некоторого сегментасети Интернет.

Какое количество страниц (в тысячах) будетнайдено по запросу Эсминец?

Считается, что все запросы выполнялисьпрактически одновременно, так что набор страниц,содержащих все искомые слова, не изменялся завремя выполнения запросов.

Решение:

Пусть

Ф – количество страниц (в тысячах) по запросу Фрегат;

Э – количество страниц (в тысячах) по запросу Эсминец;

Х – количество страниц (в тысячах) по запросу, вкотором упоминается Фрегат и не упоминаетсяЭсминец;

У – количество страниц (в тысячах) по запросу, вкотором упоминается Эсминец и неупоминается Фрегат.

Построим диаграммы Эйлера-Венна для каждогозапроса:

Согласно диаграммам имеем:

1. Х+900+У = Ф+У = 2100+У = 3400. Отсюда находим У = 3400-2100 = 1300.
2. Э = 900+У = 900+1300= 2200.

Ответ: 2200.

6. Решение логических содержательныхзадач методом диаграмм Эйлера-Венна

Задача 1.

В классе 36 человек. Ученики этого классапосещают математический, физический ихимический кружки, причем математический кружокпосещают 18 человек, физический — 14 человек,химический — 10. Кроме того, известно, что 2человека посещают все три кружка, 8 человек — иматематический и физический, 5 и математический ихимический, 3 — и физический и химический.

Сколько учеников класса не посещают никакихкружков?

Решение:

Для решения данной задачи очень удобным инаглядным является использование кругов Эйлера.

Самый большой круг – множество всех учениковкласса. Внутри круга три пересекающихсямножества: членов математического (М),физического (Ф), химического (Х) кружков.

Пусть МФХ – множество ребят, каждый изкоторых посещает все три кружка. МФ¬Х –множество ребят, каждый из которых посещаетматематический и физический кружки и непосещает химический. ¬М¬ФХ — множество ребят,каждый из которых посещает химический кружок ине посещает физический и математический кружки.

Аналогично введем множества: ¬МФХ, М¬ФХ,М¬Ф¬Х, ¬МФ¬Х, ¬М¬Ф¬Х.

Известно, что все три кружка посещают 2человека, следовательно, в область МФХ впишемчисло 2. Т.к. 8 человек посещают и математический ифизический кружки и среди них уже есть 2 человека,посещающих все три кружка, то в область МФ¬Х впишем6 человек (8-2). Аналогично определим количествоучащихся в остальных множествах:

Просуммируем количество человек по всемобластям: 7+6+3+2+4+1+5=28. Следовательно, 28 человек изкласса посещают кружки.

Значит, 36-28 = 8 учеников не посещают кружки.

Ответ: 8.

Задача 2.

После зимних каникул классный руководительспросил, кто из ребят ходил в театр, кино или цирк.Оказалось, что из 36 учеников класса двое не былини в кино. ни в театре, ни в цирке. В кино побывало25 человек, в театре — 11, в цирке 17 человек; и в кино,и в театре — 6; и в кино и в цирке — 10; и в театре и вцирке — 4.

Сколько человек побывало и в кино, и в театре, ив цирке?

Решение:

Пусть х – количество ребят, которые побывали ив кино, и в театре, и в цирке.

Тогда можно построить следующую диаграмму ипосчитать количество ребят в каждой области:

Ответ: 1.

Таким образом, круги Эйлера (диаграммыЭйлера-Венна) находят практическое применениепри решении задач в формате ЕГЭ и ГИА и прирешении содержательных логических задач.

Литература

1. В.Ю. Лыскова, Е.А. Ракитина. Логика в информатике.М.: Информатика и Образование, 2006. 155 с.
2. Л.Л. Босова. Арифметические и логические основыЭВМ. М.: Информатика и образование, 2000. 207 с.
3. Л.Л. Босова, А.Ю. Босова. Учебник. Информатика иИКТ для 8 класса: БИНОМ. Лаборатория знаний, 2012. 220с.
4. Л.Л. Босова, А.Ю. Босова. Учебник. Информатика иИКТ для 9 класса: БИНОМ. Лаборатория знаний, 2012. 244с.
5. Сайт ФИПИ: https://www.fipi.ru/