Тема: Основные понятия математической логики

Тема: Составление запросов для поисковых систем с использованием логических выражений.

• 
  таблицы истинности логических операций «И», «ИЛИ», «НЕ» (см. презентацию «Логика»)
  
• 
  если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ»
  
• 
  логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
  
• 
  логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
  
• 
  правила преобразования логических выражений (слайд из презентации «Логика»):
  

• 
  ввод какого-то слова (скажем, «кергуду») в запросе поисковой системы означает, что пользователь ищет Web-страницы, на которых встречается это слово
  
• 
  операция «И» всегда ограничивает поиск, то есть, в ответ на запрос «кергуду И бамбарбия» поисковый сервер выдаст меньше страниц, чем на запрос «кергуду», потому что будет искать страницы, на которых есть оба этих слова одновременно
  
• 
  операция «ИЛИ» всегда расширяет поиск, то есть, в ответ на запрос «кергуду ИЛИ бамбарбия» поисковый сервер выдаст больше страниц, чем на запрос «кергуду», потому что будет искать страницы, на которых есть хотя бы одно из этих слов (или оба одновременно)
  

Пример задания:

36. 
    меньше всего результатов выдаст запрос с наибольшими ограничениями – первый (нужны одновременно принтеры, сканеры и продажа)
    
37. 
    на втором месте – второй запрос (одновременно принтеры и сканеры)
    
38. 
    далее – третий запрос (принтеры или сканеры)
    
39. 
    четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа)
    
40. 
    таким образом, верный ответ – 1234 .
    

1. 
   каждое из условий можно рассматривать как сложное высказывание
   
2. 
   обозначим отдельные простые высказывания буквами:
   

3. 
   запишем все выражения-запросы через логические операции
   

4. 
   здесь присутствуют три переменные, А, B и C (хотя второе и третье выражения от С не зависят!), поэтому для составления таблицы истинности нужно рассмотреть 8 = 23²³³³ всевозможных комбинаций этих логических значений
   
5. 
   выражение равно 1 (истинно) только при , в остальных случаях – равно 0 (ложно)
   
6. 
   выражение равно 1 только при , в остальных случаях – равно 0
   
7. 
   выражение равно 0 только при , в остальных случаях – равно 1
   
8. 
   выражение равно 0 только при , в остальных случаях –  1
   
9. 
   запишем результаты пп. 5-8 в виде таблицы истинности
   

   A	B	C
   0	0	0	0	0	0	0
   0	0	1	0	0	0	1
   0	1	0	0	0	1	1
   0	1	1	0	0	1	1
   1	0	0	0	0	1	1
   1	0	1	0	0	1	1
   1	1	0	0	1	1	1
   1	1	1	1	1	1	1

10. 
    по таблице видим, что наименьшая «область действия» у первого выражения, поисковый сервер выдаст наименьшее число запросов
    
11. 
    область, где , включает в себя⁸ всю область, где и еще один вариант, поэтому «поисковик» выдаст больше запросов, чем для первого случая
    
12. 
    аналогично делаем вывод, что область включает всю область и расширяет ее, а область – это расширение области
    
13. 
    таким образом, верный ответ – 1234 .
    

Возможные проблемы: решение достаточно громоздко, хотя позволяет с помощью простых операций решить задачу, не рискуя ошибиться при вычислениях «в уме» в сложных случаях если переменных более трех, таблица получается большая, хотя заполняется несложно

1. 
   запишем все ответы через логические операции
   

2. 
   покажем области, определяемые этими выражениями, на диаграмме с тремя областями
   

3. 
   сравнивая диаграммы, находим последовательность областей в порядке увеличения: (1,2,3,4), причем каждая следующая область в этом ряду охватывает целиком предыдущую (как и предполагается в задании, это важно!)
   
4. 
   таким образом, верный ответ – 1234 .
   

Еще пример задания:

Ключевое слово	Количество сайтов, для которых данное слово является ключевым
сканер	200
принтер	250
монитор	450

1. 
   обратим внимание на такой факт⁹ (справа указано количество сайтов по каждому запросу)
   

2. 
   с этого момента все просто: для того, чтобы определить, сколько сайтов удовлетворяют заданному условию
   

3. 
   таким образом, правильный ответ: 40 + 50 = 90.
   

1. 
   для сокращения записи обозначим через C, П, М высказывания «ключевое слово на сайте – сканер» (соответственно принтер, монитор)
   
2. 
   если рассматривать задачу с точки зрения математической логики, здесь есть три переменных, с помощью которых можно составить всего 8 запросов, выдающих различные результаты
   
3. 
   

   	С	П	М
   ?	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

   составим таблицу истинности, в которую добавим левый столбец и последнюю строку, где будем записывать количество сайтов, удовлетворяющих условиям строки и столбца (см. рисунок справа); например, первая строка соответствует сайтам, на которых нет ни одного из заданных ключевых слов; такая схема непривычна, но она существенно упрощает дело
   
4. 
   сумма в последней строчке получается в результате сложения всех чисел из тех строк первого столбца, где в данном столбце стоят единицы. Например, сумма в столбце С – складывается из четырех чисел в последних четырех строчках первого столбца. Мы пока не знаем, сколько результатов возвращает каждый из восьми запросов отдельно, поэтому в первом столбце стоят знаки вопроса
   
5. 
   добавим в таблицу истинности остальные запросы, которые есть в условии, в том числе и тот, который нас интересует:
   

6. 
   проанализируем столбец П | С в этой таблице: его сумма (450) складывается из суммы столбцов С (200) и П (250) – выделены ярким зеленым цветом – плюс последние две строчки (голубой фон), то есть, 450 = 200 + 250 + X, откуда сразу получаем, что X = 0, то есть, последним двум строчкам (запросам) не удовлетворяет ни одного сайта
   
7. 
   теперь составим таблицы истинности для остальных запросов, отбросив заведомо «нулевые» варианты:
   

8. 
   таким образом, правильный ответ: 40 + 50 = 90.
   

Решение (вариант 3, через диаграммы):

1. 
   для сокращения записи обозначим через C, П, М высказывания «ключевое слово на сайте – сканер» (соответственно принтер, монитор) и нарисуем эти области виде диаграммы (кругов Эйлера); интересующему нас запросу (П | C) & M соответствует объединение областей 4, 5 и 6 («зеленая зона» на рисунке)
   
2. 
   количество сайтов, удовлетворяющих запросу в области i, будем обозначать через N_i
   
3. 
   составляем уравнения, которые определяют запросы, заданные в условии:
   

4. 
   посмотрим, что еще мы знаем (учитываем, что N₅ = 0):
   

5. 
   окончательный результат:
   

6. 
   таким образом, правильный ответ 90.
   

Возможные проблемы: внимательнее с индексами переменными, очень легко по невнимательности написать N5 вместо N6 и получить совершенно другой результат этот метод ярко демонстрирует, что в общем случае мы получаем систему уравнения с семью неизвестными (или даже с восемью, если задействована еще и область вне всех кругов); решать такую систему вручную достаточно сложно, поэтому на экзамене всегда будет какое-то условие, сильно упрощающее дело, ищите его