Задачи изучения дисциплины

В результате изучения дисциплины «Дискретная математика» студенты должны:

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

• знать основные законы, тождества и операции над множествами;

• получить навыки практической работы по решению комбинаторно-логических задач;

• уметь строить и преобразовывать переключательные функции алгебры логики.

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

Курс является базовым для всей специальности САПР. Основные задачи пользователя и разработчика САПР − уметь составлять и решать алгоритмы любых практических оптимизационных задач. При изучении дисциплины существенную помощь окажет освоение автоматизированных обучающих модулей, а также выполнение индивидуальных творческих заданий по разработке алгоритмов и их программной реализации на ЭВМ.

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

Структура учебной программы соответствует аналогичным курсам, входящим в учебные планы ведущих государственных высших учебных заведений США, например, программам курсов «Discrete mathematics p. 1, 2», «Discrete structures in Computer Science» Мичиганского государственного университета, США и других.

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

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

У. Джеймс

МОДУЛЬ 1. ОСНОВЫ Теории множеств (2 кредита)

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

Комплексная цель и задачи изучения модуля

Цель Модуля 1 – дать представление о фундаментальных понятиях, базовых принципах и законах основного раздела дискретной математики - теории множеств, рассмотреть постановку основных задач и проблем, изучить вопросы методологии решаемой проблемы.

В результате освоения Модуля 1 студент должен быть готов продемонстрировать следующие компетенции и уровень подготовки:

1) знание основных понятий теории множеств;

2) умение применять на практике законы и правила теории множеств, доказывать справедливость тождеств теории множеств;

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

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

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

Само собой понятное и очевидное

Не следует определять:

Определение лишь затемнит его.

Б. Паскаль

Глава 1. Исчисление множеств

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

ЦЕЛИ

Освоив эту главу, студенты должны:

· знать способы задания множеств;

· уметь решать задачи на включение и невключение множеств;

· знать понятие кванторов существования и общности;

· уметь строить таблицы истинности высказываний;

· знать основные свойства множеств;

1.1. Понятие множества

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

Основатель теории множеств — немецкий математик Георг Кантор (1845-1918). По его определению:

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

Понятию множества в математике соответствуют семейство, совокупность, система, класс, область и т.д. Объекты, составляющие множества, могут иметь любую природу. Например, мы можем говорить о множестве живущих на Земле людей, множестве планет солнечной системы, множестве букв русского алфавита, множестве целых чисел. Часто объекты объединяются в множество по какому-либо общему признаку. Обозначаются множества прописными латинскими буквами A, B, C и т.д.

Предметы, составляющие исследуемое множество, называются его элементами. Например, запись A = { x, a, b, c, d } означает, что множество A состоит из элементов x, a, b, c, d. Элементами множества могут быть буквы, цифры, слова, тексты, целые алфавиты, другие множества и т.д. Обычно элементы множества обозначаются строчными латинскими буквами - a, b, c и т.д. Для обозначения принадлежности или не принадлежности элемента множеству используются символы “Î“ и “Ï“ - соответственно. Запись х ÎА означает, что элемент х принадлежит множеству А, а y ÏB - элемент y не принадлежит множеству В.

По определению, множество состоит из различных элементов. Моделью множества можно считать коробку с расположенными в ней произвольным образом пронумерованными различными цифрами - кубиками. Например множества A = {1, 2, 3} и A = {2, 3, 1} описывают одно и то же множество. Следовательно, множество характеризуется тем, что все элементы в нем различны, а их местоположение не имеет значения. Фигурные скобки в записи множества обозначают, что элементы объединены в одно целое, например множество A.

Множества, не имеющие ни одного элемента, называются пустыми. Пустое множество обозначается знаком - Æ. Например, множество людей, живущих на Луне, является пустым, множество целых чисел, для которых выполняется условие: "больше 5 и одновременно меньше 3", также является пустым.

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

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

N = {1, 2, 3, …} - множество натуральных чисел;

Z = {0, ±1, ±2, ±3, …} - множество целых чисел;

Q = { x / y | x, y Î Z, y ¹ 0} - множество рациональных чисел;

R = {все десятичные дроби} - множество вещественных(действительных) чисел.

