1. Пусть универсум U — конечное множество. Элементы универсума нумеруются: U = {u1, u2, …, un}. Подмножество A универсума U представляется кодом (машинным словом или битовой шкалой) C(A) = {c1, c2, …, cn}, в котором:
| Pi = { | 1, если ui ∈ A |
| 0, если ui ∉ A |
здесь сi — это i-й разряд кода C(A).
Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. Таким образом, операции над небольшими множествами выполняются весьма эффективно.
Пример. Пусть универсальное множество, состоит из пяти элементов и упорядоченно так: U = {a1, a2, a3, a4, a5}. Код универсума С(U) = (1, 1, 1, 1, 1). Множеству А = {a2, a4, a5} соответствует код С(А) = (0, 1, 0, 1, 1), а множеству В = {a1, a3, a4} соответствует код С(В) = (1, 0, 1, 1, 0). Тогда:
А∪В соответствует код С(А∪В) = С(А)∨С(В) = (1, 1, 1, 1, 1),
А∩В соответствует код С(А∩В) = С(А)∧С(В) = (0, 0, 0, 1, 0),
А⊕В соответствует код С(А⊕В) = С(А)⊕С(В) = (1, 1, 1, 0, 1).
2. Если универсум очень велик (или бесконечен), а рассматриваемые подмножества универсума не очень велики, то представление с помощью битовых шкал не является эффективным с точки зрения экономии памяти. В этом случае множества обычно представляются списками элементов. Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент. Весь список представляется указателем на первый элемент.
Доступ к соответствующему полю осуществляется через точку, например, a.i.
Для более эффективной работы с множествами можно их упорядочить, например, так, пронумеровать элементы и каждому элементу поставить в соответствие его номер. При определении множества располагать элементы по возрастанию его номера. Такой способ определения множества будем называть упорядоченным списком элементов. Тогда в определении структуры элементов множества следует ввести новое поле (int num;). Например, из списка студентов образуем множества, размещение которых в оперативной памяти выглядит следующим образом:
Здесь множества задаются указателями на первый из упорядоченных (по полю num) элементов множества. Из примера видно, что Петров располагается в двух местах оперативной памяти, однако этот недостаток легко устранить − в поле info поставить указатель на данные отдельного элемента.
3. Представление функций в ЭВМ. Пусть f:A→B, причем множество А конечно и не очень велико, |А| = n. Наиболее общим представлением такой функции является массив array [A] of В, где А — тип данных, значения которого представляют элементы множества А, а В — тип данных, значения которого представляют элементы множества В. Если среда программирования допускает массивы только с натуральными индексами, то элементы множества А нумеруются (то есть A = {a1, a2, …, an}) и функция представляется с помощью массива array [l..n] of В. Функция нескольких аргументов представляется многомерным массивом.