Дискретная математика — Введение

Математика может быть разделена на две категории:

• Непрерывная математика — она ​​основана на непрерывной числовой линии или действительных числах. Он характеризуется тем, что между любыми двумя числами почти всегда существует бесконечный набор чисел. Например, функция в непрерывной математике может быть построена по гладкой кривой без разрывов.

• Дискретная математика — включает в себя различные ценности; т. е. между любыми двумя точками существует счетное количество точек. Например, если у нас есть конечный набор объектов, функция может быть определена как список упорядоченных пар, имеющих эти объекты, и может быть представлена ​​как полный список этих пар.

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

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

Темы в дискретной математике

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

• Наборы, отношения и функции
• Математическая логика
• Теория групп
• Теория счета
• Вероятность
• Математическая индукция и рекуррентные соотношения
• Теория графов
• деревья
• Булева алгебра

Мы обсудим каждую из этих концепций в последующих главах этого урока.

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

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

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

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

$ | 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$ и так далее.

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

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

Пример — $ 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)$

$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)$

$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 capB= lbracex|x вA AND x inB rbrace$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$

Подмножества с 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$

$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$

Дискретная математика — отношения

Всякий раз, когда обсуждаются наборы, возникает следующая взаимосвязь между элементами наборов. Отношения могут существовать между объектами одного и того же набора или между объектами двух или более наборов.

Определение и свойства

Бинарное отношение R из множества x к y (записанное как $xRy$ или $R (x, y)$) является подмножеством декартового произведения $x \ times y$. Если упорядоченная пара G перевернута, отношение также меняется.

Обычно n-арное отношение R между множествами $A_1, \ dots, \ и \ A_n$ является подмножеством n-арного произведения $A_1 \ times \ dots \ times A_n$. Минимальная мощность отношения R равна нулю, а максимальная — в этом случае $n ^ 2$.

Бинарное отношение R на одном множестве A является подмножеством $A \ times A$.

Для двух различных наборов, A и B, имеющих мощности m и n соответственно, максимальная мощность отношения R от A к B равна mn .

Домен и Диапазон

Если есть два набора A и B, и отношение R имеет пару порядка (x, y), то —

• Области R, Dom (R), является множество $ \ lbrace x \: | \: (x, y) \ in R \: for \: some \: y \: in \: B \ rbrace $

• Диапазон R, Ran (R), — это множество $\ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace$

Области R, Dom (R), является множество $ \ lbrace x \: | \: (x, y) \ in R \: for \: some \: y \: in \: B \ rbrace $

Диапазон R, Ran (R), — это множество $\ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace$

Примеры

Пусть $A = \ lbrace 1, 2, 9 \ rbrace$ и $B = \ lbrace 1, 3, 7 \ rbrace$

• Случай 1 — Если отношение R ‘равно’, то $R = \ lbrace (1, 1), (3, 3) \ rbrace$

  Dom (R) = $\ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace$

• Случай 2 — Если отношение R «меньше», то $R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace$

  Dom (R) = $\ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace$

• Случай 3 — Если отношение R «больше чем», то $R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace$

  Dom (R) = $\ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace$

Случай 1 — Если отношение R ‘равно’, то $R = \ lbrace (1, 1), (3, 3) \ rbrace$

Dom (R) = $\ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace$

Случай 2 — Если отношение R «меньше», то $R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace$

Dom (R) = $\ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace$

Случай 3 — Если отношение R «больше чем», то $R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace$

Dom (R) = $\ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace$

Представление отношений с помощью графика

Отношение может быть представлено с помощью ориентированного графа.

Количество вершин в графе равно количеству элементов в наборе, из которого определено отношение. Для каждой упорядоченной пары (x, y) в отношении R будет направленное ребро от вершины ‘x’ до вершины ‘y’. Если есть упорядоченная пара (x, x), в вершине ‘x’ будет самоконтроль.

Предположим, что на множестве $S = \ lbrace 1, 2, 3 \ rbrace$ существует отношение $R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace$, оно может быть представлен следующим графиком —

Типы отношений

• Пустая связь между множествами X и Y, или на E, является пустым множеством $\ emptyset$

• Полная связь между множествами X и Y — это множество $X \ times Y$

• Отношение идентичности на множестве X — это множество $ \ lbrace (x, x) | x \ in X \ rbrace $

• Обратная связь R ‘отношения R определяется как — $ R’ = \ lbrace (b, a) | (a, b) \ in R \ rbrace $

  Пример — если $R = \ lbrace (1, 2), (2, 3) \ rbrace$, то $R '$ будет $\ lbrace (2, 1), (3, 2) \ rbrace$

• Отношение R на множестве A называется рефлексивным, если $\ forall a \ in A$ связано с a (выполняется aRa)

  Пример . Отношение $R = \ lbrace (a, a), (b, b) \ rbrace$ на множестве $X = \ lbrace a, b \ rbrace$ является рефлексивным.

• Отношение R на множестве A называется иррефлексивным, если $a \ in A$ не связано с a (aRa не имеет места).

  Пример — Соотношение $R = \ lbrace (a, b), (b, a) \ rbrace$ на множестве $X = \ lbrace a, b \ rbrace$ нерефлексивно.

• Отношение R на множестве A называется симметричным, если из $xRy$ следует $yRx$, $\ forall x \ in A$ и $\ forall y \ in A$.

  Пример — Соотношение $R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace$ на множестве $A = \ lbrace 1, 2, 3 \ rbrace$ симметричный.

• Отношение R на множестве A называется антисимметричным, если из $xRy$ и $yRx$ следует $x = y \: \ forall x \ in A$ и $\ forall y \ in A$.

  Пример . Отношение $R = \ lbrace (x, y) \ to N | \: x \ leq y \ rbrace$ антисимметрично, так как $x \ leq y$ и $y \ leq x$ влечет $x = y$.

• Отношение R на множестве A называется транзитивным, если из $xRy$ и $yRz$ следует $xRz, \ forall x, y, z \ in A$.

  Пример — Соотношение $R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace$ на множестве $A = \ lbrace 1, 2, 3 \ rbrace$ является транзитивным.

• Отношение — это отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно.

  Пример — Соотношение $R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2) , (1,3), (3,1) \ rbrace$ на множестве $A = \ lbrace 1, 2, 3 \ rbrace$ является отношением эквивалентности, поскольку оно рефлексивно, симметрично и транзитивно.

Пустая связь между множествами X и Y, или на E, является пустым множеством $\ emptyset$

Полная связь между множествами X и Y — это множество $X \ times Y$

Отношение идентичности на множестве X — это множество $ \ lbrace (x, x) | x \ in X \ rbrace $

Обратная связь R ‘отношения R определяется как — $ R’ = \ lbrace (b, a) | (a, b) \ in R \ rbrace $

Пример — если $R = \ lbrace (1, 2), (2, 3) \ rbrace$, то $R '$ будет $\ lbrace (2, 1), (3, 2) \ rbrace$

Отношение R на множестве A называется рефлексивным, если $\ forall a \ in A$ связано с a (выполняется aRa)

Пример . Отношение $R = \ lbrace (a, a), (b, b) \ rbrace$ на множестве $X = \ lbrace a, b \ rbrace$ является рефлексивным.

Отношение R на множестве A называется иррефлексивным, если $a \ in A$ не связано с a (aRa не имеет места).

Пример — Соотношение $R = \ lbrace (a, b), (b, a) \ rbrace$ на множестве $X = \ lbrace a, b \ rbrace$ нерефлексивно.

Отношение R на множестве A называется симметричным, если из $xRy$ следует $yRx$, $\ forall x \ in A$ и $\ forall y \ in A$.

Пример — Соотношение $R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace$ на множестве $A = \ lbrace 1, 2, 3 \ rbrace$ симметричный.

Отношение R на множестве A называется антисимметричным, если из $xRy$ и $yRx$ следует $x = y \: \ forall x \ in A$ и $\ forall y \ in A$.

Пример . Отношение $R = \ lbrace (x, y) \ to N | \: x \ leq y \ rbrace$ антисимметрично, так как $x \ leq y$ и $y \ leq x$ влечет $x = y$.

Отношение R на множестве A называется транзитивным, если из $xRy$ и $yRz$ следует $xRz, \ forall x, y, z \ in A$.

Пример — Соотношение $R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace$ на множестве $A = \ lbrace 1, 2, 3 \ rbrace$ является транзитивным.

Отношение — это отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пример — Соотношение $R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2) , (1,3), (3,1) \ rbrace$ на множестве $A = \ lbrace 1, 2, 3 \ rbrace$ является отношением эквивалентности, поскольку оно рефлексивно, симметрично и транзитивно.

Дискретная математика — Функции

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

Функция — Определение

Функция или отображение (определенное как $f: X \ rightarrow Y$) представляет собой отношение элементов одного набора X к элементам другого набора Y (X и Y являются непустыми наборами). X называется Доменом, а Y — Кодоменом функции ‘f’.

Функция ‘f’ представляет собой отношение на X и Y такое, что для каждого $x \ in X$ существует единственный $y \ in Y$, такой что $(x, y) \ in R$. «x» называется предварительным изображением, а «y» — изображением функции f.

Функция может быть один к одному или много к одному, но не один ко многим.

Инъективная / индивидуальная функция

Функция $f: A \ rightarrow B$ является инъективной или взаимно-однозначной функцией, если для каждого $b \ in B$ существует не более одного $a \ in A$, такого что $f (s) = t$ ,

Это означает, что функция f инъективна, если из $a_1 \ ne a_2$ следует $f (a1) \ ne f (a2)$.

пример

• $f: N \ rightarrow N, f (x) = 5x$ инъективно.

• $f: N \ rightarrow N, f (x) = x ^ 2$ инъективно.

• $f: R \ rightarrow R, f (x) = x ^ 2$ не является инъективным, так как $(- x) ^ 2 = x ^ 2$

$f: N \ rightarrow N, f (x) = 5x$ инъективно.

$f: N \ rightarrow N, f (x) = x ^ 2$ инъективно.

$f: R \ rightarrow R, f (x) = x ^ 2$ не является инъективным, так как $(- x) ^ 2 = x ^ 2$

Surctive / Onto function

Функция $f: A \ rightarrow B$ сюръективна (на), если образ f равен его диапазону. Эквивалентно, для каждого $b \ in B$ существует такой $a \ in A$, что $f (a) = b$. Это означает, что для любого y в B существует такое x в A, что $y = f (x)$.

пример

• $f: N \ rightarrow N, f (x) = x + 2$ сюръективно.

• $f: R \ rightarrow R, f (x) = x ^ 2$ не сюръективно, поскольку мы не можем найти вещественное число, квадрат которого отрицателен.

$f: N \ rightarrow N, f (x) = x + 2$ сюръективно.

$f: R \ rightarrow R, f (x) = x ^ 2$ не сюръективно, поскольку мы не можем найти вещественное число, квадрат которого отрицателен.

Биектив / Один-на-один Корреспондент

Функция $f: A \ rightarrow B$ является биективной или взаимно-однозначной, если и только если f одновременно инъективна и сюръективна.

проблема

Докажите, что функция $f: R \ rightarrow R$, определенная как $f (x) = 2x - 3$, является биективной функцией.

Пояснение — Мы должны доказать, что эта функция является и инъективной, и сюръективной.

Если $f (x_1) = f (x_2)$, то $2x_1 - 3 = 2x_2 - 3$, и это означает, что $x_1 = x_2$.

Следовательно, f инъективен .

Здесь $2x - 3 = y$

Итак, $x = (y + 5) / 3$, принадлежащая R, и $f (x) = y$.

Следовательно, f сюръективно .

Поскольку f одновременно сюръективен и инъективен , мы можем сказать, что f биективен .

Обратная функция

Обратной к функции «один к одному» $f: A \ rightarrow B$, является функция $g: B \ rightarrow A$, обладающая следующим свойством:

$f (x) = y \ Leftrightarrow g (y) = x$

Функция f называется обратимой , если существует ее обратная функция g.

пример

• Функция $f: Z \ rightarrow Z, f (x) = x + 5$, обратима, поскольку имеет обратную функцию $g: Z \ rightarrow Z, g (x) = x-5$.

• Функция $f: Z \ rightarrow Z, f (x) = x ^ 2$ не является обратимой, поскольку она не взаимно-однозначна, как $(- x) ^ 2 = x ^ 2$.

Функция $f: Z \ rightarrow Z, f (x) = x + 5$, обратима, поскольку имеет обратную функцию $g: Z \ rightarrow Z, g (x) = x-5$.

Функция $f: Z \ rightarrow Z, f (x) = x ^ 2$ не является обратимой, поскольку она не взаимно-однозначна, как $(- x) ^ 2 = x ^ 2$.

Композиция функций

Две функции $f: A \ rightarrow B$ и $g: B \ rightarrow C$ могут быть составлены так, чтобы получить композицию $gof$. Это функция из A в C, определяемая как $(gof) (x) = g (f (x))$

пример

Пусть $f (x) = x + 2$ и $g (x) = 2x + 1$, найдите $(туман) (x)$ и $(gof) (x)$.

Решение

$(туман) (x) = f (g (x)) = f (2x + 1) = 2x + 1 + 2 = 2x + 3$

$(gof) (x) = g (f (x)) = g (x + 2) = 2 (x + 2) + 1 = 2x + 5$

Следовательно, $(туман) (x) \ neq (gof) (x)$

Некоторые факты о композиции

• Если f и g взаимно однозначны, то функция $(gof)$ также взаимно однозначна.

• Если f и g на, то функция $(gof)$ также на.

• Композиция всегда обладает ассоциативным свойством, но не обладает коммутативным свойством.

Если f и g взаимно однозначны, то функция $(gof)$ также взаимно однозначна.

Если f и g на, то функция $(gof)$ также на.

Композиция всегда обладает ассоциативным свойством, но не обладает коммутативным свойством.

Дискретная математика — логика высказываний

Правила математической логики определяют методы обоснования математических утверждений. Греческий философ Аристотель был пионером логических рассуждений. Логические рассуждения обеспечивают теоретическую основу для многих областей математики и, следовательно, информатики. Он имеет множество практических приложений в области компьютерных наук, таких как проектирование вычислительных машин, искусственный интеллект, определение структур данных для языков программирования и т. Д.

Логика высказываний связана с утверждениями, которым могут быть присвоены значения истинности «истина» и «ложь». Цель состоит в том, чтобы проанализировать эти утверждения по отдельности или в совокупности.

Предлогическая логика — определение

Предложение — это совокупность декларативных утверждений, которые имеют либо значение истины «истина», либо значение истины «ложь». Пропозициональное предложение состоит из пропозициональных переменных и связок. Мы обозначаем пропозициональные переменные заглавными буквами (A, B и т. Д.). Связки соединяют пропозициональные переменные.

Некоторые примеры предложений приведены ниже —

• «Человек — смертный», он возвращает истинное значение «ИСТИНА»
• «12 + 9 = 3 — 2», возвращает значение истинности «ЛОЖЬ»

Следующее не является предложением —

• «А меньше 2». Это потому, что если мы не дадим конкретное значение A, мы не сможем сказать, является ли утверждение истинным или ложным.

«А меньше 2». Это потому, что если мы не дадим конкретное значение A, мы не сможем сказать, является ли утверждение истинным или ложным.

Связки

В логике высказываний мы обычно используем пять связок, которые:

• ИЛИ ($\ lor$)

• AND ($\ land$)

• Отрицание / НЕ ($\ lnot$)

• Импликация / если-тогда ($\ rightarrow$)

• Если и только если ($\ Leftrightarrow$).

ИЛИ ($\ lor$)

AND ($\ land$)

Отрицание / НЕ ($\ lnot$)

Импликация / если-тогда ($\ rightarrow$)

Если и только если ($\ Leftrightarrow$).

OR ($\ lor$) — Операция OR двух предложений A и B (записанная как $A \ lor B$) выполняется, если хотя бы любая из пропозициональных переменных A или B истинна.

Таблица истинности выглядит следующим образом —

	В	A ∨ B
Правда	Правда	Правда
Правда	Ложь	Правда
Ложь	Правда	Правда
Ложь	Ложь	Ложь

AND ($\ land$) — Операция AND двух предложений A и B (записанная как $A \ land B$) верна, если обе пропозициональные переменные A и B верны.

