Дискретная математика - множества

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

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

Set - Определение

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

Некоторые примеры множеств

  • Набор всех натуральных чисел
  • Набор всех планет Солнечной системы
  • Множество всех штатов в Индии
  • Набор всех строчных букв алфавита

Представление набора

Наборы могут быть представлены двумя способами -

  • Реестр или Табличная форма
  • Установить нотацию Builder

Реестр или Табличная форма

Набор представлен списком всех составляющих его элементов. Элементы заключены в фигурные скобки и разделены запятыми.

Пример 1 - Набор гласных в английском алфавите, $ A = \ lbrace a, e, i, o, u \ rbrace $

Пример 2 - Набор нечетных чисел меньше 10, $ B = \ lbrace 1,3,5,7,9 \ rbrace $

Установить нотацию Builder

Набор определяется путем указания свойства, которое имеет общие элементы набора. Множество описывается как $ A = \ lbrace x: p (x) \ rbrace $

Пример 1. Множество $ \ lbrace a, e, i, o, u \ rbrace $ записывается как -

$ A = \ lbrace x: \ text {x - гласный в английском алфавите} \ rbrace $

Пример 2 - Множество $ \ lbrace 1,3,5,7,9 \ rbrace $ записывается как -

$ B = \ lbrace x: 1 \ le x \ lt 10 \ and \ (x \% 2) \ ne 0 \ rbrace $

Если элемент x является членом любого множества S, он обозначается через $ x \ in S $, а если элемент y не является членом множества S, он обозначается через $ y \ notin S $.

Пример - если $ S = \ lbrace1, 1.2, 1.7, 2 \ rbrace, 1 \ in S $, но $ 1.5 \ notin S $

Некоторые важные наборы

N - множество всех натуральных чисел = $ \ lbrace1, 2, 3, 4, ..... \ rbrace $

Z - множество всех целых чисел = $ \ lbrace ....., -3, -2, -1, 0, 1, 2, 3, ..... \ rbrace $

Z + - множество всех натуральных чисел

Q - множество всех рациональных чисел

R - множество всех действительных чисел

W - множество всех целых чисел

Мощность множества

Мощность множества S, обозначаемого $ | S | $, - это количество элементов множества. Номер также называется кардинальным номером. Если множество имеет бесконечное количество элементов, его мощность равна $ \ infty $.

Пример - $ | \ lbrace 1, 4, 3, 5 \ rbrace | = 4, | \ lbrace 1, 2, 3, 4, 5, \ dots \ rbrace | = \ infty $

Если есть два набора X и Y,

  • $ | X | = | Y | $ обозначает два множества X и Y, имеющих одинаковую мощность. Это происходит, когда количество элементов в X точно равно числу элементов в Y. В этом случае существует биективная функция 'f' от X до Y.

  • $ | X | \ le | Y | $ означает, что множество элементов X меньше или равно количеству элементов Y. Это происходит, когда число элементов в X меньше или равно числу элементов в Y. Здесь существует инъективная функция 'f' от X до Y.

  • $ | X | \ lt | Y | $ означает, что множество элементов X меньше, чем множество элементов Y. Это происходит, когда число элементов в X меньше, чем в Y. Здесь функция 'f' из X в Y является инъективной функцией, но не биективной.

  • $ If \ | X | \ le | Y | $ и $ | X | \ ge | Y | $, то $ | X | = | Y | $. Наборы X и Y обычно называют эквивалентными наборами.

Типы Наборов

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

Конечный набор

Множество, которое содержит определенное количество элементов, называется конечным множеством.

Пример - $ S = \ lbrace x \: | \: x \ in N $ и $ 70 \ gt x \ gt 50 \ rbrace $

Бесконечный набор

Множество, которое содержит бесконечное количество элементов, называется бесконечным множеством.

Пример - $ S = \ lbrace x \: | \: x \ in N $ и $ x \ gt 10 \ rbrace $

Подмножество

