Представление множества и его подмножеств двоичным кодом.

Пусть задано некоторое конечное упорядоченное множество мощности n, например, U = {1, 2, 3, 4, 5, 6, 7}, n = 7, будем считать что это универсум. Конечное множество и все его подмножества в памяти ЭВМ удобно представлять двоичным кодом (характеристическим вектором или, что то же самое, «словом» заданной длины.). Множеству U поставим в соответствие характеристический вектор «1111111», пустому множеству Ø поставим в соответствие «0000000», множеству {2,3,5,7} – характеристический вектор «0110101». Таким образом между множеством всех подмножеств и множеством «слов» длины 7 записанных двумя символами «0» и единица установлено взаимно однозначное соответствие. Следовательно, множество всех подмножеств множества из 7 элементов равно 2⁷.

Утверждение: Если мощность конечного множества I равна | I | , то мощность множества всех его подмножеств равна 2^{| I |}.

Пример. А = {a, b, c}. Подмножества будут иметь вид: { Ø }, {a}, {b}, {c}, {ab}, {ac}, {bc}, {abc}, т. е. 2^|A| =2³=8.

Задачи с множествами, особенно на компьютере, удобно решать, используя характеристические векторы.

· Операция объединения подмножеств может быть выполнена логическим сложением соответствующих элементов характеристических векторов этих подмножеств.

При объединении множеств соответствующие элементы характеристических векторов складывают по правилу:

· Операция пересечения подмножеств может быть выполнена логическим умножением соответствующих элементов характеристических векторов этих подмножеств.

При пересечении множеств соответствующие элементы характеристических векторов считают по правилу:

· При нахождении отрицания нули меняют на единицы, единицы – на нули;

4) При нахождении разности , используют формулу:

Пример Пусть I = {1, 2, 3, 4, 5, 6}, А={1, 2, 4, 5} и В={3, 5} Характеристическим вектором множества А является вектор а : = (1, 1, 0, 1, 1, 0). Характеристический вектор множества В равен b := (0, 0, 1, 0, 1, 0).

Тогда:

Вычислим характеристический вектор множества A U . Он равен

а или (не b) = (1, 1, 0, 1, 1, 0) или (1, 1, 0 1, 0, 1) = (1,1,0,1,1,1).

Следовательно, A U = {1, 2, 4, 5, 6}.

· При нахождении симметричной разности А + В используют формулу: A+B=(A\B)È(B\A)

Пример Пусть I = {1, 2, 3, 4, 5, 6}, А={1, 2, 4, 5} и В={3, 5} Характеристическим вектором множества А является век­тор а : = (1, 1, 0, 1, 1, 0). Характеристический вектор множе­ства В равен b := (0, 0, 1, 0, 1, 0).

Тогда:

· Вычислим характеристический вектор множества A U В .

. Откуда A U В = {1, 2, 3, 4, 5}

· Вычислим характеристический вектор множества .

. Откуда ={5}.

· Вычислим характеристический вектор множества .

Век­тор а : = (1, 1, 0, 1, 1, 0). . Тогда множество ={ 3, 6}.

· Вычислим разность , используем формулу: .

Характеристический вектор множества А: а : = (1, 1, 0, 1, 1,0).

Характеристический вектор множества

. Откуда A\ B= {1, 2, 4 }