이산수학개요
이산수학 강좌 1강 - 이산수학 개요 (Discrete Mathematics Tutorial For Beginners #1)
- 이산수학 (Discrete Mathematics)
- 불연속적 수학
- 참과 거짓으로 살펴보는 컴퓨터 수학
- 보편적인 컴퓨터 수학
- 왜 필요한가
- 이산수학이란 불연속적인 숫자를 다루는 수학이기 때문에
컴퓨터를 구성하는 0과 1의 불연속적인 데이터흐름을 다루기에 적합한 수학적 사고를 기를 수 있음
- 이산수학에서 다루는 수학적 귀납법 등의 기초개념이 알고리즘에 반복적으로 출현
명제와 연산자
이산수학 강좌 2강 - 명제와 연산자 (Discrete Mathematics Tutorial For Beginners #2)
- 명제
- 참 혹은 거짓으로 진리를 명확하게 구분할 수 있는 문장
- ex)
- 아이유는 이쁘다 → 명제X
- 1은 짝수이다 → 명제O (거짓)
- 고양이는 동물이다 → 명제O(참)
- 연산자
- 명제를 연산하기 위한 도구
- 기본 연산자의 종류
- 부정, Not(¬ )
- 명제의 진리값을 뒤집어줌
- p⇒ 참
- ¬p ⇒ 거짓
- 논리곱, And( ^ )
- 그리고
- p ^ q 일때 p,q모두 참일 경우에만 p ^ q⇒ 참 이다 나머지는 거짓
- 논리합, Or( v )
- 또는
- p v q 일때 p,q모두 거짓일 경우에만 p v q⇒ 거짓 이다 나머지는 참
- 배타적논리합, Exclusive or( ⊕ )
- 함축, 조건명제, Implication (→)
- p → q : p일때 q이다
- 조건 → 결과 (ex) 비가 올때 우산을 쓴다)
- 참 → 거짓 ⇒ 거짓 나머지 경우는 참
- 쌍방 조건명제, Biconditional (↔)
- p, q가 같으면 참
- p, q가 다르면 거짓
- ⊕와 반대
- 잘 안쓰임
진리표와 역, 이, 대우
이산수학 강좌 3강 - 역, 이, 대우 (Discrete Mathematics Tutorial For Beginners #3)
-
진리표
- 각 명제 사이의 관계식의 진리값을 보여주는 표
- ex)
-
역, 이, 대우
- 조건명제에서 사용함
- 하나의 명제를 변형해 표현함
- 본 명제
p → q
- 역
q → p
- 이
¬p → ¬q
- 대우
¬q → ¬p
대우가 참이면 본 명제도 참 ( 대우와 본 명제는 반드시 같은 명제를 가짐)
- 왜 쓰는가
- 증명을 돕기 위함
- 증명하기 어려운 본 명제를 대우를 이용해 증명 가능
- ex)
- 명제 "30이 10보다 크다면, 30은 50보다 작다"
- p: 30>10
- q: 30<50
- p → q : 30이 10보다 크다면, 30은 50보다 작다 ⇒ 참 → 참 ⇒ 참
- 역:
q → p : 30이 50보다 작다면, 30은 10보다 크다 ⇒ 참
- 이:
¬p → ¬q : 30이 10보다 작거나 같다면, 30은 50보다 크거나 같다 ⇒ 참
- 대우:
¬q → ¬p : 30이 50보다 크거나 같으면, 30은 10보다 작거나 같다 ⇒ 참
- 역, 이는 본 명제와 다른 명제가 나올 수 있지만 대우는 반드시 같은 명제를 가짐
동치
이산수학 강좌 4강 - 동치 (Discrete Mathematics Tutorial For Beginners #4)
- 동치
- 논리적으로 일치한다
- 같은 의미를 가진 더 쉬운 명제를 발견하는데 사용
- ex) 2+2+2+2+2+2+2+2+2+2 와 2*10 은 동치이다
- 동치법칙
+ 함축 법칙: p → q === ~p v q
ex)
- (p→q)^(p→~q)를 동치법칙을 이용한 간소화하라
(p→q)^(p→~q)
⇒ (~p v q)^(~p v ~q) : 함축법칙
⇒ ~p v (q ^ ~q) : 분배법칙
⇒ ~p v F : 부정법칙
⇒ ~p : 항등법칙