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

Содержание

Волгодонск 2012

КРАТКИЙ КУРС ЛЕКЦИЙ

по дисциплине «Дискретная математика» 1 семестр

для студентов заочной формы обучения

по направлению (специальности)

230400.62 «Информационные системы и технологии»

полная/сокращенная программа

Составители:

Цуверкалова О.Ф.

Цуверкалов В.Г.

Раздел «Теория множеств»
Алгебра множеств …………………………………………………………
Бинарные отношения ……………………………………………………...
Функциональные отношения ……………………………………………..
Отношение эквивалентности ……………………………………………..
Отношения порядка ……………………………………………………….
Раздел «Основы теории графов»
Неориентированные графы ……………………………………………….
Ориентированные графы ………………………………………………….
Матричное представление графов ………………………………………..
Раздел «Математическая логика»
Логические функции ………………………………………………………
Алгебра логики …………………………………………………………….
Контактные схемы …………………………………………………………
Логические схемы …………………………………………………………
Раздел «Автоматы и алгоритмы»
Конечные автоматы ……………………………………………………….

1. алгебра МНОЖЕСТВ

1.1. Понятие множества. Обозначение принадлежности

Математическое понятие множества постепенно выде­лилось из привычных представлений о совокупности, соб­рании, классе, семействе и т. д. В 1872 г. Георг Кан­тор, создатель теории множеств, определил множество как «объединение в одно целое объектов, хорошо разли­чаемых нашей интуицией или нашей мыслью». В первом издании «Теории множеств» Бурбаки, поя­вившемся в 1939 г., в сводке результатов можно найти следующее предложение: «Множество образуется из элементов, обладающих некоторыми свойствами и на­ходящихся в некоторых отношениях между собой или с элементами других множеств».

Объекты, сущности или элементы, составляющие мно­жество, обозначаются строчными латинскими буквами: х, а,...; множество часто обозначают прописными ла­тинскими буквами Е, N,.... Знак Î обозначает вхож­дение или принадлежность; х Î Е читается: «элемент х принадлежит множеству Е», или короче: «х— элемент множества Е». Следует различать «общий элемент» х множества Е, т. е. произвольный элемент, характеризую­щийся единственным свойством «принадлежать множест­ву», и конкретные элементы а, b, c,..., каждый из ко­торых отличен от остальных. Если х не принадлежит Е, будем писать х Ï Е, что читается «х не является элемен­том множества Е» или «х не принадлежит множеству Е». Если множество содержит конечное число элементов, говорят, что оно конечно; в противном случае множест­во называется бесконечным. Множество Е, состоящее из элементов а, b,..., записывается

Е= {а. b........}.

Примеры. 1) Множество четных цифр Р={2, 4,6,8}.

2) Множество трехзначных чисел в двоич­ной системе:

В₃ = {000, 001, 010, 011, 100, 101, 110, 111}.

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

1) Множество может быть задано перечислением всех его элементов.

Пример. Множество цифр: {0,1,..., 9}.

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

Пример. Считая известным множество целых чисел

Z = {....-3.-2,-1, 0. 1, 2, 3,...},

определим множество степеней числа 2

{…, 2^-3, 2^-2, 2^-1, 2⁰, 2¹, 2², 2³, …}

3) Другой способ задания множеств — описание огра­ничительного свойства, выделяющего элементы множе­ства Е среди элементов более широкого, или основного (универсального, универсума), множества U. Множество Е называется частью, или под­множеством множества U.

Пример. Пусть дано множество N натуральных чисел N = {1, 2, 3,...}. Рассмотрим совокупность всех тех элементов этого мно­жества, которые делятся на 2 (ограничительное и харак­теризующее свойство); полученное множество есть мно­жество четных чисел Р={2, 4, 6,...}.

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

1.3. Множество подмножеств. Включение

Пусть U — основное множество. Основное, или фунда­ментальное, множество в математике может быть образо­вано всеми элементами какого-нибудь определенного типа.

Пример. Множество прямых плоскости, множество простых чисел и т. д.