Множество X является подмножеством множества Y (записывается как $ X \ subseteq Y $), если каждый элемент X является элементом множества Y.

Пример 1. Пусть $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ и $ Y = \ lbrace 1, 2 \ rbrace $. Здесь множество Y является подмножеством множества X, так как все элементы множества Y находятся в множестве X. Следовательно, мы можем написать $ Y \ subseteq X $.

Пример 2. Пусть $ X = \ lbrace 1, 2, 3 \ rbrace $ и $ Y = \ lbrace 1, 2, 3 \ rbrace $. Здесь множество Y - это подмножество (не правильное подмножество) множества X, так как все элементы множества Y находятся в множестве X. Следовательно, мы можем написать $ Y \ subseteq X $.

Правильное подмножество

Термин «правильное подмножество» может быть определен как «подмножество, но не равно». Набор X является собственным подмножеством множества Y (записывается как $ X \ subset Y $), если каждый элемент X является элементом множества Y и $ | X | \ lt | Y | $.

Пример. Пусть $ X = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace $ и $ Y = \ lbrace 1, 2 \ rbrace $. Здесь установите $ Y \ subset X $, так как все элементы в $ Y $ также содержатся в $ X $, и $ X $ имеет хотя бы один элемент больше, чем набор $ Y $.

Универсальный комплект

Это коллекция всех элементов в определенном контексте или приложении. Все наборы в этом контексте или приложении по существу являются подмножествами этого универсального набора. Универсальные множества представлены как $ U $.

Пример. Мы можем определить $ U $ как совокупность всех животных на земле. В этом случае набор всех млекопитающих - это подмножество $ U $, набор всех рыб - это подмножество $ U $, набор всех насекомых - это подмножество $ U $, и так далее.

Пустой набор или Null набор

Пустой набор не содержит элементов. Обозначается $ \ emptyset $. Поскольку число элементов в пустом множестве конечно, пустое множество является конечным множеством. Количество элементов пустого или null набора равно нулю.

Пример - $ S = \ lbrace x \: | \: x \ in N $ и $ 7 \ lt x \ lt 8 \ rbrace = \ emptyset $

Синглтон или блок

Одиночный набор или единичный набор содержит только один элемент. Одиночное множество обозначается через $ \ lbrace s \ rbrace $.

Пример - $ S = \ lbrace x \: | \: x \ in N, \ 7 \ lt x \ lt 9 \ rbrace $ = $ \ lbrace 8 \ rbrace $

Равный Набор

Если два набора содержат одинаковые элементы, они называются равными.

Пример - если $ A = \ lbrace 1, 2, 6 \ rbrace $ и $ B = \ lbrace 6, 1, 2 \ rbrace $, они равны, так как каждый элемент множества A является элементом множества B и каждым элементом множество B является элементом множества A.

Эквивалентный набор

Если мощности двух множеств одинаковы, они называются эквивалентными множествами.

Пример. Если $ A = \ lbrace 1, 2, 6 \ rbrace $ и $ B = \ lbrace 16, 17, 22 \ rbrace $, они эквивалентны, так как мощность A равна мощности B. ie $ | A | = | B | = 3 $

Набор перекрывающихся

Два набора, которые имеют хотя бы один общий элемент, называются перекрывающимися наборами.

В случае перекрывающихся наборов -

  • $ n (A \ cup B) = n (A) + n (B) - n (A \ cap B) $

  • $ n (A \ cup B) = n (A - B) + n (B - A) + n (A \ cap B) $

  • $ n (A) = n (A - B) + n (A \ cap B) $

  • $ n (B) = n (B - A) + n (A \ cap B) $

Пример. Пусть $ A = \ lbrace 1, 2, 6 \ rbrace $ и $ B = \ lbrace 6, 12, 42 \ rbrace $. Существует общий элемент «6», поэтому эти наборы являются перекрывающимися.

Несвязанный набор

