1. Множества

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

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

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

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

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

Рис. 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

= {х:х = 2п, n N}.

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

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

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

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

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

а) 1 N; б) если n N, то п+1 N

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

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

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

 {2, 4, 6, ...,100}.

а) 1 N; б) если n N, то (п+2)  ; в) n 98.

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

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

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

Мощность =8

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

а) А ={1,2,3}, в)С={х:х А},

б) В ={5, 6, 6, 7}, г)D={A,C}?

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

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

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

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

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