이산 수학-빠른 가이드

수학은 크게 두 가지 범주로 분류 할 수 있습니다.

• 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의 원소 개수와 정확히 같을 때 발생합니다.이 경우 X에서 Y까지의 bijective 함수 'f'가 있습니다.

• $|X| \le |Y|$집합 X의 카디널리티가 집합 Y의 카디널리티보다 작거나 같음을 나타냅니다. X의 원소 개수가 Y보다 작거나 같을 때 발생합니다. 여기에는 X에서 Y까지의 주입 함수 'f'가 있습니다.

• $|X| \lt |Y|$집합 X의 카디널리티가 집합 Y의 카디널리티보다 작음을 나타냅니다. X의 요소 수가 Y보다 적을 때 발생합니다. 여기서 X에서 Y까지의 함수 'f'는 주입 기능이지만 bijective는 아닙니다.

• $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는 집합 Y의 모든 요소가 집합 X에 있으므로 집합 X의 하위 집합입니다. 따라서 다음과 같이 작성할 수 있습니다.$Y \subseteq X$.

Example 2 −하자, $X = \lbrace 1, 2, 3 \rbrace$ 과 $Y = \lbrace 1, 2, 3 \rbrace$. 여기서 집합 Y는 집합 Y의 모든 요소가 집합 X에 있으므로 집합 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$. 빈 집합의 요소 수가 유한하므로 빈 집합은 유한 집합입니다. 빈 세트 또는 널 세트의 카디널리티는 0입니다.

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의 카디널리티와 동일하므로 동일합니다. 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)$

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 년 John Venn이 발명 한 벤 다이어그램은 다른 수학적 세트 간의 가능한 모든 논리적 관계를 보여주는 개략도입니다.

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 − 2 세트를하면 $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의 모든 하위 집합 집합입니다. 카디널리티 n의 집합 S의 거듭 제곱 집합의 카디널리티는 다음과 같습니다.$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$

삼. $\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 동일한 세트의 객체 사이 또는 둘 이상의 세트의 객체 사이에 존재할 수 있습니다.

정의 및 속성

세트 x에서 y까지 이진 관계 R (다음과 같이 작성 됨) $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의 최소 카디널리티는 0이고 최대 값은$n^2$ 이 경우.

단일 집합 A의 이진 관계 R은 다음의 하위 집합입니다. $A \times A$.

각각 카디널리티가 m 및 n 인 두 개의 별개 세트 A와 B의 경우 A에서 B까지 관계 R의 최대 카디널리티는 mn 입니다.

도메인 및 범위

두 세트 A와 B가 있고 관계 R에 순서 쌍 (x, y)이 있으면-

• 그만큼 domain R의 Dom (R)은 $\lbrace x \:| \: (x, y) \in R \:for\: some\: y\: in\: B \rbrace$

• 그만큼 range 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$

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

• 사례 2 − 관계 R이 '보다 작 으면' $R = \lbrace (1, 3), (1, 7), (2, 3), (2, 7) \rbrace$

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

• 사례 3-관계 R이 '보다 큼'이면 $R = \lbrace (2, 1), (9, 1), (9, 3), (9, 7) \rbrace$

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

그래프를 이용한 관계 표현

관계는 유 방향 그래프를 사용하여 나타낼 수 있습니다.

그래프의 정점 수는 관계가 정의 된 세트의 요소 수와 같습니다. 관계 R의 각 순서 쌍 (x, y)에 대해 꼭지점 '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$

• 세트 A의 관계 R이 호출됩니다. Reflexive 만약 $\forall a \in A$ (aRa 홀드)

  Example − 관계 $R = \lbrace (a, a), (b, b) \rbrace$ 세트에 $X = \lbrace a, b \rbrace$ 반사적입니다.

• 세트 A의 관계 R이 호출됩니다. Irreflexive 아니라면 $a \in A$ (aRa는 보유하지 않음)과 관련이 있습니다.

  Example − 관계 $R = \lbrace (a, b), (b, a) \rbrace$ 세트에 $X = \lbrace a, b \rbrace$ 비 반사적입니다.

• 세트 A의 관계 R이 호출됩니다. 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$ 대칭입니다.

• 세트 A의 관계 R이 호출됩니다. 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$.