Таблица истинности выглядит следующим образом —

	В	A ∧ B
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Ложь

Отрицание ($\ lnot$) — отрицание предложения A (записанного как $\ lnot A$) ложно, когда A истинно, и истинно, когда A ложно.

Таблица истинности выглядит следующим образом —

	¬ A
Правда	Ложь
Ложь	Правда

Импликация / если-тогда ($\ rightarrow$) — импликация $A \ rightarrow B$ — это предложение «если A, то B». Это ложно, если A верно, а B ложно. Остальные случаи верны.

Таблица истинности выглядит следующим образом —

	В	A → B
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Правда
Ложь	Ложь	Правда

Если и только если ($\ Leftrightarrow$) — $A \ Leftrightarrow B$ — это двухусловное логическое связующее, которое истинно, когда p и q одинаковы, т.е. оба являются ложными или оба истинны.

Таблица истинности выглядит следующим образом —

	В	A ⇔ B
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Правда

Тавтологии

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

Пример — Доказать, что $\ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B$ — тавтология

Таблица истинности выглядит следующим образом —

	В	A → B	(A → B) ∧ A	[(A → B) ∧ A] → B
Правда	Правда	Правда	Правда	Правда
Правда	Ложь	Ложь	Ложь	Правда
Ложь	Правда	Правда	Ложь	Правда
Ложь	Ложь	Правда	Ложь	Правда

Как мы видим, каждое значение $\ lbrack (A \ rightarrow B) \ land A \ rbrack \ rightarrow B$ равно «True», это тавтология.

Противоречия

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

Пример — Докажите, что $(A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack$ является противоречием

Таблица истинности выглядит следующим образом —

	В	A ∨ B	¬ A	¬ B	(¬ A) ∧ (¬ B)	(A ∨ B) ∧ [(¬ A) ∧ (¬ B)]
Правда	Правда	Правда	Ложь	Ложь	Ложь	Ложь
Правда	Ложь	Правда	Ложь	Правда	Ложь	Ложь
Ложь	Правда	Правда	Правда	Ложь	Ложь	Ложь
Ложь	Ложь	Ложь	Правда	Правда	Правда	Ложь

Как мы видим, каждое значение $(A \ lor B) \ land \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack$ равно «False», это противоречие.

непредвиденные обстоятельства

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

Пример — Доказать непредвиденную случайность в $(A \ lor B) \ land (\ lnot A)$

Таблица истинности выглядит следующим образом —

	В	A ∨ B	¬ A	(A ∨ B) ∧ (¬ A)
Правда	Правда	Правда	Ложь	Ложь
Правда	Ложь	Правда	Ложь	Ложь
Ложь	Правда	Правда	Правда	Правда
Ложь	Ложь	Ложь	Правда	Ложь

Как мы видим, каждое значение $(A \ lor B) \ land (\ lnot A)$ имеет «True» и «False», это непредвиденное обстоятельство.

Пропозициональные эквивалентности

Два утверждения X и Y логически эквивалентны, если выполняется любое из следующих двух условий:

• Таблицы истинности каждого утверждения имеют одинаковые значения истинности.

• Двухусловное утверждение $X \ Leftrightarrow Y$ является тавтологией.

Таблицы истинности каждого утверждения имеют одинаковые значения истинности.

Двухусловное утверждение $X \ Leftrightarrow Y$ является тавтологией.

Пример — Докажите, что $\ lnot (A \ lor B) и \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack$ эквивалентны

Тестирование по 1- ^му методу (таблица соответствия)

	В	A ∨ B	¬ (A ∨ B)	¬ A	¬ B	[(¬ A) ∧ (¬ B)]
Правда	Правда	Правда	Ложь	Ложь	Ложь	Ложь
Правда	Ложь	Правда	Ложь	Ложь	Правда	Ложь
Ложь	Правда	Правда	Ложь	Правда	Ложь	Ложь
Ложь	Ложь	Ложь	Правда	Правда	Правда	Правда

Здесь мы видим, что значения истинности $\ lnot (A \ lor B) и \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack$ совпадают, поэтому утверждения эквивалентны.

Тестирование по 2- ^му методу (би-условность)

	В	¬ (A ∨ B)	[(¬ A) ∧ (¬ B)]	[¬ (A ∨ B)] ⇔ [(¬ A) ∧ (¬ B)]
Правда	Правда	Ложь	Ложь	Правда
Правда	Ложь	Ложь	Ложь	Правда
Ложь	Правда	Ложь	Ложь	Правда
Ложь	Ложь	Правда	Правда	Правда

Поскольку $\ lbrack \ lnot (A \ lor B) \ rbrack \ Leftrightarrow \ lbrack (\ lnot A) \ land (\ lnot B) \ rbrack$ является тавтологией, утверждения эквивалентны.

Обратное, Обратное и Противоположительное

Импликация / if-then $(\ rightarrow)$ также называется условным оператором. Он состоит из двух частей —

• Гипотеза, р
• Вывод, д

Как упоминалось ранее, он обозначается как $p \ rightarrow q$.

Пример условного высказывания — «Если вы делаете свою домашнюю работу, вы не будете наказаны». Здесь «вы делаете свою домашнюю работу» — это гипотеза, p, а «вы не будете наказаны» — это заключение, q.

Обратное . Обратным условным утверждением является отрицание как гипотезы, так и заключения. Если утверждение «Если р, то q», обратное будет «Если не р, то не q». Таким образом, обратное значение $p \ rightarrow q$ равно $\ lnot p \ rightarrow \ lnot q$.

Пример . Обратное выражение «Если вы делаете домашнее задание, вы не будете наказаны» — «Если вы не будете выполнять домашнее задание, вы будете наказаны».

Обратное — обратное условное утверждение вычисляется путем обмена гипотезы и заключения. Если утверждение «Если р, то д», обратное будет «Если д, то р». Обратным к $p \ rightarrow q$ является $q \ rightarrow p$.

Пример . Обратное выражение «Если вы делаете домашнее задание, вы не будете наказаны» — «Если вы не будете наказаны, вы делаете домашнее задание».

Противоположный — Противоположный условного рассчитывается путем обмена гипотезы и заключения обратного утверждения. Если утверждение «Если p, то q», то противоположным будет «Если не q, то не p». Противоположным для $p \ rightarrow q$ является $\ lnot q \ rightarrow \ lnot p$.

Пример — Противоположный вариант «Если вы делаете домашнее задание, вы не будете наказаны» — «Если вы наказаны, вы не сделали домашнее задание».

Принцип двойственности

Принцип двойственности гласит, что для любого истинного утверждения двойственное утверждение, полученное путем взаимного объединения союзов в пересечения (и наоборот) и взаимного изменения универсального множества в нулевое множество (и наоборот), также верно. Если дуальным каким-либо утверждением является само утверждение, оно называется самодвойственным утверждением.

Пример — двойственное значение $(A \ cap B) \ cup C$ равно $(A \ cup B) \ cap C$

Нормальные Формы

Мы можем преобразовать любое предложение в две нормальные формы —

• Конъюнктивная нормальная форма
• Дизъюнктивная нормальная форма

Конъюнктивная нормальная форма

Составной оператор находится в конъюнктивной нормальной форме, если он получен путем операции И среди переменных (включая отрицание переменных), связанных с ИЛИ. С точки зрения операций над множествами, это составное утверждение, полученное Intersection среди переменных, связанных с Unions.

Примеры

• $(A \ lor B) \ земля (A \ lor C) \ земля (B \ lor C \ lor D)$

• $(P \ cup Q) \ cap (Q \ cup R)$

$(A \ lor B) \ земля (A \ lor C) \ земля (B \ lor C \ lor D)$

$(P \ cup Q) \ cap (Q \ cup R)$

Дизъюнктивная нормальная форма

Составной оператор находится в конъюнктивной нормальной форме, если он получен путем операции ИЛИ среди переменных (включая отрицание переменных), связанных с AND. С точки зрения операций над множествами, это составное утверждение, полученное объединением среди переменных, связанных с пересечениями.

Примеры

• $(A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D)$

• $(P \ cap Q) \ cup (Q \ cap R)$

$(A \ land B) \ lor (A \ land C) \ lor (B \ land C \ land D)$

$(P \ cap Q) \ cup (Q \ cap R)$

Дискретная математика — предикатная логика

Логика предикатов имеет дело с предикатами, которые являются предложениями, содержащими переменные.

Предикатная логика — определение

Предикат — это выражение одной или нескольких переменных, определенных в некоторой конкретной области. Предикат с переменными можно сделать предложением, либо присвоив значение переменной, либо определив ее количественно.

Ниже приведены некоторые примеры предикатов:

• Пусть E (x, y) обозначает «x = y»
• Пусть X (a, b, c) обозначает «a + b + c = 0»
• Пусть M (x, y) обозначает «x женат на y»

Хорошо сформированная формула

Хорошо сформированная формула (wff) — это предикат, содержащий любое из следующего:

• Все пропозициональные константы и пропозициональные переменные являются wffs

• Если x — переменная, а Y — wff, то $\ forall x Y$ и $\ существующие x Y$ также являются wff

• Истинное значение и ложные значения являются wffs

• Каждая атомная формула является WFF

• Все соединения, соединяющие wffs, являются wffs

Все пропозициональные константы и пропозициональные переменные являются wffs

Если x — переменная, а Y — wff, то $\ forall x Y$ и $\ существующие x Y$ также являются wff

Истинное значение и ложные значения являются wffs

Каждая атомная формула является WFF

Все соединения, соединяющие wffs, являются wffs

Кванторы

Переменная предикатов определяется количественно квантификаторами. Существует два типа квантификаторов в логике предикатов — универсальный квантификатор и экзистенциальный квантификатор.

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

Универсальный квантификатор утверждает, что операторы в его области действия верны для каждого значения конкретной переменной. Обозначается символом $\ forall$.

$\ forall x P (x)$ читается как для каждого значения x, P (x) верно.

Пример — «Человек смертен» может быть преобразован в пропозициональную форму $\ forall x P (x)$, где P (x) — предикат, обозначающий x, смертный, а вселенная дискурса — все люди.

Экзистенциальный квантификатор

Экзистенциальный квантификатор утверждает, что операторы в его области истинны для некоторых значений определенной переменной. Обозначается символом $\ exist$.

$\ существует x P (x)$ читается как для некоторых значений x, P (x) верно.

Пример — «Некоторые люди нечестны» можно преобразовать в пропозициональную форму $\ exist x P (x)$, где P (x) — предикат, который обозначает, что x нечестен, а во вселенной дискурса — некоторые люди.

Вложенные квантификаторы

Если мы используем квантификатор, который появляется в области действия другого квантификатора, он называется вложенным квантификатором.

пример

• $\ forall \ a \: \ exist b \: P (x, y)$, где $P (a, b)$ обозначает $a + b = 0$

• $\ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c)$, где $P (a, b)$ обозначает $a + (b + c) = ( a + b) + c$

$\ forall \ a \: \ exist b \: P (x, y)$, где $P (a, b)$ обозначает $a + b = 0$

$\ forall \ a \: \ forall \: b \: \ forall \: c \: P (a, b, c)$, где $P (a, b)$ обозначает $a + (b + c) = ( a + b) + c$

Примечание — $\ forall \: a \: \ Существует b \: P (x, y) \ ne \ существует a \: \ forall b \: P (x, y)$

Дискретная математика — правила вывода

Чтобы вывести новые утверждения из утверждений, истинность которых мы уже знаем, используются правила вывода .

Для чего нужны правила вывода?

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

Аргумент — это последовательность утверждений. Последнее утверждение является заключением, и все его предшествующие утверждения называются предпосылками (или гипотезами). Символ «$\ следовательно$» (читайте поэтому) ставится перед заключением. Допустимым аргументом является тот, в котором вывод следует из истинных значений посылок.

Правила вывода предоставляют шаблоны или рекомендации для построения действительных аргументов из утверждений, которые у нас уже есть.

Таблица правил вывода

Правило вывода	название	Правило вывода	название
$$\ begin {matrix} P \\ \ hline \ следовательно P \ lor Q \ end {matrix}$$	прибавление	$$\ begin {matrix} P \ lor Q \\ \ lnot P \\ \ hline \ следовательно Q \ end {matrix}$$	Дизъюнктивный силлогизм
$$\ begin {matrix} P \\ Q \\ \ hline \ следовательно P \ land Q \ end {matrix}$$	конъюнкция	$$\ begin {matrix} P \ rightarrow Q \\ Q \ rightarrow R \\ \ hline \ следовательно P \ rightarrow R \ end {matrix}$$	Гипотетический силлогизм
$$\ begin {matrix} P \ land Q \\ \ hline \ следовательно P \ end {matrix}$$	упрощение	$$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ P \ lor R \\ \ hline \ следовательно Q \ lor S \ end {matrix}$$	Конструктивная дилемма
$$\ begin {matrix} P \ rightarrow Q \\ P \\ \ hline \ следовательно Q \ end {matrix}$$	Модус Поненс	$$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ \ lnot Q \ lor \ lnot S \\ \ hline \ следовательно \ lnot P \ lor \ lnot R \ end {matrix}$$	Деструктивная Дилемма
$$\ begin {matrix} P \ rightarrow Q \\ \ lnot Q \\ \ hline \ следовательно \ lnot P \ end {matrix}$$	Модус Толленс

$$\ begin {matrix} P \\ \ hline \ следовательно P \ lor Q \ end {matrix}$$

прибавление

$$\ begin {matrix} P \ lor Q \\ \ lnot P \\ \ hline \ следовательно Q \ end {matrix}$$

Дизъюнктивный силлогизм

$$\ begin {matrix} P \\ Q \\ \ hline \ следовательно P \ land Q \ end {matrix}$$

конъюнкция

$$\ begin {matrix} P \ rightarrow Q \\ Q \ rightarrow R \\ \ hline \ следовательно P \ rightarrow R \ end {matrix}$$

Гипотетический силлогизм

$$\ begin {matrix} P \ land Q \\ \ hline \ следовательно P \ end {matrix}$$

упрощение

$$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ P \ lor R \\ \ hline \ следовательно Q \ lor S \ end {matrix}$$

Конструктивная дилемма

$$\ begin {matrix} P \ rightarrow Q \\ P \\ \ hline \ следовательно Q \ end {matrix}$$

Модус Поненс

$$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ \ lnot Q \ lor \ lnot S \\ \ hline \ следовательно \ lnot P \ lor \ lnot R \ end {matrix}$$

Деструктивная Дилемма

$$\ begin {matrix} P \ rightarrow Q \\ \ lnot Q \\ \ hline \ следовательно \ lnot P \ end {matrix}$$

Модус Толленс

прибавление

Если P является предпосылкой, мы можем использовать правило сложения для получения $P \ lor Q$.

$$\ begin {matrix} P \\ \ hline \ следовательно P \ lor Q \ end {matrix}$$

пример

Пусть P будет утверждение «Он очень усердно учится» верно

Поэтому — «Либо он очень усердно учится, либо он очень плохой ученик». Здесь Q — это предложение «он очень плохой ученик».

конъюнкция

Если P и Q — две предпосылки, мы можем использовать правило Conjunction для получения $P \ land Q$.

$$\ begin {matrix} P \\ Q \\ \ hline \ следовательно P \ land Q \ end {matrix}$$

пример

Пусть П — «Он очень усердно учится»

Пусть Q — «Он лучший мальчик в классе»

Поэтому — «Он очень усердно учится, и он лучший мальчик в классе»

упрощение

Если $P \ land Q$ является предпосылкой, мы можем использовать правило упрощения для получения P.

$$\ begin {matrix} P \ land Q \\ \ hline \ следовательно P \ end {matrix}$$

пример

«Он очень усердно учится, и он лучший мальчик в классе», $P \ land Q$

Поэтому — «Он очень усердно учится»

Модус Поненс

Если P и $P \ rightarrow Q$ — две предпосылки, мы можем использовать Modus Ponens для получения Q.

$$\ begin {matrix} P \ rightarrow Q \\ P \\ \ hline \ следовательно Q \ end {matrix}$$

пример

«Если у вас есть пароль, вы можете войти на Facebook», $P \ rightarrow Q$

«У вас есть пароль», П

Поэтому — «Вы можете войти в Facebook»

Модус Толленс

