элементы дискретной математики в системе профильного обучения математике

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

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

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

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

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

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

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

ЛОГИКА

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

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

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

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

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

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

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

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

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

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

Например, 10 4 — ИСТИНА.

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

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

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

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

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

Источник

Элементы дискретной математики: конспект лекций (стр. 1 )

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5 6 7 8 9

учебно-методической комиссией филиала ЮУрГУ в г. Златоусте

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

Предназначен для студентов технических университетов, обучающихся по направлению «Информатика и вычислительная техника».

ã Издательство ЮУрГУ, 2008

ВВЕДЕНИЕ

Дискретная математика или дискретный анализ – сравнительно новое направление в математике, объединяющее отдельные её разделы, ранее сформированные как самостоятельные теории. К ним относятся математическая логика и теории множеств, графов, кодирования, автоматов.

Дискретной математикой называют совокупность математических дисциплин, изучающих свойства абстрактных дискретных объектов, т. е. свойства математических моделей объектов, процессов, зависимостей, существующих в реальном мире, которыми оперируют в различных областях знаний. Таким образом, дискретный анализ – самостоятельный раздел современной математики, изучающий свойства различных структур, имеющих конечный характер. Они могут возникать как в самой математике, так и в её приложениях. К их числу принято относить объекты, имеющие прерывный (дискретный) характер в отличие от объектов, изучаемых классической математикой и носящих непрерывный характер.

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

XXI в. называют веком информатизации, когда основной объём информации хранится в памяти ЭВМ. Любому человеку, стремящемуся ею воспользоваться, необходимо освоить азы «безбумажной информатики». Применение ЭВМ для комплексной автоматизации информационной деятельности принципиально изменило характер взаимоотношений человека и машины. Если раньше компьютер осваивали только те, кто непосредственно его обслуживал: программисты, электронщики, операторы, то в XXI в. без машинной обработки информации не обойдется ни одна отрасль деятельности.

В последнее время раздел математики, называемый «Дискретный анализ», всё чаще вводится в программы подготовки не только математиков, инженеров, программистов, но даже юристов. Интерес к этой дисциплине не случаен, так как потребность в знаниях этой области математики объясняется широким кругом её применения: электроника и информатика, вопросы оптимизации и принятия решений.

Методы, разрабатываемые дискретной математикой, используются в различных областях знаний. Так, теоретическая информатика (или теоретическая кибернетика) использует математические методы для построения и изучения моделей обработки, передачи и использования информации. Объекты её изучения – дискретные множества. Теоретическая информатика является как поставщиком задач, так и потребителем методов дискретной математики.

Теория автоматов разрабатывает методы, с помощью которых можно на основе моделей логического типа изучать процессы, протекающие в самой машине во время её работы. Для работы на компьютере информацию представляют в дискретной форме, позволяющей переводить её в программы, понятные ЭВМ.

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

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

Теория массового обслуживания изучает широкий класс моделей передачи и переработки информации в системах массового обслуживания (СМО).

Имитационное моделирование – наука, в которой создаются и используются специальные приемы воспроизведения процессов, протекающих в реальных объектах, в тех моделях этих объектов, которые реализуются в вычислительных машинах.

Теория принятия решений изучает общие схемы, используемые при выборе решения из альтернативных возможностей (в условиях неопределенности).

Теория игр изучает модели, в которых выбор происходит в условиях конфликта или противоборства.

Математическое программирование рассматривает проблемы принятия оптимальных решений с помощью математического аппарата.

Искусственный интеллект – одно из молодых и перспективных направлений информатики, появившееся во второй половине XX в. на базе вычислительной техники, математической логики, программирования, психологии, лингвистики и других отраслей знаний. Объектами его изучения являются межпредметные процедуры (метапроцедуры), используемые при решении задач, традиционно называемых интеллектуальными. Проникая в тайны творческой деятельности людей, искусственный интеллект создает программные и программно-аппаратные модели таких метапроцедур.

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

Для нас представляют интерес все эти направления современной информатики. Теперь мы сможем осознать место дискретной математики в системе знаний, необходимых для тех, кто связал свою жизнь с компьютером.

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

Глава 1. МНОЖЕСТВА И ОТНОШЕНИЯ

1.1. Множества

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

Множества обозначаются большими буквами. Например, A, B, C, X, N и т. д. Если объект a является элементом множества A, то говорят, что a принадлежит A. Это записывается, как . Запись будет означать, что a не является элементом A.

Множества как объекты могут быть элементами других множеств. Множества, элементами которых являются другие множества, называются классом или семейством.

Множество, не содержащее элементов, называется пустым и обозначается .

1.2. Задание множеств

Чтобы задать множество, нужно указать, какие элементы ему принадлежат. Это можно сделать разными способами:

­ перечислением М элементов: ;

­ характеристическим предикатом: ;

­ порождающей процедурой: .

Перечисление задается в фигурных скобках, через запятую.

Здесь и далее фигурными скобками будем обозначать множество, в котором не играет роли порядок следования элементов, и круглыми скобками последовательность, в которой порядок следования элементов важен. Угловыми скобками будем обозначать совокупности элементов, имеющие неоднородную математическую природу (структуру), например, в графе имеем два вида элементов – вершины и дуги (пары) этих элементов ().

Характеристический предикат – это некоторое условие, выраженное в форме логического утверждения. Если для данного элемента условие выполнено, то оно принадлежит определённому множеству. В противном случае – не принадлежит.

Порождающая процедура – это процедура, которая, будучи запущенной, порождает некоторые объекты, являющиеся элементами определённого множества.

Пример: .

.

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

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

Рис. 1.1. Иллюстрация кругами Эйлера

Будем также использовать символы вместо слов «для любых х», «каждый элемент х» и вместо слов «существует х».