• 세트 A의 관계 R이 호출됩니다. 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는 Domain, Y는 함수 'f'의 Codomain이라고합니다.

함수 'f'는 X와 Y에 대한 관계입니다. $x \in X$, 고유 한 $y \in Y$ 그런 $(x,y) \in R$. 'x'는 사전 이미지라고하고 'y'는 함수 f의 이미지라고합니다.

함수는 일대일 또는 다대 일일 수 있지만 일대 다일 수는 없습니다.

인젝 티브 / 일대일 기능

기능 $f: A \rightarrow B$ 주입식 또는 일대일 기능입니다. $b \in B$, 최대 1 개 $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$

Surjective / Onto 기능

기능 $f: A \rightarrow B$f의 이미지가 범위와 같으면 추측 (onto)입니다. 동등하게, 모든$b \in B$, 일부가 있습니다 $a \in A$ 그런 $f(a) = b$. 이것은 B의 y에 대해 A에 일부 x가 있음을 의미합니다.$y = f(x)$.

예

• $f : N \rightarrow N, f(x) = x + 2$ 추측입니다.

• $f : R \rightarrow R, f(x) = x^2$ 제곱이 음수 인 실수를 찾을 수 없기 때문에 추측이 아닙니다.

Bijective / 일대일 특파원

기능 $f: A \rightarrow B$ bijective 또는 일대일 통신원 인 경우 f 주입 형과 추측 형입니다.

문제

기능 증명 $f: R \rightarrow R$ 정의 $f(x) = 2x – 3$ bijective 함수입니다.

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진실 값 "참"및 "거짓"이 할당 될 수있는 진술과 관련됩니다. 목적은 이러한 진술을 개별적으로 또는 복합적으로 분석하는 것입니다.

전치사 논리 – 정의

명제는 진리 값이 "true"또는 진리 값 "false"인 선언적 진술의 모음입니다. 명제 문은 명제 변수와 연결어로 구성됩니다. 명제 변수는 대문자 (A, B 등)로 표시합니다. 연결은 명제 변수를 연결합니다.

제안의 몇 가지 예는 다음과 같습니다.

• "Man is Mortal", 진리 값 "TRUE"를 반환합니다.
• "12 + 9 = 3 – 2", 진리 값 "FALSE"를 반환합니다.

다음은 제안이 아닙니다-

• "A는 2보다 작습니다". A의 특정 값을주지 않으면 그 진술이 참인지 거짓인지 말할 수 없기 때문입니다.

연결

명제 논리에서 일반적으로 우리는 다음과 같은 5 개의 연결을 사용합니다.

• 또는 ($\lor$)

• 그리고 ($\land$)

• 부정 / 아님 ($\lnot$)

• 의미 / if-then ($\rightarrow$)

• 경우에만 ($\Leftrightarrow$).

OR ($\lor$) − 두 명제 A와 B의 OR 연산 ( $A \lor B$)는 명제 변수 A 또는 B 중 하나라도 참이면 참입니다.

진리표는 다음과 같습니다-

ㅏ	비	A ∨ B
진실	진실	진실
진실	그릇된	진실
그릇된	진실	진실
그릇된	그릇된	그릇된

AND ($\land$) − 두 명제 A와 B의 AND 연산 ( $A \land B$)는 명제 변수 A와 B가 모두 참이면 참입니다.

진리표는 다음과 같습니다-

ㅏ	비	A ∧ B
진실	진실	진실
진실	그릇된	그릇된
그릇된	진실	그릇된
그릇된	그릇된	그릇된

Negation ($\lnot$) − 명제 A의 부정 (다음으로 작성) $\lnot A$)는 A가 참이면 거짓이고 A가 거짓이면 참입니다.

진리표는 다음과 같습니다-

ㅏ	¬ A
진실	그릇된
그릇된	진실

Implication / if-then ($\rightarrow$) − 의미 $A \rightarrow B$"만약 A라면 B"라는 명제입니다. A가 참이고 B가 거짓이면 거짓입니다. 나머지 경우는 사실입니다.

진리표는 다음과 같습니다-

ㅏ	비	A → B
진실	진실	진실
진실	그릇된	그릇된
그릇된	진실	진실
그릇된	그릇된	진실