Если $P \ rightarrow Q$ и $\ lnot Q$ — две предпосылки, мы можем использовать Модус Толленс для получения $\ lnot P$.

$$\ begin {matrix} P \ rightarrow Q \\ \ lnot Q \\ \ hline \ следовательно \ lnot P \ end {matrix}$$

пример

«Если у вас есть пароль, вы можете войти на Facebook», $P \ rightarrow Q$

«Вы не можете войти в Facebook», $\ lnot Q$

Поэтому — «У вас нет пароля»

Дизъюнктивный силлогизм

Если $\ lnot P$ и $P \ lor Q$ — две предпосылки, мы можем использовать дизъюнктивный силлогизм для получения Q.

$$\ begin {matrix} \ lnot P \\ P \ lor Q \\ \ hline \ следовательно Q \ end {matrix}$$

пример

«Мороженое не ванильное», $\ lnot P$

«Мороженое со вкусом ванили или шоколада», $P \ lor Q$

Поэтому — «Мороженое со вкусом шоколада»

Гипотетический силлогизм

Если $P \ rightarrow Q$ и $Q \ rightarrow R$ являются двумя предпосылками, мы можем использовать гипотетический силлогизм для получения $P \ rightarrow R$

$$\ begin {matrix} P \ rightarrow Q \\ Q \ rightarrow R \\ \ hline \ следовательно P \ rightarrow R \ end {matrix}$$

пример

«Если пойдет дождь, я не пойду в школу», $P \ rightarrow Q$

«Если я не пойду в школу, мне не нужно будет делать домашнее задание», $Q \ rightarrow R$

Поэтому — «Если идет дождь, мне не нужно делать домашнее задание»

Конструктивная дилемма

Если $(P \ rightarrow Q) \ land (R \ rightarrow S)$ и $P \ lor R$ являются двумя предпосылками, мы можем использовать конструктивную дилемму для получения $Q \ lor S$.

$$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ P \ lor R \\ \ hline \ следовательно Q \ lor S \ end {matrix}$$

пример

«Если пойдет дождь, я уйду», $(P \ rightarrow Q)$

«Если на улице жарко, я пойду принять душ», $(R \ rightarrow S)$

«Или будет дождь, или на улице жарко», $P \ lor R$

Поэтому — «Я уйду или пойду в душ»

Деструктивная Дилемма

Если $(P \ rightarrow Q) \ land (R \ rightarrow S)$ и $\ lnot Q \ lor \ lnot S$ являются двумя предпосылками, мы можем использовать деструктивную дилемму для получения $\ lnot P \ lor \ lnot R$.

$$\ begin {matrix} (P \ rightarrow Q) \ land (R \ rightarrow S) \\ \ lnot Q \ lor \ lnot S \\ \ hline \ следовательно \ lnot P \ lor \ lnot R \ end {matrix}$$

пример

«Если пойдет дождь, я уйду», $(P \ rightarrow Q)$

«Если на улице жарко, я пойду принять душ», $(R \ rightarrow S)$

«Либо я не уйду в отпуск, либо не пойду в душ», $\ lnot Q \ lor \ lnot S$

Поэтому — «Либо не идет дождь, либо на улице не жарко»

Операторы и постулаты

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

В 1854 году Артур Кейли, британский математик, впервые дал современное определение группы —

«Набор символов, каждый из которых различен, и такой, что произведение любых двух из них (независимо от того, в каком порядке) или произведение любого из них на себя, принадлежит множеству, называется группой , Эти символы не являются вообще конвертируемыми [коммутативными], но являются ассоциативными ».

«Набор символов, каждый из которых различен, и такой, что произведение любых двух из них (независимо от того, в каком порядке) или произведение любого из них на себя, принадлежит множеству, называется группой , Эти символы не являются вообще конвертируемыми [коммутативными], но являются ассоциативными ».

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

Любой набор элементов в математической системе может быть определен с помощью набора операторов и ряда постулатов.

Бинарный оператор, определенный для набора элементов, — это правило, которое присваивает каждой паре элементов уникальный элемент из этого набора. Например, если задано множество $A = \ lbrace 1, 2, 3, 4, 5 \ rbrace$, мы можем сказать, что $\ otimes$ — бинарный оператор для операции $c = a \ otimes b$, если он указывает правило для нахождения c для пары $(a, b)$, такой, что $a, b, c \ in A$.

Постулаты математической системы формируют основные предположения, из которых можно вывести правила. Постулаты —

закрытие

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

пример

Пусть $A = \ lbrace 0, 1, 2, 3, 4, 5, \ dots \ rbrace$

Этот набор замкнут относительно бинарного оператора в $(\ ast)$, потому что для операции $c = a \ ast b$ для любого $a, b \ in A$ произведение $c \ in A$.

Множество не замкнуто относительно бинарного оператора деления $(\ div)$, потому что для операции $c = a \ div b$ для любого $a, b \ in A$ произведение c может не входить в множество A. Если $a = 7, b = 2$, то $c = 3.5$. Здесь $a, b \ in A$, но $c \ notin A$.

Ассоциативные законы

Бинарный оператор $\ otimes$ на множестве A является ассоциативным, если он обладает следующим свойством:

$(x \ otimes y) \ otimes z = x \ otimes (y \ otimes z)$, где $x, y, z \ in A$

пример

Пусть $A = \ lbrace 1, 2, 3, 4 \ rbrace$

Оператор plus $(+)$ является ассоциативным, поскольку для любых трех элементов $x, y, z \ in A$ выполняется свойство $(x + y) + z = x + (y + z)$.

Оператор минус $(-)$ не ассоциативен, так как

$$(x - y) - z \ ne x - (y - z)$$

Коммутативные законы

Бинарный оператор $\ otimes$ на множестве A является коммутативным, если он обладает следующим свойством:

$x \ otimes y = y \ otimes x$, где $x, y \ in A$

пример

Пусть $A = \ lbrace 1, 2, 3, 4 \ rbrace$

Оператор plus $(+)$ является коммутативным, поскольку для любых двух элементов $x, y \ in A$ выполняется свойство $x + y = y + x$.

Оператор минус $(-)$ не ассоциативен, так как

$$x - y \ ne y - x$$

Распределительные законы

Два бинарных оператора $\ otimes$ и $\ circledast$ на множестве A являются дистрибутивными по оператору $\ circledast$, когда выполняется следующее свойство —

$x \ otimes (y \ circledast z) = (x \ otimes y) \ circledast (x \ otimes z)$, где $x, y, z \ in A$

пример

Пусть $A = \ lbrace 1, 2, 3, 4 \ rbrace$

Операторы в $(*)$ и плюс $(+)$ являются дистрибутивными по оператору +, потому что для любых трех элементов $x, y, z \ in A$ свойство $x * (y + z) = (x * y) + (x * z)$.

Однако эти операторы не являются дистрибутивными по $*$, так как

$$x + (y * z) \ ne (x + y) * (x + z)$$

Элемент идентичности

Множество A имеет единичный элемент относительно бинарной операции $\ otimes$ на A, если существует элемент $e \ in A$, такой, что выполняется следующее свойство:

$e \ otimes x = x \ otimes e$, где $x \ in A$

пример

Пусть $Z = \ lbrace 0, 1, 2, 3, 4, 5, \ dots \ rbrace$

Элемент 1 является единичным элементом относительно операции $*$, поскольку для любого элемента $x \ in Z$,

$$1 * x = x * 1$$

С другой стороны, для операции нет минус $(-)$.

обратный

Если множество A имеет единичный элемент $e$ относительно бинарного оператора $\ otimes$, говорят, что оно имеет обратное значение всякий раз, когда для каждого элемента $x \ in A$ существует другой элемент $y \ in A$. так, что имеет место следующее свойство:

$$x \ otimes y = e$$

пример

Пусть $A = \ lbrace \ dots -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, \ dots \ rbrace$

Учитывая операцию плюс $(+)$ и $e = 0$, обратный элемент любого элемента x равен $(- x)$, так как $x + (x) = 0$

Закон де Моргана

Законы де Моргана дают пару преобразований между объединением и пересечением двух (или более) множеств с точки зрения их дополнений. Законы —

$$(A \ cup B) '= A' \ cap B '$$

$$(A \ cap B) '= A' \ cup B '$$

пример

Пусть $A = \ lbrace 1, 2, 3, 4 \ rbrace, B = \ lbrace 1, 3, 5, 7 \ rbrace$, и

Универсальный набор $U = \ lbrace 1, 2, 3, \ dots, 9, 10 \ rbrace$

$A '= \ lbrace 5, 6, 7, 8, 9, 10 \ rbrace$

$B '= \ lbrace 2, 4, 6, 8, 9, 10 \ rbrace$

$A \ cup B = \ lbrace 1, 2, 3, 4, 5, 7 \ rbrace$

$A \ cap B = \ lbrace 1, 3 \ rbrace$

$(A \ cup B) '= \ lbrace 6, 8, 9, 10 \ rbrace$

$A '\ cap B' = \ lbrace 6, 8, 9, 10 \ rbrace$

Таким образом, мы видим, что $(A \ cup B) '= A' \ cap B '$

$(A \ cap B) '= \ lbrace 2, 4, 5, 6, 7, 8, 9, 10 \ rbrace$

$A '\ cup B' = \ lbrace 2, 4, 5, 6, 7, 8, 9, 10 \ rbrace$

Таким образом, мы видим, что $(A \ cap B) '= A' \ cup B '$

Дискретная математика — теория групп

Полугрупповые

Конечное или бесконечное множество $'S'$ с бинарной операцией $'\ omicron'$ (Composition) называется полугруппой, если оно одновременно выполняет следующие два условия:

• Замыкание — для каждой пары $(a, b) \ in S \ 🙁 a \ omicron b)$ должно присутствовать в множестве $S$.

• Ассоциативно — для каждого элемента $a, b, c \ in S должно выполняться (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c)$.

Замыкание — для каждой пары $(a, b) \ in S \ 🙁 a \ omicron b)$ должно присутствовать в множестве $S$.

Ассоциативно — для каждого элемента $a, b, c \ in S должно выполняться (a \ omicron b) \ omicron c = a \ omicron (b \ omicron c)$.

пример

Множество натуральных чисел (исключая ноль) с операцией сложения является полугруппой. Например, $S = \ lbrace 1, 2, 3, \ dots \ rbrace$

Здесь свойство замыкания выполняется так же, как и для любой пары $(a, b) \ in S, (a + b)$ присутствует в множестве S. Например, $1 + 2 = 3 \ in S]$

Ассоциативное свойство также справедливо для каждого элемента $a, b, c \ in S, (a + b) + c = a + (b + c)$. Например, $(1 + 2) + 3 = 1 + (2 + 3) = 5$

Monoid

Моноид — это полугруппа с единичным элементом. Элемент идентичности (обозначаемый $e$ или E) множества S — это такой элемент, что $(a \ omicron e) = a$ для каждого элемента $a \ in S$. Элемент идентичности также называется единичным элементом . Таким образом, моноид одновременно обладает тремя свойствами — замыкание, ассоциативность, элемент идентичности .

пример

Множество натуральных чисел (исключая ноль) с операцией умножения является моноидом. $S = \ lbrace 1, 2, 3, \ dots \ rbrace$

Здесь свойство замыкания выполняется так же, как и для любой пары $(a, b) \ in S, (a \ times b)$ присутствует в множестве S. [Например, $1 \ times 2 = 2 \ in S$ и т. Д.]

Ассоциативное свойство также справедливо для каждого элемента $a, b, c \ in S, (a \ times b) \ times c = a \ times (b \ times c)$ [Например, $(1 \ times 2) \ times 3 = 1 \ times (2 \ times 3) = 6$ и т. Д.]

Свойство идентичности также выполняется для каждого элемента $a \ in S, (a \ times e) = a$ [Например, $(2 \ times 1) = 2, (3 \ times 1) = 3$ и т. Д.]. Здесь единичный элемент равен 1.

группа

Группа — это моноид с обратным элементом. Обратный элемент (обозначаемый I) множества S — это такой элемент, что $(a \ omicron I) = (I \ omicron a) = a$ для каждого элемента $a \ in S$. Таким образом, группа обладает четырьмя свойствами одновременно: i) замыкание, ii) ассоциативное, iii) элемент идентичности, iv) обратный элемент. Порядок группы G — это число элементов в G, а порядок элемента в группе — это наименьшее положительное целое число n, такое, что an является единичным элементом этой группы G.

Примеры

Множество $N \ times N$ неособых матриц образуют группу при операции умножения матриц.

Произведение двух $N \ times N$ неособых матриц также является $N \ times N$ неособой матрицей, которая обладает свойством замыкания.

Матричное умножение само по себе является ассоциативным. Следовательно, ассоциативное свойство имеет место.

Множество $N \ times N$ неособых матриц содержит единичную матрицу, содержащую свойство единичного элемента.

Поскольку все матрицы неособы, все они имеют обратные элементы, которые также являются неособыми матрицами. Следовательно, обратное свойство также имеет место.

Абелевская группа

Абелева группа G — это группа, для которой пара элементов $(a, b) \ в G$ всегда имеет коммутативный закон. Таким образом, группа одновременно обладает пятью свойствами: i) замыкание, ii) ассоциативное, iii) элемент идентичности, iv) обратный элемент, v) коммутативность.

пример

Множество натуральных чисел (включая ноль) с операцией сложения является абелевой группой. $G = \ lbrace 0, 1, 2, 3, \ dots \ rbrace$

Здесь свойство замыкания выполняется так же, как и для любой пары $(a, b) \ in S, (a + b)$ присутствует в множестве S. [Например, $1 + 2 = 2 \ in S$ и т. Д.]

Ассоциативное свойство также справедливо для каждого элемента $a, b, c \ in S, (a + b) + c = a + (b + c)$ [Например, $(1 +2) + 3 = 1 + (2 + 3) = 6$ и т. Д.]

Свойство идентичности также выполняется для каждого элемента $a \ in S, (a \ times e) = a$ [Например, $(2 \ times 1) = 2, (3 \ times 1) = 3$ и т. Д.]. Здесь элемент идентичности равен 1.

Коммутативное свойство также выполняется для каждого элемента $a \ in S, (a \ times b) = (b \ times a)$ [Например, $(2 \ times 3) = (3 \ times 2) = 3$ и т. Д. на]

Циклическая группа и подгруппа

Циклическая группа — это группа, которая может быть сгенерирована одним элементом. Каждый элемент циклической группы — это степень некоторого определенного элемента, который называется генератором. Циклическая группа может быть сгенерирована генератором «g», так что любой другой элемент группы может быть записан как степень генератора «g».

пример

Множество комплексных чисел $\ lbrace 1, -1, i, -i \ rbrace$ при операции умножения является циклической группой.

Есть два генератора — $i$ и $–i$ как $i ^ 1 = i, i ^ 2 = -1, i ^ 3 = -i, i ^ 4 = 1$, а также $(- i) ^ 1 = -i, (–i) ^ 2 = -1, (–i) ^ 3 = i, (–i) ^ 4 = 1$, что охватывает все элементы группы. Следовательно, это циклическая группа.

Примечание . Циклическая группа всегда является абелевой группой, но не каждая абелева группа является циклической группой. Прибавляемые рациональные числа не циклические, а абелевы.

Подгруппа H является подмножеством группы G (обозначается как $H ≤ G$), если она одновременно удовлетворяет четырем свойствам — Замыканию, Ассоциативности, Элементу идентичности и Обратному .

Подгруппа H группы G, не включающая всю группу G, называется собственной подгруппой (обозначается через $H <G$). Подгруппа циклической группы является циклической, и абелева подгруппа также абелева.

пример

Пусть группа $G = \ lbrace 1, i, -1, -i \ rbrace$

Тогда некоторые подгруппы являются $H_1 = \ lbrace 1 \ rbrace, H_2 = \ lbrace 1, -1 \ rbrace$,

Это не подгруппа — $H_3 = \ lbrace 1, i \ rbrace$, потому что $(i) ^ {- 1} = -i$ не входит в $H_3$

Частично заказанный набор (POSET)

Частично упорядоченный набор состоит из набора с бинарным отношением, которое является рефлексивным, антисимметричным и транзитивным. «Частично упорядоченный набор» сокращенно обозначен как ПОЗЕТ.

Примеры

