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

Практическое занятие №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, q0} — множество рациональных чисел; R = {все десятичные дроби} — множество вещественных чисел. Принцип объемности: множества А и S равны, если они состоят из одних и тех же элементов, в противном случае А  S. Совокупность допустимых объектов рассматривается как подмножество основного множества U (универсума). Для наглядного изображения соотношений между подмножествами универсума U используются диаграммы Венна Например, универсумом арифметики служат числа, в зоологии – мир животных, в лингвистике – слова. Через  (читается "содержится либо совпадает") обозначают отношение включения между множествами, т.е. АS, если каждый элемент множества А есть элемент множества S. Тогда говорят, что А есть подмножество множества S. Если АS и АS, то говорят, что А есть собственное множество S, и пишут АS. Рис.1 Диаграмма Венна подмножества АS. Для доказательства равенства множеств А=B необходимо проверить истинность двух импликаций: {х  А  х  B} и {х  B  х  А}. Операции над множествами Объединением множеств А и В называется множество АВ, все элементы которого являются элементами множества А или В: АВ= {x: xA или xB}. Рис.2 Диаграмма Венна объединения АВ. Пересечением множеств А и В называется множество АВ, все элементы которого являются элементами обоих множеств А и В: АВ= {x: xA и xB}. Рис.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 BC. Если x A, то хАВ и хАС. Следовательно, х(АВ)(АС). Если хВС, то хВ и хС. Отсюда хВА и хСА, а значит , х(АВ)(АС). (1) Докажем противоположное, что (А В)(АС)А(ВС). Если х(АВ)(АС), то хАВ и хАС. Следовательно хА или хВ и хС, т.е. хВС. Отсюда хА(ВС). (2) Отношение (1) и (2) доказывают равенство А(ВС)=(АВ)(АС). Мощность множества, декартово произведение, степень множества. Вопросы пересчета количества элементов в множествах становятся очень важными, когда у Вас ограничены ресурсы. Например, сколько пользователей может поддерживать данная компьютерная сеть? Или сколько операций будет сделано при работе данного алгоритма? Мощностью конечного множества S называется число его элементов. Она обозначается символом |S|. Теорема (правило вычисления мощности объединения двух множеств): |AB| = |А|+|В||А||В|. Эту формулу можно обобщить на произвольное конечное число множеств. При обсуждении конечных множеств, порядок, в котором перечисляются их элементы, значения не имеет. Однако, бывает необходимо работать и с упорядоченными наборами. Познакомимся с упорядоченной парой. Упорядоченной парой называется запись вида (a, b), где а  элемент некоторого множества А, а b  элемент множества В. Множество всех таких упорядоченных пар называется декартовым или прямым произведением множеств А и В и обозначается А  В. Следовательно, А  В = {(a, b) : a  А и b  В}. Операция прямого произведения множеств имеет практическое значение, поскольку вплотную подводит к понятиям «отношение» и «функция», играющим заметную роль в информатике и составляющим предмет изучения следующих практических занятий. Методические рекомендации Пример 1: Пусть А = {1, 3, 5, 7}; В = {2, 4, 6, 8}; С = {1, 2, 3, 4, 5}. Найдите АС, ВС, А\С и В+С. Решение. AC = {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}. Если AS, мы поставим ему в соответствие 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 – множество нечетных положительных чисел; С – множество решений уравнения X24X+3=0. 2) A={1, 2, 3}; B={2, 3}; C – множество решений уравнения Х1=0. 3) U={1, 2, 3, … , 20}, A – множество четных чисел, В – множество нечетных чисел. 4) А – множество решений уравнения 2Х28X+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; В  множество решений уравнения Х29=0; C={{5}, {3}}. 9) A – множество решений уравнения X24X+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) U – A; 9) U – B; 10) U – D; 11) U – A; 12) AB. 3. Множества А, В, С представленные кругами Эйлера. Записать с помощью операций над множествами выражения для множеств, соответственно заштрихованным областям: 1 2 3 4 5 6 7 8 9 10 11 12 4. Исходя из отношения принадлежности () докажите тождественность: 1) А(В – А) = А В; 2) А(В – А) = ; 3) А – (А В) =А -В; 4) А(В – С) =(АВ) – С; 5) А – (ВС) =(А – В)(А – С); 6) А – (В С) =(А – В)  (А – С); 7) (АВ) – С=(А – С)(В – С); 8) АВС=(АС)(ВС); 9) А(ВС)=(АВ)С; 10) АА=U; 11) AU=U; 12) C – (АВ)=(С – A)(С – B). 5. Докажите тождественность, используя свойства операций над множествами: 1) (ABC)  ( ABC)=BC; 2) ((AX)  (BX))  ((CX)  (DX))=((AC) X)  ((BD)X) 3) (ABCX)  ( AC)  ( BC)  (CX)=C; 4)  ((AX)  (BX))=( AX)  (BX); 5) A (B+C)=(AB)+(AC); 6) ABB=AB; 7) A – (A – B)=B – (B – A); 8) (A – B) – C=(A – C)(B – C); 9) (M – N)  (N – M)= ; 10) A (AB)=A; 11)  (AB)= AB; 12) (AB)= AB. 6. Пусть U = {1, 2, 3, 4, 5, 6} — универсальное множество. Выпишите характеристические векторы подмножеств: А = {1,2,4,5} и В = {3,5}. Найдите характеристические векторы подмножеств AU и А+В, после чего перечислите их элементы. Литература 1. Бардачов Ю.М., Соколова Н.А., Ходаков В.Є. Дискретна математика. – К.: Вища освіта., 2002. – 287с. 2. Мельников В.Н. Логические задачи. – К. «Вища школа», 1989. 3. Игошин В. И. Математическая логика и теория алгоритмов : учеб. пособие для студ. высш. учеб. заведений / В. И. Игошин— 2-е изд., стер. — М. : Издательский центр «Академия», 2008. — 448 с. 4. Игошин В. И Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И.Игошин. — 3-е изд., стер. — М. : Издательский центр «Академия», 2007. — 304 с.