42416

Теория множеств. Операции над множествами. Диаграммы Венна

Лабораторная работа

Математика и математический анализ

Тип данных представляет собой множество объектов со списком стандартных операций над ними. Множество  это совокупность объектов называемых элементами множества. Объекты которые образуют множество называются элементами этого множества. Пример: Множество S = {3 2 11 5 7}  элементы множества записывают в фигурных скобках.

Русский

2013-10-29

758 KB

175 чел.

Практическое занятие №3

Тема: Теория множеств. Операции над множествами.

Диаграммы Венна.

Занятие рассчитано на 4 академических часа.

Цель работы: ознакомиться с основными понятиями: логика, дискретная математика, теории множеств, операциями над множествами, законами алгебры множеств. Изучить основные приемы доказательства тождеств в теории множеств.

Дискретная математика и логика лежат в основе любого современного изучения информатики. Слово «дискретный» означает «составленный из отдельных частей», а дискретная математика имеет дело с совокупностями объектов, называемых множествами, определенными на них структурами. Элементы этих множеств изолированы друг от друга и геометрически не связаны. Действительно, большинство интересующих нас множеств конечны или, по крайней мере, счетны.

Эта область математики привлекается для решения задач на компьютере в терминах аппаратных средств и программного обеспечения с привлечением организации символов и манипуляции данными. Современный цифровой компьютер — по существу конечная дискретная система. Понимания того, как такая машина работает, можно достигнуть, если представить машину как дискретную математическую систему.

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

Теория множеств обеспечивает удобный язык для описания концепций в математике и информатике. Мы введем понятие множества и опишем различные способы комбинирования разных множеств для получения новых. Результат операций объединения, пересечения, дополнения и симметрической разности иллюстрируется на диаграммах Венна, будет сформулирован набор тождеств. Некоторое число этих тождеств, собранных вместе, определяют законы алгебры множеств и, в свою очередь, будут использованы для вывода более сложных соотношений.

Теоретический материал

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

Множество это совокупность объектов, называемых элементами множества.  Объекты, которые образуют множество, называются элементами  этого множества. Пример: Множество S = {3, 2, 11, 5, 7} элементы множества записывают в фигурных скобках.

Принадлежность элемента множеству обозначается значком , например, 3  S, 8  S.

Некоторые множества имеют стандартные названия и обозначения:

— пустое множество;

N = {1, 2, 3, ...} — множество натуральных чисел;

Z = {0, ±1, ±2, ±3, ...} — множество целых чисел;

Q = {p,q Z, q0} — множество рациональных чисел;

R = {все десятичные дроби} — множество вещественных чисел.

Принцип объемности: множества А и S равны, если они состоят из одних и тех же элементов, в противном случае А  S.

Совокупность допустимых объектов рассматривается как подмножество основного множества U (универсума). Для наглядного изображения соотношений между подмножествами  универсума U используются диаграммы Венна

Например, универсумом арифметики служат числа, в зоологии – мир животных, в лингвистике – слова.

Через (читается "содержится либо совпадает") обозначают отношение включения между множествами, т.е. АS, если каждый элемент множества А есть элемент множества S. Тогда говорят, что А есть подмножество множества S. Если АS и АS, то говорят, что А есть собственное множество S, и пишут АS.

Рис.1 Диаграмма Венна подмножества АS.

Для доказательства равенства множеств А=B необходимо проверить истинность двух импликаций:

А х  B} и {х  B  х А}.

Операции над множествами

Объединением множеств А и В называется множество АВ, все элементы которого являются элементами множества А или В:

АВ= {x: xA или xB}.

Рис.2 Диаграмма Венна объединения АВ.

Пересечением множеств А и В называется множество АВ, все элементы которого являются элементами обоих множеств А и В:

АВ= {x: xA и xB}.

Рис.3 Диаграмма Венна пересечения АВ.

Выполняется включение АВААВ и АВВАВ.

Дополнением множества B до множества A называется множество

A\B = {х: x A и x B}

Рис.4 Диаграмма Венна разности А\В.

Симметрической разностью множеств А и В называется множество А+В={х: (x A и x B) или (x B и x A)}.

Рис.5 Диаграмма Венна симметрической разности А+В.

Абсолютным дополнением множества А называется множество  всех тех элементов х, которые не принадлежат множеству А:

. Заметим, что X\A=XA.

Рис.6 Диаграмма Венна дополнения .

Законы алгебры множеств

Для любых подмножеств А, В и С универсального множества U выполняются следующие тождества:

Законы коммутативности

А В=В А    А В=ВА