Два набора A и B называются непересекающимися, если они не имеют хотя бы одного общего элемента. Следовательно, непересекающиеся множества обладают следующими свойствами:

  • $ n (A \ cap B) = \ emptyset $

  • $ n (A \ cup B) = n (A) + n (B) $

Пример - Пусть, $ A = \ lbrace 1, 2, 6 \ rbrace $ и $ B = \ lbrace 7, 9, 14 \ rbrace $, нет ни одного общего элемента, поэтому эти наборы являются перекрывающимися.

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

Диаграмма Венна, изобретенная в 1880 году Джоном Венном, представляет собой схематическую диаграмму, которая показывает все возможные логические связи между различными математическими наборами.

Примеры

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

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

Операции над множествами включают в себя объединение множеств, пересечение множеств, разность множеств, дополнение множества и декартово произведение.

Установить Союз

Объединение множеств A и B (обозначается как $ A \ cup B $) - это множество элементов, которые находятся в A, в B или в A и B. Следовательно, $ A \ cup B = \ lbrace x \: | \: x \ in A \ OR \ x \ in B \ rbrace $.

Пример. Если $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ и B = $ \ lbrace 13, 14, 15 \ rbrace $, то $ A \ cup B = \ lbrace 10, 11, 12, 13, 14, 15 $. (Общий элемент встречается только один раз)

Установить Союз

Установить пересечение

Пересечение множеств A и B (обозначается как $ A \ cap B $) - это множество элементов, которые находятся как в A, так и в B. Следовательно, $ A \ cap B = \ lbrace x \: | \: x \ в A \ AND \ x \ in B \ rbrace $.

Пример. Если $ A = \ lbrace 11, 12, 13 \ rbrace $ и $ B = \ lbrace 13, 14, 15 \ rbrace $, то $ A \ cap B = \ lbrace 13 \ rbrace $.

Установить пересечение

Установить разницу / относительное дополнение

Разность множеств множеств A и B (обозначаемая $ A - B $) - это множество элементов, которые находятся только в A, но не в B. Следовательно, $ A - B = \ lbrace x \: | \: x \ in A \ AND \ x \ notin B \ rbrace $.

Пример. Если $ A = \ lbrace 10, 11, 12, 13 \ rbrace $ и $ B = \ lbrace 13, 14, 15 \ rbrace $, то $ (A - B) = \ lbrace 10, 11, 12 \ rbrace $ и $ (B - A) = \ lbrace 14, 15 \ rbrace $. Здесь мы можем увидеть $ (A - B) \ ne (B - A) $

Установить разницу

Дополнение набора

