Элементы комбинаторики, теории множеств и математической логики (2)

1. Элементы комбинаторики, теории множеств и математической логики

2. Алгебра логики и теория множеств

• Высказывание – это утверждение, о котором можно однозначно сказать, истинно
оно или ложно.
• Примеры:
• «5 > 2» - истинное высказывание.
• «Москва - столица Франции» - ложное высказывание.
• «x + 2 = 5» - не является высказыванием, пока не указано значение переменной.
Истинность высказываний обозначается:
• 1 (И) - истина;
• 0 (Л) - ложь.

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

• Инверсия (¬, НЕ, NOT)
• ¬A = 1, если A = 0;
• ¬A = 0, если A = 1.
• Конъюнкция (∧, И, AND)
• A ∧ B = 1, только если A = 1 и B = 1.
• Эквиваленция (↔, тогда и
только тогда, EQUIV)
• A ↔ B = 1, если A и B
одинаковы (оба 1 или оба 0).
• Дизъюнкция (∨, ИЛИ, OR)
• A ∨ B = 1, если хотя бы одно из
A или B истинно.
• Импликация (→, ЕСЛИ…ТО)
• A → B = 0, только если A = 1, а
B = 0.
• В остальных случаях A → B =
1.

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

Символ
Название
Читается как
Смысл
¬
Инверсия
НЕ
Меняет истину на ложь и
наоборот
∧
Конъюнкция
И
Истина, если оба
истинны
∨
Дизъюнкция
ИЛИ
Истина, если хотя бы
одно истинно
→
Импликация
ЕСЛИ…ТО
Ложь только при 1→0
↔
Эквиваленция
ТОГДА И ТОЛЬКО
ТОГДА
Истина, если оба
одинаковы

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

• Конъюнкция - логическая операция, ставящая в соответствие каждым двум
высказываниям новое высказывание, являющееся истинным тогда и только
тогда, когда оба исходных высказывания истинны.
Для записи конъюнкции используются следующие знаки: ∧ , •, И, &.
Например: А ∧ В, А • В, А И В, А & B.
• Иначе конъюнкцию называют логическим умножением

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

• Дизъюнкция - логическая операция, которая каждым двум высказываниям
ставит в соответствие новое высказывание, являющееся ложным тогда и
только тогда, когда оба исходных высказывания ложны.
• Для записи дизъюнкции используются следующие знаки: ∨ , |, ИЛИ, +.
Например: A∨ B, А|В, А ИЛИ Б, А+Б.
• Иначе дизъюнкцию называют логическим сложением.

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

• Инверсия - логическая операция, которая каждому высказыванию ставит в
соответствие новое высказывание, значение которого противоположно
исходному.
• Для записи инверсии используются следующие знаки: НЕ, ¬, ‾. Например: НЕ
А, ¬А.
• Инверсию иначе называют логическим отрицание

8. Понятие множества

• Множество - это группа объектов, собранных вместе по какому-то признаку.
• Элементы множества обозначают фигурными скобками:
• Множество гласных букв: {а, о, у, е, и}.
• Множество чётных чисел меньше 10: {2, 4, 6, 8}.

9. Мощность множества

• Мощность множества - это количество элементов в нём.
• Обозначается |A|.
• Пример:
• A = {1, 2, 3, 4} → |A| = 4.
• B = ∅ (пустое множество) → |B| = 0.

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

• Объединение (A ∪ B) – все элементы, которые есть в A или в B.
• Пример: A = {1,2,3}, B = {3,4,5} → A ∪ B = {1,2,3,4,5}.
• Это аналог «ИЛИ».
• Пересечение (A ∩ B) – только те элементы, которые есть и там, и там.
• Пример: A = {1,2,3}, B = {3,4,5} → A ∩ B = {3}.
• Это аналог «И».

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

• Разность (A \ B) – элементы из A, которых нет в B.
• Пример: A = {1,2,3}, B = {3,4} → A \ B = {1,2}.
• Дополнение (Ā) – всё, что не принадлежит множеству A (берётся относительно
«универсального множества» U – всех возможных объектов задачи).
• Пример: U = {1,2,3,4,5}, A = {1,2} → Ā = {3,4,5}.
• Это аналог «НЕ».

12. Графический метод алгебры логики

• Для наглядного решения логических задач используют диаграммы Эйлера-
Венна.
• Каждый круг изображает множество.
• Пересечение кругов - логическая операция «И».
• Объединение кругов - логическая операция «ИЛИ».
• Область вне круга - операция «НЕ».

13. Решение логических задач графическим способом

• Алгоритм:
• Определяем множества (например: «А – кто любит математику», «B – кто
любит спорт»).
• Рисуем круги (A, B).
• Переводим условие в операции над множествами (∪, ∩, , ¬).
• Закрашиваем нужные области.
• Считаем элементы

14. Пример задачи

• В классе 25 учеников:
• 12 любят математику (множество A),
• 10 – физику (множество B),
• 5 любят и математику, и физику.
Вопрос: Сколько учеников любят только математику?
• Решение:
• Из 12 математиков 5 любят и физику → только математику любят 12 – 5 = 7.
• На диаграмме Венна это область A без пересечения с B.

15. Пример задачи

• В университете 100 студентов.
• 40 учат английский (A),
• 30 учат немецкий (B),
• 20 учат оба языка.
Сколько учат хотя бы один язык?

16. Пример задачи

• Нужно найти сколько учат хотя бы один язык.
Это означает, что нам нужны все студенты, которые входят в A или в B, то есть
объединение множеств A и B:
• Чтобы посчитать |A ∪ B|, используем правило:
• ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
• Почему так?
• Если сложить |A| и |B|, то студенты, которые учат оба языка, попадут дважды
(один раз в A, один раз в B).
• Поэтому мы один раз вычитаем пересечение |A ∩ B|.

17. Пример задачи

• Подставляем числа
∣A∪B∣=40+30−20=50
• Значит, всего 50 студентов учат хотя бы один язык.
На диаграмме Венна:
• Один круг = множество A (английский).
• Второй круг = множество B (немецкий).
• Если нужно «хотя бы один язык», то это все студенты из A и все из B.
• Значит, закрашиваем оба круга полностью (включая пересечение).

18. Пример задачи

• В образовательном центре открыли три класса: физико-математический (27)
• Соц.-гум (32), хим-био (22). Всего в центре учится 70 учеников.
• В физ-мат – 10 детей из соц-гум
• В соц-гум – 6 детей из хим-био
• В физ-мат – 8 детей из хим-био
• 3 ребенка из хим-био были и в физ-мате и в соц-гуме
• Сколько детей учатся только в физ-мате, только в соц-гуме и только в хим-био?
• Сколько ребят не учатся в физ-мате, соц-гуме и хим-био

19. Пример задачи

• Только футбол:
• ∣A∣−∣A∩B∣=28−12=16
• Только баскетбол:
• ∣B∣−∣A∩B∣=20−12=8
• Хотя бы одна игра (объединение):
• ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣=28+20−12=36
• Не играют ни в одну игру:
• Всего−∣A∪B∣=50−36=14

20. Домашнее задание

• В летнем лагере 70 ребят. Из них 27 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются
спортом. В драмкружке 10 ребят из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов, 3
спортсмена посещают и драмкружок и хор. Сколько ребят не поют в хоре, не увлекаются
спортом и не занимаются в драмкружке?