Об этой статье Эта статья содержит лишь малую часть информации по заявленной теме. Рассматривайте ее как вводный курс перед началом всестороннего изучения предмета. Надеюсь, вы найдете в ней полезную информацию. Знание дискретной математики помогает описывать объекты и задачи в информатике, особенно когда дело касается алгоритмов, языков программирования, баз данных и криптографии. В дальнейшем я планирую подробнее раскрыть темы, затронутые в этой статье. Приятного чтения!

 

ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА? Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.

 

Мы рассмотрим пять основных разделов в следующем порядке.

 

Логика

 

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

 

Отношения

 

Функции

 

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

 

Графы

 

ЛОГИКА Что такое логика?

 

Это наука о корректных рассуждениях. Мы будем использовать приемы идеализации и формализации. Неформальная логика изучает использование аргументов в естественном языке.

 

Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).

 

Начнем с азов. Рассмотрим следующее высказывание на естественном языке:

 

«Если я голоден, я ем».

 

Пусть «голоден» будет посылкой A, а «ем» — следствием B. Попробуем формализовать:

 

A => B (то есть из A следует B)

 

NB. Посылка и следствие являются суждениями.

 

Логические выражения

 

Для нас важна форма, а НЕ содержание. Значение будет истинным, если оно соответствует форме.

 

Например, 10 < 4 — ЛОЖЬ, а 10 > 4 — ИСТИНА.

 

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

 

Суждение P — это утверждение, которое может быть как истинным, так и ложным.

 

Обозначим истинное значение P единицей (1), а ложное значение P нулем (0).

 

Существует другое суждение; обозначим истинное значение Q единицей (1), а ложное значение Q нулем (0).

 

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

 

Отрицание

 

 

 

  ИЛИ

 

 

 

  И

 

 

 

  Эквивалентность

 

 

 

  Импликация

 

 

 

  Исключающее ИЛИ

 

 

 

  Три закона

 

Теперь введем суждение R — утверждение, которое может быть как истинным, так и ложным.

 

Обозначим истинное значение R единицей (1), а ложное значение R нулем (0).

 

Закон ассоциативности

 

 

 

  Закон дистрибутивности

 

 

 

  Законы де Моргана

 

 

 

  Логическая формула

 

Включает суждения, выражения в скобках и следующие символы:

 

 

 

   

 

  Квантификаторы

 

Что такое квантификатор? Квантификатор в естественном языке — это слово, которое используется для обозначения количественных отношений (сколько). Например: все, несколько, много, мало, большинство и нисколько.

 

 

 

  ТЕОРИЯ МНОЖЕСТВ Что такое множество?

 

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

 

Например, если A = {1, 2, 3, 4} и B = {2, 4, 1, 3} и порядок неважен, то A = B

 

Разобравшись в этом, мы можем дать более точное определение множества — это коллекция различных, строго определенных объектов.

 

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

 

 

 

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

 

Подмножество

 

 

 

  Количество элементов

 

 

 

  Объединение

 

 

 

  Пересечение

 

 

 

  Дополнение

 

 

 

  ОТНОШЕНИЯ Логика отношений изучает отношения между математическими объектами. Мы можем установить связь с N элементами (где N — положительное натуральное число).

 

Бинарное отношение — это отношение между двумя элементами (объектами). Формально мы можем записать любое отношение между x и y так: x ~ y

 

Например, 4 < 8 или «Я студент по отношению к моему преподавателю».

 

 

 

  Свойства бинарных отношений

 

 

 

  Числовые множества

 

 

 

   

 

  ФУНКЦИИ Функция — это отношение, которое присваивает переменным новые значения. То есть это отношение между множеством А и множеством В.

 

 

 

   

 

  Свойства

 

 

 

  Функциональная композиция

 

Это точечное использование функции, результатом которого является другая функция.

 

 

 

   

 

  КОМБИНАТОРИКА Простыми словами, это наука о счете.

 

 

 

  Перестановки

 

Это упорядочение уникальных объектов, при котором важен порядок следования.

 

 

 

  Комбинации

 

Это упорядочение уникальных объектов, при котором не важен порядок следования.

 

 

 

  Блок-схема алгоритма

 

 

 

  ГРАФЫ Что такое граф?

 

Это коллекция точек, которые называются узлами или вершинами, и линий между этими точками, которые называются ребрами. Ребро соединяет только два узла. Ребро может быть ориентированным, если ему присвоено направление, или неориентированным.