If and only if ($ \Leftrightarrow $) − $A \Leftrightarrow B$ p와 q가 같을 때, 즉 둘 다 거짓이거나 둘 다 참일 때 참인 양 조건 논리 연결입니다.

진리표는 다음과 같습니다-

ㅏ	비	A ⇔ B
진실	진실	진실
진실	그릇된	그릇된
그릇된	진실	그릇된
그릇된	그릇된	진실

토톨 로지

Tautology는 명제 변수의 모든 값에 대해 항상 참인 공식입니다.

Example − 증명 $\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$ "진실"입니다.

모순

모순은 명제 변수의 모든 값에 대해 항상 거짓 인 공식입니다.

Example − 증명 $(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$ "거짓"이고 모순입니다.

우연성

우발성은 명제 변수의 모든 값에 대해 참 값과 거짓 값을 모두 갖는 공식입니다.

Example − 증명 $(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$ 긴장감입니다.

Example − 증명 $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ 동등하다

^{첫 번째} 방법으로 테스트 (Matching Truth Table)

ㅏ	비	A ∨ B	¬ (A ∨ B)	¬ A	¬ B	[(¬ A) ∧ (¬ B)]
진실	진실	진실	그릇된	그릇된	그릇된	그릇된
진실	그릇된	진실	그릇된	그릇된	진실	그릇된
그릇된	진실	진실	그릇된	진실	그릇된	그릇된
그릇된	그릇된	그릇된	진실	진실	진실	진실

여기에서 우리는 진실 가치를 볼 수 있습니다 $\lnot (A \lor B) and \lbrack (\lnot A) \land (\lnot B) \rbrack$ 동일하므로 문은 동일합니다.

두 ^번째 방법으로 테스트 (Bi-conditionality)

ㅏ	비	¬ (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
• 결론, q

앞에서 언급했듯이 다음과 같이 표시됩니다. $p \rightarrow q$.

Example of Conditional Statement−“숙제를하면 처벌을받지 않습니다.” 여기서 "당신은 숙제를한다"는 가설, p이고 "당신은 벌을받지 않을 것입니다"는 결론, q입니다.

Inverse− 조건 문의 반대는 가설과 결론의 부정입니다. 문이 "If p, then q"이면 역은 "If not p, then not q"가됩니다. 따라서$p \rightarrow q$ 이다 $ \lnot p \rightarrow \lnot q$.

Example −“숙제를하면 벌을받지 않는다”의 역은“숙제를하지 않으면 벌을 받는다”입니다.

Converse− 조건 문의 반대는 가설과 결론을 교환하여 계산됩니다. 문이 "If p, then q"이면 반대는 "If q, then p"가됩니다. 의 반대$p \rightarrow q$ 이다 $q \rightarrow p$.

Example − "숙제를하면 벌을받지 않는다"는 말은 "벌을받지 않으면 숙제를한다"입니다.

Contra-positive− 조건 문의 반대 양성은 가설과 역문의 결론을 교환하여 계산됩니다. 만약 문장이 "If p, then q"이면 반대 양성은 "If not q, then not p"가됩니다. 반대 양성$p \rightarrow q$ 이다 $\lnot q \rightarrow \lnot p$.

Example − "숙제를하면 벌을받지 않는다"의 반대 양성은 "벌을 받으면 숙제를하지 않았다"입니다.

이중성 원칙

이중성 원칙은 모든 실제 문에 대해 공용체를 교차로 (또는 그 반대로) 교환하고 Universal 집합을 Null 집합으로 (또는 그 반대로) 교환하여 얻은 이중 문도 참이라고 말합니다. 어떤 진술의 이중이 진술 자체라면,self-dual 성명서.

Example − 이중 $(A \cap B ) \cup C$ 이다 $(A \cup B) \cap C$

일반 형식

우리는 모든 명제를 두 가지 정규 형식으로 변환 할 수 있습니다.

• 결합 정상형
• 분리형 정규형

결합 정규형

OR로 연결된 변수 (변수의 부정 포함) 중 AND를 연산하여 얻은 복합 문은 결합 정규형입니다. 집합 연산의 경우 Union으로 연결된 변수 중 Intersection에서 얻은 복합 문입니다.

Examples

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

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

분리형 정규형

AND로 연결된 변수 (변수의 부정 포함) 중 OR을 연산하여 얻은 복합 문은 분리 정규형입니다. 집합 연산의 경우 교차점과 연결된 변수 중 Union을 통해 얻은 복합 문입니다.

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와 결혼 함"을 나타냅니다.

잘 형성된 공식

Well Formed Formula (wff)는 다음 중 하나를 보유하는 술어입니다.

• 모든 명제 상수와 명제 변수는 wff입니다.

• x가 변수이고 Y가 wff이면 $\forall x Y$ 과 $\exists x Y$ 또한 wff입니다

• 진실 값과 거짓 값은 wffs입니다.

• 각 원자 공식은 wff입니다.

• wff를 연결하는 모든 연결은 wff입니다.

수량 자

술어의 변수는 수량 자로 수량화됩니다. 술어 논리에는 Universal Quantifier와 Existential Quantifier의 두 가지 유형의 수량자가 있습니다.

범용 수량 자

범용 수량자는 해당 범위 내의 명령문이 특정 변수의 모든 값에 대해 참임을 나타냅니다. 기호로 표시됩니다.$\forall$.

$\forall x P(x)$ x의 모든 값에 대해 읽히고 P (x)는 참입니다.

Example − "인간은 필사자"는 명제 형식으로 변형 될 수 있습니다. $\forall x P(x)$ 여기서 P (x)는 x가 필사자이고 담론의 우주가 모든 사람임을 나타내는 술어입니다.

존재 한정자

Existential quantifier는 특정 변수의 일부 값에 대해 범위 내의 명령문이 참임을 나타냅니다. 기호로 표시됩니다.$\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}$$	모두 스 포 넨스	$$\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}$$

예

Let P- "그는 매우 열심히 공부합니다"

하자 Q − "그는 반에서 가장 좋은 소년"

따라서- "그는 매우 열심히 공부하고 그는 반에서 최고의 소년입니다"

단순화

만약 $P \land Q$ 전제이므로 단순화 규칙을 사용하여 P를 도출 할 수 있습니다.

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

예

"그는 매우 열심히 공부하고 그는 반에서 최고의 소년", $P \land Q$

그러므로- "그는 아주 열심히 공부한다"

모두 스 포 넨스

P와 $P \rightarrow Q$ 두 개의 전제이며 Modus Ponens를 사용하여 Q를 도출 할 수 있습니다.

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

예

"비밀번호가 있으면 페이스 북에 로그인 할 수 있습니다", $P \rightarrow Q$

"비밀번호가 있습니다", P

따라서- "페이스 북에 로그온 할 수 있습니다"

Modus Tollens

만약 $P \rightarrow Q$ 과 $\lnot Q$ 두 개의 전제입니다. Modus Tollens를 사용하여 $\lnot P$.

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

예

"비밀번호가 있으면 페이스 북에 로그인 할 수 있습니다", $P \rightarrow Q$

"페이스 북에 로그온 할 수 없습니다", $\lnot Q$

따라서- "비밀번호가 없습니다"

분리형 삼단 법

만약 $\lnot P$ 과 $P \lor Q$ 두 가지 전제입니다. Disjunctive Syllogism을 사용하여 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 년 영국 수학자 Arthur Cayley는 처음으로 그룹의 현대적인 정의를 내 렸습니다.

“모두 다른 기호의 집합으로, 순서에 관계없이 두 개의 제품 또는 그 중 하나의 제품이 집합에 속하도록 그룹이라고합니다. . 이러한 기호는 일반적으로 변환 가능하지 않지만 연관성이 있습니다.”

이 장에서 우리는 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$.

연관 법

이항 연산자 $\otimes$ 집합 A는 다음 속성을 보유 할 때 연관됩니다.

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

예

허락하다 $A = \lbrace 1, 2, 3, 4 \rbrace$

연산자 플러스 $( + )$ 세 가지 요소에 대해 $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$

연산자 플러스 $( + )$ 두 요소에 대해 교환이 가능합니다. $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 )$$

