Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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

Читайте также:
  1. Cent; Операции над множествами
  2. Cent; Основные законы над множествами
  3. Cent; Понятие множества. Способы задания множества
  4. Алгоритм построения множества Мандельброта
  5. Б) Кассационная жалоба или представление
  6. Б) представлением
  7. Билет №4. Представление информации в ПК. Двоичное кодирование информации. Системы счисления, применяемые в ПК.
  8. Бюджетная линия потребителя. Наклон бюджетной линии. Понятие бюджетного множества. Уравнение бюджетной линии.
  9. В3. Представление в отчетности финансовых активов по НСФО.
  10. В3. Представление в отчетности финансовых обязательств и производных инструментов по НСФО.

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

 

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

Пример. А = {a, b, c}. Подмножества будут иметь вид: { Ø }, {a}, {b}, {c}, {ab}, {ac}, {bc}, {abc}, т. е. 2|A| =23=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 }


Дата добавления: 2015-07-26; просмотров: 22; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Свойства действий над множествами. Алгебра теории множеств | Решение.
lektsii.com - Лекции.Ком - 2014-2019 год. (0.014 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты