Логика
Теория: булева алгебра, булевы функции, таблицы истинности. Преобразования по законам булевой алгебры; разложение на конституэнты, СКНФ, СДНФ, функционально полная система/базис; операции над множествами, мощность множества, пересечения, объединения. Текстовые задачи.
Обозначения
a*b, a & b, a ∧ b
a+b, a | b, a v b
a', ¬a, ā
Инфиксная, префиксная, функциональная запись
(a ^ b) v c
v
/ \
^ c
/ \
a b
v∧abc
OR(AND(A1;B1);C1)
Об отличии дизъюнкции от "либо" (исключающего "или"):
Вертолет 3400
Самолет 5600
Вертолет | Самолет 8000
Сколько страниц будет выдано
по запросу Вертолет & Самолет?
Можно нарисовать круги эйлера / диаграммы венна
и сделать вывод, что объединение - это (3400 - x ) + x + (5600 - x) = 3400 - x + x + 5600 - x = 9000 - x = 8000 т.е. x = 1000
или можно вывести формулу
Рассмотрим упрощенный пример:
множество {1,2,3,4,5,6} и множество {5,6,7,8,9}
их пересечение содержит 2 элемента: {5,6}
их объединение содержит 9 элементов: {1,2,3,4,5,6,7,8,9}
в первом множестве 6 элементов, во втором 5
если суммировать количества элементов, получим 5 +6 = 11
но 2 элемента общие
11 - 2 = 9
∑ - ⋂ = ⋃
сумма - это перечисление всех элементов обоих множеств - сначала первого, потом второго
объединение - это перечисление всех элементов обоих множеств по одному разу (т.е. после вычеркивания копий элементов)
M N
| M | + | N | - | M ∩ N | = | M ∪ N |
Таким образом вывод:
A|B = A + B - A&B
A = A|B - B + A&B
B = A|B - A + A&B
A&B = A + B - A|B
В демоверсии 2014 года эта задача была усложнена
там появляются ТРИ категории.
Хоккей И футбол И волейбол = 80
Футбол И волейбол = 260
Хоккей И Волейбол = 230
А спрашивается, сколько будет найдено
по запросу (хоккей ИЛИ футбол ) И волейбол
На первый взгляд тут придется применять формулу для трех множеств
N(A∪B∪C)=N(A)+N(B)+N(C)−N(A∩B)−N(A∩C)−N(B∩C)+N(A∩B∩C).
Но для применения такой формулы не хватает данных
на самом деле всё проще.
пользуемся законом булевой алгебры: (хоккей ИЛИ футбол ) И волейбол = (хоккей И волейбол ) ИЛИ ( футбол И волейбол)
переобозначим: А = (хоккей И волейбол ) = 230
Б = ( футбол И волейбол) = 260
А что дает первое? где 80? а это на самом деле перечение А и Б
Потому что А и Б = (хоккей И волейбол ) И ( футбол И волейбол) = Хоккей И футбол И волейбол = 80
и таким образом задача сводится к предыдущей
А И Б = 80
А = 230
Б = 260
А ИЛИ Б = 230 + 260 - 80 = 410
О задачах на маску подсети из Демо-2012
Ответ: 217.233.232.0
т.е. CDEA
Помощь при проверке себя может оказать ресурс http://www.ispreview.ru/ipcalc.html
¬ (1Г -> 2Г) & ПГ = ¬ (1C v 2Г) & ПГ = 1Г & 2С & ПГ