Identity 요소

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

드 모건의 법칙

De Morgan의 법칙은 보완 측면에서 두 세트 (또는 그 이상)의 결합과 교차 사이에 한 쌍의 변환을 제공합니다. 법은-

$$(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)$ 유지해야합니다.

예

더하기 연산이있는 양의 정수 세트 (0 제외)는 세미 그룹입니다. 예를 들면$ 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.

예

곱하기 연산이있는 양의 정수 세트 (0 제외)는 모노 이드입니다. $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$ 등등]

Identity 속성은 모든 요소에도 적용됩니다. $a \in S, (a \times e) = a$ [예 : $(2 \times 1) = 2, (3 \times 1) = 3$등등]. 여기서 정체성 요소는 1입니다.

그룹

그룹은 역 요소가있는 모노 이드입니다. 집합 S의 역 요소 (I로 표시)는 다음과 같은 요소입니다.$(a \omicron I) = (I \omicron a) = a$, 각 요소에 대해 $a \in S$. 따라서 그룹은 동시에 4 개의 속성을 보유합니다-i) 클로저, ii) 연관성, iii) 동일성 요소, iv) 역 요소. 그룹 G의 순서는 G의 요소 수이고 그룹의 요소 순서는 an이 해당 그룹 G의 동일 요소가되는 최소 양의 정수 n입니다.

