1. 이산수학 기초

 

1. 이산수학 개요

참과 거짓으로 살펴보는 컴퓨터 수학

 

이산수학이란?

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

• 이산수학에서 다루는 자료구조, 알고리즘 등의 베이스가 전체적인 컴퓨팅 사고력을 길러줄 것임.

• 추후에 배우는 수학적 귀납법 등의 다양한 기초 개념이 알고리즘에 반복적으로 출현하기 때문에 컴퓨터 과학의 베이스 학문

 

---

2. 명제와 연산자

명제

진실(T) 혹은 거짓(F)으로 진리를 명확히 구분할 수 있는 문장

 

연산자

면제를 연산하기 위한 도구

<6가지의 연산자>

1. Not (￢) : 부정

   연산	결과
   ￢T	F
   ￢F	T

2. And (^) : 논리곱

   연산	결과
   T ^ T	T
   T ^ F or F ^ T	F
   F ^ F	F

3. Or (∨) : 논리합

   연산	결과
   T ∨ T	T
   T ∨ F or F ∨ T	T
   F ∨ F	F

4. Exclusive or (⊕) : 배타적 논리합:
   1개만 참
   일 경우 결과가
   참
   이다

   연산	결과
   T ⊕ T	F
   T ⊕ F or F ⊕ T	T
   F ⊕ F	F

5. Implication (→) : 함축 / 조건 명제p ⇒ q : p일 때, q이다.

   연산	결과
   T → T	T
   T → F	F
   F → T	T
   F → F	T

6. p의 조건에 일 때, q의 결과가 나온다.

6. Biconditional (⇔) : 쌍방 조건 명제
   두 값이 서로 일치할 때
   만
   T
   값을 반환

   연산	결과
   T → T	T
   T → F	F
   F → T	F
   F → F	T

---

3. 역, 이, 대우

: 하나의 명레를 변형해 표현하는 것

: 대우를 활용해 증명하기 어려운 명제를 증명할 수 있다.

: 명제와 대우는 항상 진리치가 같다.

명제	P → Q	(IF p: F, Q:T) 참
역	Q → P	거짓
이	￢P → ￢Q	거짓
대우	￢Q → ￢P	참

 

---

4. 동치

: ‘논리적으로 일치한다’ 의 의미를 가짐.

 

Q. 동치법칙을 이용하여 (p → q) ^ (p → ￢q)를 간소화하라.

(￢p ∨ q) ^ (￢p ∨￢q) : 함축 법칙

￢p ∨ (q ^ ￢q) : 분배 법칙

￢p ∨ F : 부정 법칙

￢p : 항등 법칙

 

 

---

 

참고

 

https://ingyeoking13.tistory.com/80

Foundation: propositional equivalence

https://www.youtube.com/playlist?list=PLD8rdlfZeJk7ijUM8ckwLLNyDKRD2aQa2 

이산수학-1