Множества и их спецификация

МНОЖЕСТВА

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

Основная литература:

Кук Д., Бейз Г. Компьютерная математика: Пер. с англ.— М.: Наука, Гл. ред. физ.-мат. лит., 1990.— 384 с.
ISBN 5-02-014216-6.

 

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

 

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

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

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

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

Это также означает, что часть или же вся рассматриваемая теория может быть запрограммирована.

 

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

 

 

 

 

 


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

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

Например:

— множество всех подземных станций города;

— множество левых ботинок;

— множество натуральных чисел: 1, 2, 3, 4 и т. д.;

— множество кодов операций конкретного компьютера;

— множество зарезервированных слов языка Паскаль.

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

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

Если множество содержит несколько элементов, то мы просто записываем все его элементы. Например, если мы определим Акак множество всех целых чисел строго между 6 и 10, то это можно записать следующим образом:

А = {7, 8, 9}

и прочитать как:

«А — множество, содержащее 7, 8, 9».

Здесь символ «=» используется в определенном смысле: А равно множеству...

Далее будет использоваться высказывание «равно ли А...». Поэтому мы должны предложить процедуру установления справедливости этого утверждения.

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

Следовательно, множество А можно определить как:

А = {х: х — целое число и 6 < х < 10}

и прочитать как

«А есть множество всех х таких, что... »

Множеству А принадлежат только те элементы, которые являются целыми числами, большими 6 и меньшими 10, т. е. 7, 8 и 9, и, следовательно, мы имеем 7, 8, 9, как и ранее.

 

Множества часто рассматривают как «неупорядоченныесовокупности элементов», хотя иногда полезно подчеркнуть, что, например,

{7, 8, 9} = {8, 9, 7} = {9, 8, 7} = …;

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