예

세트 $N \times N$ 비 특이 행렬은 행렬 곱셈 연산에서 그룹을 형성합니다.

두 제품 $N \times N$ 비 특이 행렬도 $N \times N$ 클로저 속성을 보유하는 비 특이 행렬.

행렬 곱셈 자체는 연관성이 있습니다. 따라서 연관 속성이 유지됩니다.

세트 $N \times N$ 비 특이 행렬에는 단위 요소 속성을 포함하는 단위 행렬이 포함됩니다.

모든 행렬이 비 특수 행렬이기 때문에 모두 비 특수 행렬 인 역 원소를 가지고 있습니다. 따라서 역 속성도 유지됩니다.

아벨 리안 그룹

아벨 그룹 G는 요소 쌍이 $(a,b) \in G$항상 교환 법칙을 유지합니다. 따라서 그룹은 동시에 5 개의 속성을 보유합니다. i) 클로저, ii) 연관성, iii) 동일성 요소, iv) 역 요소, v) 교환.

예

더하기 연산이있는 양의 정수 세트 (0 포함)는 아벨 그룹입니다. $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$ 등등]

Identity 속성은 모든 요소에도 적용됩니다. $a \in S, (a \times e) = a$ [예 : $(2 \times 1) = 2, (3 \times 1) = 3$등등]. 여기서 identity 요소는 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 − A cyclic group항상 아벨 그룹이지만 모든 아벨 그룹이 순환 그룹 인 것은 아닙니다. 덧셈의 ​​유리수는 순환 적이 지 않지만 아벨입니다.

ㅏ subgroup H는 그룹 G의 하위 집합입니다 ( $H ≤ G$) 4 가지 속성을 동시에 만족한다면 − Closure, Associative, Identity element, 및 Inverse.