Законы ассоциативности

А С)=(А В) С   АС)=(АВ)С

Законы дистрибутивности

АС)=(А В) С)  АС)=(АВ)  С)

Законы тождества

А =А     А U=А

АU=U      А= 

Законы дополнения

А А=U      А А= 

=U          U=

Законы идемпотентности

А А=А             АА=А

Законы поглощения

АВ)=А      АВ)=А

Законы де Моргана

 В)= А В      В)= А В

Доказательство тождеств, основанное на отношении принадлежности.

Докажем, что А С) = (А В) С)

Доказательство: Если хА С), то x A или x BC. Если x A, то хАВ и хАС.  Следовательно, хВ)С). Если хВС, то хВ и хС. Отсюда хВА и хСА, а значит , хВ)С).   (1)

Докажем противоположное, что (А В)С)АС).

Если хВ)С), то хАВ и хАС.

Следовательно хА или хВ и хС, т.е. хВС.

Отсюда  хАС).         (2)

Отношение (1) и (2) доказывают равенство  АС)=(АВ)С).

Мощность множества, декартово произведение, степень множества.

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

Мощностью конечного множества S называется число его элементов. Она обозначается символом |S|.

Теорема (правило вычисления мощности объединения двух множеств):

|AB| = |А|+|В||А||В|.

Эту формулу можно обобщить на произвольное конечное число множеств.

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

Познакомимся с упорядоченной парой. Упорядоченной парой называется запись вида (a, b), где а элемент некоторого множества А, а b  элемент множества В.

Множество всех таких упорядоченных пар называется декартовым или прямым произведением множеств А и В и обозначается А В.

Следовательно, А В = {(a, b) : a А и b  В}.

Операция прямого произведения множеств имеет практическое значение, поскольку вплотную подводит к понятиям «отношение» и «функция», играющим заметную роль в информатике и составляющим предмет изучения следующих практических занятий.

Методические рекомендации

Пример 1: Пусть А = {1, 3, 5, 7}; В = {2, 4, 6, 8}; С = {1, 2, 3, 4, 5}.

Найдите АС, ВС, А\С и В+С.

Решение.

AC = {1, 2, 3, 4, 5, 7}; ВС = {2, 4}; А\С= {7};

В+С = (B\C)U(C\B) = {6, 8}U{1, 3, 5} = {6, 8, 1, 3, 5}.

Пример 2: Пусть А = {х, у} и В = {1, 2, 3}.

Найдите декартовы произведения: АВ, ВА и ВВ.

Решение.

Прямым произведением АВ является множество: {(х, 1), (х, 2), (х, 3), (у, 1), (у, 2), (у, 3)}.

Прямое произведение ВА: {1, х), 2, х), 3, х), (1, у), (2, у), (3, у)}.

Множества АВ и ВА различны!

Прямым произведением ВВ служит множество: {1, 1), 1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}.

Мощность прямого произведения конечных множеств А и В равна:

В| = mn, если |А| = m и |В|= n.

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

Диаграмма Венна, иллюстрирующая прямое произведение множества А В

Рисунок 7.

Пример 3. Пусть В = {0, 1}. Опишите множество Вn.

Решение. Множество В состоит из последовательностей нулей и единиц длины n. Они называются строкой бит или битовой строкой длины n.

Покажем, как строка бит применяется для моделирования операций на конечных множествах.

Пусть S = {s1, s2, s3, s4, … sn}. Если AS, мы поставим ему в соответствие n-битную строку (b1, b2, …bn), где bi = 1, если si  А и bi = 0 в противном случае. Такая строка бит называется характеристическим вектором подмножества А. 

Теперь мы можем имитировать операции на множествах логическими операциями, применяемыми к соответствующим характеристическим векторам, условившись считать 1 за И, а 0 за Л.

Пример 4. Пусть S = {1, 2, 3, 4, 5}, А = {1, 3, 5} и В = {3, 4}. Выписать характеристические векторы А и В, а затем определить характеристические векторы множеств A В, А В и .

Решение. Характеристическим вектором множества А является а = (1, 0, 1, 0, 1), а характеристический вектор множества В равен b = (0, 0, 1, 1, 0). Значит,

а или b = (1, 0, 1, 0, 1) или (0, 0, 1, 1, 0) =(1, 0, 1, 1, 1);

а и b = (1, 0, 1, 0, 1) и (0, 0, 1, 1, 0) = (0, 0, 1, 0, 0);

не b = не (0, 0, 1, 1, 0) = (1, 1, 0, 0, 1).

