Учебники

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 1. Множество  lbracea,e,i,o,u rbrace записывается как –

A= lbracex: textxгласныйванглийскомалфавите rbrace

Пример 2 – Множество  lbrace1,3,5,7,9 rbrace записывается как –

B= lbracex:1 lex lt10 and (x%2) ne0 rbrace

Если элемент x является членом любого множества S, он обозначается как x inS, а если элемент y не является членом множества S, он обозначается как y notinS.

Примересли S= lbrace1,1.2,1.7,2 rbrace,1 inS, но 1.5 notinS

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

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 обычно называют эквивалентными наборами.

$ | 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 subseteqY), если каждый элемент X является элементом множества Y.

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

Пример 2. Пусть X= lbrace1,2,3 rbrace и Y= lbrace1,2,3 rbrace. Здесь множество Y – это подмножество (не правильное подмножество) множества X, так как все элементы множества Y находятся в множестве X. Следовательно, мы можем записать Y subseteqX.

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

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

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

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

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

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

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

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

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

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

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

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

Равный Набор

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

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

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

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

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

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

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

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

  • n(A cupB)=n(A)+n(B)n(A capB)

  • n(A cupB)=n(AB)+n(BA)+n(A capB)

  • n(A)=n(AB)+n(A capB)

  • n(B)=n(BA)+n(A capB)

n(A cupB)=n(A)+n(B)n(A capB)

n(A cupB)=n(AB)+n(BA)+n(A capB)

n(A)=n(AB)+n(A capB)

n(B)=n(BA)+n(A capB)

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

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

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

  • n(A capB)= emptyset

  • n(A cupB)=n(A)+n(B)

n(A capB)= emptyset

n(A cupB)=n(A)+n(B)

Пример – Пусть, A= lbrace1,2,6 rbrace и B= lbrace7,9,14 rbrace, не существует ни одного общего элемента, поэтому эти наборы являются перекрывающимися.

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

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

Примеры

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

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

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

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

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

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

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

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

Пересечение множеств A и B (обозначается как A capB) – это множество элементов, которые находятся в A и B. Следовательно, A capB= lbracex|x вA AND x inB rbrace.

Пример. Если A= lbrace11,12,13 rbrace и B= lbrace13,14,15 rbrace, то A capB= lbrace13 rbrace.

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

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

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

Пример. Если A= lbrace10,11,12,13 rbrace и B= lbrace13,14,15 rbrace, то (AB)= lbrace10,11,12 rbrace и (BA)= lbrace14,15 rbrace. Здесь мы можем увидеть (AB) ne(BA)

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

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

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

В частности, A=(UA), где U – универсальное множество, которое содержит все объекты.

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

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

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

Декартово произведение n числа множеств A1,A2, dotsAn, обозначаемого как A1 timesA2 dots timesAn, может быть определено как все возможные упорядоченные пары (x1,x2, dotsxn), где x1 inA1,x2 inA2, dotsxn inAn

Пример – Если мы возьмем два набора A= lbracea,b rbrace и B= lbrace1,2 rbrace,

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

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

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

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

Пример –

Для множества S= lbracea,b,c,d rbrace вычислим подмножества –

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

  • Подмножества с 1 элементом –  lbracea rbrace, lbraceb rbrace, lbracec rbrace, lbraced rbrace

  • Подмножества с 2 элементами –  lbracea,b rbrace, lbracea,c rbrace, lbracea,d rbrace, lbraceb,c rbrace, lbraceb,d rbrace, lbracec,d rbrace

  • Подмножества с 3 элементами –  lbracea,b,c rbrace, lbracea,b,d rbrace, lbracea,c,d rbrace, lbraceb,c,d rbrace

  • Подмножества с 4 элементами –  lbracea,b,c,d rbrace

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

Подмножества с 1 элементом –  lbracea rbrace, lbraceb rbrace, lbracec rbrace, lbraced rbrace

Подмножества с 2 элементами –  lbracea,b rbrace, lbracea,c rbrace, lbracea,d rbrace, lbraceb,c rbrace, lbraceb,d rbrace, lbracec,d rbrace

Подмножества с 3 элементами –  lbracea,b,c rbrace, lbracea,b,d rbrace, lbracea,c,d rbrace, lbraceb,c,d rbrace

Подмножества с 4 элементами –  lbracea,b,c,d rbrace

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

 lbrace quad lbrace emptyset rbrace, lbracea rbrace, lbraceb rbrace, lbracec rbrace, lbraced rbrace, lbracea,b rbrace, lbracea,c rbrace, lbracea,d rbrace, lbraceb,c rbrace, lbraceb,d rbrace, lbracec,d rbrace, lbracea,b,c rbrace, lbracea,b,d rbrace, lbracea,c,d rbrace, lbraceb,c,d rbrace, lbracea,b,c,d rbrace quad rbrace

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

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

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

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

Разделение множества, скажем, S , представляет собой набор из n непересекающихся подмножеств, скажем, P1,P2, dotsPn, который удовлетворяет следующим трем условиям:

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

     lbrackPi ne lbrace emptyset rbrace for all 0 lti len rbrack

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

     lbrackP1 cupP2 cup dots cupPn=S rbrack

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

     lbrackPa capPb= lbrace emptyset rbrace, for a neb where n gea,b ge0 rbrack

Pi не содержит пустого набора.

 lbrackPi ne lbrace emptyset rbrace for all 0 lti len rbrack

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

 lbrackP1 cupP2 cup dots cupPn=S rbrack

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

 lbrackPa capPb= lbrace emptyset rbrace, for a neb where n gea,b ge0 rbrack

пример

Пусть S= lbracea,b,c,d,e,f,g,h rbrace

Одним из вероятных разбиений является  lbracea rbrace, lbraceb,c,d rbrace, lbracee,f,g,h rbrace

Другим вероятным разбиением является  lbracea,b rbrace, lbracec,d rbrace, lbracee,f,g,h rbrace

Белл номера

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

Пример

Пусть S= lbrace1,2,3 rbrace, $ n = | S | = 3 $

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

1.  emptyset, lbrace1,2,3 rbrace

2.  lbrace1 rbrace, lbrace2,3 rbrace

3.  lbrace1,2 rbrace, lbrace3 rbrace

4.  lbrace1,3 rbrace, lbrace2 rbrace

5.  lbrace1 rbrace, lbrace2 rbrace, lbrace3 rbrace

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