1. Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: пирожное & выпечка 3200пирожное 8700выпечка 7500Сколько страниц будет найдено по запросу пирожное | выпечка
Ответ:
2. Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: фрегат & эсминец 500фрегат | эсминец 4500эсминец 2500Сколько страниц будет найдено по запросу фрегат
Ответ:
3. Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: фрегат & эсминец 1000фрегат 2000эсминец 2500Сколько страниц будет найдено по запросу фрегат | эсминец
Ответ:
4. Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: пирожное | выпечка 14200пирожное 9700пирожное & выпечка 5100Сколько страниц будет найдено по запросу выпечка
Ответ:
5. Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: сомики 250меченосцы 200гуппи 500сомики & гуппи 0сомики & меченосцы 20меченосцы & гуппи 10Сколько страниц будет найдено по запросу сомики | меченосцы | гуппи
Ответ:
6. Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: сомики 250меченосцы 200гуппи 500сомики | гуппи 750сомики & меченосцы 100меченосцы & гуппи 0Сколько страниц будет найдено по запросу (сомики & меченосцы) | гуппи
Ответ:
7. Ниже приведены запросы и к
sites.google.com
Информатика — Задание 17. Пример
Условие: В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц(в тысячах)
Шахматы | Теннис
7770
Теннис
5500
Шахматы & Теннис
1000
Какое количество страниц (в тысячах) будет найдено по запросу
Шахматы?
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Решение: Через Ответ(Z) будем обозначать множество страниц, найденных по запросу Z, а через N(Z) – размер множества Ответ(Z), то есть количество страниц, найденных по запросу Z. В этих обозначениях множество Ответ(X&Y) = это пересечение множеств Ответ(X) и Ответ(Y), а множество Ответ(X | Y) – объединение Ответ(X) и Ответ(Y).
Если по запросу Шахматы | Теннис было найдено 7770 страниц, то среди них были страницы, содержавшие либо оба этих слова, либо только одно из них. Так как страниц, содержащих оба эти слова, было найдено ровно 1000, то из 5500 страниц, содержащих слово «Теннис», 1000 содержит также слово «Шахматы», а 4500 – не содержат этого слова. Поэтому из общего количества 7770 страниц, надо вычесть 4500, на которых есть слово «Теннис», но нет слова «Шахматы». Полученное число в 3270 страниц и будет результатом запроса «Шахматы» и, соответственно, ответом на задание.
Ответ:3270
Замечание. Приведенные рассуждения отражают следующий простой факт из теории множеств. Применительно к нашей задаче его можно записать так. Для любых запросов X и Y выполнено:
N(X | Y) = N(X)+N(Y) – N(X&Y)
ege-go.ru
10-3_Логика |authorSTREAM
Логические основы компьютеров:
1 Логические основы компьютеров § 18 . Логика и компьютер § 19 . Логические операции § 20 . Диаграммы
Логические основы компьютеров:
2 Логические основы компьютеров § 18. Логика и компьютер
Логика, высказывания:
3 Логика, высказывания Аристотель (384-322 до н.э.) Логика (др.греч. λογικ ο ς ) – это наука о том, как правильно рассуждать, делать выводы, доказывать утверждения. Формальная логика отвлекается от конкретного содержания, изучает только истинность и ложность высказываний. Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.
Высказывание или нет?:
4 Высказывание или нет? Сейчас идет дождь. Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час?
Логика и компьютер:
5 Логика и компьютер Двоичное кодирование – все виды информации кодируются с помощью 0 и 1. Задача – разработать оптимальные правила обработки таких данных. Почему «логика»? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания. Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра).
Логические основы компьютеров:
6 Логические основы компьютеров § 19 . Логические операции
Обозначение высказываний:
7 Обозначение высказываний A – Сейчас идет дождь. B – Форточка открыта. простые высказывания (элементарные) Составные высказывания строятся из простых с помощью логических связок (операций) « и» , « или» , « не» , « если … то» , « тогда и только тогда» и др. Любое высказывание может быть ложно (0) или истинно (1). ! A и B A или не B если A , то B A тогда и только тогда, когда B Сейчас идет дождь и открыта форточка. Сейчас идет дождь или форточка закрыта. Если сейчас идет дождь, то форточка открыта. Дождь идет тогда и только тогда, когда открыта форточка.
Операция НЕ (инверсия):
8 Операция НЕ ( инверсия) Если высказывание A истинно, то « не А» ложно, и наоборот. А не А 1 0 0 1 таблица истинности операции НЕ также , , not A ( Паскаль ) , ! A ( Си) Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.
Операция И:
9 Операция И Высказывание « A и B » истинно тогда и только тогда, когда А и B истинны одновременно. 220 В A и B A B
Операция И (логическое умножение, конъюнкция):
10 Операция И ( логическое умножение, конъюнкция) A B А и B 1 0 также: A·B , A B , A and B ( Паскаль ) , A && B ( Си) 0 0 0 1 1 0 1 1 0 1 2 3 0 0 конъюнкция – от лат. conjunctio — соединение A B
Операция ИЛИ (логическое сложение, дизъюнкция):
11 Операция ИЛИ ( логическое сложение, дизъюнкция) Высказывание « A или B » истинно тогда, когда истинно А или B , или оба вместе. 220 В A или B A B
Операция ИЛИ (логическое сложение, дизъюнкция):
12 Операция ИЛИ ( логическое сложение, дизъюнкция) A B А или B 1 0 также: A + B , A B , A or B ( Паскаль ) , A || B ( Си) 0 0 0 1 1 0 1 1 1 1 дизъюнкция – от лат. dis junctio — разъединение
Задачи:
Задачи 13 В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ | , а для логической операции «И» – &. 1) принтеры & сканеры & продажа 2) принтеры & продажа 3) принтеры | продажа 4) принтеры | сканеры | продажа 1 2 3 4
Операция «исключающее ИЛИ»:
14 Операция « исключающее ИЛИ » Высказывание « A B » истинно тогда, когда истинно А или B , но не оба одновременно ( то есть A B ) . «Либо пан, либо пропал». A B А B 0 0 также: A xor B ( Паскаль ) , A ^ B ( Си) 0 0 0 1 1 0 1 1 1 1 сложение по модулю 2: А B = ( A + B) mod 2 арифметическое сложение, 1+1=2 остаток
Свойства операции «исключающее ИЛИ»:
15 Свойства операции «исключающее ИЛИ» A A = ( A B) B = A 0 = A 1 = A 0 ? A B А B 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 A
Импликация («если …, то …»):
16 Импликация («если …, то …») Высказывание « A B » истинно, если не исключено, что из А следует B . A – «Работник хорошо работает». B – «У работника хорошая зарплата». A B А B 0 0 0 1 1 0 1 1 1 1 1 0
Импликация («если …, то …»):
17 Импликация («если …, то …») «Если Вася идет гулять, то Маша сидит дома». A – «Вася идет гулять». B – «Маша сидит дома». Маша может пойти гулять ( B=0) , а может и не пойти (B=1) ! A B А B 0 0 1 0 1 1 1 0 0 1 1 1 А если Вася не идет гулять? ?
Эквивалентность («тогда и только тогда, …»):
18 Эквивалентность («тогда и только тогда, …») Высказывание « A B » истинно тогда и только тогда, когда А и B равны. A B А B 0 0 1 0 1 0 1 0 0 1 1 1
Базовый набор операций:
19 Базовый набор операций С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию. ИЛИ И НЕ базовый набор операций Сколько всего существует логических операции с двумя переменными? ?
Штрих Шеффера, «И-НЕ» :
20 Штрих Шеффера, «И-НЕ» A B А | B 0 0 1 0 1 1 1 0 1 1 1 0 Базовые операции через «И-НЕ»: Как доказать? ?
Стрелка Пирса, «ИЛИ-НЕ» :
21 Стрелка Пирса, «ИЛИ-НЕ» A B А ↓ B 0 0 1 0 1 0 1 0 0 1 1 0 Базовые операции через «ИЛИ-НЕ»: Самостоятельно… !
Формализация:
22 Формализация Прибор имеет три датчика и может работать, если два из них исправны. Записать в виде формулы ситуацию «авария». A – «Датчик № 1 неисправен». B – «Датчик № 2 неисправен». C – «Датчик № 3 неисправен». Аварийный сигнал : X – «Неисправны два датчика». X – «Неисправны датчики № 1 и № 2» или «Неисправны датчики № 1 и № 3» или «Неисправны датчики № 2 и № 3». логическая формула Формализация – это переход к записи на формальном языке! !
Вычисление логических выражений:
23 Вычисление логических выражений Порядок вычислений : скобки НЕ И ИЛИ, исключающее ИЛИ импликация эквивалентность A B + + B C A С 1 4 2 5 3
25 Составление таблиц истинности A B A · B X 0 0 0 1 1 0 1 1 0 1 2 3 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 1 Логические выражения могут быть: тождественно истинными (всегда 1, тавтология) тождественно ложными (всегда 0, противоречие) вычислимыми (зависят от исходных данных)
Задачи (таблица истинности):
Задачи ( таблица истинности ) 26 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? ¬X ¬Y ¬Z X Y Z X Y Z ¬X ¬Y ¬Z X Y Z F 1 0 0 1 0 0 0 1 1 1 1 0 Упрощённый способ подбора :
Задачи (таблица истинности):
Задачи ( таблица истинности ) 27 X Y Z F 1 0 0 1 0 0 0 1 1 1 1 0 Упрощённый способ подбора : один нуль операция «ИЛИ» получить 0, применив «НЕ» к слагаемым: 1 1 1 X Y Z F 1 0 1 0 0 1 0 1 1 1 1 0 одна единица операция «И» получить 1, применив «НЕ» к сомножителям: 0 1 0
Логические основы компьютеров:
28 Логические основы компьютеров § 20. Диаграммы
Диаграммы Венна (круги Эйлера):
29 Диаграммы Венна (круги Эйлера) A B A B A A · B A B A+B A B A B A B A B A B
Диаграмма с тремя переменными:
30 Диаграмма с тремя переменными Х очу М огу Н адо 1 2 3 4 5 6 7 8 Логические выражения можно упрощать! !
Задачи:
Известно количество сайтов, которых находит поисковый сервер по следующим запросам : Сколько сайтов будет найдено по запросу огурцы | помидоры Задачи 31 Запрос Количество сайтов огурцы 100 помидоры 200 огурцы & помидоры 50
Задачи:
Задачи 32 N A|B = N A + N B A B A B N A|B = N A + N B – N A&B огурцы | помидоры 50 огурцы помидоры 10 0 2 0 0 огурцы & помидоры 2 50
Задачи:
Известно количество сайтов, которых находит поисковый сервер по следующим запросам : Сколько сайтов будет найдено по запросу Динамо & Спартак & Рубин Задачи 33 Запрос Количество сайтов Динамо & Рубин 320 Спартак & Рубин 280 ( Динамо | Спартак) & Рубин 430 Общее условие с & можно отбросить ! !
Задачи:
Известно количество сайтов, которых находит поисковый сервер по следующим запросам : Сколько сайтов будет найдено по запросу Динамо & Спартак Задачи 34 Запрос Количество сайтов Динамо 320 Спартак 280 Динамо | Спартак 430 Ответ: 320 + 280 – 430 = 170
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент: Сколько сайтов будет найдено по запросу (принтер | сканер) & монитор если по трем следующим запросам найдено: принтер | сканер – 450 сайтов, принтер & монитор – 40 сайтов сканер & монитор – 50 сайтов. Задачи 36 Ключевое слово Количество сайтов, для которых данное слово является ключевым сканер 200 принтер 250 монитор 450
Задачи:
Задачи 37 А (сканер) B (принтер) N A|B = N A + N B – N A&B принтер | сканер 450 сканер принтер 2 0 0 250 0 сканер принтер монитор 90 40 + 50 = принтер & монитор = 40 сканер & монитор = 50 50 40 (принтер | сканер) & монитор = ?
Сложная задача:
Сложная задача 38 Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: мезозой 500 кроманьонец 600 неандерталец 700 мезозой | кроманьонец 800 мезозой | неандерталец 1000 неандерталец & (мезозой | кроманьонец) 200 Сколько страниц будет найдено по запросу кроманьонец & (мезозой | неандерталец)