전체 그룹 G를 포함하지 않는 그룹 G의 하위 그룹 H를 적절한 하위 그룹이라고합니다 (로 표시 $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.

• '도달 가능성'작업에서 방향성 비순환 그래프의 꼭지점 집합은 포셋입니다.

Hasse 다이어그램

포셋의 Hasse 다이어그램은 정점이 해당 포셋의 요소이고 호가 포셋의 쌍 (x, y)을 덮는 방향성 그래프입니다. 포셋에 있다면$x < y$이면 점 x가 Hasse 다이어그램에서 점 y보다 낮게 나타납니다. 만약$x<y<z$ 포셋에서 화살표는 암시 적이므로 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$ 다음 Hasse 다이어그램으로 표시됩니다-

선형 정렬 된 세트

선형 순서 집합 또는 전체 순서 집합은 모든 요소 쌍이 비교할 수있는 부분 순서 집합입니다. 요소$a, b \in S$ 어느 쪽이든 비교 가능하다고 $a \le b$ 또는 $b \le a$보류. Trichotomy 법칙은이 총 주문 세트를 정의합니다. 완전히 정렬 된 집합은 속성을 갖는 분배 격자로 정의 할 수 있습니다.$\lbrace a \lor b, a \land b \rbrace = \lbrace a, b \rbrace$ 세트 S의 모든 a 및 b 값에 ​​대해

예

파워 셋 $\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 | 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$

일상 생활에서 일련의 사건에 대해 가능한 모든 결과의 수를 알아 내야하는 경우가 많습니다. 예를 들어, 남성 50 명과 여성 38 명 중에서 남성 6 명과 여성 4 명으로 구성된 심사위 원단을 몇 가지 방법으로 선택할 수 있습니까? 처음 5 개 문자는 대문자, 다음 4 개는 숫자, 마지막 문자는 다시 대문자가되도록 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까지 가야합니다. 그는 버스 3 개 또는 기차 2 개 노선을 통해 X에서 Y까지 갈 수 있습니다. 거기에서 그는 4 개의 버스 노선 또는 5 개의 기차 노선을 선택하여 Z에 도달 할 수 있습니다. X에서 Z까지가는 방법은 몇 개입니까?

Solution − X에서 Y까지, 그는 들어갈 수 있습니다 $3 + 2 = 5$방법 (Rule of Sum). 그 후, 그는 Y에서 Z로 갈 수 있습니다.$4 + 5 = 9$방법 (Rule of Sum). 따라서 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입니다.

순열 수

한 번에 'r'을 취하는 'n'개의 서로 다른 사물의 순열 수는 다음과 같이 표시됩니다. $n_{P_{r}}$

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

어디 $n! = 1.2.3. \dots (n - 1).n$

Proof − 'n'다른 요소가 있도록하십시오.

첫 번째 자리를 채우는 방법은 n 가지가 있습니다. 첫 번째 장소 (n-1)를 채운 후 요소 수가 남습니다. 따라서 2 위를 채우는 방법은 (n-1) 가지가 있습니다. 첫 번째와 두 번째 장소를 채운 후 (n-2) 개의 요소가 남습니다. 따라서 3 위를 채우는 방법은 (n-2) 가지가 있습니다. 이제 r 번째 자리를 채우는 방법의 수를 [n – (r–1)] = n–r + 1로 일반화 할 수 있습니다.

그래서 총 아니. 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!$

• x 개의 특정 사물이 항상 일정한 위치를 차지할 때 한 번에 r 개의 요소를 취하는 n 개의 서로 다른 요소의 순열 수 = $n-x_{p_{r-x}}$

• 지정된 r 개가 항상 함께 올 때 n 개의 서로 다른 요소의 순열 수는 다음과 같습니다. $r! (n−r+1)!$

• 지정된 r 개가 함께 오지 않을 때 n 개의 서로 다른 요소의 순열 수는 다음과 같습니다. $n!–[r! (n−r+1)!]$

• 시간에 x 요소를 취한 n 개의 서로 다른 요소의 순환 순열 수 = $^np_{x}/x$

• n 개의 서로 다른 것의 순환 순열 수 = $^np_{n}/n$

몇몇 문제들

Problem 1 − 6 개의 서로 다른 카드 묶음에서 얼마나 많은 방법으로 그것을 바꿀 수 있습니까?

Solution − 6 장의 카드 한 벌에서 한 번에 6 장의 카드를 가져 오므로 순열은 $^6P_{6} = 6! = 720$

Problem 2 − 'READER'라는 단어의 글자는 몇 가지 방법으로 배열 할 수 있습니까?

Solution − 'READER'라는 단어에는 6 글자 (2 E, 1 A, 1D 및 2R.)가 있습니다.

순열은 $= 6! /\: [(2!) (1!)(1!)(2!)] = 180.$

Problem 3 -자음이 짝수 위치 만 차지하도록 'ORANGE'라는 단어의 글자를 어떻게 배열 할 수 있습니까?

Solution− 'ORANGE'라는 단어에는 모음 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

6 명 중 3 명을 선택하는 방법은 다음과 같습니다. $^6C_{3}$ 5 명의 여성 중 2 명의 여성을 선택하는 방법은 $^5C_{2}$

따라서 총 방법 수는- $^6C_{3} \times ^5C_{2} = 20 \times 10 = 200$

Problem 3

총 9 명의 학생 중에서 3 명의 학생으로 구성된 3 개의 개별 그룹을 몇 가지 방법으로 선택할 수 있습니까?

Solution

그룹 번호를 1, 2, 3으로 지정하겠습니다.

^{첫 번째} 그룹에 3 명의 학생을 선택 하는 방법은 다음과 같습니다.$^9C_{3}$

1 ^차 그룹 선택 후 2 ^차 그룹 3 명 선택 방법 -$^6C_{3}$

3 3 명 학생들이 선택하는 방법의 수 ^번째의 1 선택한 후 그룹을 ^일 및 2 ^차 그룹 -$^3C_{3}$

따라서 총 방법 수는 $= ^9C_{3} \times ^6C_{3} \times ^3C_{3} = 84 \times 20 \times 1 = 1680$

파스칼의 정체성

제 17 파스칼 의해 도출 파스칼의 ID, ^제 세기, n 개의 원소 중에서 k 개의 요소를 선택하는 방법의 수 (N-1) 엘리먼트의 (K-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 } }$