Полученные векторы позволяют нам «без запинки прочитать» элементы требуемых подмножеств: А В = {1, 3, 4, 5}, А В = {3} и  = {1, 2, 5}.

Контрольные вопросы

  1.  Что такое множество? Как обозначают пустое множество, универсальное? Запишите множества натуральных, целых, рациональных, вещественных чисел.
  2.  Дайте определение подмножества. Какие множества называются равными?
  3.  Запишите объединение, пересечение, дополнение, симметрическую разность двух множеств.
  4.  Что означает выражение «декартово произведение множеств»? Покажите на своем примере.

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

1. Определить в каких отношениях находятся между собой три множества:

1) А{1, 3}; B – множество нечетных положительных чисел; С – множество решений уравнения X24X+3=0.

2) A={1, 2, 3}; B={2, 3}; C – множество решений уравнения Х1=0.

3) U={1, 2, 3, … , 20}, A – множество четных чисел, В – множество нечетных чисел.

4) А – множество решений уравнения 2Х28X+6=0; В – множество решений уравнения X-1=0; N – множество натуральных чисел.

5) A={a, b, c}; B={a, b, d}; C={b, c}.

6) A={a, b}; B={a, c}; C={a, b, c}.

7) A={a}; B={{a}, {b}}; C={b}.

8) A – множество решений уравнения Х5=0; В множество решений уравнения Х29=0; C={{5}, {3}}.

9) A – множество решений уравнения X24X+3=0; B={{1}, {3}}; C – множество нечетных натуральных чисел.

10) A={a, b, c}; B={{c}}; C={c}.

11) A={a, b}; B={b, c}; C={a}.

12) A={a}; B={b}; C={a, b, c}.

2. Приняв множество первых 20 натуральных чисел в качестве универсума U, запишите его подмножества: А – четных чисел; В – нечетных чисел; С – квадратов чисел; D – простых чисел; и запишите множества, которые получатся в результате следующих операций:

1) АВ; 2) АВ; 3) АС; 4) АD; 5) C – А; 6) C – В; 7) C+D; 8) UA;

9) UB; 10) UD; 11) UA; 12) AB.

3. Множества А, В, С представленные кругами Эйлера. Записать с помощью операций над множествами выражения для множеств, соответственно заштрихованным областям:

1        2

3        4

  1.  

6

7        8

  1.  

10

11        12

4. Исходя из отношения принадлежности () докажите тождественность:

  1.  А(В – А) = А В;
  2.  А(В – А) = ;
  3.  А – (А В) =А -В;
  4.  А(В – С) =(АВ) – С;
  5.  А – (ВС) =(А – В)(А – С);
  6.  А – (В С) =(А – В)  (А – С);
  7.  В) – С=(А – С)(В – С);
  8.  АВС=(АС)С);
  9.  АС)=(АВ)С;
  10.  АА=U;
  11.  AU=U;
  12.  C – (АВ)=(С – A)(С – B).

5. Докажите тождественность, используя свойства операций над множествами:

  1.  (ABC)  ( ABC)=BC;
  2.  ((AX)  (BX))  ((CX)  (DX))=((AC) X)  ((BD)X)
  3.  (ABCX)  ( AC)  ( BC)  (CX)=C;
  4.   ((AX)  (BX))=( AX)  (BX);
  5.  A (B+C)=(AB)+(AC);
  6.  ABB=AB;
  7.  A – (A – B)=B – (B – A);
  8.  (A – B) – C=(A – C)(B – C);
  9.  (M – N)  (N – M)= ;
  10.  A (AB)=A;
  11.   (AB)= AB;
  12.  (AB)= AB.

  1.  Пусть U = {1, 2, 3, 4, 5, 6} — универсальное множество. Выпишите характеристические векторы подмножеств: А = {1,2,4,5} и В = {3,5}. Найдите характеристические векторы подмножеств AU и А+В, после чего перечислите их элементы.

Литература

  1.  Бардачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика. – К.: Вища освіта., 2002. – 287с.
  2.  Мельников В.Н. Логические задачи. – К. «Вища школа», 1989.
  3.  Игошин В. И. Математическая логика и теория алгоритмов : учеб.  

пособие для студ. высш. учеб. заведений / В. И. Игошин— 2-е изд.,

стер. — М. : Издательский центр «Академия», 2008. — 448 с.

  1.  Игошин В. И Задачи и упражнения по математической логике и  теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И.Игошин. — 3-е изд., стер. — М. : Издательский центр «Академия», 2007. — 304 с.


EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  

EMBED PBrush  


 

А также другие работы, которые могут Вас заинтересовать

