42416

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

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

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

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

Русский

2013-10-29

758 KB

191 чел.

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


 

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

42694. Тестирование с целью определения характеристик компьютерной системы 146 KB
  4 dobe Bridge 1.0 dobe Common File Instller 1.0000 dobe Flsh Plyer 10 ctiveX 10.64 dobe Flsh Plyer 10 Plugin 10.
42695. Гидродинамика псевдосжиженого слоя 35 KB
  Гидродинамика псевдосжиженого слоя. Определение критической скорости газа Wкр скорости начала уноса слоя Gсл и расхода газа Vук при котором начинается унос твердых частиц из аппарата. Сопротивление кипящего слоя показывает дифманометр 10 который измеряет разность давлений внутри аппарата над кипящим слоем и под решёткой. После загрузки в аппарат измеряется высота слоя.
42696. Коммерческая работа по организации хозяйственных связей с поставщиками ювелирных изделий 779.5 KB
  Раскрыть сущность и содержание коммерческой работы по организации хозяйственных связей с поставщиками, их правовое регулирование; выявить факторы, влияющие на организацию хозяйственных связей с поставщиками; дать экономико-организационную характеристику ЗАО «ПроРАМПО»; провести анализ информационного обеспечения коммерческой деятельности и работы по определению потребности в товарах; охарактеризовать поставщиков ювелирных изделий;
42697. ОЗНАКОМЛЕНИЕ С ПАКЕТОМ АНАЛИЗА ЭЛЕКТРОННЫХ СХЕМ WORKBENCH 102.5 KB
  Необходимо: знать состав пакета его возможности а также используемые математические модели с помощью которых в нем описываются компоненты РЭА; уметь пользоваться меню и контекстной помощью; уметь самостоятельно набирать схемы в графическом редакторе пакета; знать и понимать принцип действия реальных измерительных приборов аналоги которых применяются в пакете; уметь объяснить отличие реальных приборов от их моделей; знать чем вызваны погрешности измерения и их теорию; уметь анализировать схемы с помощью средств пакета....
42698. Основные приемы программирования. Разветвления 78.5 KB
  h подключение библиотеки switch это оператор для выбора одного из многих продолжений cout счет вывод cse N выбор условия flot тип данных printf вывод scnf считывание defult: brek завершение условия switch= count= brek if else условие Текст программы решения задачи на языке высокого уровня С include stdfx.h int min { setlocleLC_LL RUS ;int lm = 0; для меню cout Выберите желаемое действие: endl; cout 1: Решить задачу: endl; cout 2: Выйти из приложения без решения задачи endl; cout Введите желаемое действие: ;...
42700. Алгоритмизация циклических вычислительных процессов 101 KB
  Спецификации всех разработанных процедур и/или функций. Данная программа считает заданную по условию задачи формулу, находит сумму чисел, а также наибольшее число и выводит все это на экран. Программа реализованна в связи с условиями задачи т.е создает массив нужный пользователю далее с помощью 3 разных циклов for, while (постусловием), while (предусловвием) выполняет условия задачи.
42701. Создание игры Spider 2 154 KB
  Успех вашего проекта во многом будет зависеть от выбранной вами платформой под которую будет вестись разработка, жанра игры и аудитории на которую рассчитана эта игра. Проект, процесс разработки которого, я бы хотел описать в этой курсовой работе я начал разрабатывать, потому что мне это нравится и я хотел получить опыт разработки под платформу Android
42702. Криптографические алгоритмы. Процесс формирования цифровой подписи 2.64 MB
  Криптографическая система PGP . Ознакомиться с программой PGP. Работа с программой PGP В консоли: Сгенерировать вашу собственную уникальную пару секретный открытый ключи. Проверка подлинности подписи В случае успешной верификации будет выведенно сообщение: Работа с криптографическими средствами программы PGP Pretty Good Privcy PGP выпущено фирмой Phil's Pretty Good Softwre и является криптографической системой с высокой степенью секретности.