[이산수학] 이산수학 기초

문래동까마귀 2022. 1. 8. 20:03

이산수학 강좌 (Discrete Mathematics Tutorial For Beginners)

www.youtube.com

1강 이산수학 개요

- 불연속적인 숫자를 다루는 수학

- 컴퓨터를 위한 수학, 참과 거짓으로 살펴보는 컴퓨터 수학, 전산, 정보 수학, 1학년이나 처음 컴퓨터를 배우는 입장에서 배우게됨, 자료구조 또는 알고리즘의 베이스, 논리적 사고, 컴퓨팅 사고력 향상

2강 명제와 연산자
- 명제 : 참/ 거짓으로 구분할 수 있는 문장

ex) "저 안경쓴 사람은 남자이다" -> 참이라는 진리값을 가지는 명제

-> 여러 개의 명제를 조합할 수 있다.

- 명제 예시

1) 원빈은 잘생겼다 -> 개인의 주관이 개입가능, 명제X

2) 컴퓨터는 재미 없다 -> 개인의 주관이 개입가능, 명제X

3) 11은 소수이다 -> 명제(참)

4) 모기는 동물이다. -> 명제(참)

- 연산자로 명제 다루기

-> 연산자 : 명제를 연산하기 위한 도구

Not	And (논리곱)	Or (논리합)	Exclusive or (배타적 논리합)	Implication (함축, 조건명제)	Biconditional (쌍방 조건명제)
~, ￢	^	v	⊕	→	↔
참을 거짓으로, 거짓을 참으로 반환	둘 다 참일때만 결과도 참	둘 중 하나라도 참이라면 결과는 참	단 하나만 참일때 결과값 참 (둘 다 참이거나 거짓이면 결과는 거짓)	조건과 결과에 따른 흐름 p -> q (T, T) = T (T, F) = F (F, T) = T (F, F) = T EX) 1+1=2일때, 2+2=4이다. (참) 1+1=2일때, 2+3=4이다. (거짓)	두 값이 서로 일치할때만 참 p <-> q (T, T) = T (T, F) = F (F, T) = F (F, F) = T

: 여러 개의 명제를 합치면 합성명제/ 원인 -> 결과가 되는 명제는 조건명제

3강 역, 이, 대우(주로 조건명제에서 사용)

- 진리표 : 각 명제 사이의 관계식의 진리값을 보여주는 표, 아무리 복잡한 합성 명제라도 진리표로 해결할 수 있다.

Q. 명제 "30이 10보다 크다면 30은 50보다 작다."에 대한 진리값과 역, 이, 대우 각각의 진리값 구하기

: 본명제와 대우값은 반드시 같은 진리값을 반환한다.

4강 동치 관계

- 동치 : '논리적으로 일치한다'는 의미

-> 같은 의미를 가진 더 쉬운 명제를 발견하는데 사용

-> 동치법칙에는 다양한 종류가 있다.

- 동치법칙을 이용한 증명

: 복잡한 합성명제도 간단한 명제로 바꿀 수 있다.

-> 중요 : 드모르간의 법칙/ 흡수법칙/ 부정법칙/ 함축법칙

예시 문제) 동치법칙을 잘 알고있다면 진리표를 작성하지 않고 빠르게 간소화가 가능하다

1) (p -> q) ^ (p->~q)
= (~p v q) ^ (~p v ~q) : 함축법칙
= ~p v (q ^ ~q) : 분배법칙
= ~p v F : 부정법칙
= ~p : 항등법칙

2) ~(p v ~q) v (~p ^ ~q)
= (~p ^ q) v (~p ^ ~q) : 드모르간의 법칙
= ~p ^ (q v ~q) : 분배법칙
= ~p ^ T : 부정법칙
= ~p : 항등법칙