Решение задачи B12 (2012)

Задача

В языке запросов поискового сервера для обозначения логической операции ИЛИ используется символ "|", а для логической операции И - символ "&".
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

Запрос	Найдено страниц (в тысячах)
Шахматы | Теннис	7770
Теннис	5500
Шахматы & Теннис	1000

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

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

Решение

Рассмотрим найденные по запросам наборы страниц как множества, мощность которых нам известна. 

Отношения между множествами и операции над ними

Отношения между множествами

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

Такое отношение называется включением множества A в множество B:
A ⊆ B, если каждый элемент множества A является также элементом множества B.
В этом случае множество B включает в себя множество А.

Говорят, что множество А строго включено в множество B, если А включено в B и не равно ему:
A ⊂ B
В этом случае множество B строго включает в себя множество А; А является собственным множеством множества В.

Собственное множество — множество, которое является частью другого и не равно ему. В обоих случаях принято называть множество А подмножеством множества В; в свою очередь, множество В будет надмножеством множества А.

Два множества A и B будут равны, если каждый элемент A будет также являться элементом B, и каждый элемент множества B будет также являться элементом A
A = B
В таком случае можно сказать, что каждое из них будет подмножеством (надмножеством) другого.

Говорят, что множества не пересекаются, если у них нет общих элементов.

Множества A и B находятся в общем положении, если существует элемент (хотя бы один), принадлежащий исключительно множеству A, элемент, принадлежащий исключительно множеству B, а также элемент, принадлежащий обоим множествам.

Операции над множествами

Если имеется два множества или более, то с ними можно выполнить ряд операций. К таким операциям относятся:
- пересечение,
- объединение,
- дополнение,
- разность,
- симметрическая разность.
Все перечисленные операции, кроме дополнения, являются бинарными, т. е. выполняющимися с двумя множествами. Дополнение — унарная операция (выполняемая с одним множеством), которая, однако, может быть осуществлена лишь с учётом всех других множеств, предоставленных по условию задачи: дополнение всегда осуществляется до конкретного множества.
При этом пересечение, объединение и дополнение являются базовыми операциями, через которые могут быть выражены остальные.

Основные понятия теории множеств

Не новость, что информатика неразрывно связана с математикой, и подготовка к сдаче ЕГЭ требует актуализации знаний по многим темам, оказавшимся "на обочине" школьного курса.

В школьном курсе математики отводится очень мало времени на такой обширный и важный раздел, как теория множеств, хотя множества как таковые встречаются довольно часто; в то же время, в рамках ЕГЭ по информатике экзаменуемым предлагается задача, решение которой полностью основано на действиях со множествами.

Рассмотрим основные определения теории множеств.

Теория множеств — это раздел дискретной математики , в котором рассматриваются множества, их свойства и операции над ними.

Само понятие множества вводится аксиоматически и не может быть определено через какие-либо элементарные понятия. Однако мы можем дать описательное определение множества, например, в формулировке Бертрана Рассела:

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

Согласно Георгу Кантору, под множеством мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться элементами множества M).

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