С понятием множества тесно связано понятие «высказывание». Определим термин «высказывание». Высказывание — это предположение (предложение), которое считается истинным или ложным. Будем обозначать Истина — 1(И), Ложь — 0(Л).

Например, высказывание «два больше одного» - истинно, а высказывание «пять принадлежит множеству отрицательных чисел» - ложно.

Предикатом называется высказывание, содержащее переменные, принимающее значения 1 или 0 в зависимости от значения переменных. Например, высказывание x ² = 4 является предикатом, так как оно истинно при x = 2 и ложно во всех остальных случаях.

К основным операциям над высказываниями относятся отрицание, дизъюнкция, конъюнкция, эквивалентность, импликация.

1. Операция отрицания (инверсия). Обозначается следующим образом: — отрицание ”A”. Читается как «не “A”».

2. Операция дизъюнкции (логическое сложение, ИЛИ). Обозначается следующим образом: A Ú B. Читается как «A или B».

3. Операция конъюнкции (логическое умножение, И). Обозначается следующим образом: A & B, либо A Ù B. Читается как «A и B».

4. Операция импликации (логическое следствие). Обозначается следующим образом: A ® B. Читается как «A влечет B» или «если А, то В».

5. Операция эквивалентности (логическое равенство). Обозначается следующим образом: A «B. Читается как «A равносильно B» или «А эквивалентно В».

Результат выполнения вышеуказанных операций определяется по таблицам истинности. Таблицы истинности этих высказываний приведены в части 3 настоящего учебного пособия.

Введем понятие кванторов существования и общности.

Квантор общности читается (для любого) изаписывается так: ". Запись вида (" x ÎX)(B(x)) означает, что для любого элемента x из множества X истинно высказывание B(x) об этом элементе.

Квантор существования читается (существует) изаписывается так: $. Запись вида ($ х ÎX)(B(x)) означает, что существует хотя бы один элемент x из множества X, для которого истинно высказывание B(x) об этом элементе.

Множества бывают конечные и бесконечные.

Конечное множество - это такое множество, число элементов которого можно представить натуральным числом. Множество называется бесконечным, если оно не является конечным. Например, множество планет солнечной системы конечно, т.к. количество планет в этой системе равно 9, а множество целых чисел является бесконечным.

1.2. Способы задания множеств

Существуют два основных способа задания множеств:

1) перечисление (перечислительный способ),

2) описание характеристического свойства (высказывательный способ).

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

Например: A = {Меркурий, Венера, Земля, Марс, Юпитер, Сатурн, Уран, Нептун, Плутон} - это множество планет солнечной системы, B = {ФАВТ, РТФ, ФЭМП, ФЭП, ФИБ, ЕГФ} - это множество факультетов университета. В общем случае, этим способом множество А задается следующим образом: А = { a ₁, a ₂, a ₃, a ₄,..., a _n} или А = { a_i }, где i Î I = {1, 2, 3, 4,..., n}.

Высказывательный способ состоит в задании такого свойства, наличие которого у элементов определенного множества является истиной. Запись A = { x ÎM | P(x)} означает, что множество А состоит из элементов некоторого множества М, обладающих свойством Р.

Например: запись B = { x ÎR | (x ⁴ - 2 x ² - 3 = 0)} означает, что множество В состоит из действительных корней уравнения: x ⁴ - 2 x ² - 3 = 0. Это же множество можно также задать перечислительным способом: .

Если из контекста понятно, какое множество М рассматривается, то высказывательную форму задания множества можно упростить в виде - A = { x | P(x)}. Последняя запись читается так: "Множество А таких элементов х, для которых высказывание Р(х) - истинно".

Конечное множество может быть задано обоими способами. Выбор способа задания зависит от дальнейшей работы с этим множеством. Бесконечные множества можно задать лишь высказывательным способом. Пустые множества относятся к конечным.

Если А - конечное множество, то через |A| обозначается количество его элементов и эту величину называют мощностьюмножества.

Мощность пустого множества равна нулю. Например, если множество А = Æ, то его мощность равна нулю (|Æ| = 0). Мощность одноэлементного множества равна единице. Например, для множества A = {9} имеем |A| = 1.

