Множества и элементы логики

Множества и логика — это «грамматика» математики. На языке множеств записывают решения уравнений и неравенств, области определения и значений функций, события в теории вероятностей. Логика учит точно понимать слова «необходимо», «достаточно», «хотя бы один», «любой», «существует» и делать правильные выводы. Эта тема — также основа задач на подсчёт и методов доказательства.

§1. Понятие множества и обозначения

Множество — совокупность объектов, объединённых по некоторому признаку; эти объекты называются элементами множества. Множество задают двумя способами: перечислением элементов (A = {1, 2, 3}) или характеристическим свойством (B = {x | x² < 9}).

• a ∈ A — элемент a принадлежит A, a ∉ A — не принадлежит.
• ∅ — пустое множество (не содержит ни одного элемента).
• A ⊂ B — каждый элемент A есть и в B (A — подмножество B).
• A = B — одновременно A ⊂ B и B ⊂ A.

Порядок и повторение элементов в множестве не важны: {1, 2, 2, 3} = {3, 1, 2}.
Основные числовые множества: N — натуральные, Z — целые, Q — рациональные, R — действительные числа; N ⊂ Z ⊂ Q ⊂ R. Промежутки — тоже множества: [2; 5) = {x | 2 ≤ x < 5}.

Почему 2ⁿ? Для каждого элемента есть два варианта: входит в подмножество или нет. n независимых выборов дают 2 · 2 · … · 2 = 2ⁿ вариантов.

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

Если пересечение пусто (A ∩ B = ∅), множества называют непересекающимися. Свойства операций похожи на свойства чисел: A ∪ B = B ∪ A, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Законы де Моргана: (A ∪ B)‾ = Ā ∩ B̄, (A ∩ B)‾ = Ā ∪ B̄ — «дополнение объединения есть пересечение дополнений».
Операции с числовыми промежутками выполняют на числовой оси: [1; 5) ∩ (3; 7] = (3; 5), [1; 5) ∪ (3; 7] = [1; 7]. Именно эти операции используются при записи ответа системы неравенств (пересечение) и совокупности (объединение).

Пример

A = {1, 2, 3, 4}, B = {3, 4, 5}. Найдите объединение, пересечение и разность.

1. A ∪ B = {1, 2, 3, 4, 5} — все элементы обоих множеств без повторов.
2. A ∩ B = {3, 4} — общие элементы.
3. A \ B = {1, 2}, B \ A = {5}.

§3. Диаграммы Эйлера–Венна и число элементов

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

Пересечение вычитают потому, что оно посчитано и в n(A), и в n(B), то есть дважды. Для трёх множеств общая часть сначала трижды прибавляется и трижды вычитается, поэтому её прибавляют ещё раз.
Диаграмму удобно заполнять от центра (от части, где пересекается больше всего множеств).

Пример

В классе 30 учеников: 18 изучают английский, 15 — немецкий, 5 не изучают ни одного. Сколько изучают оба языка?

1. Изучают хотя бы один: 30 − 5 = 25.
2. Формула: 25 = 18 + 15 − x.
3. x = 33 − 25 = 8.

Пример

Из 120 студентов 60 ходят в кружок математики, 50 — физики, 40 — химии. Математику и физику посещают 25, математику и химию 20, физику и химию 15, все три — 10. Сколько студентов не ходят ни в один кружок?

1. n(М ∪ Ф ∪ Х) = 60 + 50 + 40 − 25 − 20 − 15 + 10.
2. = 150 − 60 + 10 = 100.
3. Не ходят ни в один: 120 − 100 = 20.

§4. Высказывания и логические операции

Высказывание — повествовательное предложение, которое истинно (И) или ложно (Л). «7 — простое число» — истинное высказывание; а «x > 2» не высказывание, так как x неизвестен (это предикат).

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

Понимайте импликацию как обещание: «Если пойдёт дождь, я возьму зонт». Обещание нарушено, только если дождь пошёл, а зонт не взят. Если дождя нет, что бы вы ни сделали, обещание не нарушено — поэтому Л ⇒ И и Л ⇒ Л истинны.
Де Морган: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B.
Равносильна A ⇒ B контрапозиция ¬B ⇒ ¬A. А обратное утверждение B ⇒ A ей не равносильно.

§5. Кванторы, необходимые и достаточные условия

• ∀ — «для любого», ∃ — «существует».
• При отрицании квантор меняется: ¬(∀x: P(x)) = ∃x: ¬P(x), ¬(∃x: P(x)) = ∀x: ¬P(x).
• Если A ⇒ B истинно: A — достаточное условие для B, B — необходимое условие для A.
• Если A ⇔ B, каждое — необходимое и достаточное условие для другого.

На языке множеств: A ⇒ B означает, что множество, удовлетворяющее A, — подмножество множества для B. Меньшее множество — достаточное условие, большее — необходимое.

Пример

Каким условием является «x > 3» для «x > 1»?

1. Если x > 3, то обязательно x > 1 — значит x > 3 ⇒ x > 1 истинно, условие достаточное.
2. Обратное неверно: при x = 2 x > 1, но не x > 3 — условие не необходимое.
3. Ответ: достаточное, но не необходимое.

§6. Методы доказательства

• Прямое доказательство: от условия через известные факты к выводу.
• Контрапозиция: вместо A ⇒ B доказываем ¬B ⇒ ¬A. Например, «если n² чётно, то n чётно» легко доказать в форме «если n нечётно, то n² нечётно»: (2k + 1)² = 2(2k² + 2k) + 1.
• От противного: предполагаем, что вывод ложен, и приходим к противоречию. Классический пример — доказательство иррациональности √2.
• Контрпример: чтобы опровергнуть утверждение со словом «любой», достаточно одного примера: «все простые числа нечётны» — контрпример 2.

Проверьте себя

1. A = {2, 4, 6, 8}, B = {4, 8, 12}. Найдите A ∩ B.

2. Сколько подмножеств у множества из 5 элементов?

3. Из 40 человек 25 пьют чай, 20 — кофе, 8 — и то и другое. Сколько не пьют ни того, ни другого?

4. Запишите отрицание высказывания «некоторые числа чётны».

5. Каково значение импликации Л ⇒ И?

6. Каким условием является «a делится на 4» для «a чётно»?

7. Найдите [1; 5) ∩ (3; 7].

8. Сколько чисел от 1 до 100 делятся на 2 или на 3?

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

• Дважды учитывать пересечение при объединении.
• Думать, что из ложной посылки всегда следует ложный вывод (Л ⇒ … всегда истинно).
• При отрицании высказывания с квантором отрицать только предикат, не меняя квантор.
• Путать необходимое и достаточное условия.
• Считать из A ⇒ B верным и обратное B ⇒ A.
• При подсчёте подмножеств забывать пустое множество или само множество.