이산수학 렉쳐노트 정리

이산수학 렉쳐노트 정리

수업 교안을 간단하게 개념만 적는거라 내용이 많이 부실합니다. 자세한 내용은 나중에 추가하도록 하겠습니다.

1주차: 명제와 논리

명제와 논리연산자

명제

명제(Proposition): 참이나 거짓으로 구분할 수 있는 문장이나 수식
진리값(Truth Value): 참이나 거짓을 가리키는 값(i.e., T or F, 0 or 1)
- In R, Zero is considered FALSE and non-zero numbers are taken as TRUE

논리 연산자

부정(Negation): Not
- 명제 p가 명제이면, “p가 아니다” 또한 마찬가지로 명제이다
- 즉, 명제의 부정또한 명제이다.
- $\neg$ p
논리곱(Conjunction): And
- 문장 p,q가 명제일때, p,q의 진리값이 모두 참일때’만’ 참이되고, 그렇지 않을때는 거짓이 되는 명제
- $p \land q$
논리합(Disjunction): OR
- 문장 p,q가 명제일때, p,q의 진릿값이 모두 거짓일때’만’ 거짓이 되고, 그렇지 않으면 참이되는 명제
- $p \lor q$
배타적 논리합(Exclusive OR): XOR
- 문장 p,q가 명제일때, p,q의 진릿값 중 하나’만’ 참일때 참이되고, 그렇지 않으면 거짓이 되는 명제
- $p \oplus q$

합성명제(Compound Proposition)

우선순위
1. $\neg$
2. $\land$, $\lor$
3. $\oplus$
항진명제(Tautology): 합성명제를 구성하는 명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 참인 명제 ($p\lor \neg p$)
모순명제(Contradiction): 합성명제를 구성하는 명제들의 진릿값에 상관없이 합성명제의 진릿값이 항상 거짓인 명제 ($p\land \neg p$)
사건명제(Contingency): 항진명제도, 모순명제도 아닌 명제

Below is R example.

p = c(TRUE, TRUE, FALSE, FALSE)
q = c(TRUE, FALSE, TRUE, FALSE)
isTRUE(FALSE)
## [1] FALSE

!p # NOT
## [1] FALSE FALSE  TRUE  TRUE

# Element-wise logical AND (&) 
p&q 
## [1]  TRUE FALSE FALSE FALSE
p&!q 
## [1] FALSE  TRUE FALSE FALSE

# Element-wise logical OR (|)
p|q
## [1]  TRUE  TRUE  TRUE FALSE

# Element-wise exclusive OR
xor(p,q)
## [1] FALSE  TRUE  TRUE FALSE

# Logical AND
# Examines only the first element of the operands resulting into a single length logical vector
!p&&!q 
## [1] FALSE
q&&q 
## [1] TRUE
p&&p
## [1] TRUE

# Logical OR
# Examines only the first element of the operands resulting into a single length logical vector
p||q
## [1] TRUE
!p||!q
## [1] FALSE

xor(!(p&q),(!p|q))
## [1]  TRUE  TRUE FALSE FALSE

합성/함축조건/쌍방조건 명제

함축(Implication)에 관한 진리표

p	q	p $\rightarrow$ q
T	T	T
T	F	F
F	T	T
F	F	T

Ex) 부산이 대한민국의 수도면, 10은 양수다의 진릿값은 참이다. 왜냐하면 결과 명제가 원인 명제와 상관없이 항상 참이기 때문이다.

쌍방조건명제(Biconditional)에 관한 진리표

p	q	p $\leftrightarrow$ q
T	T	T
T	F	F
F	T	F
F	F	T

역/이/대우와 논리적 동치

p $\rightarrow$ q
- 역(converse): q $\rightarrow$ p
- 이(inverse) : $\neg$p $\rightarrow$ $\neg$q
- 대우(contraposition): $\neg$q $\rightarrow$ $\neg$p

논리적 동치

합성명제 p와 q의 진릿값이 같은 경우
$p \equiv q$
$p \rightarrow q \equiv \neg p \lor q$

