Множества

Множество в математике – это произвольный набор объектов, понимаемый как единое целое. Два множества, отличающиеся только порядком следования элементов, считаются одинаковыми, например:

{A, B, C}, {A, C, B}, {B, C, A}

и т.д., то есть элементы множества не упорядочены.

На вид объектов и их число не накладываются никакие ограничения, но в языке Турбо-Паскаль это понятие существенно уже: в качестве базовых типов допускаются дискретные типы не более чем с 256 различными значениями, то есть типы byte, char, boolean, перечисляемый и диапазон.

Описание типа:

 

Туре <тип_множество> = SET OF <базовый_тип>

Var <список_переменных>: SET OF <базовый_тип>

 

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

[Blue, Yellow, Red] или [1,4..8,12,15].

Существует единственное пустое множество, которое принадлежит всем типам множеств и обозначается как [ ].

Пусть есть описание:

 

Var A, B, C: Set of 0..9;

D, E: Set of '0'..'9';

F, G: Set of Boolean;

 

Тогда:

A:=[1, 3, 5];

D:=['3', '6'..'9'];

F:=[5, 7]; {неверная строка – «не то» множество}

 

При использовании диапазонов, если значение первой константы меньше значения второй константы диапазона, то задается пустое множество. Запись [5..3] эквивалентна [ ].

 

Операции над множествами – обычные из теории множеств и математической логики. Пусть S1 и S2 – однотипные множества, тогда над ними можно выполнять следующие операции.

 

1. Объединение множеств.

S1+S2 содержит элементы, которые принадлежат либо S1, либо S2, либо и тому и другому:

 

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A+B;

 

что эквивалентно

C:=[1, 2, 3, 5, 9];

 

2. Пересечение множеств.

S1*S2 содержит элементы, которые принадлежат как S1, так и S2:

 

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A*B;

 

что эквивалентно

C:=[1];

Или выражение

C:=A*[8];

соответствует пустому множеству:

C:=[ ];

 

3. Относительное дополнение или разность множеств.

S1-S2 содержит элементы из S1, которые не принадлежат S2:

 

A:=[1, 2, 3];

B:=[1, 5, 9];

C:=A-B;

 

что эквивалентно

C:=[2, 3];

Или выражение

C:=A-[3..9];

соответствует:

C:=[1, 2 ];

 

4. Проверка на равенство, неравенство и включение множеств.

S1=S2 тогда и только тогда, когда S1 и S2 содержат одни и те же элементы. В противном случае истинно выражение S1<>S2. S1<=S2 принимает истинное значение, когда все элементы S1 являются элементами S2 (множество S2 включает в себя множество S1). Пусть

 

A:=[1..5];

B:=[1..5];

C:=[1..6];

 

Тогда логические выражения примут значения:

 

A=B — истинно;

А=С — ложно;

B<>C — истинно;

A<=C — истинно (С включает А).

 

5. Проверка принадлежности множеству (включение во множество).

Эта логическая операция обозначается служебным словом in. Выражение X in S1 истинно, если элемент Х принадлежит множеству S1 и ложно в противном случае:

 

2 in A — истинно;

9 in A — ложно.

 

Этот тип данных используется довольно редко, за исключением операции проверки принадлежности к множеству. Например, нажата ли клавиша «p» в любом регистре и алфавите:

 

If CH in ['p', 'P', 'з', 'З'] then ... {нажата клавиша «р»}