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

Математику можно в общих чертах разделить на две категории:

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

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

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

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

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

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

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

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

Набор - Определение

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

Некоторые примеры наборов

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

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

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

• Реестр или табличная форма
• Обозначение конструктора множеств

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

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

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

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

Обозначение конструктора множеств

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

Example 1 - Набор $\lbrace a,e,i,o,u \rbrace$ записывается как -

$A = \lbrace x : \text{x is a vowel in English alphabet} \rbrace$

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

Example- Если$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$.

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

Типы наборов

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

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

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

Example - $S = \lbrace x \:| \:x \in N$ и $70 \gt x \gt 50 \rbrace$

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

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

Example - $S = \lbrace x \: | \: x \in N $ и $ x \gt 10 \rbrace$

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

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

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

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

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

Универсальный набор

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

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

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

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

Example - $S = \lbrace x \:| \: x \in N$ и $7 \lt x \lt 8 \rbrace = \emptyset$

Одноэлементный набор или набор единиц

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

Example - $S = \lbrace x \:| \:x \in N,\ 7 \lt x \lt 9 \rbrace$ знак равно $\lbrace 8 \rbrace$

Равный набор

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

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

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

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

Example - Если $A = \lbrace 1, 2, 6 \rbrace$ и $B = \lbrace 16, 17, 22 \rbrace$, они эквивалентны, поскольку мощность A равна мощности B. т.е. $|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)$

Example - Пусть, $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)$

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

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

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

Examples

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

К операциям с множеством относятся: «Установить соединение», «Установить пересечение», «Установить разность», «Дополнение к множеству» и «Декартово произведение».

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

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

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

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

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

Example - Если $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$.

Example - Если $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$ универсальный набор, в который входят все предметы.

Example - Если $A = \lbrace x \:| \: x\ \: {belongs\: to\: set\: of\: odd \:integers} \rbrace$ тогда $A' = \lbrace y\: | \: y\ \: {does\: not\: belong\: to\: set\: of\: odd\: integers } \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$

Example - Если взять два комплекта $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)$.

Example −

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

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

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

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

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

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

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

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

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

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

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

Example

Позволять $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 - мощность множества.

Example -

Позволять $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$

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

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

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

Обычно n-арное отношение R между множествами $A_1, \dots ,\ and\ 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), то -

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

• В range 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$

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

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

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

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

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

• В Empty Relation между множествами X и Y, или на E, пустое множество $\emptyset$

• В Full Relation между множествами X и Y есть множество $X \times Y$

• В Identity Relation на множестве X есть множество $\lbrace (x, x) | x \in X \rbrace$

• Обратное отношение R 'отношения R определяется как - $R' = \lbrace (b, a) | (a, b) \in R \rbrace$

  Example - Если $R = \lbrace (1, 2), (2, 3) \rbrace$ тогда $R' $ будет $\lbrace (2, 1), (3, 2) \rbrace$

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

  Example - Отношение $R = \lbrace (a, a), (b, b) \rbrace$ на съемочной площадке $X = \lbrace a, b \rbrace$ рефлексивно.

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

  Example - Отношение $R = \lbrace (a, b), (b, a) \rbrace$ на съемочной площадке $X = \lbrace a, b \rbrace$ иррефлексивно.

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

  Example - Отношение $R = \lbrace (1, 2), (2, 1), (3, 2), (2, 3) \rbrace$ на съемочной площадке $A = \lbrace 1, 2, 3 \rbrace$ симметрично.

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

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

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

  Example - Отношение $R = \lbrace (1, 2), (2, 3), (1, 3) \rbrace$ на съемочной площадке $A = \lbrace 1, 2, 3 \rbrace$ транзитивен.

• Отношение - это Equivalence Relation если он рефлексивный, симметричный и транзитивный.

  Example - Отношение $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$ является отношением эквивалентности, поскольку оно рефлексивно, симметрично и транзитивно.

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

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