명제함수 (Propositional Function) P(x) - 명제함수 $P(x) = x^2 - 3x =0$ 일때, P(1)은 거짓이고 P(3)은 참이다.

한정기호 - 전체한정자(Universal Quantifier): $\forall$ - 존재한정자(Existential Quantifier): $\exists$

논리적 추론법칙

예제: 다음과 같이 전제로 주어진 명제가 항상 참이라고 할때, 열쇠가 어디에 있는지 찾아라.

열쇠가 서랍에 있었다면, 출근할 때 열쇠를 보았다.
내가 아침을 먹었다면, 열쇠는 서랍에 있다.
나는 샤워를 했거나 아침을 먹었다.
내가 샤워를 했다면, 열쇠는 가방 속에 있다.
내가 출근할 때, 나는 열쇠를 보지 못했다.

$\therefore$ 열쇠는 가방 속에 있다.

2주차: 증명의 정의와 종류

공리
- 별도의 증명 없이 참으로 이용되는 명제
정의
- 논의의 대상을 보편화하기 위해 사용하는 용어 또는 기호의 의미를 확실하게 규정한 문장이나 식
정리
- 공리와 정의를 통해 참으로 확인된 명제
증명
- 하나의 명제가 참임을 확인하는 과정
- 증명법: 직접증명법/간접증명법/대우증명법/모순증명법/반례증명법/존재증명법/수학적 귀납법

3주차: 집합의 개념과 종류 & 연산과 법칙

직합의 표기형식
- 원소 나열법: $S={1,2,3,4,5}$
- 조건제시법: $S = \{ s|0\le s\le 5, s\in\mathbb{N} \}$
$x \in X$, $x \notin X$
기수 (Cardinality): $|A|$
- 집합 A 가 포함하는 원소의 수
유한집합 / 무한집합
합집합 / 교집합 / 서로소(Disjoint) / 차집합(Difference) / 대칭차집합 (Symmetric Difference) / 여집합 (Complement) / 곱집합 (Cartesian Product) / 멱집합 (Power Set) /
집합의 대수법칙
- 항등법칙, 지배법칙, 멱등(Idempotent)법칙, 교환법칙, 결합법칙, 분배법칙, 보법칙, 드모르간의 법칙, 흡수법칙

4주차: 수의 표현 및 연산

$\mathbb{N},\mathbb{Q},\mathbb{R},\mathbb{C}$
수체계: 10진수, 2진수, 8진수, 16진수 그리고 서로간의 변환

#install.packages('DescTools')
library(DescTools)
DecToBin(c(21,12))
## [1] "10101" "1100"
BinToDec(c(10101,1100))
## [1] 21 12
DecToHex(c(21,12))
## [1] "15" "0c"
HexToDec(c(15,'0c'))
## [1] 21 12
DecToOct(c(21,12))
## [1] 25 14
OctToDec(c(25,14))
## [1] 21 12

temp = c('11100101')
DecToOct(BinToDec(temp))

## [1] 345

5주차 : 보수와 행렬

보수: 보충해 주는 수
- 1의 보수: 어떤 수 n 과의 합이 1이 되는 수
- 2의 보수: 어떤 수 n 과의 합이 2가 되는 수
부호화 - 절대치 표현: 부호와 데이터의 절댓값을 그대로 표현하는 방법
부호화 - 1의 보수표현
- 음수의 표현에만 적용된다.
- 음수에 대한 부호화: 절대치 표현에서 부호 비트는 그대로 사용
- 음수에 대한 부호화: 절대치 표현에서 절대치 비트에 대해 0은 1로, 1은 0으로 바꿔 표현
부호화 - 2의 보수 표현
- 음수 표현에만 적용된다.
- 음수에 대한 부호화: 절대치 표현에서 부호 비트는 그대로 사용
- 음수에 대한 부호화: 절대치 표현에서 절대치 비트에 대한 1의 보수에 1을 더함