Pigeonhole 원리

1834 년 독일의 수학자 Peter Gustav Lejeune Dirichlet은 그가 서랍 원리라고 부르는 원리를 발표했습니다. 자, 그것은 pigeonhole 원리로 알려져 있습니다.

Pigeonhole Principle총 비둘기 수보다 비둘기 구멍이 적고 각 비둘기를 비둘기 구멍에 넣으면 하나 이상의 비둘기가있는 비둘기 구멍이 하나 이상 있어야합니다. n> m 인 m 개의 비둘기 구멍에 n 개의 비둘기를 넣으면 둘 이상의 비둘기가있는 구멍이 있습니다.

예

• 10 명의 남자가 한 방에 있고 그들은 악수를하고있다. 각 사람이 적어도 한 번은 악수하고 한 사람의 손을 한 번 이상 흔드는 사람이 없다면 두 사람이 같은 수의 악수에 참여한 것입니다.

• 이름이 같은 알파벳으로 시작하는 30 인 클래스에는 최소 2 명이 있어야합니다.

포함-제외 원칙

그만큼 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이벤트 발생 가능성을 찾는 것으로 개념화 할 수 있습니다. 수학적으로는 무작위 과정과 그 결과에 대한 연구입니다. 확률 법칙은 유전학, 일기 예보, 여론 조사, 주식 시장 등과 같은 다양한 분야에서 광범위하게 적용됩니다.

기본 개념

확률 이론은 우연에 관한 수학적 문제를 다루는 두 명의 프랑스 수학자 Blaise Pascal과 Pierre de Fermat에 의해 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

따라서 헤드를 얻을 확률은 $(H)$ 맨 위에는 1/2이고 꼬리를 얻을 확률 $(T)$ 위에는 1/2

주사위 던지기

주사위를 던지면 6 개의 가능한 결과가 맨 위에있을 수 있습니다. $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가 상호 배타적 인 경우 사건 A 이후 사건 B의 조건부 확률은 다음과 같은 사건 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

6 개의 양호한 노트북과 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)$ B가 참일 때 A의 확률입니다. $P(B | A)$ A가 참일 때 B의 확률이며 Bayes의 정리는 다음과 같습니다.

$$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를 빨간 펜이 그려지는 이벤트라고합시다.

첫 번째 펜 스탠드의 5 개 펜 중 빨간 펜이 선택 될 확률,

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

두 번째 펜 스탠드의 5 개 펜 중 빨간 펜이 선택 될 확률,

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

세 번째 펜 스탠드의 5 개 펜 중 빨간색 펜이 선택 될 확률,

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

Bayes의 정리에 따르면,

$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$ n = 1, 2, ...에 대해 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$ 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)$ 모든 양의 정수에 대해 true입니다. $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$) 1 차 다항식으로 숫자 시퀀스에.

다음은 선형 반복 방정식의 몇 가지 예입니다.

재발 관계	초기 값	솔루션
F n = F n-1 + F n-2	a 1 = a 2 = 1	피보나치 수
F n = F n-1 + F n-2	a 1 = 1, a 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	펠 번호

선형 반복 관계를 해결하는 방법

2 차 선형 반복 관계가 다음과 같다고 가정합니다. $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)$ 다음과 같습니다-