Дополнением множества A (обозначается $ A '$) является множество элементов, не входящих в множество A. Следовательно, $ A' = \ lbrace x | x \ notin A \ rbrace $.

В частности, $ A '= (U - A) $, где $ U $ - универсальный набор, содержащий все объекты.

Пример - если $ A = \ lbrace x \: | \: x \ \: {принадлежит \: к \: множеству \: из \: нечетных \: целых чисел} \ rbrace $ then $ A '= \ lbrace y \: | \: y \ \: {не \: не \: принадлежат \: к \: набору \: of \: нечетные \: целые числа} \ rbrace $

Набор дополнений

Декартово произведение / кросс произведение

Декартово произведение n числа множеств $ A_1, A_2, \ dots A_n $, обозначенного как $ A_1 \ times A_2 \ dots \ times A_n $, можно определить как все возможные упорядоченные пары $ (x_1, x_2, \ dots x_n) $, где $ x_1 \ in A_1, x_2 \ in A_2, \ dots x_n \ in A_n $

Пример. Если взять два набора $ A = \ lbrace a, b \ rbrace $ и $ B = \ lbrace 1, 2 \ rbrace $,

Декартово произведение A и B записывается в виде - $ A \ times B = \ lbrace (a, 1), (a, 2), (b, 1), (b, 2) \ rbrace $

Декартово произведение B и A записывается в виде - $ B \ times A = \ lbrace (1, a), (1, b), (2, a), (2, b) \ rbrace $

Набор питания

Набор мощности набора S - это набор всех подмножеств S, включая пустой набор. Мощность множества степеней множества S мощности n равна $ 2 ^ n $. Набор мощности обозначается как $ P (S) $.

Пример -

Для множества $ S = \ lbrace a, b, c, d \ rbrace $ вычислим подмножества -

  • Подмножества с 0 элементами - $ \ lbrace \ emptyset \ rbrace $ (пустой набор)

  • Подмножества с 1 элементом - $ \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace c \ rbrace, \ lbrace d \ rbrace $

  • Подмножества с 2 элементами - $ \ lbrace a, b \ rbrace, \ lbrace a, c \ rbrace, \ lbrace a, d \ rbrace, \ lbrace b, c \ rbrace, \ lbrace b, d \ rbrace, \ lbrace c, d \ rbrace $

  • Подмножества с 3 элементами - $ \ lbrace a, b, c \ rbrace, \ lbrace a, b, d \ rbrace, \ lbrace a, c, d \ rbrace, \ lbrace b, c, d \ rbrace $

  • Подмножества с 4 элементами - $ \ lbrace a, b, c, d \ rbrace $

Следовательно, $ P (S) = $

$ \ lbrace \ quad \ lbrace \ emptyset \ rbrace, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace c \ rbrace, \ lbrace d \ rbrace, \ lbrace a, b \ rbrace, \ lbrace a, c \ rbrace, \ lbrace a, d \ rbrace, \ lbrace b, c \ rbrace, \ lbrace b, d \ rbrace, \ lbrace c, d \ rbrace, \ lbrace a, b, c \ rbrace, \ lbrace a, b, d \ rbrace, \ lbrace a, c, d \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace a, b, c, d \ rbrace \ quad \ rbrace $

$ | P (S) | = 2 ^ 4 = 16 $

Примечание. Набор мощности пустого набора также является пустым набором.

$ | P (\ lbrace \ emptyset \ rbrace) | = 2 ^ 0 = 1 $

Разделение набора

Разделение множества, скажем, S , представляет собой набор из n непересекающихся подмножеств, скажем, $ P_1, P_2, \ dots P_n $, который удовлетворяет следующим трем условиям:

  • $ P_i $ не содержит пустого набора.

    $ \ lbrack P_i \ ne \ lbrace \ emptyset \ rbrace \ for \ all \ 0 \ lt i \ le n \ rbrack $

  • Объединение подмножеств должно равняться всему исходному набору.

    $ \ lbrack P_1 \ cup P_2 \ cup \ dots \ cup P_n = S \ rbrack $

  • Пересечение любых двух различных множеств пусто.

    $ \ lbrack P_a \ cap P_b = \ lbrace \ emptyset \ rbrace, \ for \ a \ ne b \ where \ n \ ge a, \: b \ ge 0 \ rbrack $

пример

Пусть $ S = \ lbrace a, b, c, d, e, f, g, h \ rbrace $

Одним из вероятных разбиений является $ \ lbrace a \ rbrace, \ lbrace b, c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $

Другим вероятным разбиением является $ \ lbrace a, b \ rbrace, \ lbrace c, d \ rbrace, \ lbrace e, f, g, h \ rbrace $

Белл номера

Числа в колокольчиках подсчитывают количество способов разбить набор. Они обозначаются через $ B_n $, где n - мощность множества.

Пример -

Пусть $ S = \ lbrace 1, 2, 3 \ rbrace $, $ n = | S | = 3 $

Альтернативные разделы -

1. $ \ emptyset, \ lbrace 1, 2, 3 \ rbrace $

2. $ \ lbrace 1 \ rbrace, \ lbrace 2, 3 \ rbrace $

3. $ \ lbrace 1, 2 \ rbrace, \ lbrace 3 \ rbrace $

4. $ \ lbrace 1, 3 \ rbrace, \ lbrace 2 \ rbrace $

5. $ \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace $

Следовательно, $ B_3 = 5 $