• Множество действительных чисел при бинарной операции, меньше или равное $(\ le)$, является набором.

  Пусть множество $S = \ lbrace 1, 2, 3 \ rbrace$ и операция равна $\ le$

  Соотношения будут $\ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace$

  Это отношение R рефлексивно как $\ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ in R$

  Это отношение R антисимметрично, так как

  $\ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ и \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R$

  Это отношение R также транзитивно как $\ lbrace (1,2), (2,3), (1,3) \ rbrace \ in R$.

  Следовательно, это посет .

• Множество вершин ориентированного ациклического графа в операции «достижимость» — это множество.

Множество действительных чисел при бинарной операции, меньше или равное $(\ le)$, является набором.

Пусть множество $S = \ lbrace 1, 2, 3 \ rbrace$ и операция равна $\ le$

Соотношения будут $\ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \ rbrace$

Это отношение R рефлексивно как $\ lbrace (1, 1), (2, 2), (3, 3) \ rbrace \ in R$

Это отношение R антисимметрично, так как

$\ lbrace (1, 2), (1, 3), (2, 3) \ rbrace \ in R \ и \ \ lbrace (1, 2), (1, 3), (2, 3) \ rbrace ∉ R$

Это отношение R также транзитивно как $\ lbrace (1,2), (2,3), (1,3) \ rbrace \ in R$.

Следовательно, это посет .

Множество вершин ориентированного ациклического графа в операции «достижимость» — это множество.

Диаграмма Хассе

Диаграмма Хассе для Poset — это ориентированный граф, вершинами которого являются элементы этого набора, а дуги покрывают пары (x, y) в poset. Если в poset $x <y$, то точка x оказывается ниже, чем точка y на диаграмме Хассе. Если $x <y <z$ в poset, то стрелка не показана между x и z, поскольку она неявная.

пример

Множество подмножеств $\ lbrace 1, 2, 3 \ rbrace = \ lbrace \ emptyset, \ lbrace 1 \ rbrace, \ lbrace 2 \ rbrace, \ lbrace 3 \ rbrace, \ lbrace 1, 2 \ rbrace, \ lbrace 1 , 3 \ rbrace, \ lbrace 2, 3 \ rbrace, \ lbrace 1, 2, 3 \ rbrace \ rbrace$ показаны следующей диаграммой Хассе —

Линейно упорядоченный набор

Линейно упорядоченный набор или Всего упорядоченный набор является частичным набором порядка, в котором каждая пара элементов сопоставима. Элементы $a, b \ in S$ называются сравнимыми, если выполняется либо $a \ le b$, либо $b \ le a$. Закон трихотомии определяет это общее упорядоченное множество. Полностью упорядоченное множество может быть определено как дистрибутивная решетка, имеющая свойство $\ lbrace a \ lor b, a \ land b \ rbrace = \ lbrace a, b \ rbrace$ для всех значений a и b в множестве S.

пример

Множество степеней в $\ lbrace a, b \ rbrace$, упорядоченных по \ subseteq, является полностью упорядоченным множеством, поскольку все элементы степенного множества $P = \ lbrace \ emptyset, \ lbrace a \ rbrace, \ lbrace b \ rbrace, \ lbrace a, b \ rbrace \ rbrace$ сравнимы.

Пример набора неполных заказов

Множество $S = \ lbrace 1, 2, 3, 4, 5, 6 \ rbrace$ при операции x делит y не является полным упорядоченным множеством.

Здесь для всех $ (x, y) \ in S, x | у $ надо держать, но это не правда, что 2 | 3, поскольку 2 не делит 3 или 3 не делит 2. Следовательно, это не полный упорядоченный набор.

решетчатый

Решетка — это множество $(L, \ le)$, для которого каждая пара $\ lbrace a, b \ rbrace \ in L$ имеет наименьшую верхнюю границу (обозначаемую $a \ lor b$) и наибольшую нижнюю границу ( обозначается как $a \ land b$). LUB $(\ lbrace a, b \ rbrace)$ называется объединением a и b. GLB $(\ lbrace a, b \ rbrace)$ называется собранием a и b.

пример

Этот рисунок выше является решеткой, потому что для каждой пары $\ lbrace a, b \ rbrace \ in L$ существует GLB и LUB.

Этот рисунок не является решеткой, поскольку $GLB (a, b)$ и $LUB (e, f)$ не существует.

Некоторые другие решетки обсуждаются ниже —

Ограниченная решетка

Решетка L становится ограниченной решеткой, если она имеет наибольший элемент 1 и наименьший элемент 0.

Дополненная решетка

Решетка L становится дополненной решеткой, если она является ограниченной решеткой и если у каждого элемента в решетке есть дополнение. Элемент x имеет дополнение x ‘, если $\ существует x (x \ land x' = 0 и x \ lor x '= 1)$

Распределительная решетка

Если решетка удовлетворяет следующим двум свойствам распределения, она называется распределительной решеткой.

• $a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c)$

• $a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c)$

$a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c)$

$a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c)$

Модульная решетка

Если решетка удовлетворяет следующему свойству, она называется модульной решеткой.

$a \ land (b \ lor (a \ land d)) = (a \ land b) \ lor (a \ land d)$

Свойства решеток

Идемпотент Свойства

• $a \ lor a = a$

• $a \ land a = a$

$a \ lor a = a$

$a \ land a = a$

Абсорбционные свойства

• $a \ lor (a \ land b) = a$

• $a \ land (a \ lor b) = a$

$a \ lor (a \ land b) = a$

$a \ land (a \ lor b) = a$

Коммутативные свойства

• $a \ lor b = b \ lor a$

• $a \ land b = b \ land a$

$a \ lor b = b \ lor a$

$a \ land b = b \ land a$

Ассоциативные свойства

• $a \ lor (b \ lor c) = (a \ lor b) \ lor c$

• $a \ land (b \ land c) = (a \ land b) \ land c$

$a \ lor (b \ lor c) = (a \ lor b) \ lor c$

$a \ land (b \ land c) = (a \ land b) \ land c$

Двойной Решетки

Двойственность решетки получается путем взаимного обмена операциями ‘$\ lor$‘ и ‘$\ land$‘.

пример

Двойственное из $\ lbrack a \ lor (b \ land c) \ rbrack \ is \ \ lbrack a \ land (b \ lor c) \ rbrack$

Дискретная математика — теория счета

В повседневной жизни очень часто нужно выяснить количество всех возможных результатов для серии событий. Например, каким образом можно выбрать коллегию судей в составе 6 мужчин и 4 женщин из 50 мужчин и 38 женщин? Сколько различных 10-буквенных номеров PAN можно сгенерировать таким образом, чтобы первые пять букв были заглавными, следующие четыре — цифрами, а последняя — снова заглавной. Для решения этих задач используется математическая теория счета. Подсчет в основном охватывает фундаментальное правило подсчета, правило перестановки и правило комбинации.

Правила суммы и продукта

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

• Правило суммы — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно (условие состоит в том, что никакие задачи не могут быть выполнены одновременно), тогда Количество способов выполнить одну из этих задач: $w_1 + w_2 + \ dots + w_m$. Если мы рассмотрим две задачи A и B, которые не пересекаются (то есть $A \ cap B = \ emptyset$), то математически $ | A \ cup B | = | A | + | B | $

• Правило продукта — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно, и каждая задача прибывает после возникновения предыдущей задачи, то есть $w_1 \ times w_2 \ times \ dots \ times w_m$ способы выполнения задач. Математически, если задача B появляется после задачи A, то $ | A \ times B | = | A | \ times | B | $

Правило суммы — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно (условие состоит в том, что никакие задачи не могут быть выполнены одновременно), тогда Количество способов выполнить одну из этих задач: $w_1 + w_2 + \ dots + w_m$. Если мы рассмотрим две задачи A и B, которые не пересекаются (то есть $A \ cap B = \ emptyset$), то математически $ | A \ cup B | = | A | + | B | $

Правило продукта — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно, и каждая задача прибывает после возникновения предыдущей задачи, то есть $w_1 \ times w_2 \ times \ dots \ times w_m$ способы выполнения задач. Математически, если задача B появляется после задачи A, то $ | A \ times B | = | A | \ times | B | $

пример

Вопрос — Мальчик живет в X и хочет пойти в школу в Z. Из своего дома X он должен сначала добраться до Y, а затем от Y до Z. Он может пройти X до Y на 3 автобусных маршрутах или 2 железнодорожных маршрутах. Оттуда он может выбрать либо 4 автобусных маршрута, либо 5 железнодорожных маршрутов, чтобы добраться до Z. Сколько путей можно пройти от X до Z?

Решение — От X до Y он может пойти путями $3 + 2 = 5$ (Rule of Sum). После этого он может перейти от Y к Z путями $4 + 5 = 9$ (Rule of Sum). Следовательно, от X до Z он может идти в $5 \ times 9 = 45$ (правило продукта).

Перестановки

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

Примеры

• Из множества S = {x, y, z}, взяв по два за раз, все перестановки имеют вид —

  $xy, yx, xz, zx, yz, zy$.

• Мы должны сформировать перестановку трехзначных чисел из набора чисел $S = \ lbrace 1, 2, 3 \ rbrace$. Различные трехзначные числа будут сформированы, когда мы организуем цифры. Перестановка будет = 123, 132, 213, 231, 312, 321

Из множества S = {x, y, z}, взяв по два за раз, все перестановки имеют вид —

$xy, yx, xz, zx, yz, zy$.

Мы должны сформировать перестановку трехзначных чисел из набора чисел $S = \ lbrace 1, 2, 3 \ rbrace$. Различные трехзначные числа будут сформированы, когда мы организуем цифры. Перестановка будет = 123, 132, 213, 231, 312, 321

Количество перестановок

Количество перестановок ‘n’ разных вещей, взятых ‘r’ за один раз, обозначается как $n_ {P_ {r}}$

$$n_ {P_ {r}} = \ frac {n!} {(n - r)!}$$

где $ n! = 1.2.3. \ dots (n — 1) .n $

Доказательство — пусть будет «n» разных элементов.

Есть n способов заполнить первое место. После заполнения первого места (n-1) количество элементов осталось. Следовательно, есть (n-1) способов занять второе место. После заполнения первого и второго места, (n-2) количество элементов осталось. Следовательно, есть (n-2) способы занять третье место. Теперь мы можем обобщить количество способов занять r-е место следующим образом: [n — (r – 1)] = n – r + 1

Итак, итого нет. способов пополнения с первого места до r-го места —

$n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1)$

$= [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ dots 3.2.1] / [(nr) (nr-1) \ dots 3.2.1]$

Следовательно,

$ n_ {P_ {r}} = n! / (номер)! $

Некоторые важные формулы перестановки

• Если существует n элементов, из которых $a_1$ похожи в некотором роде, $a_2$ похожи на другие; $a_3$ похожи на третий тип и т. д., а $a_r$ — на $r ^ {th}$, где $(a_1 + a_2 + ... a_r) = n$.

  Тогда число перестановок этих n объектов равно = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.

• Количество перестановок из n различных элементов, принимающих n элементов за раз = $n_ {P_n} = n!$

• Количество перестановок из n разнородных элементов, занимающих r элементов за один раз, когда x конкретных вещей всегда занимают определенные места = $n-x_ {p_ {rx}}$

• Число перестановок n разнородных элементов, когда r указанных вещей всегда собираются вместе, равно — $ r! (П-р + 1)! $

• Число перестановок n разнородных элементов, когда r указанных вещей никогда не объединяются, составляет — $ n! — [r! (П-г + 1)!] $

• Количество циклических перестановок n различных элементов, взятых по x элементам за раз = $^ np_ {x} / x$

• Количество циклических перестановок из n разных вещей = $^ np_ {n} / n$

Если существует n элементов, из которых $a_1$ похожи в некотором роде, $a_2$ похожи на другие; $a_3$ похожи на третий тип и т. д., а $a_r$ — на $r ^ {th}$, где $(a_1 + a_2 + ... a_r) = n$.

Тогда число перестановок этих n объектов равно = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.

Количество перестановок из n различных элементов, принимающих n элементов за раз = $n_ {P_n} = n!$

Количество перестановок из n разнородных элементов, занимающих r элементов за один раз, когда x конкретных вещей всегда занимают определенные места = $n-x_ {p_ {rx}}$

Число перестановок n разнородных элементов, когда r указанных вещей всегда собираются вместе, равно — $ r! (П-р + 1)! $

Число перестановок n разнородных элементов, когда r указанных вещей никогда не объединяются, составляет — $ n! — [r! (П-г + 1)!] $

Количество циклических перестановок n различных элементов, взятых по x элементам за раз = $^ np_ {x} / x$

Количество циклических перестановок из n разных вещей = $^ np_ {n} / n$

Некоторые проблемы

Задача 1 — Сколько способов мы можем переставить из 6 разных карт?

Решение — Поскольку мы берем 6 карт одновременно из колоды из 6 карт, перестановка будет $ ^ 6P_ {6} = 6! = 720 $

Задача 2 — Как можно расположить буквы слова «ЧИТАТЕЛЬ»?

Решение — В слове «ЧИТАТЕЛЬ» есть слово из 6 букв (2 E, 1 A, 1D и 2R.).

Перестановка будет $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $

Задача 3. Каким образом можно расположить буквы слова «ОРАНЖЕВЫЙ» так, чтобы согласные занимали только четные позиции?

Решение — в слове «ОРАНЖЕВЫЙ» 3 гласных и 3 согласных. Количество способов расположения согласных между собой $ = ^ 3P_ {3} = 3! = 6 $ Оставшиеся 3 вакантных места будут заполнены 3 гласными в $ ^ 3P_ {3} = 3! = 6 $ способов. Следовательно, общее число перестановок составляет $6 \ times 6 = 36$

Комбинации

Комбинация — это выбор некоторых заданных элементов, в которых порядок не имеет значения.

Количество всех комбинаций из n вещей, взятых по r, составляет —

$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$

Проблема 1

Найдите число подмножеств множества $\ lbrace1, 2, 3, 4, 5, 6 \ rbrace$, содержащего 3 элемента.

Решение

Мощность набора составляет 6, и мы должны выбрать 3 элемента из набора. Здесь порядок не имеет значения. Следовательно, количество подмножеств будет $^ 6C_ {3} = 20$.

Проблема 2

В комнате 6 мужчин и 5 женщин. Во сколько способов мы можем выбрать 3 мужчин и 2 женщин из комнаты?

Решение

Количество способов выбрать 3 женщин из 6 мужчин составляет $^ 6C_ {3}$, а количество способов выбрать 2 женщин из 5 женщин — $^ 5C_ {2}$

Следовательно, общее количество способов составляет — $^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200$

Проблема 3

Сколько способов вы можете выбрать 3 отдельные группы из 3 студентов из общего количества 9 студентов?

Решение

Давайте нумеруем группы как 1, 2 и 3

Для выбора 3 учеников для 1- ^й группы, количество способов — $^ 9C_ {3}$

Количество способов выбора 3 учеников для 2- ^й группы после выбора 1-й группы — $^ 6C_ {3}$

Количество способов выбора 3 учеников для 3- ^й группы после выбора 1- ^й и 2- ^й группы — $^ 3C_ {3}$

Следовательно, общее количество способов $= ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680$

Личность Паскаля

Идентичность Паскаля, впервые полученная Блезом Паскалем в 17 веке, гласит, что количество способов выбора k элементов из n элементов равно сумме количества способов выбора (k-1) элементов из (n-1) элементов. и количество способов выбора элементов из n-1 элементов.

Математически для любых натуральных чисел k и n: $^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k}$

Доказательство —

$$^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k}$$

$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $

$= (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!})$

$ = (n-1)! \ frac {n} {k! (nk)! } $

$ = \ frac {n! } {k! (nk)! } $

$= n_ {C_ {k}}$

Принцип голубиных отверстий

В 1834 году немецкий математик Питер Густав Лежен Дирихле сформулировал принцип, который он назвал принципом ящика. Теперь это известно как принцип «голубиного отверстия».

Принцип «Голубиная лунка» гласит, что если голубиных отверстий меньше, чем общее число голубей, и каждый голубь помещается в голубиную лунку, то должна быть как минимум одна лунка голубя с более чем одним голубем. Если n голубей помещают в m голубых отверстий, где n> m, то есть отверстие с более чем одним голубем.

