Русский
Русский
English
Статистика
Реклама

Дискретная математика

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

24.11.2020 12:18:29 | Автор: admin

Привет, хабр. В преддверии старта базового курса "Математика для 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


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


Читать ещё:

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru