42416

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

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

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

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

Русский

2013-10-29

758 KB

176 чел.

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


 

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

52056. Інтерактивні технології навчання на уроках математики та інформатики 419 KB
  Інтерактивне навчання 3 2 розділ. Використання інтерактивного навчання на уроках інформатики 15 4. Використання інтерактивного навчання на уроках математики 24 5.
52057. Урок-концерт з іноземної мови у 4 класi 981 KB
  Teacher. Good morning, dear guests! Good morning, dear boys and girls. We would like to show you how we can rest and play. I know that all of you like study English. Do you like riddles? Guess!
52058. До побачення, Букварику! 47 KB
  Я літери вчу. Ой ніколи гратись бо літери вчу. Шановні літери ласкаво просимо до нас на свято. Заходять літери 1а літера.
52059. Розвиток координації рухів засобами художньої гімнастики 66.5 KB
  Розвивати координацію рухів у дівчат старшої ланки засобами художньої гімнастики. Формувати компетенцію саморозвитку та самоосвіти під час виконання вправ з м`чем, обручем, скакалкою.
52060. МЕДИЦИНСКАЯ ЗАЩИТА НАСЕЛЕНИЯ И СПАСАТЕЛЕЙ В ЧРЕЗВЫЧАЙНЫХ СИТУАЦИЯХ 108 KB
  Медицинская защита - комплекс мероприятий, проводимых (организуемых) службой медицины катастроф и медицинской службой гражданской обороны (МСГО) для предупреждения или максимального ослабления воздействия на население и спасателей поражающих факторов.
52061. Калинка — згадка про добре серце 96 KB
  Організація класу Слайд 1 Вчитель: Любі діти у наш клас Завітали гості щирі . Метод Мікрофон Слайд 2 А цікаво вам дізнатись Що сьогодні може статись Ну то всядьтеся зручніше Попрацюємо скоріше Діти а до якого уроку ми приготувалися до уроку читання Що ми робимо на уроках читання читаємо; вчимося читати і переказувати; вивчаємо прислівя приказки скоромовки і т. Слайд 3 Дихальні вправи. Слайд4...
52062. Володимир Винниченко. «Федько — халамидник». Щедрий на добро внутрішній світ героя. Федько як особистість. Образи Федька і Толі 141 KB
  Образи Федька і Толі. Образи Федька і Толі. На уроці ми з вами визначимо риси характеру Федька які вирізняють його з кола друзів однолітків прокоментуємо їх. Порівняємо Федька і Толю зробимо відповідні висновки.
52063. Подорож. Переваги і недоліки різних видів подорожей 76.5 KB
  Travelling by plane is the fastest. You can get to many cities only in a few hours. You can stop wherever you like. During the trip you can sit comfortably in the armchair and read, eat or sleep. During the trip you need no tickets. People can
52064. Підсумковий урок – подорож «Синоніми, антоніми, омоніми» 37.5 KB
  учні дають визначення синонімам наводять приклади; Гра Синонімічний ланцюжок І варіант щирий ІІ варіант казати ІІІ варіант кричати виконання вправ за варіантами різних рівнів складності І варіант скласти звязний текст з синонімічного ланцюжка ІІ варіант відредагувати речення замінивши однокореневі слова синонімами. ІІІ варіант Підберіть потрібне слово. Коли групи приїхали на зупинку диктор оголошував назву станції але мікрофон був зламаний і ми почули останні слова деньніч Зясуємо яке це місто...