Раздел 1. Введение в теорию множеств

Теоретико-множественные представления - описание иссле­дуемой системы, процессов средствами теории множеств, т.е. как множества взаимосвязанных и/или взаимодействующих частей - элементов. Связи между элементами задаются через отношения и/или соответствия. Множества, элементы, отношения, соот­ветствия характеризуются определенными свойствами и набо­ром допустимых операций над ними.

Глава 1. Множества `

Состав объекта исследования может быть представлен в виде дискретного множества. Множество - основное поня­тие в теории множеств, которое вводится без определения.

О множестве известно как минимум, то, что оно состоит из элементов.

§1.1. Основные понятия

Множество - состоит из элементов. Принадлежность эле­мента а множеству М обозначается а  М (“а принадлежит М”), непринадлежность - a  M.

Множество А называется подмноже­ством множества В (обозначается AÍ В), если всякий элемент из А является элемен­том В (рис 1.1). Если AÍ В и А  В, то А называется строгим (собственным) под­множеством (обозначается А Ì В).

Содержательные примеры множеств и их возможные обозначения: Рис. 1.1

A - множество сотрудников фирмы “Элегант”;

М₁ - множество всех операций (работ) по сборке компью­тера;

М₂ - множество видов услуг, предоставляемых фирмой “Силуэт”;

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

N₁ - множество натуральных чисел, не превосходящих 100;

R - множество всех действительных чисел и т.д.

Два определения равенства множеств:

1. Множества А и В равны (А = В), если их элементы со­впадают.

2. Множества А иВ равны, если А  ВиВ А.

Множество, состоящее из конечного числа элементов, на­зывается конечным, в противном случае - бесконечным (на­пример, множества N, R- бесконечные множества). Число элементов в конечном множестве Мназывается его мощнос­тью и обозначается \М\.

Множество мощности , т.е. не содержащее элементов, называется пустым (обозначается  ): |  | = 0. Принято считать, что пустое множество является подмножеством любого множества.

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

• Перечислением, т.е. списком своих элементов. Спис­ком можно задать лишь конечные множества. Обозначение списка - в фигурных скобках. Например, множество А уст­ройств домашнего компьютера, состоящего из процессор­ного блока д, а также периферийных устройств В (монито­ра Ь, клавиатуры с и принтера d), может быть представлено списком:

А = {а, В} или А = {а, Ь, с, d).

(Задание типа М= 1,2,3, ...-не список, но лишь допусти­мое условное обозначение.)

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

лых чисел, являющихся степенями двойки , n  N, где N - множество натуральных чисел, (допустимое обозначение = 1,2,4,8,16,...) может быть представлено порождающей процедурой, заданной двумя правилами, называемыми рекур­сивными, или индуктивными:

а) 1  ; б) если т , то 2т .

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

М= {x | Р(х)} или М- { x: Р(х)}.

(“Множество Л/состоит из элементов х таких, что x обла­дает свойством Р”) Например, множество А периферийных устройств персонального компьютера PC может быть опре­делено:

А = {х:х- периферийное устройство персонального компьютера PC}.

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

М_2п = {х:х = 2п, nÎ N}.

Надежным способом точно описать свойство элементов данного множества является задание распознающей (раз­решающей) процедуры. Она должна устанавливать для лю­бого объектах, обладает ли он данным свойством Р (и, сле­довательно, принадлежит множеству) или нет. Например, распознающей процедурой для множества А всех сотруд­ников фирмы “Квант”, имеющих удостоверение фирмы, является проверка его наличия. Тогда множество А может быть представлено более точно: “А - множество всех со­трудников фирмы «Квант», имеющих соответствующее удо­стоверение фирмы”.

Еще пример: для описания характеристического свой­ства элементов множества всех целых чисел, являющих­ся степенями двойки (“быть степенью двойки”), разреша­ющей процедурой может служить любой метод разложе­ния целых чисел на простые множители. Тогда а  М₂» , если а = 1 или если а = 2 х 2 х ... х 2 = , п Î N.

Пример 1. Задать различными способами множество N всех натуральных чисел: 1,2, 3,...

a) Списком множество N задать нельзя ввиду его бес­конечности.

Порождающая процедура содержит два правила:

a) lÎN;

б) если n Î N, то п +1 Î N.

Описание характеристического свойства элементов множества N:

N = {x: х - целое положительное число}.

Пример 2. Задать различными способами множество М всех четных чисел 2,4, 6,..., не превышающих 100.

Решение

М_2п = {2,4,6,..., 100}.

а) 2 Î М_2п;

б) если n Î N, то (n+2) Î M_2n,

в) п 98.

М_2п= {п:п- целое положительное число, не превыша­ющее 100} или М_2п = {n: n Î N и п/2 Î N, п 100}.

Пример 3. Пусть U= {а, b, с}. Определить в явном виде (перечислением своих элементов) булеан (U) - множество всех подмножеств, состоящих из элементов множества U. Ка­кова мощность множества (U) ?

Решение

(b(U) = { , {а}, {b}, {с}, {а, b}, {а, с}, {b, с}, {а, b, с}}.

Мощность |b(U)|⁼ 8.

Пример 4. Какие из приведенных определений множеств А, В, С, D являются корректными:

а) А = {1, 2, 3},	в) С={x: хÎ А,
б) В ={5, 6, 6, 7},	R) D= {А, С}?

Принадлежит ли число 1 множеству D?

а) Определение множества А = {1,2,3} списком своих элементов формально корректно.

Решение

б) При перечислении элементов множества не следует ука­зывать один и тот же элемент несколько раз. Корректное оп­ределение В = {5, 6, 7}.

в) Определение множества С = {х:хÎ А} заданием харак­теристического свойства его элементов “принадлежать мно­жеству А” корректно, А = {1,2,3}.

Решение

г) Определение списком множества D = {А, С} коррект­но: элементами множества D являются множества А и С. Однако 1 не принадлежит Д 1  D, так как элемент 1 не перечислен в списке.