Лабораторная работа 5 Изучение множеств с помощью их числовых кодов

1. Цель работы

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

2. Краткие теоретические положения

Одномерный булевский куб это  множество, состоящее из 0 и 1.

Многомерный булевский куб  множество n-координатных двоичных наборов, n-мерный булевский куб. При этом  мощность множества , например,. Для каждого двоичного вектораопределяется числодесятичный эквивалент двоичного набораили номер набора, при этом, где правая часть соотношения принадлежности это множество всех возможных номеров двоичных наборов.

Пример 2.1.

Соответствие взаимно-однозначно, то есть является нумерующей биекцией .

Пример 2.2 Найти 5-мерный двоичный набор , для которого.

Решение. Используем таблицу весов двоичных разрядов:

	5	4	3	2	1	0
	32	16	8	4	2	1

Имеем начальное число Находим наибольший вес. Таким весом являетсяВыделяем найденный максимальный вес разряда, получаем.

К остатку применяем тот же алгоритм. Получаем, где  новый остаток.

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

Работа алгоритма закончена. В результате получено разложение исходного числа по степеням 2:. Получаем ответ задачи:

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

Пример 2.. Дан универсум . Найти десятичный эквивалент подмножества универсума .

Решение. Строим характеристический булев вектор: . Находим десятичный эквивалент данного подмножества:

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

Пример 2.3. Дан универсум . Найти состав подмножества универсума, которое имеет десятичный эквивалент

Решение. Находим 4-разрядное двоичное число, соответствующее десятичному числу 14:

Выписываем состав искомого подмножества:

.

3. Задание

   1. Задание 1

Дан универсум и подмножествоэтого универсума. Найти десятичный числовой кодданного подмножества. Считать, что элементы универсума пронумерованы в естественном порядке слева направо.

Индивидуальные задания

№ вар	U	A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. Задание 2

Дан универсум и целое число. Найти подмножествоуниверсума, для которого десятичный числовой код(каноническая нумерация) равен заданному числу. Считать, что элементы универсума пронумерованы в естественном порядке слева направо.