Примеры

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

• В классе из 30 человек должно быть не менее двух человек, имена которых начинаются с одинакового алфавита.

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

В классе из 30 человек должно быть не менее двух человек, имена которых начинаются с одинакового алфавита.

Принцип включения-исключения

Принцип включения-исключения вычисляет кардинальное число объединения нескольких непересекающихся множеств. Для двух множеств A и B принцип гласит:

$ | A \ cup B | = | A | + | B | — | A \ cap B | $

Для трех наборов A, B и C принцип гласит:

$ | A \ чашка B \ чашка C | = | A | + | B | + | C | — | A \ cap B | — | A \ cap C | — | B \ cap C | + | A \ cap B \ cap C | $

Обобщенная формула —

$| \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limit_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limit_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 |$

Проблема 1

Сколько целых чисел от 1 до 50 кратно 2 или 3, но не оба?

Решение

От 1 до 100 чисел $50/2 = 25$, кратных 2.

Есть $50/3 = 16$ чисел, которые кратны 3.

Есть $50/6 = 8$ чисел, которые кратны 2 и 3.

Итак, $| A | = 25$, $| B | = 16$ и $| A \ cap B | = 8$.

$ | A \ cup B | = | A | + | B | — | A \ cap B | = 25 + 16 — 8 = 33 $

Проблема 2

В группе из 50 учеников 24 любят холодные напитки, а 36 — горячие напитки, и каждому ученику нравится по крайней мере один из двух напитков. Кто любит кофе и чай?

Решение

Пусть X — группа студентов, которые любят холодные напитки, а Y — группа людей, которые любят горячие напитки.

Итак, $ | X \ чашка Y | = 50 $,$ | X | = 24 $,$ | Y | = 36 $

$ | X \ cap Y | = | X | + | Y | — | X \ чашка Y | = 24 + 36 — 50 = 60 — 50 = 10 $

Следовательно, есть 10 студентов, которые любят чай и кофе.

Дискретная математика — вероятность

С понятиями счета тесно связана вероятность. Мы часто пытаемся угадать результаты азартных игр, таких как карточные игры, игровые автоматы и лотереи; то есть мы пытаемся найти вероятность или вероятность того, что будет получен конкретный результат.

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

Основные понятия

Теория вероятностей была изобретена в 17 веке двумя французскими математиками, Блезом Паскалем и Пьером де Ферма, которые занимались математическими проблемами случайности.

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

Случайный эксперимент — эксперимент, в котором известны все возможные результаты и точный результат не может быть предсказан заранее, называется случайным экспериментом. Бросок честной монеты — пример случайного эксперимента.

Пробное пространство — когда мы проводим эксперимент, то множество S всех возможных результатов называется пробным пространством. Если мы подбрасываем монету, образец пространства $S = \ left \ {H, T \ right \}$

Событие — любое подмножество пробного пространства называется событием. После броска монеты, получение головы на вершине является событием.

Слово «вероятность» означает вероятность наступления определенного события. Лучшее, что мы можем сказать, это то, насколько вероятно, что они произойдут, используя идею вероятности.

$Вероятность \: of \: occurence \: of \: an \: event = \ frac {Итого \: число \: of \: благоприятный \: результат} {Итого \: число \: of \: Результаты}$

Поскольку возникновение какого-либо события варьируется от 0% до 100%, вероятность варьируется от 0 до 1.

Шаги, чтобы найти вероятность

Шаг 1 — Рассчитайте все возможные результаты эксперимента.

Шаг 2 — Рассчитайте количество благоприятных результатов эксперимента.

Шаг 3 — Примените соответствующую формулу вероятности.

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

Если подброшена монета, возможны два исхода — головы $(H)$ или хвосты $(T)$

Итак, общее количество результатов = 2

Следовательно, вероятность получить Хед $(H)$ сверху равна 1/2, а вероятность получить Хвост $(T)$ сверху 1/2

Бросать кости

Когда бросают кости, шесть возможных результатов могут быть на вершине — $1, 2, 3, 4, 5, 6$.

Вероятность любого из чисел равна 1/6

Вероятность получения четных чисел составляет 3/6 = 1/2

Вероятность получения нечетных чисел составляет 3/6 = 1/2

Взятие карт из колоды

Из колоды из 52 карт, если выбрана одна карта, найдите вероятность получения туза, а также вероятность получения алмаза.

Общее количество возможных результатов — 52

Результаты туза — 4

Вероятность быть тузом = 4/52 = 1/13

Вероятность быть бриллиантом = 13/52 = 1/4

Аксиомы вероятности

• Вероятность события всегда варьируется от 0 до 1. $[0 \ leq P (x) \ leq 1]$

• Для невозможного события вероятность равна 0, а для определенного события — 1.

• Если на возникновение одного события не влияет другое событие, они называются взаимоисключающими или непересекающимися.

  Если $A_1, A_2 .... A_n$ являются взаимоисключающими / непересекающимися событиями, то $P (A_i \ cap A_j) = \ emptyset$ для $i \ ne j$ и $P (A_1 \ cup A_2 \ cup .. .. A_n) = P (A_1) + P (A_2) + ..... P (A_n)$

Вероятность события всегда варьируется от 0 до 1. $[0 \ leq P (x) \ leq 1]$

Для невозможного события вероятность равна 0, а для определенного события — 1.

Если на возникновение одного события не влияет другое событие, они называются взаимоисключающими или непересекающимися.

Если $A_1, A_2 .... A_n$ являются взаимоисключающими / непересекающимися событиями, то $P (A_i \ cap A_j) = \ emptyset$ для $i \ ne j$ и $P (A_1 \ cup A_2 \ cup .. .. A_n) = P (A_1) + P (A_2) + ..... P (A_n)$

Свойства вероятности

• Если есть два события $x$ и $\ overline {x}$, которые являются дополнительными, то вероятность дополнительного события равна —

  $$p (\ overline {x}) = 1-p (x)$$

• Для двух непересекающихся событий A и B вероятность объединения двух событий —

  $P (A \ cup B) = P (A) + P (B)$

• Если событие A является подмножеством другого события B (т.е. $A \ subset B$), то вероятность A меньше или равна вероятности B. Следовательно, $A \ subset B$ подразумевает $P (A ) \ leq p (B)$

Если есть два события $x$ и $\ overline {x}$, которые являются дополнительными, то вероятность дополнительного события равна —

$$p (\ overline {x}) = 1-p (x)$$

Для двух непересекающихся событий A и B вероятность объединения двух событий —

$P (A \ cup B) = P (A) + P (B)$

Если событие A является подмножеством другого события B (т.е. $A \ subset B$), то вероятность A меньше или равна вероятности B. Следовательно, $A \ subset B$ подразумевает $P (A ) \ leq p (B)$

Условная возможность

Условная вероятность события B — это вероятность того, что событие произойдет, если событие A уже произошло. Это записывается как $P (B | A)$.

Математически — $P (B | A) = P (A \ cap B) / P (A)$

Если события A и B являются взаимоисключающими, то условная вероятность события B после события A будет вероятностью события B, равной $P (B)$.

Проблема 1

В стране 50% всех подростков имеют велосипед, а 30% всех подростков имеют велосипед и велосипед. Какова вероятность того, что у подростка есть велосипед, если у подростка есть велосипед?

Решение

Предположим, что A — это случай подростков, владеющих только велосипедом, а B — это случай подростков, владеющих только велосипедом.

Итак, $P (A) = 50/100 = 0,5$ и $P (A \ cap B) = 30/100 = 0,3$ из данной задачи.

$P (B | A) = P (A \ cap B) / P (A) = 0,3 / 0,5 = 0,6$

Следовательно, вероятность того, что подросток владеет велосипедом, учитывая, что у подростка есть велосипед, составляет 60%.

Проблема 2

В классе 50% всех учащихся играют в крикет и 25% всех учащихся играют в крикет и волейбол. Какова вероятность того, что ученик играет в волейбол, учитывая, что ученик играет в крикет?

Решение

Предположим, что A — это игра студентов, играющих только в крикет, а B — это игра студентов, играющих только в волейбол.

Итак, $P (A) = 50/100 = 0,5$ и $P (A \ cap B) = 25/100 = 0,25$ из данной задачи.

$P \ lgroup B \ rvert A \ rgroup = P \ lgroup A \ cap B \ rgroup / P \ lgroup A \ rgroup = 0.25 / 0.5 = 0.5$

Следовательно, вероятность того, что ученик играет в волейбол, учитывая, что ученик играет в крикет, составляет 50%.

Проблема 3

Шесть хороших ноутбуков и три неисправных ноутбука перепутаны. Чтобы найти неисправные ноутбуки, все они проверяются один за другим наугад. Какова вероятность найти оба бракованных ноутбука в первых двух комплектациях?

Решение

Пусть A — это случай, когда мы обнаружим неисправный ноутбук в первом тесте, а B — случай, когда мы обнаружим неисправный ноутбук во втором тесте.

Следовательно, $P (A \ cap B) = P (A) P (B | A) = 3/9 \ times 2/8 = 1/12$

Теорема Байеса

Теорема. Если A и B — два взаимоисключающих события, где $P (A)$ — это вероятность A, а $P (B)$ — это вероятность B, $P (A | B)$ — это вероятность A учитывая, что B верно. $P (B | A)$ — вероятность B, учитывая, что A истинно, тогда теорема Байеса утверждает:

$$P (A | B) = \ frac {P (B | A) P (A)} {\ sum_ {i = 1} ^ {n} P (B | Ai) P (Ai)}$$

Применение теоремы Байеса

• В ситуациях, когда все события выборочного пространства являются взаимоисключающими событиями.

• В ситуациях, когда известны либо $P (A_i \ cap B)$ для каждого $A_i$, либо $P (A_i)$ и $P (B | A_i)$ для каждого $A_i$.

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

В ситуациях, когда известны либо $P (A_i \ cap B)$ для каждого $A_i$, либо $P (A_i)$ и $P (B | A_i)$ для каждого $A_i$.

проблема

Рассмотрим три подставки для ручек. Первая подставка для ручек содержит 2 красные ручки и 3 синие ручки; второй имеет 3 красных ручки и 2 синих ручки; и третий имеет 4 красных ручки и 1 синюю ручку. Существует равная вероятность выбора каждого подставки для пера. Если одна ручка нарисована случайным образом, какова вероятность того, что это красная ручка?

Решение

Пусть $A_i$ будет событием, когда выбран i- ^й подставка для пера.

Здесь я = 1,2,3.

Поскольку вероятность выбора подставки для ручки равна, $P (A_i) = 1/3$

Пусть B будет событием, когда нарисовано красное перо.

Вероятность того, что красная ручка выбрана среди пяти ручек первой подставки для ручки,

$P (B | A_1) = 2/5$

Вероятность того, что красная ручка выбрана среди пяти ручек второй подставки,

$P (B | A_2) = 3/5$

Вероятность того, что красная ручка выбрана среди пяти ручек третьей подставки,

$P (B | A_3) = 4/5$

Согласно теореме Байеса,

$P (B) = P (A_1) .P (B | A_1) + P (A_2) .P (B | A_2) + P (A_3) .P (B | A_3)$

$ = 1/3. 2/5 \: + \: 1/3. 3/5 \: + \: 1/3. 4/5 $

$= 3/5$

Математическая индукция

Математическая индукция — это метод доказательства результатов или установления утверждений для натуральных чисел. Эта часть иллюстрирует метод на множестве примеров.

Определение

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

Техника состоит из двух шагов, чтобы доказать утверждение, как указано ниже —

Шаг 1 (Базовый шаг) — Это доказывает, что утверждение верно для начального значения.

Шаг 2 (Индуктивный шаг) — Это доказывает, что если утверждение верно для n- ^й итерации (или числа n ), то оно также верно для (n + 1) ^-й итерации (или числа n + 1 ).

Как это сделать

Шаг 1 — Рассмотрим начальное значение, для которого утверждение верно. Следует показать, что утверждение верно для n = начального значения.

Шаг 2 — Предположим, что утверждение верно для любого значения n = k . Затем докажите, что утверждение верно для n = k + 1 . На самом деле мы разбиваем n = k + 1 на две части, одна часть — n = k (что уже доказано), и пытаемся доказать другую часть.

Проблема 1

$3 ^ n-1$ является кратным 2 для n = 1, 2, …

Решение

Шаг 1 — для $n = 1, 3 ^ 1-1 = 3-1 = 2$, который кратен 2

Шаг 2. Предположим, что $3 ^ n-1$ верно для $n = k$, следовательно, $3 ^ k -1$ верно (это предположение)

Мы должны доказать, что $3 ^ {k + 1} -1$ также кратно 2

$3 ^ {k + 1} - 1 = 3 \ раз 3 ^ k - 1 = (2 \ раза 3 ^ k) + (3 ^ k - 1)$

Первая часть $(2 \ times 3k)$ наверняка будет кратна 2, а вторая часть $(3k -1)$ также верна, как наше предыдущее предположение.

Следовательно, $3 ^ {k + 1} - 1$ кратно 2.

Итак, доказано, что $3 ^ n - 1$ кратно 2.

Проблема 2

$1 + 3 + 5 + ... + (2n-1) = n ^ 2$ для $n = 1, 2, \ dots$

Решение

Шаг 1 — для $n = 1, 1 = 1 ^ 2$, следовательно, шаг 1 выполняется.

Шаг 2. Предположим, что утверждение верно для $n = k$.

Следовательно, $1 + 3 + 5 + \ dots + (2k-1) = k ^ 2$ верно (это предположение)

Мы должны доказать, что $1 + 3 + 5 + ... + (2 (k + 1) -1) = (k + 1) ^ 2$ также имеет место

$1 + 3 + 5 + \ dots + (2 (k + 1) - 1)$

$= 1 + 3 + 5 + \ dots + (2k + 2 - 1)$

$= 1 + 3 + 5 + \ dots + (2k + 1)$

$= 1 + 3 + 5 + \ dots + (2k - 1) + (2k + 1)$

$= k ^ 2 + (2k + 1)$

$= (k + 1) ^ 2$

Итак, выполняется $1 + 3 + 5 + \ dots + (2 (k + 1) - 1) = (k + 1) ^ 2$, что удовлетворяет шагу 2.

Следовательно, $1 + 3 + 5 + \ dots + (2n - 1) = n ^ 2$ доказано.

Проблема 3

Докажите, что $(ab) ^ n = a ^ nb ^ n$ верно для каждого натурального числа $n$

Решение

Шаг 1 — Для $n = 1 (ab) ^ 1 = a ^ 1b ^ 1 = ab$, следовательно, шаг 1 выполняется.

Шаг 2 — Предположим, что утверждение верно для $n = k$, следовательно, $(ab) ^ k = a ^ kb ^ k$ верно (это предположение).

Мы должны доказать, что $(ab) ^ {k + 1} = a ^ {k + 1} b ^ {k + 1}$ также имеет место

Учитывая, $(ab) ^ k = a ^ kb ^ k$

Или, $(ab) ^ k (ab) = (a ^ kb ^ k) (ab)$ [Умножение обеих сторон на ‘ab’]

Или $(ab) ^ {k + 1} = (aa ^ k) (bb ^ k)$

Или $(ab) ^ {k + 1} = (a ^ {k + 1} b ^ {k + 1})$

Следовательно, шаг 2 доказан.

Таким образом, $(ab) ^ n = a ^ nb ^ n$ верно для каждого натурального числа n.

Сильная Индукция

Сильная индукция является еще одной формой математической индукции. С помощью этой техники индукции мы можем доказать, что пропозициональная функция $P (n)$ справедлива для всех натуральных чисел $n$, используя следующие шаги:

• Шаг 1 (Базовый шаг) — Доказано, что начальное предложение $P (1)$ верно.

• Шаг 2 (Индуктивный шаг) — Доказывается, что условное утверждение $[P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1)$ верно для натуральных чисел $k$.

Шаг 1 (Базовый шаг) — Доказано, что начальное предложение $P (1)$ верно.

Шаг 2 (Индуктивный шаг) — Доказывается, что условное утверждение $[P (1) \ land P (2) \ land P (3) \ land \ dots \ land P (k)] → P (k + 1)$ верно для натуральных чисел $k$.

Дискретная математика — рекуррентное соотношение

В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.

