Раздел 3. Логика. Множества. Графы

Определения и обозначения

Логическое высказывание — предложение, про которое можно однозначно сказать, истинно оно или ложно. Например, «7 больше 3» — истинное высказывание, а «закрой окно» — нет, потому что это просьба. Понятие нужно, чтобы рассуждать не на глаз, а проверять утверждения и связывать их логическими операциями.

Множество — совокупность объектов, объединённых некоторым признаком; сами объекты называют его элементами. Запись x ∈ A означает, что элемент x принадлежит множеству A, а x ∉ A — что не принадлежит. Множества помогают описывать группы объектов и сравнивать их состав, не перечисляя каждый раз все свойства по отдельности.

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

Как это устроено

Сложное высказывание можно составить из простых с помощью слов «не», «и», «или». Отрицание A обозначают ¬A: оно меняет истинность на противоположную. Конъюнкция A ∧ B («A и B») истинна только тогда, когда оба высказывания истинны, потому что союз «и» требует выполнения двух условий одновременно. Дизъюнкция A ∨ B («A или B») истинна, если истинно хотя бы одно из условий; в логике обычно допускается, что истинны оба.

Множества удобно задавать перечислением элементов или общим условием. Например, множество чётных чисел меньше 8 можно записать как {2, 4, 6}. Объединение A ∪ B собирает элементы, которые входят хотя бы в одно из множеств, а пересечение A ∩ B оставляет только общие элементы. Разность A \ B содержит то, что есть в A, но отсутствует в B; поэтому порядок важен: A \ B и B \ A могут различаться.

Граф можно представить рисунком, но его смысл задают не расположение вершин на листе, а наличие рёбер между ними. Если ребро соединяет две вершины, между соответствующими объектами есть связь. Рёбра могут быть направленными, например обозначать дорогу только в одну сторону, или ненаправленными — когда связь действует в обоих направлениях. Последовательность соседних вершин образует путь, а его длину в простом графе считают по числу пройденных рёбер.

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

Сравнение логики, множеств и графов

Пользуйся таблицей, чтобы выбрать подходящий способ описания задачи: сначала определи, что требуется изучить — условие, состав группы или связи. Обозначения помогают кратко записать модель, но сами по себе не заменяют понимания смысла. Перед вычислениями проговори, что означает каждый знак именно в твоей задаче.

Разбор задач

Задача. В кружке 12 учеников: 7 занимаются шахматами, 6 — робототехникой, а 3 посещают оба занятия. Сколько учеников посещают хотя бы один кружок и сколько не посещают ни одного? Обозначим множество шахматистов буквой A, а множество участников робототехники — B. Условие «хотя бы один» означает объединение A ∪ B, а не только одну из групп.

1. Найдём число учеников, попавших в объединение. Если сложить 7 и 6, три ученика из пересечения A ∩ B будут посчитаны дважды. Поэтому число участников хотя бы одного кружка равно 7 + 6 − 3 = 10.

2. Проверим смысл вычитания. Сначала сложение учитывает всех шахматистов и всех робототехников, включая общих учеников два раза. Вычитая 3, мы оставляем каждого общего участника посчитанным один раз.

3. Чтобы найти тех, кто не посещает кружки, сравним общее число учеников с размером объединения. Из 12 учеников 10 входят в A ∪ B, поэтому вне объединения остаётся 12 − 10 = 2 человека.

Ответ: хотя бы один кружок посещают 10 учеников, ни одного — 2 ученика. В подобных задачах удобно изобразить группы двумя пересекающимися кругами или записать формулу |A ∪ B| = |A| + |B| − |A ∩ B|. Перед ответом проверь, что общие элементы не посчитаны дважды и что число оставшихся учеников неотрицательно.

Типичные ошибки

• Считать, что «или» в логике обязательно означает выбор только одного варианта. Так ошибаются из-за бытового смысла слова, но логическое A ∨ B допускает истинность обоих высказываний. Проверь себя: если A и B одновременно истинны, дизъюнкция тоже истинна.

• Путать объединение и пересечение множеств. Объединение включает элементы хотя бы одного множества, а пересечение — только общие элементы; ошибка возникает, если не перевести знак в слова. Для проверки перечисли элементы каждого множества и отметь, какие попадут в результат.

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

• При подсчёте участников двух групп складывать их количества без поправки на общих участников. Это приводит к повторному учёту элементов пересечения, потому что каждый из них входит в обе группы. Проверь, есть ли общая часть, и вычти её один раз.

Связь с другими темами

Логические операции встречаются в алгоритмах и программах: условие может требовать сразу нескольких проверок или разрешать один из вариантов. Множества помогают упорядочивать данные и описывать группы объектов, например при поиске по нескольким признакам. Графы применяют в задачах на маршруты, сети и отношения между объектами. Все три модели связаны общей идеей: сложную ситуацию можно представить точными элементами и правилами взаимодействия между ними.

Что запомнить

• Логическое высказывание имеет значение «истина» или «ложь»; ∧ означает «и», ∨ — «или», ¬ — отрицание.

• Множество состоит из элементов; объединение собирает элементы групп, пересечение оставляет общие, а разность зависит от порядка множеств.

• Граф состоит из вершин и рёбер; он показывает связи, а путь описывает переход от одной вершины к другой.

• Для решения задачи сначала выбери подходящую модель, затем переведи условие в обозначения и проверь, что результат соответствует смыслу.