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

Вопросы к теме

1. Основы теории множеств.

2. Элементы математической логики.

Краткие теоретические сведения

Основы теории множеств

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

Пример: Множество S страниц в данной методичке. Множество натуральных чисел Множество простых чисел Множество целых чисел: Множество R вещественных чисел. Множество A различных символов на этой странице.

Если объект является элементом множества , то говорят, что (Обозначение: ). В противном случае говорят, что (Обозначение: ).

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

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

Обозначение:

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

Это можно сделать различными способами:

перечисление элементов: (обозначения элементов обычно заключают в фигурные скобки и разделяются запятыми);

характеристическим предикатом: (это некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение: если для данного элемента условие выполнено, то он принадлежит определенному множеству, в противном случае – не принадлежит);

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

Примеры: 1. ;

2. &

Перечислением можно задавать только конечные множества. Бесконечные множества задаются характеристическим предикатом или порождающей процедурой.

Множество целых чисел в диапазоне от m до n обозначается так: m…n. То есть ;

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

В этом случае называется подмножеством , - надмножеством . Если и , то называется собственным подмножеством .

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

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

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

- объединение : ;

- персечение : & ;

- разность : & ;

- симметрическаяразность :

- дополнение : .

Операция дополнения подразумевает универсум .

Пример: Пусть .

Тогда

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

Свойства операций над множествами :

Пусть задан универсум . Тогда выполняются следующие свойства.

1. идемпотентность: ;

2. коммутативность: ;

3. ассоциативность: ;

 

4. дистрибутивность:

5. поглощение: ;

6. свойство нуля: ;

7. свойство единицы: ;

8. инволютивность: ;

9. законы Моргана: ;

10. свойства дополнения: ;

11. выражение для разности: .

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

Элементы математической логики (алгебры логики)

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

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

О предметах можно судить верно или неверно, то есть высказывание может быть истинным ( обозначается 1 ) или ложным ( обозначается 0).

Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание, состоящее из простых высказываний, называется составным (сложным).

Например, А = {Аристотель – основоположник логики}

В = {Лондон – столица Парижа}

Таким образом, А = 1, В = 0.

Составные высказывания на естественном языке образуются с помощью союзов, которые в алгебре логики заменяются на логические операции. Логические операции задаются таблицами истинности и могут быть графически проиллюстрированы с помощью диаграмм Эйлера-Венна.

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

1. Конъюнкция (логическое умножение)

· в естественном языке соответствует союзу И;

· обозначается & или

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

Диаграмма Эйлера-Венна соответствует пересечению множеств.

Таблица истинности

А	В	А&В

 

2. Дизъюнкция (логическое сложение)

· в естественном языке соответствует союзу ИЛИ;

· обозначается

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

Диаграмма Эйлера-Венна соответствует объединению множеств.

 

 

Таблица истинности

А	В	А В

 

3. Инверсия (отрицание)

· в естественном языке соответствует словам НЕВЕРНО, ЧТО… и частице НЕ;

· обозначается

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

Таблица истинности

А

Диаграмма Эйлера-Венна

 

4. Импликация (логическое следование)

· в естественном языке соответствует обороту ЕСЛИ …, ТО…

· обозначение

Импликация – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

 

Таблица истинности

А	В	А В

 

5. Эквиваленция (равнозначность)

· в естественном языке соответствует обороту ТОГДА И ТОЛЬКО ТОГДА, КОГДА…

· обозначение

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

Таблица истинности

А	В	А В

Последовательности и ряды

Вопросы к теме

1. Числовые ряды Знакопеременные ряды.

2. Степенные ряды.

3. Признаки сходимости ряда

Краткие теоретические сведения

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

Суммы

Составленные из первых членов ряда, называются частными суммами этого ряда.

Каждому ряду можно сопоставить последовательность частичных сумм . Если при бесконечном возрастании номера частичная сумма ряда стремится к пределу , то ряд называется сходящимся, а число - суммой сходящегося ряда, т.е. или . Эта запись равносильна записи .

