теория множеств

1.

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

2. Теория множеств

Раздел математики, в котором изучаются общие
свойства множеств — совокупностей элементов
произвольной природы, обладающих каким-либо общим
свойством. Создана во второй половине XIX
века Георгом Кантором.
Привнесла в математику новое понимание
природы бесконечности, была обнаружена глубокая связь
теории с формальной логикой, однако уже в конце XIX —
начале XX века теория столкнулась со значительными
сложностями в виде возникающих парадоксов, поэтому
изначальная форма теории известна как наивная теория
множеств.

3. Математическая логика

Раздел математики, который изучает вопросы
применения математических методов для
решения логических схем, которые лежат в
основе построения компьютера.
Суждения в математической логике называют
высказываниями или логическими выражениями.

4. Высказывания и операции над ними

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

5.

Классический пример утверждения, НЕ
являющегося высказыванием, таков:
Всё, что написано в этой рамке, есть ложь.

6.

Действительно, попытка определить
истинностное значение этого «высказывания»
приводит к противоречию: если то, что
написано, истинно, то это противоречит
смыслу слов в рамке. То же противоречие
возникает, если предположить, что оно ложно.
Вопросительные, повелительные и
бессмысленные предложения не являются
логическими высказываниями. Говорят, что
если предложение истинно, то его значение
истинности равно 1, если ложно — то 0.

7. Отрицание. Логическая связка «не»

Отрицанием (инверсией) высказывания A называется
высказывание, которое истинно, если высказывание A
ഥ или
ложно, и ложно, когда A истинно. Записывается: А
¬A. Читается: «не A» («не верно, что A»).
Операция меняет значение выражения (истинное значение
становится ложным, а ложное значение — истинным).
Отметим, что отрицание является логической операцией,
выполняемой над одним аргументом.

8. Отрицание. Логическая связка «не»

Эта логическая связка может быть
проиллюстрирована следующей таблицей (таблицей
истинности):

9. Конъюнкция. Логическое умножение

Конъюнкция двух высказываний A и B — это
сложное логическое высказывание, которое
истинно только в случае истинности всех
составляющих высказываний, в противном
случае оно ложно. Обозначения: A & B, A ^ B.
Читается: «A и B».

10. Конъюнкция. Логическое умножение

Эта логическая связка может быть также
проиллюстрирована таблицей истинности, в которой
показаны значения истинности сложного высказывания в
зависимости от значений истинности составляющих его
простых высказываний A и B.

11. Дизъюнкция. Логическое сложение

Дизъюнкция двух высказываний A и B — это сложное
логическое высказывание, которое ложно только в
случае ложности всех составляющих высказываний,
в противном случае оно истинно. Таким образом,
это высказывание считается истинным, когда
истинно хотя бы одно из составляющих
высказываний. Обозначается: A ∨ B. Иногда
встречается обозначение A + B. Читается: « A или
B».

12. Дизъюнкция. Логическое сложение

Дизъюнкция иллюстрируется следующей таблицей
истинности:

13. Импликация. Логическое следование

В математических доказательствах часто пользуются
сложными высказываниями, образованными с помощью слов
«если…, то…». Здесь высказывание, расположенное после
слова «если», называется основанием или посылкой, а
высказывание, расположенное после слова «то»,
называется следствием или заключением. Импликацией
двух высказываний A и B называется высказывание,
обозначаемое символом A → B, которое ложно тогда и
только тогда, когда A истинно, а B ложно. Иногда
встречается обозначение A ⊃ B . Читается: «если A, то
B» («из A следует B»).

14. Импликация. Логическое следование

Импликация проиллюстрирована таблицей истинности:

15. Эквиваленция. Логическое тождество

Эквиваленцией (эквивалентностью,
равнозначностью) двух высказываний A и B
называется высказывание, обозначаемое
символом A ~ B (или A
B), которое истинно
когда истинностные значения высказываний A и
B совпадают, и ложно — в противном случае

16. Эквиваленция. Логическое тождество

Таблица истинности для эквивалентности имеет
вид:

17. Неравнозначность. Исключающее «или»

Неравнозначностью двух высказываний A и B
называется высказывание, истинное, когда
истинностные значения A и B не совпадают, и
ложное — в противном случае. Обозначается:
A ⊕ B. Читается: «либо A, либо B»
(понимается — в разделительном смысле).

18. Неравнозначность. Исключающее «или»

Таблица истинности для неравнозначности имеет
вид:

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

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

20. Формулы алгебры высказываний

Логическая формула определяется индуктивно по
следующей схеме:
1) Всякая пропозициональная переменная есть формула.
2) Если A — формула, то и ¬ A является формулой.
3) Если A и B — формулы, то выражения (A & B), (А∨В),
(А → В), (A ~ B), (А ⊕ В) также являются формулами.
4) Других формул, кроме построенных по правилам трех
предыдущих пунктов, нет.

21. Формулы алгебры высказываний

Определение формулы таково, что формулы насыщены
скобками и трудночитаемы, поэтому обычно принимают
соглашение об упрощении записи формул:
1) Наружные скобки в записи формул можно опускать.
2) Считается, что конъюнкция «сильнее» дизъюнкции, а
обе они «сильнее» неравнозначности, импликации и
эквиваленции. Отрицание «сильнее» всех других
операций. Поэтому часть скобок, определяющих порядок
действий, можно опускать.

22. Формулы алгебры высказываний

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

23. Представить сложное высказывание логической формулой. «Если допоздна работаешь с компьютером и при этом пьешь много кофе, то

утром просыпаешься в дурном
настроении или с головной болью».

24. Составьте таблицу истинности логического выражения

F = (A ∧ B) ∨ A

25. Составьте таблицу истинности логического выражения

ഥ ∨ (B ∨ С)
F = А

26. Составьте таблицу истинности логического выражения

27. Комбинаторика

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

28. Комбинаторика

Возможности комбинаторики широко
используются при построении алгоритмов в
науке о данных и в классическом
программировании. Поиск оптимального
маршрута в «Яндекс Картах», рекомендации
товаров в интернет-магазинах, расчёт цепочек
поставок — во всех этих алгоритмах
присутствует комбинаторика.

29. Основные понятия

1.
Множество — это набор элементов, которые мы перебираем.
Например, в случае с паролем это были цифры и буквы
латинского алфавита — всего 62 символа.
2.
Выбор — это действие, при котором мы из множества
достаём какие-то составляющие. Например, в случае с
паролем можно выбрать символы i, C, 5, K, x, k, 0, w.
3.
Расположение — это действие, при котором мы расставляем
выбранные элементы в определённом порядке. Например,
Cxi0kK5w или kxw0C5iK.
4.
Факториал — это математическая функция, с помощью
которой мы перемножаем все числа от 1 до какого-то
числа. Факториал обозначается восклицательным знаком.
Например, 5! = 1 * 2 * 3 * 4 * 5 = 120.

30.

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

31. Сложение

Сложение используется тогда, когда мы выбираем
элемент из нескольких пересекающихся подмножеств.
Правило сложения:
Если элемент