Определение

Рекуррентное отношение — это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая $F_n$ как некоторую комбинацию $F_i$ с $i <n$).

Пример — ряд Фибоначчи — $F_n = F_ {n-1} + F_ {n-2}$, Ханойская башня — $F_n = 2F_ {n-1} + 1$

Линейные рекуррентные отношения

Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате $x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ {nk}$ ($A_n$ — константа, а $A_k \ neq 0$) на последовательности чисел как полинома первой степени.

Вот некоторые примеры линейных рекуррентных уравнений —

Рецидив отношений	Начальные значения	Решения
F n = F n-1 + F n-2	a 1 = a 2 = 1	Число Фибоначчи
F n = F n-1 + F n-2	а 1 = 1, а 2 = 3	Номер Лукаса
F n = F n-2 + F n-3	a 1 = a 2 = a 3 = 1	Падовская последовательность
F n = 2F n-1 + F n-2	a 1 = 0, a 2 = 1	Число Пелла

Как решить линейное рекуррентное соотношение

Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — $F_n = AF_ {n-1} + BF_ {n-2}$, где A и B — действительные числа.

Характеристическое уравнение для вышеуказанного рекуррентного соотношения —

$$x ^ 2 - Axe - B = 0$$

Три случая могут возникнуть при поиске корней —

Случай 1 — Если это уравнение учитывается как $(x- x_1) (x- x_1) = 0$ и оно дает два различных реальных корня $x_1$ и $x_2$, то $F_n = ax_1 ^ n + bx_2 ^ n$ является решение. [Здесь a и b являются константами]

Случай 2 — Если это уравнение вычисляется как $(x- x_1) ^ 2 = 0$, и оно порождает один действительный корень $x_1$, то решением является $F_n = a x_1 ^ n + bn x_1 ^ n$.

Случай 3 — Если уравнение дает два различных комплексных корня, $x_1$ и $x_2$ в полярной форме $x_1 = r \ angle \ theta$ и $x_2 = r \ angle (- \ theta)$, то $F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta))$ является решением.

Проблема 1

Решите рекуррентное соотношение $F_n = 5F_ {n-1} - 6F_ {n-2}$, где $F_0 = 1$ и $F_1 = 4$.

Решение

Характеристическое уравнение рекуррентного соотношения —

$$x ^ 2 - 5x + 6 = 0,$$

Итак, $(x - 3) (x - 2) = 0$

Следовательно, корни —

$x_1 = 3$ и $x_2 = 2$

Корни реальны и различны. Итак, это в форме дела 1

Следовательно, решение —

$$F_n = ax_1 ^ n + bx_2 ^ n$$

Здесь $F_n = a3 ^ n + b2 ^ n \ (As \ x_1 = 3 \ and \ x_2 = 2)$

Следовательно,

$1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b$

$4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b$

Решая эти два уравнения, мы получаем $a = 2$ и $b = -1$

Следовательно, окончательное решение —

$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n — 2 ^ n $$

Проблема 2

Решите рекуррентное соотношение — $F_n = 10F_ {n-1} - 25F_ {n-2}$, где $F_0 = 3$ и $F_1 = 17$.

Решение

Характеристическое уравнение рекуррентного соотношения —

$$x ^ 2 - 10x -25 = 0$$

Итак, $(x - 5) ^ 2 = 0$

Следовательно, существует один действительный корень $x_1 = 5$

Поскольку существует единый действительный корень, он имеет вид случая 2

Следовательно, решение —

$F_n = ax_1 ^ n + bnx_1 ^ n$

$3 = F_0 = a.5 ^ 0 + b.0.5 ^ 0 = a$

$17 = F_1 = a.5 ^ 1 + b.1.5 ^ 1 = 5a + 5b$

Решая эти два уравнения, мы получаем $a = 3$ и $b = 2/5$

Следовательно, окончательное решение — $F_n = 3.5 ^ n + (2/5) .n.2 ^ n$

Проблема 3

Решите рекуррентное соотношение $F_n = 2F_ {n-1} - 2F_ {n-2}$, где $F_0 = 1$ и $F_1 = 3$

Решение

Характеристическое уравнение рекуррентного соотношения —

$$x ^ 2 -2x -2 = 0$$

Следовательно, корни —

$x_1 = 1 + i$ и $x_2 = 1 - i$

В полярной форме,

$x_1 = r \ angle \ theta$ и $x_2 = r \ angle (- \ theta),$ где $r = \ sqrt 2$ и $\ theta = \ frac {\ pi} {4}$

Корни воображаемые. Итак, это в форме случая 3.

Следовательно, решение —

$F_n = (\ sqrt 2) ^ n (cos (n. \ Sqcap / 4) + b sin (n. \ Sqcap / 4))$

$1 = F_0 = (\ sqrt 2) ^ 0 (a cos (0. \ Sqcap / 4) + b sin (0. \ Sqcap / 4)) = a$

$3 = F_1 = (\ sqrt 2) ^ 1 (a cos (1. \ Sqcap / 4) + b sin (1. \ Sqcap / 4)) = \ sqrt 2 (a / \ sqrt 2 + b / \ sqrt 2 )$

Решая эти два уравнения, мы получаем $a = 1$ и $b = 2$

Следовательно, окончательное решение —

$F_n = (\ sqrt 2) ^ n (cos (n. \ Pi / 4) + 2 sin (n. \ Pi / 4))$

Неоднородное рекуррентное соотношение и частные решения

Рекуррентное отношение называется неоднородным, если оно имеет вид

$F_n = AF_ {n-1} + BF_ {n-2} + f (n)$, где $f (n) \ ne 0$

Связанное с ним однородное рекуррентное соотношение равно $F_n = AF_ {n – 1} + BF_ {n-2}$

Решение $(a_n)$ неоднородного рекуррентного отношения состоит из двух частей.

Первая часть — это решение $(a_h)$ связанного однородного рекуррентного соотношения, а вторая часть — это частное решение $(a_t)$.

$$a_n = A_H + a_t$$

Решение первой части выполняется с использованием процедур, описанных в предыдущем разделе.

Чтобы найти конкретное решение, мы находим подходящее пробное решение.

Пусть $f (n) = cx ^ n$; пусть $x ^ 2 = Ax + B$ — характеристическое уравнение связанного однородного рекуррентного соотношения, а $x_1$ и $x_2$ — его корни.

• Если $x \ ne x_1$ и $x \ ne x_2$, то $a_t = Ax ^ n$

• Если $x = x_1$, $x \ ne x_2$, то $a_t = Anx ^ n$

• Если $x = x_1 = x_2$, то $a_t = An ^ 2x ^ n$

Если $x \ ne x_1$ и $x \ ne x_2$, то $a_t = Ax ^ n$

Если $x = x_1$, $x \ ne x_2$, то $a_t = Anx ^ n$

Если $x = x_1 = x_2$, то $a_t = An ^ 2x ^ n$

пример

Пусть неоднородное рекуррентное соотношение имеет вид $F_n = AF_ {n – 1} + BF_ {n-2} + f (n)$ с характеристическими корнями $x_1 = 2$ и $x_2 = 5$. Пробные решения для различных возможных значений $f (n)$ следующие:

е (п)	Пробные решения
4
5,2 н	An2 n
8,5 n	An5 n
4 н	A4 н
2n 2 + 3n + 1	Ан 2 + Бн + С

проблема

Решите рекуррентное соотношение $F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n$, где $F_0 = 4$ и $F_1 = 3$

Решение

Это линейное неоднородное отношение, где ассоциированное однородное уравнение имеет вид $F_n = 3F_ {n-1} + 10F_ {n-2}$ и $f (n) = 7,5 ^ n$.

Характеристическое уравнение его связанного однородного отношения —

$$x ^ 2 - 3x -10 = 0$$

Или $(x - 5) (x + 2) = 0$

Или $x_1 = 5$ и $x_2 = -2$

Следовательно, $a_h = a.5 ^ n + b. (- 2) ^ n$, где a и b — постоянные.

Поскольку $f (n) = 7,5 ^ n$, то есть в форме $cx ^ n$, разумным пробным решением at будет $Anx ^ n$.

$a_t = Anx ^ n = An5 ^ n$

После помещения решения в рекуррентное соотношение мы получаем —

$An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7,5 ^ n$

Разделив обе стороны на $5 ^ {n-2}$, получим

$An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7,5 ^ 2$

Или $25An = 15An - 15A + 10An - 20A + 175$

Или 35 $​​= 175$

Или $A = 5$

Итак, $F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1}$

Решение рекуррентного отношения можно записать в виде —

$F_n = a_h + a_t$

$= А.5 ^ п + Ь. (- 2) ^ п + n5 ^ {п + 1}$

Положив значения $F_0 = 4$ и $F_1 = 3$, в приведенном выше уравнении получим $a = -2$ и $b = 6$

Следовательно, решение —

$F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2,5 ^ n$

Генерация функций

Генерирующие функции представляют последовательности, где каждый член последовательности выражается в виде коэффициента переменной x в формальном степенном ряду.

Математически, для бесконечной последовательности, скажем, $a_0, a_1, a_2, \ dots, a_k, \ dots,$ производящая функция будет —

$$G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k$$

Некоторые области применения

Генерирующие функции могут быть использованы для следующих целей —

• Для решения различных задач подсчета. Например, количество способов внести изменения для рупий. 100 примечание с примечаниями достоинств Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 и Rs.50

• Для решения рекуррентных отношений

• Для доказательства некоторых комбинаторных тождеств

• Для нахождения асимптотических формул для членов последовательностей

Для решения различных задач подсчета. Например, количество способов внести изменения для рупий. 100 примечание с примечаниями достоинств Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 и Rs.50

Для решения рекуррентных отношений

Для доказательства некоторых комбинаторных тождеств

Для нахождения асимптотических формул для членов последовательностей

Проблема 1

Каковы производящие функции для последовательностей $\ lbrace {a_k} \ rbrace$ с $a_k = 2$ и $a_k = 3k$?

Решение

Когда $a_k = 2$, производящая функция, $G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ точки$

Когда $a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ dots \ точки$

Проблема 2

Что является производящей функцией бесконечного ряда; $1, 1, 1, 1, \ dots$?

Решение

Здесь $a_k = 1$ для $0 \ le k \ le \ infty$

Следовательно, $G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)}$

Некоторые полезные функции генерации

• Для $a_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dots \ dots \ dots = 1 / (1 - топор)$

• Для $a_ {k} = (k + 1) G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} \ dots \ dots \ dots = \ frac {1} {(1 - x) ^ {2}}$

• Для $a_ {k} = c_ {k} ^ {n}, G (x) = \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \ dots \ dots \ dots + x ^ {2} = (1 + x) ^ {n}$

• Для $a_ {k} = \ frac {1} {k!}, G (x) = \ sum_ {k = 0} ^ {\ infty} \ frac {x ^ {k}} {k!} = 1 + x + \ frac {x ^ {2}} {2!} + \ frac {x ^ {3}} {3!} \ dots \ dots \ dots = e ^ {x}$

Для $a_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ dots \ dots \ dots = 1 / (1 - топор)$

Для $a_ {k} = (k + 1) G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} \ dots \ dots \ dots = \ frac {1} {(1 - x) ^ {2}}$

Для $a_ {k} = c_ {k} ^ {n}, G (x) = \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \ dots \ dots \ dots + x ^ {2} = (1 + x) ^ {n}$

Для $a_ {k} = \ frac {1} {k!}, G (x) = \ sum_ {k = 0} ^ {\ infty} \ frac {x ^ {k}} {k!} = 1 + x + \ frac {x ^ {2}} {2!} + \ frac {x ^ {3}} {3!} \ dots \ dots \ dots = e ^ {x}$

Граф и графические модели

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

Мы рассмотрим две дискретные структуры: графы и деревья. Граф — это набор точек, называемых узлами или вершинами, которые связаны набором линий, называемых ребрами. Изучение графов, или теория графов, является важной частью ряда дисциплин в области математики, инженерии и информатики.

Что такое график?

Определение — граф (обозначается как $G = (V, E)$) состоит из непустого набора вершин или узлов V и множества ребер E.

Пример. Рассмотрим граф: $G = (V, E)$, где $V = \ lbrace a, b, c, d \ rbrace$ и $E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a, c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace$

Степень вершины . Степень вершины V графа G (обозначается через deg (V)) — это число ребер, инцидентных с вершиной V.

темя	степень	Даже странно
	2	четное
б	2	четное
с	3	странный
d	1	странный

Четная и нечетная вершина — если степень вершины четная, вершина называется четной вершиной, а если степень вершины нечетная, вершина называется нечетной вершиной.

Степень графа . Степень графа является наибольшей степенью вершины этого графа. Для приведенного выше графа степень графа равна 3.

Лемма о рукопожатии. В графе сумма всех степеней всех вершин равна удвоенному числу ребер.

Типы графиков

Существуют различные типы графиков, которые мы изучим в следующем разделе.

Нулевой график

Нулевой граф не имеет ребер. Нулевой граф вершин $n$ обозначается через $N_n$

Простой график

Граф называется простым графом / строгим графом, если граф ненаправленный и не содержит петель или кратных ребер.

Multi-Graph

Если в графе допускается несколько ребер между одним и тем же набором вершин, это называется Multigraph. Другими словами, это граф, имеющий по крайней мере один цикл или несколько ребер.

Направленный и неориентированный граф

Граф $G = (V, E)$ называется ориентированным графом, если множество ребер составлено из упорядоченной пары вершин, а граф называется ненаправленным, если множество ребер составлено из неупорядоченной пары вершин.

Подключенный и отключенный график

Граф связен, если любые две вершины графа связаны путем; в то время как граф отключен, если хотя бы две вершины графа не соединены путем. Если граф G несвязен, то каждый максимальный связный подграф в $G$ называется связной компонентой графа $G$.

Обычный график

Граф является регулярным, если все вершины графа имеют одинаковую степень. В регулярном графе G степени $r$ степень каждой вершины $G$ равна r.

Полный график

Граф называется полным графом, если каждые две пары вершин соединены ровно одним ребром. Полный граф с n вершинами обозначается через $K_n$

Цикл графика

Если граф состоит из одного цикла, он называется графом циклов. Граф цикла с n вершинами обозначается через $C_n$

Двудольный график

Если множество вершин графа G можно разбить на два непересекающихся множества, $V_1$ и $V_2$, таким образом, чтобы каждое ребро графа соединяло вершину в $V_1$ с вершиной в $V_2$, и в G нет ребер, соединяющих две вершины в $V_1$ или две вершины в $V_2$, тогда граф $G$ называется двудольным графом.

Полный двудольный график

Полный двудольный граф — это двудольный граф, в котором каждая вершина в первом наборе соединяется с каждой отдельной вершиной во втором наборе. Полный двудольный граф обозначается через $K_ {x, y}$, где граф $G$ содержит $x$ вершин в первом наборе и $y$ вершин во втором наборе.

Представление графиков

Есть в основном два способа представления графика —

• Матрица смежности
• Список смежности

Матрица смежности

Матрица смежности $A [V] [V]$ — это двумерный массив размером $V \ times V$, где $V$ — количество вершин в неориентированном графе. Если между $V_x$ и $V_y$ имеется ребро, то значение $A [V_x] [V_y] = 1$ и $A [V_y] [V_x] = 1$, в противном случае значение будет равно нулю. А для ориентированного графа, если существует ребро от $V_x$ до $V_y$, тогда значение $A [V_x] [V_y] = 1$, в противном случае значение будет равно нулю.

Матрица смежности неориентированного графа

Рассмотрим следующий неориентированный граф и построим матрицу смежности:

Матрица смежности вышеприведенного неориентированного графа будет —

		б	с	d
	0	1	1	0
б	1	0	1	0
с	1	1	0	1
d	0	0	1	0

б

с

d

0

1

1

0

б

1

0

1

0

с

1

1

0

1

d

0

0

1

0

Матрица смежности ориентированного графа

Рассмотрим следующий ориентированный граф и построим его матрицу смежности.

Матрица смежности вышеуказанного ориентированного графа будет —

		б	с	d
	0	1	1	0
б	0	0	1	0
с	0	0	0	1
d	0	0	0	0

б

с

d

0

1

1

0

б

0

0

1

0

с

0

0

0

1

d

0

0

0

0

Список смежности

