Множество в математике - это произвольный набор элементов, понимаемых как единое целое. На вид элементов и их количество никаких ограничений не накладывается. Каждый элемент множества уникальный, т.е. не может повторяться (он или есть в множестве, или его нет). Свойство уникальности элемента - одно из основных отличий множества от массива (в массиве элементы могут повторяться).
Множества в математике могут быть абстрактные и конкретные. Для абстрактного множества имеет значение лишь наличие или отсутствие элемента; тип входящих в множество элементов при этом игнорируется. В конкретных множествах элементы имеют вполне определенный тип, одинаковый для всех. Например, в множество натуральных чисел могут входить лишь целые положительные числа. В Паскале множество может быть только конкретным, поскольку любая обрабатываемая в программе переменная должна быть описана в разделе Var.
Множества в математике могут быть конечные и бесконечные. Например, множество натуральных чисел является бесконечным, множество букв какого-либо алфавита - конечным. В Паскале множество может быть только конечным, поскольку память ЭВМ, в которой размещаются все переменные, сама является конечной.
Множество может быть непрерывным или дискретным. Например, множество вещественных чисел является непрерывным, поскольку между двумя любыми числами можно расположить бесконечное количество других вещественных чисел. Множество натуральных чисел является дискретным. Так, между элементами 8 и 9 других натуральных чисел не существует. В Паскале множество может быть только дискретным. Этому требованию соответствует ординальный тип элементов множества.
Для множеств в математике определены операции пересечения, объединения и разности множеств.
Пусть мы имеем произвольные множества и с одинаковым типом элементов. Тогда пересечение множеств означает, что в множество входят лишь элементы, которые одновременно имеются и в множестве , и в множестве . При объединении множеств в включаются как элементы, находящиеся в , так и элементы, находящиеся в . Разность множеств определяет, что в множество записываются все элементы множества за исключением тех элементов, которые заданы в множестве .
Если множество является частью множества , то это обозначается . Запись означает, что является подмножеством множества . Эквивалентность множеств означает, что в оба эти множества входят одни и те же элементы. Фактически записанные здесь соотношения между множествами - это операции отношения. Для конкретных множеств эти отношения могут выполняться или не выполняться и, следовательно, результатом операции являются значения true или false.
Для отдельного элемента отношением является операция, определяющая его наличие или отсутствие в конкретном множестве: или . Результатом этой операции также являются значения true или false.
Количество элементов в множестве называют его мощностью. Запись означает, что в множестве содержится элементов. Множество может быть пустым, т.е. не содержать ни одного элемента.
Предположим, что элементами множества могут быть только объекты, обозначаемые символами . Тогда в математической записи множество может иметь следующие конкретные значения:
; ; ; ;
; ; ;
Каждый элемент того типа, который определен для множества, может быть или не быть в данном множестве. Поэтому логично поставить в соответствие каждому элементу множества один бит памяти. Тогда значение бита 0 будет означать, что данный элемент отсутствует в множестве, а значение 1 будет свидетельствовать о нахождении его в этом множестве.
Множество в целом реализуется в Паскале как битовая строка. Для приведенного выше примера достаточно иметь строку длиной три бита. Пусть первый бит - это элемент , второй - элемент , третий - элемент . Тогда множество может иметь следующие значения:
0 0 0 1 1 0
1 0 0 1 0 1
0 1 0 0 1 1
0 0 1 1 1 1
Битовая строка не может быть неограниченной, т.е. мощность множества не может быть бесконечной. В Турбо Паскале максимальная длина битовой строки определяется численным значением переменной типа byte и равна 256 бит (32 байта).
Объявление множественного типа имеет вид:
Например,
set of byte
set of char
set of 1..100
Сопоставим описания массива и множества.
В описании массива
array[T1] of T2
T1 - это тип индекса, T2 - тип элемента массива. Тип T1, в частности, указывает, какие значения имеет право принимать индекс элемента массива и, следовательно, определяет количество элементов массива, т.е. его размер. Например, описание
array[byte] of T2
означает, что в массиве содержится 256 элементов, а его индекс может иметь целочисленные значения 0, 1, 2, ..., 255. При описании
array[char] of T2
массив имеет такой же размер, но индекс элемента массива принимает значения символов таблицы ASCII: #0, #1, #2, ..., #255.
Возможные значения элементов множества заранее определены: 0 или 1, поэтому тип T2 по отношению к множеству не имеет смысла. В описании множества
set of T1
тип T1 в основном аналогичен такому же типу для индекса массива: он определяет, какие конкретно элементы могут быть в множестве и количество этих элементов, т.е. мощность множества. Например, описание
set of byte
означает, что в множество могут входить 256 элементов, имеющих значения 0,1,2,...,255. При описании
set of char
потенциальными элементами множества являются символы #0, #1, ..., #255. В обоих случаях для множества выделяется поле памяти длиной 32 байта.
Так как тип T1 определяет, в частности, мощность множества, то объявление типа
SetType = set of integer
является неправильным, так как битовая строка не может иметь длину 65536 бит (тип integer принимает значения -32768, -32767, ..., -1, 0, 1, ... , 32767).
Обычно для описания множества используют диапазонный тип.
Пример.
TypeDiap1 = 1..100;
Diap2 = 'a'..'z';
SetNumberType = set of Diap1;
SetLetterType = set of Diap2;
VarSetNumber : SetNumberType;
SetLetter : SetLetterType;
Здесь элементами множества SetNumber являются числа 1, 2, ..., 100, элементами множества SetLetter - малые буквы латинского алфавита a, b, ..., z.
Память для размещения множества выделяется при старте блока, где описано это множество, но значение множества при этом остается неопределенным. Другими словами, объявление множества SetNumber типа SetNumberType указывает лишь на принципиально возможный набор значений элементов множества (в данном случае целые числа от 1 до 100), но в поле переменной SetNumber никакие значения не записываются.
Простой переменной присвоить конкретное значение можно в разделе операторов путем задания соответствующей константы. Для множества роль константы играет так называемый конструктор множества.
Конструктор множества - это список элементов, заключенный в квадратные скобки. В списке могут быть отдельные элементы и диапазоны.
Например,
SetNumber := [];
SetLetter := ['a','d','k'..'p','y'];
Остановимся на смысловом значении приведенных выше операторов присваивания для множеств SetNumber и SetLetter.
Из объявления множества SetNumber следует, что для него при старте программы выделяется 100 бит памяти (13 байт, в последнем байте используются 4 бита). При выделении памяти поле SetNumber заполнено случайным образом. Оператор SetNumber:=[ ] указывает, что всем 100 битам этого поля должно быть присвоено нулевое значение.
Для множества SetLetter выделяется 26 бит (количество букв алфавита от 'a' до 'z'). В этом поле биты 1,2,3,4 (порядковые номера букв 'a','b','c','d' в диапазонном типе Diap2), биты 11,12,13,14,15,16 и 25 (порядковые номера букв 'k'..'p' и 'y') устанавливаются в единичное положение, все остальные биты - в нулевое.
Если A и B - множества одного типа, то к ним применимы следующие операции:
1) A * B - пересечение множеств;
2) A + B - объединение множеств;
3) A - B - разность множеств.
В Турбо Паскале определены четыре логические операции: отрицание (not), логическое умножение (and), логическое сложение (or), исключающее ИЛИ (xor). Эти операции применимы не только к булевским переменным, но и к операндам целого типа. В последнем случае операция выполняется отдельно для каждого бита, т.е. ее можно рассматривать как операцию над битовыми строками. Поскольку на машинном уровне множество - это битовая строка, то выполнение операций пересечения, объединения и разности множеств сводится к соответствующим логическим операциям.
Операция объединения множеств - это логическое сложение двух битовых строк; пересечение множеств - это логическое умножение битовых строк. Если обозначить биты, входящие в множества A и B, через a и b, то операция разности множеств сводится к вычислению для каждой пары битов логического выражения a and (not b).
Пересечение и объединение двух множеств часто называют соответственно умножением и сложением множеств. Отсюда и приоритеты этих операций: пересечение старше операций объединения и вычитания, а они в свою очередь старше рассматриваемых ниже операций отношения.
Пример выполнения операций над множествами:
TypeDiap = 0..15;
SetType = set of Diap;
VarA,B,C,D,E : SetType;
Begin
A := [0..3, 5, 7..9, 12, 14];
B := [4..7, 9, 11..13, 15];
C:=A+B; D:=A*B; E:=A\B;
По отношению к битовым строкам имеем:
A = 1111 0101 1100 1010
B = 0000 1111 0101 1101
Тогда
C = 1111 1111 1101 1111, т.е. С=[0..9,11..15]
D = 0000 0101 0100 1000, т.е. D=[5,7,9,12]
E = 1111 0000 1000 0010, т.е. E=[0..3,8,14]
Для множеств допустимы следующие операции отношения:
1) a inA - вхождение элемента в множество ( );
2) A = B - равенство множеств;
3) A <> B - неравенство множеств;
4) A < B - множество A является подмножеством в B ( );
5) A > B - множество B является подмножеством в A ( );
6) A <= B - множество равно множеству или является его подмножеством ( );
7) A >= B - множество равно множеству или является его подмножеством ( ).
Операция проверки вхождения элемента в множество (a in A) эквивалентна вычислению выражения [a] * A. При проверке равенства и неравенства множеств для каждой пары битов выполняется операция xor. Вычисление отношения A <= B эквивалентно вычислению логического выражения A + B = A, а вычисление отношения A >= B заменяется вычислением выражения A + B = B.
Логические операции выполняются значительно быстрее, чем арифметические (например, при логическом сложении нет переноса единицы в старший разряд в отличие от арифметического сложения). Поэтому программы, использующие множества для реализации какого-либо алгоритма, работают быстрее, чем программы, в которых этот же алгоритм реализован другим способом.
Например, вместо оператора
If (ch='Д') or(ch='д') or (ch='L') or (ch='l') then S,
где ch - переменная типа char; S - произвольный оператор, более целесообразно использовать оператор
If ch in['Д','д','L','l'] then S.
Непосредственный ввод-вывод множества не допускается, однако это можно сделать косвенным путем:
и 
с одинаковым типом элементов. Тогда пересечение множеств 
означает, что в множество 
входят лишь элементы, которые одновременно имеются и в множестве 
в 
определяет, что в множество 
. Запись 
означает, что 
означает, что в оба эти множества входят одни и те же элементы. Фактически записанные здесь соотношения между множествами - это операции отношения. Для конкретных множеств эти отношения могут выполняться или не выполняться и, следовательно, результатом операции являются значения true или false.
или 
. Результатом этой операции также являются значения true или false.
означает, что в множестве 
элементов. Множество может быть пустым, т.е. не содержать ни одного элемента.
могут быть только объекты, обозначаемые символами 
. Тогда в математической записи множество 
; 
; 
; 
;
; 
; 
; 
, второй - элемент 
, третий - элемент 
. Тогда множество 
);
);
);
).