Функция или отображение (определяется как $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: 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: A \rightarrow B$ биективно или взаимно однозначно соответствует тогда и только тогда, когда f одновременно инъективен и сюръективен.

Проблема

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

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

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

Следовательно, f есть injective.

Вот, $2x – 3= y$

Так, $x = (y+5)/3$ который принадлежит R и $f(x) = y$.

Следовательно, f есть surjective.

поскольку f оба surjective и injective, мы можем сказать f является bijective.

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

В inverse взаимно однозначной соответствующей функции $f : A \rightarrow B$, - функция $g : B \rightarrow A$, владеющий следующим имуществом -

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

Функция f называется invertible, если существует обратная к нему функция 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: A \rightarrow B$ и $g: B \rightarrow C$ можно составить, чтобы получить композицию $g o f$. Это функция от A до C, определяемая$(gof)(x) = g(f(x))$

пример

Позволять $f(x) = x + 2$ и $g(x) = 2x + 1$, находить $( f o g)(x)$ и $( g o f)(x)$.

Решение

$(f o g)(x) = f (g(x)) = f(2x + 1) = 2x + 1 + 2 = 2x + 3$

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

Следовательно, $(f o g)(x) \neq (g o f)(x)$

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

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

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

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

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

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

Предложная логика - определение

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

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

• «Человек смертен», возвращает истинное значение «ИСТИНА».
• «12 + 9 = 3–2», возвращает истинное значение «FALSE».

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

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

Соединительные

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

• ИЛИ ЖЕ ($\lor$)

• И ($\land$)

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

• Значение / если-то ($\rightarrow$)

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

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

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

А	B	А ∨ Б
Правда	Правда	Правда
Правда	Ложь	Правда
Ложь	Правда	Правда
Ложь	Ложь	Ложь

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

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

А	B	А ∧ Б
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Ложь

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

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

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

Implication / if-then ($\rightarrow$) - Намек $A \rightarrow B$предложение «если А, то В». Это ложь, если A истинно, а B ложно. Остальные случаи верны.

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

А	B	А → Б
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Правда
Ложь	Ложь	Правда

If and only if ($ \Leftrightarrow $) - $A \Leftrightarrow B$ является двухусловной логической связкой, которая истинна, когда p и q совпадают, т.е. оба ложны или оба истинны.

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

А	B	А ⇔ Б
Правда	Правда	Правда
Правда	Ложь	Ложь
Ложь	Правда	Ложь
Ложь	Ложь	Правда

Тавтологии

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

Example - Доказать $\lbrack (A \rightarrow B) \land A \rbrack \rightarrow B$ это тавтология

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

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

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

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

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

Example - Доказать $(A \lor B) \land \lbrack ( \lnot A) \land (\lnot B) \rbrack$ противоречие

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

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

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

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

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

Example - Доказать $(A \lor B) \land (\lnot A)$ непредвиденное обстоятельство

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

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

Как мы видим, каждое значение $(A \lor B) \land (\lnot A)$ имеет как «Истина», так и «Ложь», это случайность.

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

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

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

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

Example - Доказать $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ эквивалентны

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

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

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

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

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

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

Обратный, обратный и контрположительный

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

• Гипотеза, стр.
• Заключение, q

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

Example of Conditional Statement- «Если вы сделаете домашнее задание, вас не накажут». Здесь «вы делаете домашнее задание» - это гипотеза, p, а «вы не будете наказаны» - это заключение, q.

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

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

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

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

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

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

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

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

Example - Двойник $(A \cap B ) \cup C$ является $(A \cup B) \cap C$

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

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

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

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

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

Examples

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

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

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

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

Examples

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

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

Predicate Logic имеет дело с предикатами, которые представляют собой предложения, содержащие переменные.

Логика предикатов - определение

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

Ниже приведены несколько примеров предикатов -

• Пусть 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$ и $\exists x Y$ также wff

• Истинное и ложное значения - это wffs

• Каждая атомарная формула - это wff

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

Квантификаторы

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

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

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

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

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

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

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

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

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

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

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

Example

• $\forall\ a\: \exists 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$

Note - $\forall\: a\: \exists b\: P (x, y) \ne \exists a\: \forall b\: P (x, y)$

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

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

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

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

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

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

Правило вывода	имя	Правило вывода	имя
$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$	Дополнение	$$\begin{matrix} P \lor Q \\ \lnot P \\ \hline \therefore Q \end{matrix}$$	Дизъюнктивный силлогизм
$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$	Соединение	$$\begin{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}$$	Гипотетический силлогизм
$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$	Упрощение	$$\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}$$	Конструктивная дилемма
$$\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}$$	Modus Ponens	$$\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}$$	Разрушительная дилемма
$$\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}$$	Modus Tollens

Дополнение

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

$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$

пример

Пусть P будет утверждением "Он очень много учится" верно

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

Соединение

Если P и Q - две посылки, мы можем использовать правило конъюнкции, чтобы получить $ P \land Q $.

$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$

пример

Пусть П - «Он очень много учится»

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

Поэтому - «Он очень много учится и лучший мальчик в классе».