В списке смежности массив $(A [V])$ связанных списков используется для представления графа G с $V$ числом вершин. Запись $A [V_x]$ представляет связанный список вершин, смежных с $Vx-й$ вершиной. Список смежности неориентированного графа показан на рисунке ниже —

Планарный и непланарный граф

Планарный граф . Граф $G$ называется плоским графом, если его можно нарисовать на плоскости без пересечений ребер. Если мы рисуем граф на плоскости без пересечения ребер, это называется встраиванием графа в плоскость.

Неплоский граф — граф неплоский, если его нельзя нарисовать на плоскости без пересечения ребер графа.

изоморфизм

Если два графа G и H содержат одинаковое количество вершин, связанных одинаково, они называются изоморфными графами (обозначаемыми $G \ cong H$).

Легче проверить неизоморфизм, чем изоморфизм. Если выполняется любое из этих следующих условий, то два графика неизоморфны:

• Количество подключенных компонентов различно
• Набор вершин различен
• Края кардинальности разные
• Степени последовательности разные

пример

Следующие графы изоморфны —

Гомоморфизм

Гомоморфизм из графа $G$ в граф $H$ является отображением (не может быть биективным отображением) $h: G \ rightarrow H$ таким, что — $(x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ in E (H)$. Он отображает смежные вершины графа $G$ на смежные вершины графа $H$.

Свойства гомоморфизмов

• Гомоморфизм — это изоморфизм, если он является биективным отображением.

• Гомоморфизм всегда сохраняет ребра и связность графа.

• Композиции гомоморфизмов также являются гомоморфизмами.

• Выяснить, существует ли какой-либо гомоморфный граф другого графа, является NP-полной задачей.

Гомоморфизм — это изоморфизм, если он является биективным отображением.

Гомоморфизм всегда сохраняет ребра и связность графа.

Композиции гомоморфизмов также являются гомоморфизмами.

Выяснить, существует ли какой-либо гомоморфный граф другого графа, является NP-полной задачей.

Эйлеровы графы

Связный граф $G$ называется графом Эйлера, если существует замкнутый след, включающий каждое ребро графа $G$. Путь Эйлера — это путь, который использует каждое ребро графа ровно один раз. Путь Эйлера начинается и заканчивается в разных вершинах.

Схема Эйлера — это схема, которая использует каждое ребро графа ровно один раз. Схема Эйлера всегда начинается и заканчивается в одной и той же вершине. Связный граф $G$ является графом Эйлера тогда и только тогда, когда все вершины $G$ имеют четную степень, а связный граф $G$ эйлерова, если и только если его множество ребер можно разложить на циклы.

Вышеупомянутый граф является графом Эйлера как $«a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ покрывает все ребра графа.

Гамильтоновы графы

Связный граф $G$ называется гамильтоновым графом, если существует цикл, включающий каждую вершину в $G$, и этот цикл называется гамильтоновым циклом. Гамильтоново блуждание в графе $G$ — это блуждание, которое проходит через каждую вершину ровно один раз.

Если $G$ — простой граф с n вершинами, где $n \ geq 3$. Если $deg (v) \ geq \ frac {n} {2}$ для каждой вершины $v$, то граф $G$ равен Гамильтонов граф. Это называется теорема Дирака .

Если $G$ — простой граф с $n$ вершинами, где $n \ geq 2$, если $deg (x) + deg (y) \ geq n$ для каждой пары несмежных вершин x и y, то граф $G$ является гамильтоновым графом. Это называется теорема Оре .

Дискретная математика — больше на графиках

Раскраска графика

Раскраска графа — это процедура присвоения цветов каждой вершине графа G таким образом, что смежные вершины не получают одинаковый цвет. Цель состоит в том, чтобы минимизировать количество цветов при окрашивании графика. Наименьшее количество цветов, необходимое для окраски графа G, называется его хроматическим числом этого графа. Проблема раскраски графов — это проблема NP Complete.

Способ раскрасить график

Шаги, необходимые для раскраски графа G с n числом вершин, следующие:

Шаг 1 — Расположите вершины графа в некотором порядке.

Шаг 2 — Выберите первую вершину и раскрасьте ее первым цветом.

Шаг 3 — Выберите следующую вершину и раскрасьте ее цветом с наименьшим номером, который не был окрашен ни в одной из соседних вершин. Если все смежные вершины закрашены этим цветом, присвойте ему новый цвет. Повторяйте этот шаг, пока все вершины не будут окрашены.

пример

На рисунке выше первая вершина $a$ окрашена в красный цвет. Поскольку смежные вершины вершины a снова являются смежными, вершина $b$ и вершина $d$ окрашиваются в разные цвета, зеленый и синий соответственно. Тогда вершина $c$ окрашивается в красный цвет, так как ни одна из смежных вершин $c$ не окрашивается в красный цвет. Следовательно, мы могли бы раскрасить график на 3 цвета. Следовательно, хроматическое число графа равно 3.

Приложения для раскраски графиков

Некоторые приложения раскраски графа включают —

• Распределение регистра
• Раскраска карты
• Проверка двудольных графиков
• Присвоение подвижной радиочастоты
• Составление расписания и т. Д.

Обход графика

Обход графа — это проблема посещения всех вершин графа в некотором систематическом порядке. Есть в основном два пути для обхода графа.

• Ширина Первый Поиск
• Глубина Первый Поиск

Ширина Первый Поиск

Поиск в ширину (BFS) начинается с начальной вершины нулевого уровня $X$ графа $G$. Затем мы посещаем все вершины, которые являются соседями $X$. После посещения мы помечаем вершины как «посещенные» и помещаем их на уровень 1. Затем мы начинаем с вершин уровня 1 и применяем один и тот же метод к каждой вершине уровня 1 и так далее. Обход BFS заканчивается, когда каждая вершина графа посещена.

Алгоритм BFS

Концепция состоит в том, чтобы посетить все соседние вершины до посещения других соседних вершин соседних вершин.

• Инициализируйте статус всех узлов как «Готов».

• Поместите исходную вершину в очередь и измените ее статус на «Ожидание».

• Повторите следующие два шага, пока очередь не станет пустой —

  • Удалите первую вершину из очереди и отметьте ее как «Посещенные».

  • Добавьте в конец очереди всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

Инициализируйте статус всех узлов как «Готов».

Поместите исходную вершину в очередь и измените ее статус на «Ожидание».

Повторите следующие два шага, пока очередь не станет пустой —

Удалите первую вершину из очереди и отметьте ее как «Посещенные».

Добавьте в конец очереди всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

проблема

Давайте возьмем граф (исходная вершина — «a») и применим алгоритм BFS, чтобы выяснить порядок обхода.

Решение —

• Инициализируйте статус всех вершин как «Готов».

• Поставьте в очередь и измените ее статус на «Ожидание».

• Удалить из очереди, отметить его как «Посещенные».

• Добавьте соседей a в состоянии «Готово» b, d и e в конец очереди и отметьте их как «Ожидание».

• Удалите b из очереди, пометьте его как «Посещенный», поместите соседа «Готово» c в конец очереди и отметьте c как «Ожидание».

• Удалите d из очереди и отметьте его как «Посещенные». У него нет соседа в состоянии «Готов».

• Удалить e из очереди и отметить его как «Посещенные». У него нет соседа в состоянии «Готов».

• Удалить c из очереди и пометить его как «Посещенные». У него нет соседа в состоянии «Готов».

• Очередь пуста, так что остановитесь.

Инициализируйте статус всех вершин как «Готов».

Поставьте в очередь и измените ее статус на «Ожидание».

Удалить из очереди, отметить его как «Посещенные».

Добавьте соседей a в состоянии «Готово» b, d и e в конец очереди и отметьте их как «Ожидание».

Удалите b из очереди, пометьте его как «Посещенный», поместите соседа «Готово» c в конец очереди и отметьте c как «Ожидание».

Удалите d из очереди и отметьте его как «Посещенные». У него нет соседа в состоянии «Готов».

Удалить e из очереди и отметить его как «Посещенные». У него нет соседа в состоянии «Готов».

Удалить c из очереди и пометить его как «Посещенные». У него нет соседа в состоянии «Готов».

Очередь пуста, так что остановитесь.

Таким образом, порядок обхода —

$a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c$

Альтернативные порядки прохождения:

$a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c$

Или $a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c$

Или $a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c$

Или $a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c$

Или $a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c$

Применение BFS

• Нахождение кратчайшего пути
• Минимальное связующее дерево для невзвешенного графика
• GPS навигационная система
• Обнаружение циклов в неориентированном графе
• Поиск всех узлов в одном подключенном компоненте

Анализ сложности

Пусть $G (V, E)$ — граф с числом вершин $| V |$ и числом ребер $| E |$. Если алгоритм поиска в ширину посещает каждую вершину графа и проверяет каждое ребро, то его временная сложность будет:

$$ O (| V | + | E |). O (| E |) $$

Может варьироваться от $O (1)$ до $O (| V2 |)$

Глубина Первый Поиск

Алгоритм поиска в глубину (DFS) начинается с вершины $v$, затем переходит к смежной вершине (скажем, х), которая ранее не посещалась, помечается как «посещенная» и продолжается со смежной вершиной $x$, и скоро.

Если в любой вершине он обнаруживает, что все смежные вершины посещены, то он возвращается назад, пока не найдет первую вершину, имеющую соседнюю вершину, которая не была пройдена ранее. Затем он пересекает эту вершину, продолжается со смежными вершинами, пока не пройдет все посещенные вершины и не должен вернуться назад. Таким образом, он будет проходить через все вершины, достижимые из начальной вершины $v$.

Алгоритм DFS

Концепция состоит в том, чтобы посетить все соседние вершины соседней вершины до посещения других соседних вершин.

• Инициализировать статус всех узлов как «Готов»

• Поместите исходную вершину в стек и измените ее статус на «Ожидание»

• Повторите следующие два шага, пока стек не станет пустым —

  • Вставьте верхнюю вершину из стека и отметьте ее как «Посещенные».

  • Нажмите на вершину стека всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

Инициализировать статус всех узлов как «Готов»

Поместите исходную вершину в стек и измените ее статус на «Ожидание»

Повторите следующие два шага, пока стек не станет пустым —

Вставьте верхнюю вершину из стека и отметьте ее как «Посещенные».

Нажмите на вершину стека всех соседей удаленной вершины, чей статус «Готов». Отметьте их статус «Ожидание».

проблема

Давайте возьмем граф (исходная вершина — «a») и применим алгоритм DFS, чтобы выяснить порядок обхода.

Решение

• Инициализируйте статус всех вершин как «Готов».

• Вставьте в стек и измените его статус на «Ожидание».

• Нажмите a и отметьте его как «Посещенные».

• Переведите соседей a в состояние «Готово» e, d и b в верхнюю часть стека и отметьте их как «Ожидание».

• Извлеките b из стека, отметьте его как «Посещенный», поместите соседа «Готово» c в стек.

• Вытащите c из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

• Вытащите d из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

• Извлеките e из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

• Стек пуст. Так что остановись.

Инициализируйте статус всех вершин как «Готов».

Вставьте в стек и измените его статус на «Ожидание».

Нажмите a и отметьте его как «Посещенные».

Переведите соседей a в состояние «Готово» e, d и b в верхнюю часть стека и отметьте их как «Ожидание».

Извлеките b из стека, отметьте его как «Посещенный», поместите соседа «Готово» c в стек.

Вытащите c из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

Вытащите d из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

Извлеките e из стека и отметьте его как «Посещенный». У него нет «готового» соседа.

Стек пуст. Так что остановись.

Таким образом, порядок обхода —

$a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e$

Альтернативные порядки прохождения:

$a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d$

Или $a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d$

Или $a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c$

Или $a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b$

Или $a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e$

Анализ сложности

Пусть $G (V, E)$ — граф с числом вершин $| V |$ и числом ребер $| E |$. Если алгоритм DFS посещает каждую вершину графа и проверяет каждое ребро, то временная сложность составляет:

$$\ circleddash (| V | + | E |)$$

Приложения

• Обнаружение цикла на графике
• Найти топологическую сортировку
• Чтобы проверить, является ли график двудольным
• Поиск подключенных компонентов
• Нахождение мостов графа
• Нахождение двунаправленности в графах
• Решение задачи «Рыцарский тур»
• Решение головоломок только с одним решением

Введение в деревья

Дерево — это дискретная структура, которая представляет иерархические отношения между отдельными элементами или узлами. Дерево, в котором родитель имеет не более двух детей, называется бинарным деревом.

Дерево и его свойства

Определение — Дерево — это связный ациклический неориентированный граф. Между каждой парой вершин в $G$ существует уникальный путь. Дерево с N числом вершин содержит $(N-1)$ число ребер. Вершина, которая имеет 0 градусов, называется корнем дерева. Вершина, имеющая 1 градус, называется листовым узлом дерева, а степень внутреннего узла составляет не менее 2.

Пример . Ниже приведен пример дерева.

Центры и Би-Центры Дерева

Центр дерева — это вершина с минимальным эксцентриситетом. Эксцентриситет вершины $X$ в дереве $G$ — это максимальное расстояние между вершиной $X$ и любой другой вершиной дерева. Максимальный эксцентриситет — диаметр дерева. Если у дерева есть только один центр, оно называется Центральным деревом, а если у дерева есть только несколько центров, оно называется Би-центральным деревом. Каждое дерево является либо центральным, либо двухцентральным.

Алгоритм нахождения центров и бицентров дерева

Шаг 1 — Удалите все вершины степени 1 из данного дерева, а также удалите их падающие ребра.

Шаг 2 — Повторяйте шаг 1, пока не останется одна вершина или две вершины, соединенные ребром. Если осталась одна вершина, то это центр дерева, а если осталось две вершины, соединенные ребром, то это бицентр дерева.

Проблема 1

Узнайте центр / би-центр следующего дерева —

Решение

Сначала мы удалим все вершины степени 1, а также удалим их падающие ребра и получим следующее дерево:

Опять же, мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Наконец, мы получили одну вершину «c» и остановили алгоритм. Поскольку существует единственная вершина, у этого дерева есть один центр ‘c’, и дерево является центральным деревом.

Проблема 2

Узнайте центр / би-центр следующего дерева —

Решение

Сначала мы удалим все вершины степени 1, а также удалим их падающие ребра и получим следующее дерево:

Опять же, мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Наконец, у нас осталось две вершины «c» и «d», поэтому мы останавливаем алгоритм. Поскольку оставлены две вершины, соединенные ребром, это дерево имеет двухцентровый «cd», а дерево является двухцентровым.

Маркированные деревья

Определение — помеченное дерево — это дерево, вершинам которого присваиваются уникальные номера от 1 до n. Мы можем посчитать такие деревья для малых значений n вручную, чтобы предположить общую формулу. Число помеченных деревьев из n вершин равно $n ^ {n-2}$. Два помеченных дерева изоморфны, если их графы изоморфны и соответствующие точки двух деревьев имеют одинаковые метки.

пример

Немеченые деревья

Определение — немеченое дерево — это дерево, вершинам которого не назначены никакие числа. Число помеченных деревьев с числом вершин n равно $ \ frac {(2n)!} {(N + 1)! N! } $ (n- ^е каталонское число)

пример

Укорененное дерево

Корневое дерево $G$ — это связный ациклический граф со специальным узлом, который называется корнем дерева, и каждое ребро прямо или косвенно происходит от корня. Упорядоченное корневое дерево — это корневое дерево, в котором упорядочены дочерние элементы каждой внутренней вершины. Если каждая внутренняя вершина корневого дерева имеет не более m дочерних элементов, она называется m-арным деревом. Если каждая внутренняя вершина корневого дерева имеет ровно m детей, она называется полным m-арным деревом. Если $m = 2$, корневое дерево называется бинарным деревом.

Двоичное дерево поиска

Двоичное дерево поиска — это двоичное дерево, которое удовлетворяет следующему свойству:

• $X$ в левом поддереве вершины $V, Value (X) \ le Value (V)$
• $Y$ в правом поддереве вершины $V, Value (Y) \ ge Value (V)$

Таким образом, значение всех вершин левого поддерева внутреннего узла $V$ меньше или равно $V$, а значение всех вершин правого поддерева внутреннего узла $V$ больше или равно $V$. Количество ссылок от корневого узла к самому глубокому узлу является высотой дерева двоичного поиска.

пример

Алгоритм поиска ключа в BST

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)  

