Дискретная математика: Учебное пособие. Часть I - Основания дискретной математики

        ”Целые числа создал Господь Бог.

Все остальное – дело рук человеческих... ”

Л. Кронекер

“Теперь в математике остаются

                                             только целые числа и конечные...

системы целых чисел...”

Анри Пуанкаре.

Введение

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

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

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

В главе 2 - Элементы комбинаторики - сформулированы основные требования к комбинаторным объектам, определены основные правила и процедуры формирования упорядоченных и неупорядоченных выборок этих элементов; все разделы главы также подкреплены примерами и контрольными вопросами.

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

В главе 4 – Основы математической логики – изложены правила логики высказываний и логики предикатов, показаны основные процедуры дедуктивного метода и принципа резолюции при проверке истинности заключения и описаны возможности их реализации на языке PROLOG, даны правила и процедуры реляционной логики  и их реализация в формировании запросов к реляционным базам данных на языке SQL, сформулированы правила и процедуры нечеткой логики  и показано их применение в экспертных системах на примере MYCIN. Все разделы главы сопровождаются примерами и контрольными вопросами. По основным разделам предлагается выполнить индивидуальное задание (см. Приложения).

1.  Основания дискретной математики

1.1  Множество

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

В языках программирования так задают типы данных: целые числа (INTEGER), литеры (CHAR), строки (STRING)  логические переменные (BOOLEAN) и др.

Объекты, включаемые в множество, называют его элементами. Например, ’3’ - элемент INTEGER, ‘c’ - элемент CHAR , ‘monday’ – элемент STRING, ‘true’ – элемент BOOLEAN  и т. п..

Общим обозначением множества служит пара фигурных скобок ”{”, “}” между которыми перечисляют элементы множества.

Например, {1, 3, 5, 7} или {a, b, c, d}.

На языке pascal для обозначения множества используют скобки “[“, “]“, между которыми перечисляют элементы множества. Например, [1, 3, 5, 7] или

[‘a’, ‘b’, ‘c’, ‘d’].

Для обозначения множества в тексте используют прописные буквы латинского алфавита A, B, C, ...X, Y, Z, а для обозначения его элементов - строчные буквы a, b, c,...x, y, z. Иногда эти буквы используют с индексами.

Принадлежность элемента x множеству A обозначают знаком “Î“ (например, xÎA). На языке pascal эту операцию описывают так: “x in А, где x - <идентификатор_элемента >, а А - <идентификатор_множества>”.

 Если элемент х не принадлежит множеству A, то используют знак “Ï“ (например, хÏA), а на языке pascal это записывают так: “not(xin А)”.

Порядок перечисления элементов между фигурными скобками произвольный, т.е. {a, b, c, d}={b, c, d, a}, но не допускается неоднократное перечисление одного элемента среди остальных элементов множества.

Например, {a, a, a, b, b, c, c, d}={a, b, c, d}

Множество, каждый элемент которого можно индексировать целым числом 1,2,... n, называют счетным. На языке pascal такому элементу присвовают <идентификатор_порядкового_типа>.

Если n конечно, то множество называют конечным. Например, множество цифр счетно и конечно, а множество целых чисел (INTEGER) – счетно, но не конечно. На языке pascal, как правило, число элементов множества указывают в диапазоне [1..n].

Число элементов счетного конечного множества A называют его мощностью и обозначают так: |A|=n. Например, мощность множества цифр равна 10, а мощность множества строчных букв латинского алфавита – 26.

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

Например, если А={1, 2, 3} и B={1, 2, 3, 4, 5}, то A есть подмножество B. Для обозначения этого в тексте используют символ “Í“ - знак включения: AÍB. На языке pascal факт включения множества A в множество B записывают так: A£B.