Основы дискретной математики

Original author: Abdulaziz Al Ghannami
  • Translation
  • Tutorial

Привет, хабр. В преддверии старта базового курса "Математика для Data Science" делимся с вами переводом еще одного полезного материала.


Об этой статье

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

ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?

Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.

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

  • Логика

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

  • Отношения

  • Функции

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

  • Графы

ЛОГИКА

Что такое логика?

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

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

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

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

Пусть «голоден» будет посылкой 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 или «Я студент по отношению к моему преподавателю».

 

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

 

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

 

 

ФУНКЦИИ

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

 

 

Свойства

 

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

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

 

 

КОМБИНАТОРИКА

Простыми словами, это наука о счете.

 

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

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

 

Комбинации

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

 

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

 

ГРАФЫ

Что такое граф?

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

 

Если вам понравилась эта статья, приглашаю почитать также мой блог:

www.quantq8.com


Успеть на курс по специальной цене


Читать ещё:

OTUS. Онлайн-образование
Цифровые навыки от ведущих экспертов

Comments 9

    +1
    А это разве ещё не изучают в школе?
      0
      Точно не знаю, но уверен в том, что не все помнят школьную программу)
        0

        Возникает закономерный вопрос, насколько далеко базовый курс «Математика для Data Science» ушёл от школьного курса.

      +4
      Чтобы прочесть надписи на картинках, требуется приложить немалые усилия, но и после этого нет уверенности, что все распарсил правильно. Надо это врачам давать читать в качестве наказания.
        0
        Ахах. Отличная идея. На самом деле это картинки из оригинальной статьи, поэтому повлиять на почерк автора мы, увы, никак не можем
          +2

          Можете, для этого есть LaTeX. Но это дополнительная работа, несомненно.

            0
            Тут скорее вопрос в сохранении авторских иллюстраций. Но на будущее подумаем, конечно, как с этим быть
              0

              Можно и то, и это. Но куча дополнительной работы — это несомненно. Имхо, если действительно есть желание дать хорошие азы, то и некоторые примеры LaTeX можно подробно разобрать, чтобы у людей была возможность записывать себе в блокнот типа Zim.

        0

        А можно "Конкретную математику" прочитать?

        Only users with full accounts can post comments. Log in, please.