32641. Принципы и процессы планирования проекта. Уровни планирования 62.5 KB
  Принципы и процессы планирования проекта. Принципы и процессы планирования Сущность планирования состоит в задании целей и способов их достижения на основе формирования комплекса работ мероприятий действий которые должны быть выполнены применении методов и средств реализации этих работ увязки ресурсов необходимых для их выполнения согласовании действий организаций участников проекта. Основная цель планирования состоит в построении модели реализации проекта. Она необходима для координации деятельности участников проекта с ее помощью...
32642. Формирование статей затрат проекта. Калькуляция расходов, сметы, бюджет проекта 27.5 KB
  Формирование статей затрат проекта. Калькуляция расходов сметы бюджет проекта. Бюджет проекта предназначен для планирования расхода средств проекта по временным периодам год квартал месяц в течение всего времени его осуществления. Обычно расход средств проекта первого года планируется более подробно показывается поквартальное и помесячное распределение денежных средств.
32643. Управление качеством в проекте 40 KB
  Управление качеством в проекте. Управление качеством Одной из ключевых функций управления проектом наряду с такими как управление стоимостью и временем является управление качеством проекта. Качество это целостная совокупность характеристик объекта относящихся к его способности удовлетворять установленные или предполагаемые потребности. Понятие качество следует отличать от понятия градация сорт класс.
32644. Проектные риски и их основные виды 39.5 KB
  Вероятность рисков это вероятность того что в результате принятия решения произойдут потери для предприятия то есть вероятность нежелательного исхода. Проектные риски – это совокупность рисков угрожающих реализации инвестиционного проекта или способных снизить его эффективность коммерческую экономическую бюджетную социальную и т. Виды инвестиционных рисков многообразны. В отдельных источниках также выделяют такие риски как: риск связанный с отраслью производства вложение в производство товаров народ ного потребления в среднем...
32645. Методы анализа и прогнозирования риска и неопределенности в проекте 274.5 KB
  Анализ рисков – процедуры выявления факторов рисков и оценки их значимости по сути анализ вероятности того что произойдут определенные нежелательные события и отрицательно повлияют на достижение целей проекта. Анализ рисков включает оценку рисков и методы снижения рисков или уменьшения связанных с ним неблагоприятных последствий. Назначение анализа рисков дать потенциальным партнерам необходимые данные для принятия ре шений о целесообразности участия в проекте и выработки мер по защите от воз можных финансовых потерь. Анализ рисков можно...
32646. Методы снижения риска в проекте 465.5 KB
  Принципы выбора метода снижения риска Нельзя рисковать больше чем это может позволить собственный капитал; Надо думать о последствиях риска; Нельзя рисковать многим ради малого. Кр = У С где Кр – коэффициент риска У – максимально возможная сумма убытка; С – объем собственных ресурсов с учетом точно известных поступлений средств. Методы снижения риска Распределение риска между участниками сделки долевое финансирование проектов Гарантии Лимитирование установление предельных сумм сделок кредита Резервные фонды Залог Модель управления...
32647. Контрактная работа над проектом 37 KB
  Контрактная стадия проекта открывает фазу реализации проекта и следует сразу за фазой предынвестиционных исследований за принятием решения о вложении инвестиций в проект. На этой стадии определяются все участники проекта контракторы отношения которых с заказчиком формализуются в контрактах. Определение потребности в ресурсах работах и услугах необходимых для реализации проекта. Определение потенциальных участников проекта контракторов и анализ их возможностей.
32648. Организация и проведение подрядных торгов для заключения контрактов по проектам 35 KB
  Организация и проведение подрядных торгов для заключения контрактов по проектам. Объект торгов производственный или непроизводственный объект к которому относится предмет торгов. Предмет торгов конкретные виды работ и услуг по которым проводятся торги. В качестве предмета торгов могут выступать подряды на: строительство реконструкцию и капитальный ремонт предприятий зданий сооружений производственного и непроизводственного назначения в том числе на условиях под ключ; выполнение комплексов строительных и монтажных работ и их...
32649. Организация работ и выполнение проекта 29 KB
  Организация работ и выполнение проекта. Задачи управления проектом при его выполнении выполнение сводного плана проекта – реализация плана проекта путем выполнения включенных в него работ; подтверждение предметной области – процесс формальной приемки предметной области проекта. обеспечение качества – процесс регулярной оценки выполнения работ проекта для подтверждения того что проект будет удовлетворять принятым стандартам качества. развитие команды – освоение индивидуальных и групповых навыков и квалификации для улучшения выполнения...