Упрощение

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

$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$

пример

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

Поэтому - «Он очень много учится».

Modus Ponens

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

$$\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}$$

пример

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

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

Поэтому - «Вы можете войти в facebook»

Modus Tollens

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

$$\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \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 \therefore 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 \therefore 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 \therefore 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 \therefore \lnot P \lor \lnot R \end{matrix}$$

пример

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

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

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

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

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

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

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

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

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

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

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

Закрытие

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

пример

Позволять $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$.

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

A binary operator $\otimes$ on a set A is associative when it holds the following property −

$(x \otimes y) \otimes z = x \otimes (y \otimes z)$, where $x, y, z \in A $

Example

Let $A = \lbrace 1, 2, 3, 4 \rbrace$

The operator plus $( + )$ is associative because for any three elements, $x,y,z \in A$, the property $(x + y) + z = x + ( y + z )$ holds.

The operator minus $( - )$ is not associative since

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

Commutative Laws

A binary operator $\otimes$ on a set A is commutative when it holds the following property −

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

пример

Позволять $A = \lbrace 1, 2, 3, 4 \rbrace$

Оператор плюс $( + )$ коммутативен, потому что для любых двух элементов $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’$ (Композиция) называется полугруппой, если она выполняется одновременно при выполнении двух условий:

• Closure - Для каждой пары $(a, b) \in S, \:(a \omicron b)$ должен присутствовать в наборе $S$.

• Associative - Для каждого элемента $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$

Моноид

Моноид - это полугруппа с единичным элементом. Элемент идентичности (обозначается$e$ или E) множества S - такой элемент, что $(a \omicron e) = a$, для каждого элемента $a \in S$. Элемент идентичности также называетсяunit element. Итак, моноид одновременно обладает тремя свойствами -Closure, Associative, Identity element.

пример

Множество натуральных чисел (исключая ноль) с операцией умножения является моноидом. $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) \in 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$ и так далее]

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

А cyclic groupгруппа, которая может быть создана одним элементом. Каждый элемент циклической группы - это мощность определенного элемента, называемого генератором. Циклическая группа может быть сгенерирована генератором «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$который охватывает все элементы группы. Следовательно, это циклическая группа.

Note - А cyclic groupвсегда является абелевой группой, но не всякая абелева группа является циклической группой. Добавляемые рациональные числа не циклические, а абелевы.

А subgroup H - подмножество группы G (обозначается $H ≤ G$), если он одновременно удовлетворяет четырем свойствам - Closure, Associative, Identity element, и Inverse.

Подгруппа 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)

Частично упорядоченный набор состоит из набора с бинарным отношением, которое является рефлексивным, антисимметричным и транзитивным. «Частично упорядоченный набор» сокращенно называется 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\ and\ \lbrace (1, 2), (1, 3), (2, 3) \rbrace ∉ R$

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

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

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

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

Диаграмма Хассе чугуна - это ориентированный граф, вершины которого являются элементами чугуна, а дуги покрывают пары (x, y) в чугуре. Если в посете$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$ упорядоченный по \ substeq является полностью упорядоченным набором, так как все элементы набора мощности $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 | y$должны выполняться, но неверно, что 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 ', если$\exists x(x \land x’=0 and 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 \land( b \lor (a \land d)) = (a \land b) \lor (a \land d)$

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

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

• $a \lor a = a$

• $a \land a = 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 \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 можно сгенерировать так, чтобы первые пять букв были заглавными буквами, следующие четыре - цифрами, а последняя - снова заглавной буквой. Для решения этих задач используется математическая теория счета.Counting в основном включает фундаментальное правило подсчета, правило перестановки и правило комбинирования.

Правила суммы и произведения

В Rule of Sum и Rule of Product используются для разложения сложных задач счета на простые задачи.

• The Rule of Sum - Если последовательность задач $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|$

• The Rule of Product - Если последовательность задач $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|$

пример

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

Solution - От X до Y он может войти $3 + 2 = 5$способов (Правило суммы). После этого он может перейти от Y к Z в$4 + 5 = 9$способов (Правило суммы). Следовательно, от X до Z он может войти$5 \times 9 = 45$ способами (Правило продукта).

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

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

Примеры

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

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

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

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

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

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

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

Proof - Пусть будет 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)..... (n-r + 1)$

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

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

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

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

• Если есть 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_{r-x}}$

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

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

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

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

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

Problem 1 - Из набора из 6 разных карт, сколькими способами мы можем переставить их?

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

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