Если множества А и В содержат одни и те же элементы и мощности их равны, то эти множества считаются равными. Это обозначается так: А = В. Неравные множества состоят из различных элементов. Если в множестве А есть элементы, не принадлежащие множеству В, либо в множестве В имеются элементы, не принадлежащие множеству А, то множество А не равно множеству В. Неравенство множеств А и В обозначается: A ¹ B.

Согласно определению множеств, следует, что порядок элементов в множестве несущественен. Следовательно, если А = {1, 2, 3, 4}, a B = {4, 3, 2, 1}, то А = В, т.е. А и В - одинаковые множества или одно и то же множество.

Из определения равенства множеств вытекает, что все пустые множества равны, т.е. существует только одно пустое множество.

Равенство множеств обладает следующими свойствами:

· А = А - рефлексивность;

· если А = В, то В = А - симметричность;

· если А = В и В = С, то А = С - транзитивность.

Запись A = {1, 2, 3, 2} не является множеством, т.к. содержит повторяющиеся элементы.

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

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

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

Существуют некоторые множества, относительно которых неизвестно, пусты они или нет. Например, неизвестно, имеет ли положительное целочисленное решение уравнение xⁿ + yⁿ = zⁿ, при n > 2.

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

Различают два вида включений – строгое и нестрогое. Множество В является подмножеством множества А, если любой элемент множества В принадлежит множеству А. Говорят, что множество В нестрого включается в множество А,если выполняется одно из двух условий (В Í А Ú А = В) (Í — знак нестрогого включения). В этом случае также говорят, что множество А включает множество В или множество А является надмножествоммножества В. На рис. 1 показан пример нестрогого включения. Здесь элементы множеств A, B представляются точками плоскости, расположенными внутри соответствующих прямоугольников.

Рис. 1.1. Два случая нестрогого включения множеств

Множество В строго включается в множество А, если одновременно выполняются два условия (В Í А & А ¹ В). В этом случае также говорят, что множество В является истинным подмножеством множества А, и обозначают АÌ В, где "Ì" - символ строгого включения. Этим подчеркивают, что множество А содержит не только элементы множества В. Если множество В не включается в множество А, пишут В Ë А.

Теперь равенство множеств можно записать в теоретико-множественном виде:

А = В ® А Í В & В Í А.

Очевидно, что для пустого множества справедливо Æ Í А, Æ Ì А.

Приведем основные свойства включения множеств:

* А Í А - рефлексивность;

* А Í B & B Í C ® A Í C - транзитивность;

* A = B ® A Í B & B Í А - равенство.

Из последнего свойства следует, что для того, чтобы доказать равенство двух множеств, достаточно доказать, что A Í B, а затем, что В Í А.

Определение истинного подмножества в высказывательной форме запишется следующим образом:

А Ì В ® (("хÎА)(хÎB) & A ¹ В)).

Приведем основные свойства строгого включения:

· А Ë А - антирефлексивность;

· - транзитивность;

· А Ì В ® А ¹ В - неравенство.

Любое непустое множество М включает, по крайней мере, два подмножества - пустое и само себя, т.е. М Í М и Æ Í М. Доказательство этого утверждения следует из определения подмножества. Множества М и Æ называют несобственными подмножествами множества М, все остальные подмножества множества М называются собственными подмножествами.

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

Множество всех подмножеств множества М называется семейством подмножеств множества Ми обозначается Â(M)(читается "Пэ от Эм"). Из определения семейства следует, что ÆÎÂ(М), М ÎÂ(М) и если В Í М, то ® ВÎÂ(М).

Если множество М содержит m элементов, то мощность семейства подмножеств множества М равна 2 ^m.

Например, подсчитаем, сколько подмножеств имеет конечное множество А = {a, b}. Так как n = 2, то семейство подмножеств содержит 2 ^m = 4 подмножества:

{a, b}; {a}, {b}, {Æ}.

Для B = {a, b, c} семейство подмножеств равно 2 ^m = 8.

Если множество содержит n элементов, а его подмножество состоит из k элементов, то число k элементных подмножеств, называемых сочетанием из n по k, равно