Ex1) 10진수 +53과 -53을 8비트의 부호화-절대치 표현으로 나타내는 경우: 53을 2진수로 변화하면 1101012이다. 8비트의 가장 왼쪽에 있는 비트는 최상위 비트므로 그 자리에 부호를 의미하는 0(양수) 또는 1(음수)가 입려된다. 나머지 자리에는 절댓값이 오른쪽부터 채워진다.

-$+53_{10} = 00110101$ -$-53_{10} = 10110101$

Ex2) 10진수 +53과 -53을 8비트 1의 보수 표현으로 나타내라.: 보수는 음수 표현에만 사용하므로 +53에대한 1의 보수표현은 부호화-절대치표현과 같다.

$-53_{10}$ 은 음수이므로 1의 보수표현으로 바꿀 수 있다. $-53_{10}$의 부호화-절대치 표현은 -$-53_{10} = 10110101$ 이므로, 부호 비트를 제외한 절대치 표현에 대해 0은 1로, 1은 0으로 바꾸면 된다.

$\therefore -53_{10}=11001010$

Ex3) 10진수 +53과 -53을 8비트 2의 보수 표현으로 나타내라.: 보수는 음수 표현에만 사용하므로 +53에대한 2의 보수표현은 부호화-절대치표현과 같다.

$-53_{10}$ 은 음수이므로 2의 보수표현으로 바꿀 수 있다. $-53_{10}$의 부호화-절대치 표현은 -$-53_{10} = 10110101$ 이고, 1의 보수표현은 11001010이므로 여기서 1을 더하면 11001011이다.

보수 표현을 사용하는 이유 - 부호화-절대치 표현의 한계 - 연산 결과가 정확하지 않다. - 0의 표현이 두 가지 - 양수0: 0000 / 음수0: 1000 - 1의 보수 표현의 한계 - 계산 결과는 정확하나, 여전히 0의 표현이 두가지 - 양수0: 0000 / 음수0: 1111 - 1의 보수 10진수 변환 (2가지) 1. $-(2^{n-1}-1)$ + 절대치 비트의 10진수 표현 2. 주어진 1의 보수를 다시 한번 1의 보수로 변환 후, 그에 대해 10진수 표현

예시) 8비트 표현을 사용하는 컴퓨터에서 1의 보수 11001011을 10진수로 변환하라.

11001011에서 최상위 비트 1은 부호 비트고 나머지는 절대치 비트다.

$11001011 = -(2^{8-1}-1) + 12^6 + 02^5 + 02^4 + 12^3 + 02^2 + 12^1 + 12^0 $

$-127+(64+0+0+8+0+2+1)=-127+75=-52$

보수연산시 주의사항 - 초과가 발생하는경우 - 1의보수: 다시 한번더 연산 - 2의보수: 무시

행렬 - 부울행렬(Bollean Matrix, Zero-One Matrix) - 행렬식

A = matrix(c(3,2,1,-1),2,2)
B = rbind(c(3,-1,-2),c(-4,2,1),c(1,4,-3))
det(A)

## [1] -5

det(B)

## [1] 17

소행렬 (Minor MAtrix): $M_{rs}$
- n차 정사각 행렬에서 r번째 행과 s번째 열을 제거해서 얻은 $(n-1)\times(n-1)$ 행렬
여인수 (Cofactor) $A_{ij}$
- n차 정사각행렬 $A=[a_{ij}]$ 에서 원소 $a_{ij}$ 에 관련된 수 와 그 수에 대한 행렬 $A_{ij}=(-1)^{i+j} det(M_{ij})$

6주차: 행렬

역행렬

C = rbind(c(1,2,3),c(2,-1,1),c(3,0,-1))
C

##      [,1] [,2] [,3]
## [1,]    1    2    3
## [2,]    2   -1    1
## [3,]    3    0   -1

solve(C)

##      [,1] [,2]  [,3]
## [1,] 0.05  0.1  0.25
## [2,] 0.25 -0.5  0.25
## [3,] 0.15  0.3 -0.25

이산수학 전반부 정리

Roh

2020/10/17