42416

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

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

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

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

Русский

2013-10-29

758 KB

172 чел.

Практическое занятие №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  


 

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

14093. Свята в Україні. План-конспект уроку з англійської мови для учнів 11-х класів 38 KB
  Планконспект уроку з англійської мови для учнів 11х класів Урок 115 Тема: Людина й природа Підтема: Свята в Україні Мета: Повторити ЛО теми. Практикувати учнів у непідготовлених висловлюваннях за темою уроку. Продемонструвати граматичні структури Perfect Infinitive у ти
14094. Шляхи покращення маркетингової діяльності ДП ВАТ «Київхліб» «Булочно-кондитерський комбінат» 1.07 MB
  Виявлення маркетингових можливостей, які відповідають ресурсам фірми; визначення маркетингових загроз і розробка заходів щодо знешкодження їхнього впливу; виявлення сильних сторін фірми й зіставлення їх з ринковими можливостями; визначення слабкостей фірми та розроблення стратегічних напрямів їх подолання; виявлення ролі функціональної маркетингової стратегії в розвитку підприємства; напрацювання комбінованої стратегії росту для ДП ВАТ «Київхліб» «Булочно-кондитерський комбінат»...
14095. Наша Земля - наш дім. План-конспект уроку з англійської мови для учнів 11-х класів 16.31 KB
  Планконспект уроку з англійської мови для учнів 11х класів Урок 118 Тема: Природа й людина Підтема: Наша Земля наш дім. Мета: Закріпляти та розвивати мовні навички. Підкреслити необхідність захисту оточуючого середовища. Обладнання: підручник плакати малюнки за...
14096. Оценка анализа и конкуренции на примере ООО «Уралпромсрой» за период 2007-2008 годов 133.96 KB
  Стратегический менеджмент как концепция управления фирмой позволяет взглянуть на организацию как на единое целое, объяснить с общесистемных позиций, почему происходит постоянное перераспределение ролей основных участников рынка.
14097. Роль массажа в комплексной реабилитации больных бронхиальной астмой 48.78 KB
  Астма - это хроническое воспалительное заболевание дыхательных путей. При наличии предрасположенности это воспаление вызывает повторяющиеся приступы кашля, хрипов, возникает чувство сдавления в груди, дыхание затруднено
14098. Форматування диска. Діагностика та дефрагментація дисків. Відновлення інформації на диску. Правила записування та зчитування інформації з дискет 218.5 KB
  Тема: Форматування диска. Діагностика та дефрагментація дисків. Відновлення інформації на диску. Правила записування та зчитування інформації з дискет. Мета: Охарактеризувати нову тему висвітлити її роль в курсі інформатики. Ввести поняття форматування діагностики
14099. Розпис тарелі «Летіла зозуля з яру в долину» та Ліплення з пластиліну на тему «Красивий кіт» 1.47 MB
  Конспект залікового уроку з Образотворчого мистецтва проведеного в 2А класі ЗОШ ІІІІ ступенів № 2 Тема уроку: Розпис тарелі Летіла зозуля з яру в долину. Мета. Ознайомити учнів із традиційним видом українського декоративноприкладного мистецтва – петриківським ...
14100. Конструювання моделей із сірникових коробок та Аплікація. Види аплікацій. Естетика і культура 5.11 MB
  Конспект залікового уроку з трудового навчання проведеного в 2А класі ЗОШ ІІІІ ступенів № 2 Тема уроку: Конструювання моделей із сірникових коробок. Об’єкт праці. Виготовлення моделей вантажних та легкових автомобілів. Мета. Ознайомити учнів із поняттям констр
14101. Конспект уроку Я і Україна. Декларація прав дитини. Про доброту і милосердя 607.11 KB
  Конспект уроку Я і Україна 2 клас 02. 03 Тема. Декларація прав дитини. Основний Закон держави. Обов’язки батьків та дітей. Мета. Формувати в учнів уявлення про Декларацію прав людини Основний Закон нашої держави; з’ясувати обов’язки батьків і дітей; виховувати шано...