Сложность бинарного дерева поиска

	Средний случай	Худший случай
Космическая сложность	На)	На)
Сложность поиска	O (log n)	На)
Сложность вставки	O (log n)	На)
Сложность удаления	O (log n)	На)

Дискретная математика — связующие деревья

Остовное дерево связного неориентированного графа $G$ — это дерево, минимально включающее в себя все вершины $G$. Граф может иметь много связующих деревьев.

пример

Минимальное остовное дерево

Остовное дерево с присвоенным весом, меньшим или равным весу каждого возможного остовного дерева взвешенного связного и ненаправленного графа $G$, называется минимальным остовным деревом (MST). Вес связующего дерева — это сумма всех весов, назначенных каждому ребру связующего дерева.

пример

Алгоритм Крускала

Алгоритм Крускала — это жадный алгоритм, который находит минимальное остовное дерево для связанного взвешенного графа. Он находит дерево этого графа, которое включает в себя каждую вершину, и общий вес всех ребер в дереве меньше или равен каждому возможному остовному дереву.

Алгоритм

Шаг 1 — Расположите все ребра данного графа $G (V, E)$ в неубывающем порядке по весу ребра.

Шаг 2 — Выберите наименьшее взвешенное ребро на графике и проверьте, образует ли оно цикл с остовным деревом, сформированным до сих пор.

Шаг 3 — Если цикла нет, включите это ребро в связующее дерево, иначе отбросьте его.

Шаг 4 — Повторите Шаг 2 и Шаг 3 до тех пор, пока в остовном дереве не останется $(V-1)$ количество ребер.

проблема

Предположим, что мы хотим найти минимальное остовное дерево для следующего графа G, используя алгоритм Крускала.

Решение

Из приведенного выше графика мы строим следующую таблицу —

Край	Пара вершин	Крайний вес
E1	(а, б)	20
E2	(а, в)	9
E3	(а, г)	13
E4	(До нашей эры)	1
E5	(б, д)	4
E6	(б, е)	5
E7	(CD)	2
E8	(д, д)	3
E9	(д, ж)	14

Теперь мы переставим таблицу в порядке возрастания веса ребра —

Край	Пара вершин	Крайний вес
E4	(До нашей эры)	1
E7	(CD)	2
E8	(д, д)	3
E5	(б, д)	4
E6	(б, е)	5
E2	(а, в)	9
E3	(а, г)	13
E9	(д, ж)	14
E1	(а, б)	20

Поскольку мы получили все 5 ребер на последнем рисунке, мы останавливаем алгоритм, и это минимальное остовное дерево, и его общий вес составляет $(1 + 2 + 3 + 5 + 9) = 20$.

Алгоритм Прима

Алгоритм Прима, открытый в 1930 году математиками Войтехом Ярником и Робертом С. Примом, является жадным алгоритмом, который находит минимальное остовное дерево для связанного взвешенного графа. Он находит дерево этого графа, которое включает в себя каждую вершину, и общий вес всех ребер в дереве меньше или равен каждому возможному остовному дереву. Алгоритм Прима быстрее на плотных графах.

Алгоритм

• Инициализируйте минимальное остовное дерево с единственной вершиной, случайно выбранной из графа.

• Повторяйте шаги 3 и 4, пока все вершины не будут включены в дерево.

• Выберите ребро, которое соединяет дерево с вершиной, которой еще нет в дереве, чтобы вес ребра был минимальным, а включение ребра не образовывало цикл.

• Добавьте выбранное ребро и вершину, которую оно соединяет с деревом.

Инициализируйте минимальное остовное дерево с единственной вершиной, случайно выбранной из графа.

Повторяйте шаги 3 и 4, пока все вершины не будут включены в дерево.

Выберите ребро, которое соединяет дерево с вершиной, которой еще нет в дереве, чтобы вес ребра был минимальным, а включение ребра не образовывало цикл.

Добавьте выбранное ребро и вершину, которую оно соединяет с деревом.

проблема

Предположим, что мы хотим найти минимальное остовное дерево для следующего графа G, используя алгоритм Прима.

Решение

Здесь мы начинаем с вершины «а» и продолжаем.

Это минимальное связующее дерево, и его общий вес составляет $(1 + 2 + 3 + 5 + 9) = 20$.

Булевы выражения и функции

Булева алгебра является алгеброй логики. Он имеет дело с переменными, которые могут иметь два дискретных значения: 0 (False) и 1 (True); и операции, которые имеют логическое значение. Самый ранний метод манипулирования символической логикой был изобретен Джорджем Булем и впоследствии стал известен как Булева алгебра.

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

Булевы функции

Булева функция — это особый вид математической функции $f: X ^ n \ rightarrow X$ степени n, где $X = \ lbrace {0, 1} \ rbrace$ — булева область, а n — неотрицательное целое число , Он описывает способ получения логического вывода из логических входных данных.

Пример — Пусть, $F (A, B) = A'B '$. Это функция степени 2 из набора упорядоченных пар булевых переменных в набор $\ lbrace {0, 1} \ rbrace$, где $F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0$ и $F (1, 1) = 0$

Логические выражения

Булево выражение всегда создает логическое значение. Логическое выражение состоит из комбинации логических констант (True или False), логических переменных и логических связок. Каждое логическое выражение представляет логическую функцию.

Пример — $AB'C$ является логическим выражением.

Булевы тождества

Закон о двойном дополнении

$\ sim (\ sim A) = A$

Закон о дополнениях

$A + \ sim A = 1$ (ИЛИ Форма)

$ A. \ sim A = 0 $ (форма AND)

Идемпотентный закон

$A + A = A$ (ИЛИ Форма)

$ A. A = A $ (И Форма)

Закон об идентичности

$A + 0 = A$ (ИЛИ Форма)

$ A. 1 = A $ (форма И)

Закон о доминировании

$A + 1 = 1$ (ИЛИ Форма)

$ A. 0 = 0 $ (форма И)

Коммутативное право

$A + B = B + A$ (ИЛИ Форма)

$ A. B = B. A $ (И Форма)

Ассоциативное право

$A + (B + C) = (A + B) + C$ (ИЛИ Форма)

$ A. (B. C) = (A. B). C $ (И Форма)

Закон поглощения

$ A. (A + B) = A $

$A + (A. B) = A$

Закон об упрощении

$ A. (\ sim A + B) = A. B $

$A + (\ sim A. B) = A + B$

Распределительный закон

$ A + (B. C) = (A + B). (A + C) $

$ A. (B + C) = (A. B) + (A. C) $

Закон Моргана

$\ sim (A. B) = \ sim A + \ sim B$

$ \ sim (A + B) = \ sim A. \ sim B $

Канонические Формы

Для булева выражения есть два вида канонических форм:

• Форма суммы minterms (SOM)
• Произведение формы maxterms (POM)

Форма Сумма Минтерм (SOM) или Сумма Продуктов (SOP)

Минтерма — это произведение всех переменных, взятых либо в их прямой, либо в дополненной форме. Любая булева функция может быть выражена как сумма ее 1-минут, а обратная функция может быть выражена как сумма ее 0-минут. Следовательно,

F (список переменных) = ∑ (список 1-минутных индексов)

а также

F ‘(список переменных) = ∑ (список 0-минутных индексов)

	В	С	Срок	Minterm
0	0	0	x’y’z»	м 0
0	0	1	x’y’z	м 1
0	1	0	x’yz»	м 2
0	1	1	x’yz	м 3
1	0	0	xy’z»	м 4
1	0	1	xy’z	м 5
1	1	0	хуг»	м 6
1	1	1	хуг	м 7

пример

Пусть $F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz$

Или $F (x, y, z) = m_0 + m_5 + m_6 + m_7$

Следовательно,

$F (x, y, z) = \ sum (0, 5, 6, 7)$

Теперь мы найдем дополнение $F (x, y, z)$

$F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z'$

Или $F '(x, y, z) = m_3 + m_1 + m_2 + m_4$

Следовательно,

$F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4)$

Форма «Продукт Maxterms» (POM) или «Сумма продукта» (POS)

Максимум — это сложение всех переменных, взятых либо в их прямой, либо в дополненной форме. Любая булева функция может быть выражена как произведение ее 0-maxterms, а обратная функция может быть выражена как произведение ее 1-maxterms. Следовательно,

F (список переменных) = $\ pi$ (список индексов 0-maxterm).

а также

F ‘(список переменных) = $\ pi$ (список индексов 1-maxterm).

	В	С	Срок	Maxterm
0	0	0	х + у + г	М 0
0	0	1	x + y + z ‘	М 1
0	1	0	x + y ‘+ z	М 2
0	1	1	x + y ‘+ z’	М 3
1	0	0	x ‘+ y + z	М 4
1	0	1	x ‘+ y + z’	М 5
1	1	0	x ‘+ y’ + z	М 6
1	1	1	x ‘+ y’ + z ‘	М 7

пример

Пусть $ F (x, y, z) = (x + y + z). (x + y + z ‘). (х + у ‘+ г). (х ‘+ у + г) $

Или $ F (x, y, z) = M_0. М_1. М_2. M_4 $

Следовательно,

$F (x, y, z) = \ pi (0, 1, 2, 4)$

$ F » (x, y, z) = (x + y ‘+ z’). (x ‘+ y + z’). (x ‘+ y’ + z). (Х ‘+ у’ + г ‘) $

Или $ F (x, y, z) = M_3. М_5. М_6. M_7 $

Следовательно,

$F '(x, y, z) = \ pi (3, 5, 6, 7)$

Логические ворота

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

НЕ Ворота

Гейт НЕ инвертирует однобитовый вход в один бит вывода.

	~ A
0	1
1	0

И Ворота

Логический элемент И представляет собой логический вентиль, который дает высокий выходной сигнал, только если все его входные данные являются высокими, в противном случае он дает низкий выходной сигнал. Точка (.) Используется для отображения операции AND.

	В	AB
0	0	0
0	1	0
1	0	0
1	1	1

ИЛИ Ворота

ИЛИ вентиль — это логический вентиль, который дает высокий выходной сигнал, если хотя бы один из входов имеет высокий уровень. Плюс (+) используется для отображения операции ИЛИ.

	В	А + В
0	0	0
0	1	1
1	0	1
1	1	1

NAND Gate

Вентиль NAND — это логический вентиль, который выдает низкий выходной сигнал, только если все его входы являются высокими, в противном случае он дает высокий выходной сигнал.

	В	~ (АВ)
0	0	1
0	1	1
1	0	1
1	1	0

NOR Gate

Вентиль NOR — это логический вентиль, который дает высокий выход, если оба входа низки, в противном случае он дает низкий выход.

	В	~ (А + В)
0	0	1
0	1	0
1	0	0
1	1	0

XOR (Эксклюзив ИЛИ) Ворота

Вентиль XOR — это логический вентиль, который дает высокий выход, если входы различны, в противном случае он дает низкий выход.

	В	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Ворота X-NOR (Эксклюзив NOR)

Вентиль EX-NOR — это логический вентиль, который дает высокий выходной сигнал, если входы одинаковы, в противном случае он дает низкий выходной сигнал.

	В	A X-NOR B
0	0	1
0	1	0
1	0	0
1	1	1

Упрощение булевых функций

Упрощение с использованием алгебраических функций

В этом подходе одно булево выражение минимизируется в эквивалентное выражение путем применения булевых тождеств.

Проблема 1

Минимизируйте следующее логическое выражение, используя логические тождества —

$$F (A, B, C) = A'B + BC '+ BC + AB'C'$$

Решение

Учитывая, $F (A, B, C) = A'B + BC '+ BC + AB'C'$

Или $F (A, B, C) = A'B + (BC '+ BC') + BC + AB'C '$

[По идемпотентному закону, BC ‘= BC’ + BC ‘]

Или $F (A, B, C) = A'B + (BC '+ BC) + (BC' + AB'C ')$

Или $F (A, B, C) = A'B + B (C '+ C) + C' (B + AB ')$

[По распределительным законам]

Или $F (A, B, C) = A'B + B.1 + C '(B + A)$

[(C ‘+ C) = 1 и закон поглощения (B + AB’) = (B + A)]

Или $F (A, B, C) = A'B + B + C '(B + A)$

[B.1 = B]

Или $F (A, B, C) = B (A '+ 1) + C' (B + A)$

Или $F (A, B, C) = B.1 + C '(B + A)$

[(A ‘+ 1) = 1]

Или $F (A, B, C) = B + C '(B + A)$

[As, B.1 = B]

Или $F (A, B, C) = B + BC '+ AC'$

Или $F (A, B, C) = B (1 + C ') + AC'$

Или $F (A, B, C) = B.1 + AC '$

[As, (1 + C ‘) = 1]

Или $F (A, B, C) = B + AC '$

[As, B.1 = B]

Итак, $F (A, B, C) = B + AC '$ является минимизированной формой.

Проблема 2

Минимизируйте следующее логическое выражение, используя логические тождества —

$$F (A, B, C) = (A + B) (A + C)$$

Решение

Учитывая, $F (A, B, C) = (A + B) (A + C)$

Или $F (A, B, C) = AA + AC + BA + BC$ [Применение дистрибутивного правила]

Или $F (A, B, C) = A + AC + BA + BC$ [Применение закона Идемпотента]

Или $F (A, B, C) = A (1 + C) + BA + BC$ [Применение закона распределения]

Или $F (A, B, C) = A + BA + BC$ [Применение закона доминирования]

Или $F (A, B, C) = (A + 1) .A + BC$ [Применение закона распределения]

Или $F (A, B, C) = 1.A + BC$ [Применение закона доминирования]

Или $F (A, B, C) = A + BC$ [Применение закона доминирования]

Итак, $F (A, B, C) = A + BC$ — это минимизированная форма.

Карно Карты

Карта Карно (K – map), представленная Морисом Карнофином в 1953 году, представляет собой сетчатое представление таблицы истинности, которая используется для упрощения выражений булевой алгебры. Карта Карно имеет ноль и одну запись в разных позициях. Он обеспечивает группировку логических выражений с общими факторами и исключает нежелательные переменные из выражения. На K-карте пересечение вертикальной или горизонтальной границы ячейки всегда является изменением только одной переменной.

Пример 1

Произвольная таблица истинности взята ниже —

	В	Операция Б
0	0	вес
0	1	Икс
1	0	Y
1	1	Z

Теперь мы сделаем k-карту для приведенной выше таблицы истинности —

Пример 2

Теперь мы сделаем K-карту для выражения — AB + A’B ‘

Упрощение с использованием K-карты

K-map использует некоторые правила для упрощения логических выражений, объединяя смежные ячейки в один термин. Правила описаны ниже —

Правило 1 — Любая ячейка, содержащая ноль, не может быть сгруппирована.

Неправильная группировка

Правило 2 — Группы должны содержать 2n ячеек (n, начиная с 1).

Неправильная группировка

Правило 3 — Группировка должна быть горизонтальной или вертикальной, но не должна быть диагональной.

Неправильная диагональная группировка

Правильная вертикальная группировка

Правильная горизонтальная группировка

Правило 4 — Группы должны быть охвачены как можно шире.

Недостаточная группировка

Правильная группировка

Правило 5 — Если 1 из любой ячейки не может быть сгруппирована с какой-либо другой ячейкой, она будет действовать как сама группа.

Правильная группировка

Правило 6 — Группы могут перекрываться, но должно быть как можно меньше групп.

Правильная группировка

Правило 7 — Самая левая ячейка / ячейки могут быть сгруппированы с самой правой ячейкой / ячейками, а самая верхняя ячейка / ячейки может быть сгруппирована с самой нижней ячейкой / ячейками.

Правильная группировка

проблема

Минимизируйте следующее логическое выражение, используя K-map —

$$F (A, B, C) = A'BC + A'BC '+ AB'C' + AB'C$$

Решение

Каждый термин помещается в k-карту, и мы получаем следующее —

K-карта для F (A, B, C)

Теперь мы сгруппируем ячейки 1 согласно правилам, изложенным выше —

K-карта для F (A, B, C)

У нас есть две группы, которые называются $A'B$ и $AB '$. Следовательно, $F (A, B, C) = A'B + AB '= A \ oplus B$. Это минимизированная форма.