Множество A содержится во множестве B (множество B включает в себя множество A), если каждый элемент A принадлежит также и B (рис 1.1 б):

В этом случае A называется подмножеством B, а B – надмножеством A.

Если и , то A называется собственным подмножеством B.

Два множества равны, если они являются подмножествами друг друга, т. е..

Мощность множества обозначается как |М|. Для конечных множеств мощность – это число элементов. Например, , но .

Если А=В, то множества A и B называются равномощными.

Пример. Множество решений (корней) уравнения , т. е. . Множество простых чисел, меньших пяти . Следовательно, А=В.

Для некоторых числовых множеств приняты стандартные обозначения:

N – множество натуральных чисел ;

Z – множество целых чисел ;

Q – множество рациональных чисел ;

R – множество действительных чисел;

C – множество комплексных чисел.

Тогда и т. д.

Если в множестве A найдется хотя бы один элемент, не принадлежащий B, то A не является подмножеством B, т. е. .

Например, интервал не является подмножеством промежутка , так как , но .

Из определения следует, что любое множество является подмножеством самого себя, т. е. справедливо утверждение . Полагают, что Æ является подмножеством любого множества.

Пример. Рассмотрим множество, состоящее из трех элементов: . Найдем все его подмножества:

а) пустое ;

б) по одному

в) по два

г) по три .

Число всех подмножеств составляет 8=23. Если множество состоит из n элементов, то число всех подмножеств равно 2n. Или булеан |2М|=2|М|.

Множество, состоящее из всех элементов, принадлежащих и множеству A, и множеству B, называется пересечением и обозначается .

.

Пример: .

Если же множества A и B не имеют общих элементов, то их пересечением является пустое множество, то есть . Например, пересечение множества четных чисел с множеством нечетных.

Пересечение пустого множества с любым множеством – пустое множество: .

1. Коммутативность (переместительное свойство). По аналогии с а+b=b+a

.

2. Ассоциативность. По аналогии с

.

3. Свойство нуля. По аналогии с

.

4. Идемпотентность (аналогии нет)

.

5. Дистрибутивность. По аналогии с

;

6. Свойство единицы.

Если задан универсум U и любые , то можно записать: (рис. 1.2 а); (рис. 1.2 б).

Множество, состоящее из всех элементов, принадлежащих или множеству A, или множеству B, называется объединением множеств. Обозначается так: .

Пример. Даны множества и . Их объединением будет .

Даны числовые промежутки (рис. 1.3). Их объединением будет .

Объединение и пересечение множеств хорошо иллюстрируются на плоскости (рис. 1.4). При этом множества изображаются кругами или прямоугольниками.

Свойства объединения множеств можно сравнить со свойствами сложения чисел. Проведем аналогию этих свойств.

1. Коммутативность (переместительное свойство). По аналогии с

.

2. Ассоциативность. По аналогии с

.

3. Свойство нуля. По аналогии с

.

4. Идемпотентность (аналогии нет)

.

5. Дистрибутивность. По аналогии с

.

Рис. 1.3. Множества точек отрезков

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

Записывается так: .

Геометрическое представление разности множеств на рис. 1.5.

Симметричная разность (рис. 1.6):

;

.

Рис. 1.5. Разность множеств Рис. 1.6. Симметричная разность

Дополнение множеств (рис. 1.7):

;

.

Свойства дополнения :

1) ; 4) ;

2) ; 5) ;

3) ; 6) .

Пример. Рассмотрим операцию дополнения множества, являющегося пересечением множеств A и B. Её результат совпадает с объединением дополнений этих множеств, (свойство 6) ; в этом можно убедиться с помощью диаграмм Эйлера – Венна (рис. 1.8).

Рис. 1.8. Геометрическая иллюстрация свойства 6

Декартово произведение множеств

Пусть A – конечное множество, состоящее из n элементов. Кортежем длины n элементов множества A называется упорядоченная последовательность (а1, а2, …, аn) элементов этого множества.

Из двух данных кортежей (а1, а2, …, ai, …, аk), где , длины k и (b1, b2, …, bj, …, bm), где , длины m можно составить новый кортеж длиной , элементы которого (а1, а2, …, аk, b1, b2, …, bm) принадлежат множеству . Эта операция называется соединением кортежей. Кортеж можно образовать двумя способами, поэтому важно, какой кортеж назван первым. Так, соединив кортежи четных и нечетных однозначных чисел и , получим кортеж всех однозначных чисел .

Пусть A – конечное множество, элементами которого являются некоторые символы, например цифры, буквы, знаки препинания. Такие множества принято называть алфавитом над заданным множеством символов. Алфавит есть кортеж попарно различимых символов, называемых буквами алфавита. Элементы множества An принято называть словами длины n в алфавите A. Слово над алфавитом есть просто некоторая конечная последовательность символов. Так, шестизначный телефонный номер является словом длины 6 над алфавитом цифр .

Рассмотрим множество B, состоящее из двух элементов: 0 и 1. Кортежи длины m из этих элементов обозначим Bm. Тогда . Такие кортежи называют упорядоченными наборами или векторами. Они имеют широкое применение в дискретной математике.

Вектор из нулей и единиц можно рассматривать как двоичное представление натурального числа.

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

Пусть заданы множества . Декартовым произведением этих множеств называется множество , состоящее из всех кортежей длины n, в которых , где . Поскольку для задания кортежа важен порядок, то порядок множителей важен и в декартовом произведении.

Например, декартовым произведением множеств и будет являться множество пар . Скобки для указания пар опускают там, где это не может привести к затруднениям: . Если множества А:= и В:= конечны, то их декартово произведение может быть представлено в общем виде таблицей из m столбцов и k строк (рис. 1.9).

Источник