Множества и логика
Множество — это набор различных объектов. Логика — правила, по которым из одних утверждений следуют другие. В экзамене эта тема проверяет аккуратность: почти все ошибки здесь от невнимательности, а не от незнания.
Операции над множествами
- Объединение A ∪ B — все элементы обоих множеств; пересечение A ∩ B — только общие.
- Разность A \ B — то, что есть в A и нет в B. Дополнение — все, что вне множества.
- Формула включений: |A ∪ B| = |A| + |B| − |A ∩ B|. Общая часть иначе посчиталась бы дважды.
- У множества из n элементов ровно 2ⁿ подмножеств.
Высказывания
Высказывание либо истинно, либо ложно. Из них строят сложные при помощи связок «и», «или», «если — то», «не».
«Или» в математике включающее: A или B истинно и тогда, когда истинны оба.
- Импликация «если A, то B» ложна ровно в одном случае: A истинно, B ложно.
- Законы де Моргана: не(A и B) = неA или неB; не(A или B) = неA и неB.
Кванторы
«Для любого» и «существует» меняются местами при отрицании: отрицание «все кошки серые» — это не «все кошки не серые», а «существует несерая кошка».
Чтобы опровергнуть утверждение со словом «все», достаточно одного контрпримера.
Разобранный пример
В классе 30 человек. Английский учат 18, китайский — 15, оба языка — 7. Сколько человек не учат ни одного из этих языков?
- Учат хотя бы один язык: |A ∪ B| = 18 + 15 − 7 = 26.
- Не учат ни одного: 30 − 26 = 4.
4 человека. Если сложить 18 и 15 без вычитания пересечения, получится 33 — больше, чем весь класс: это и есть сигнал об ошибке.
Что помнить
- Пересечение вычитают один раз, иначе оно посчитано дважды.
- «Или» включающее, «если — то» ложно только в одном случае.
- Отрицание «для всех» — это «существует».
- Пустое множество — подмножество любого.