Если частичная сумма ряда при неограниченном возрастании не имеет конечного предела (в частности, стремится к или ), то такой ряд называется расходящимся.

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

Разность называется остатком ряда. Если ряд сходится, то его остаток стремится к нулю, т.е. , и наоборот, если остаток стремится к нулю, то ряд сходится.

Пример: записать ряд по его заданному общему члену .

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

Пример: записать ряд по его заданному общему члену .

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

Пример: записать ряд по его заданному общему члену .

Полагая и учитывая, что , получим ряд .

Пример: найти - й член ряда по его данным первым членам .

Знаменатели членов ряда, начиная с третьего, являются нечетными числами; следовательно, - й член ряда имеет вид .

Пример: найти - й член ряда по его данным первым членам .

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

Пример: найти - й член ряда по его данным первым членам .

Числители членов ряда образуют натуральный ряд чисел, а соответствующие им знаменатели – натуральный ряд чисел, начиная с . Знаки чередуются по закону или по закону . Значит - й член ряда имеет вид или .

Пример: найти сумму членов ряда .

Находим частичные суммы членов ряда:

Запишем последовательность частичных сумм: . Общий член этой последовательности есть . Следовательно, . Последовательность частичных сумм имеет предел, равный . Итак, ряд сходится и его сумма равна .

Необходимый признак сходимости ряда

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

Если , то ряд расходится – это достаточный признак расходимости ряда.

Пример: Исследовать сходимость ряда, применяя необходимый признак сходимости .

Находим . Необходимый признак сходимости ряда выполняется.

Пример: Исследовать сходимость ряда, применяя необходимый признак сходимости .

Имеем . Здесь выполняется достаточный признак расходимости ряда; следовательно, ряд расходится.

Пример: Исследовать сходимость ряда, применяя необходимый признак сходимости .

Находим . Необходимый признак сходимости ряда выполняется.

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

Признак Даламбера: Если для ряда с положительными членами выполняется условие , то ряд сходится при и расходится при .

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

Пример: Исследовать сходимость ряда, используя признак Даламбера

Подставив в общий член ряда вместо n число n+1, получим . Найдем предел отношения (n+1) –го члена к n –му члену при n :

. Следовательно, данный ряд сходится.

Числовые последовательности

Под числовой последовательностью понимается функция заданная на множестве натуральных чисел. Кратко последовательность обозначается в виде или . Число называется первым членом (элементом) последовательности, - вторым, …, - общим или -м членом последовательности.

Чаще всего последовательность задается формулой его общего члена. Формула позволяет вычислить любой член последовательности по номеру .

Так, равенства

Задают соответственно последовательности

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

Последовательность называется возрастающей (неубывающей), если для любого выполняется неравенство . Аналогично определяется убывающая (невозрастающая) последовательность.

Все эти последовательности называются монотонными последовательностями. Последовательности , и монотонные, а - не монотонная.

Если все элементы последовательности равны одному и тому же числу , то ее называют постоянной.

Другой способ задания числовых последовательностей – рекуррентный способ. В нем задается начальный элемент (первый член последовательности) и правило определения -го элемента по -му: . Таким образом, , и т.д. При таком способе задания последовательности для определения -го члена надо сначала посчитать все предыдущих.

Степенные ряды

Степенным рядом называется ряд вида , где числа называются коэффициентами ряда, а член - общим членом ряда.

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

Число называется радиусом сходимости степенного ряда, если при ряд сходится и при том абсолютно, а при ряд расходится.

Если существует предел , то радиус сходимости ряда равен этому пределу и степенной ряд сходится при , т.е. в промежутке , который называется промежутком (интервалом) сходимости.

Если предел равен нулю , то степенной ряд сходится в единственной точке .

На концах промежутка ряд может сходиться (абсолютно или условно), но может и расходится. Сходимость степенного ряда при и исследуется с помощью какого-либо из признаков сходимости.

Пример: дан ряд . Исследовать его сходимость в точках .

При данный ряд превращается в числовой ряд . Исследуем сходимость этого ряда по признаку Даламбера. Имеем ;

, т.е. ряд сходится.

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