В этих задачах один и тот же объект удобно видеть по-разному: условие — как логическое выражение, дороги — как граф, запросы — как множества страниц. Сначала переведите текст в модель, затем считайте.

Логические операции

Пусть $A$ и $B$ — высказывания.

Запись	Название	Когда истинно
$\neg A$	отрицание	когда $A$ ложно
$A\land B$	конъюнкция, «и»	когда истинны обе части
$A\lor B$	дизъюнкция, «или»	когда истинна хотя бы одна часть
$A\to B$	импликация	ложна только при истинном $A$ и ложном $B$
$A\leftrightarrow B$	эквивалентность	когда значения $A$ и $B$ совпадают

Приоритет: отрицание, затем «и», затем «или». Скобки меняют порядок.

Полная таблица для «и» и «или»:

$A$	$B$	$A\land B$	$A\lor B$
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

Пример. Для $A=1$, $B=0$:

[ \neg A\lor B=0\lor0=0, ]

[ \neg(A\lor B)=\neg(1\lor0)=\neg1=0. ]

Результат совпал, но это не общее тождество. Проверьте остальные строки таблицы истинности.

Законы де Моргана

Отрицание выражения раскрывают так:

[ \neg(A\land B)=\neg A\lor\neg B, ]

[ \neg(A\lor B)=\neg A\land\neg B. ]

Пример. Отрицание условия «целое число положительное и чётное» означает «целое число неположительное или нечётное». Союз меняется, отрицание применяется к каждой части.

Числовые условия

Текст «$x$ не меньше 7» означает $x\ge7$, «не больше 12» — $x\le12$, «вне отрезка от 7 до 12» — $x<7\lor x>12$.

Пример. Найдём целые $x$, для которых истинно $x\ge4\land x<8$. Пересечение условий даёт $4,5,6,7$: всего 4 значения.

Множества поисковых запросов

Запрос с «И» соответствует пересечению множеств страниц, запрос с «ИЛИ» — объединению. Для двух запросов:

[ |A\cup B|=|A|+|B|-|A\cap B|. ]

Пример. Запрос робот нашёл 620 страниц, алгоритм — 480, а робот И алгоритм — 170. Тогда

[ |A\cup B|=620+480-170=930. ]

Пересечение вычитают один раз, потому что в сумме $620+480$ общие страницы посчитаны дважды.

Для трёх множеств:

[ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|. ]

Пример. Три запроса дали 100, 80 и 60 страниц; попарные пересечения — 30, 20 и 10, общее пересечение — 5:

[ 100+80+60-30-20-10+5=185. ]

Формулы сравнивают запросы к одной фиксированной базе страниц. В учебной задаче это обычно подразумевается. Результаты реальной выдачи, полученные в разное время из меняющейся базы, смешивать нельзя.

Граф: вершины, рёбра и вес

Вершины обозначают объекты, рёбра — связи. В ориентированном графе направление важно. Вес ребра может означать длину, время или стоимость.

В простом неориентированном графе без петель степень вершины — число рёбер, которые к ней подходят. Сумма степеней всех вершин равна удвоенному числу рёбер:

[ \sum \deg(v)=2E. ]

Пример. Степени четырёх вершин равны 2, 3, 2 и 1. Сумма равна 8, значит, рёбер $E=8:2=4$.

Кратчайший путь

Для небольшого графа выпишите несколько допустимых маршрутов и сложите веса. Для большого графа с неотрицательными весами используйте порядок Дейкстры:

Начальной вершине присвойте расстояние 0, остальным — бесконечность.
Выберите непосещённую вершину с наименьшим расстоянием.
Попробуйте улучшить расстояния до её соседей.
Пометьте вершину посещённой и повторяйте.

Пример. Есть дороги $A-B=4$, $A-C=2$, $C-B=1$, $B-D=5$, $C-D=8$. Сначала из $A$ получаем $B=4$, $C=2$. Через $C$ улучшаем $B$: $2+1=3$. Через $B$ получаем $D=3+5=8$. Путь $A-C-B-D$ короче прямого варианта $A-C-D=10$.

Количество путей в ориентированном графе

Если граф не содержит циклов на рассматриваемом направлении, число путей удобно считать динамически. Начальной вершине присвойте 1. Для каждой следующей вершины сложите числа у всех вершин, из которых в неё входят рёбра.

Пример. Из $A$ идут рёбра в $B$ и $C$, из $B$ и $C$ — в $D$, из $C$ — ещё в $E$, из $D$ — в $E$.

[ P(A)=1,\quad P(B)=1,\quad P(C)=1, ]

[ P(D)=P(B)+P(C)=2, ]

[ P(E)=P(C)+P(D)=1+2=3. ]

Ответ: из $A$ в $E$ ведут 3 пути. При наличии циклов сначала уточните, разрешено ли посещать вершины повторно: без ограничения число маршрутов может стать бесконечным.

Адреса и сеть

URL обычно содержит схему, имя узла, путь и иногда параметры, например https://example.org/tasks/list?page=2. IP-адрес идентифицирует узел в сети, доменное имя даёт человеку удобное имя, DNS сопоставляет доменное имя с сетевым адресом.

В задаче на составление адреса не угадывайте порядок фрагментов. Сначала соберите шаблон схема://домен/путь, затем подставьте части и проверьте разделители.

Самопроверка

Союзы «и», «или», «не» переведены без перестановки смысла?
В запросах «И» стало пересечением, а «ИЛИ» — объединением?
Общая часть множеств не посчитана дважды?
У графа учтены направления и веса?
Кратчайший маршрут проверен сравнением сумм?
При подсчёте путей сложены все входящие варианты?

Подробные статьи: логические выражения, графы и сети, файлы и поиск.

Источник

Охват тем и экзаменационных действий сверён с проектом кодификатора ОГЭ-2027 ФИПИ. Схемы решения и числа в примерах созданы FastLearn.