Два свойства, эквивалентные относительно основного множества, определяют одну и ту же часть этого мно­жества, и обратно. Множество элементов U, облада­ющих свойством хÎ Е, очевидно, совпадает с Е.

Пример. Пусть I — множество нечетных чисел в де­сятичной системе

I = {1, 3, 5, 7, 9, 11, 13. 15, 17, 19....};

за основное множество примем множество N натураль­ных чисел. Можно определить множество нечетных чи­сел исходя из свойства оканчиваться на нечетную деся­тичную цифру 1, 3, 5, 7 или 9 (Р ₁); то же множество соответствует свойству не делиться на 2 (Р ₂). Свойства P₁ и P₂ эквивалентны относительно N и задают мно­жество нечетных чисел, подмножество основного множе­ства N.

Обратимся теперь к свойству не быть целым числом (Р ₃), соответствующее этому свойству подмножество ос­новного множества N не содержит ни одного элемента; такое множество будем называть пустым и обозначать Æ.

Таким образом, свойства, присущие некоторым эле­ментам множества U, могут служить для задания под­множеств этого множества; свойство, отличное от всех свойств элементов U, порождает пустое множество, пус­тое подмножество множества U. Напротив, наибольшее подмножество, т. е. само множество U, может быть за­дано любым свойством, присущим всем элементам основ­ного множества.

Пусть А и В - два подмножества основного множест­ва U. Если все элементы из А принадлежат В, то гово­рят, что А содержится (или включено) в В; употреб­ляются также выражения; В содержит A, или А есть часть множества В. В этом случае будем писать А Ì В или В É A.

Пример. Множество Р четных чисел содержится в множестве N натуральных чисел: РÌN.

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

Наоборот, если мы знаем характеристические свойст­ва общего элемента подмножества Е, то мы можем определить, какие элементы основного множества U принадлежат этому подмножеству: речь идет о пара­метризации подмножества Е: такой способ задания яв­ляется синтетическим.

Из соотношений А Ì В и В Ì С следует соотношение A Ì С; следовательно, отношение включения транзитивно. Заметим, что из А Ì В и B Ì A следует А = В, и наоборот. Действительно, два множества равны (идентичны), если они состоят из одних и тех же эле­ментов.

Иногда вво­дят понятия собственного и несобственного подмноже­ства. Множество B называется собственным подмножеством множества A, если оно отлично от A и от.

В этом случае пишут A Í B, если возможен случай A = B (в этом случае A называется несобственным подмноже­ством множества В), и А Ì В, если В содержит хотя бы один элемент, не принадлежащий A. При такой системе обозначений невозможен случай, когда А Ì В и B Ì A одновременно.

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

1) Пустое множество является подмножеством любого множества: Æ

2) Всякое множество является своим собственным подмножеством:

Два множества называются равными, если они содержат одни и те же элементы и количество этих элементов одинаково.

или или.

Множеством подмножеств некоторого основного или произвольного множества Е называется множество, эле­ментами которого являются подмножества множества Е. Это множество P(Е) включает в качестве элементов пустое множество 0 и само множество Е; каждый от­дельный элемент Е есть также подмножество множест­ва Е.

Пример. Е ={ а, b, с};

P(Е)={{Æ}, {а}, {b}, {с}, {а, b}, {а, с}, {b, с}, {а, b, с,}}.

Теорема: Конечное множество, содержащее n элементов, имеет 2 ⁿ подмножеств.

1) Дополнение: Дополнение множества A - множество, состоящее из всех элементов универсума, не принадлежащих A.
2) Пересечение: Пересечение множеств A и B - множество, состоящее из всех элементов, принадлежащих одновременно и A, и B.
3) объединение: Объединение множеств A и B - множество, состоящее из элементов, принадлежащих хотя бы одному из указанных множеств.
4) Дизъюнктивная сумма (симметрическая разность): Дизъюнктивная сумма множеств A и B - это множество, состоящее из элементов, принадлежащих либо только A, либо только B.
5) Разность: Разность множеств A и B - это множество, состоящее из элементов, принадлежащих A, но не принадлежащих B.