Solution - Слово «ЧИТАТЕЛЬ» состоит из 6 букв (2 E, 1 A, 1D и 2R.).

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

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

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

Комбинации

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

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

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

Problem 1

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

Solution

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

Problem 2

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

Solution

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

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

Problem 3

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

Solution

Пронумеруем группы 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 элементов из п элементов равно суммирования числа способов выбора (K-1) элементов из (N-1) элементов и количество способов выбрать элементы из n-1 элементов.

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

Proof -

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

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

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

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

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

$= n_{ C_{ k } }$

Принцип голубятни

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

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

Примеры

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

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

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

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

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

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

$|A \cup B \cup 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\limits_{1\leq i<j<k\leq n}|A_i \cap A_j|+\sum\limits_{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|$

Problem 1

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

Solution

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

Problem 2

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

Solution

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

Так, $| X \cup Y | = 50$, $|X| = 24$, $|Y| = 36$

$|X \cap Y| = |X| + |Y| - |X \cup Y| = 24 + 36 - 50 = 60 - 50 = 10$

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

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

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

Базовые концепты

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

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

Random Experiment- Эксперимент, в котором известны все возможные исходы, а точный результат нельзя предсказать заранее, называется случайным экспериментом. Подбрасывание честной монеты - пример случайного эксперимента.

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

Event- Любое подмножество пробного пространства называется событием. Если после подбрасывания монеты выпадет голова, то это событие.

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

$Probability\:of\:occurence\:of\:an\:event = \frac{Total\:number\:of\:favourable \: outcome}{Total\:number\:of\:Outcomes}$

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

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

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

Шаг 2 - Подсчитайте количество благоприятных исходов эксперимента.

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

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

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

Итак, общее количество исходов = 2

Следовательно, вероятность получить Head $(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)$

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

• Если есть два события $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)$.

Problem 1

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

Solution

Предположим, что 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%.

Problem 2

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

Solution

Предположим, что 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%.

Problem 3

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

Solution

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

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

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

Theorem - Если 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$ известен.

Problem

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

Solution

Позволять $A_i$быть в случае выбора 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$

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

Определение

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

Техника включает в себя два шага для доказательства утверждения, как указано ниже:

Step 1(Base step) - Доказывает, что утверждение верно для начального значения.

Step 2(Inductive step)- Доказывает, что если утверждение верно для n- ^й итерации (или числа n ), то оно также верно для (n + 1) ^-й итерации (или числа n + 1 ).

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

Step 1- Рассмотрите начальное значение, для которого утверждение верно. Необходимо показать, что утверждение верно для n = начального значения.

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

Проблема 1

$3^n-1$ делится на 2 при n = 1, 2, ...

Solution

Step 1 - Для $n = 1, 3^1-1 = 3-1 = 2$ что кратно 2

Step 2 - Допустим $3^n-1$ верно для $n=k$, Следовательно, $3^k -1$ верно (это предположение)

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

$3^{k+1} - 1 = 3 \times 3^k - 1 = (2 \times 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 $

Solution

Step 1 - Для $n=1, 1 = 1^2$, Следовательно, шаг 1 выполнен.

Step 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$ hold, удовлетворяющее шагу 2.

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

Проблема 3

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

Solution

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

Step 2 - Предположим, утверждение верно для $n=k$, Следовательно, $(ab)^k = a^kb^k$ верно (это предположение).

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

Дано, $(ab)^k = a^k b^k$

Или же, $(ab)^k (ab) = (a^k b^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$, используя следующие шаги -

• Step 1(Base step) - Это доказывает, что первоначальное предложение $P(1)$ правда.

• Step 2(Inductive step) - Это доказывает, что условное утверждение $[P(1) \land P(2) \land P(3) \land \dots \land P(k)] → P(k + 1)$ верно для положительных целых чисел $k$.

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

Определение

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

Example - Ряд Фибоначчи - $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_{n-k} $($A_n$ постоянная и $A_k \neq 0$) на последовательности чисел как полином первой степени.

Это несколько примеров линейных рекуррентных уравнений -

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

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

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

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

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

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

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

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

Case 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))$ это решение.

Problem 1

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

Solution

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

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

Problem 2

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

Solution

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

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

Problem 3

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

Solution

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

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

пример

Пусть неоднородное рекуррентное соотношение есть $F_n = AF_{n–1} + BF_{n-2} + f(n)$ с характерными корнями $x_1 = 2$ и $x_2 = 5$. Пробные решения для различных возможных значений$f(n)$ следующие -