이산수학이란?
- 문제를 해결하는 효과적인 모델링
주어진 문제 -> 아이디어 스케치 -> 추상적 모델 구성 -> 수학적 모델링
-> 문제풀이 및 적용 -> 해결
이산수학을 이용하여 해결할 수 있는 문제의 종류
- 그래프를 통한 네트워크 분석
- 교통망에서 두 도시를 연결하는 최단거리
- 트리 개념을 적용한 실세계 문제풀이
- 논리적인 사고를 통한 상황의 논리적 분석
- 불대수, 스위치 이론을 통한 하드웨어의 이해
2. 논리와 명제
-
논리
인간의 사고가 논리적인지를 판단하는 것은 사고하는 사람이 주어진 문제를 객관적으로 명확한지의 여부와 사고의 법칙을 체계적으로 추구하여 분석하는지의 여부로 결정됨 -
논리의 목적
-> 특정한 논리를 통한 입증이 옳은가를 측정하는데 필요한 법칙을 제공한다는 것
-> 컴퓨터 관련 학문이나 공학 등 여러 분야에 폭넓게 응용됨
명제논리 (Propositional Logic)
주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리하여 참/거짓 판별하는 법칙
술어논리(Predicate Logic)
주어와 술어를 구분하여 참/거짓 판단
-> 명제는 통상 영문 소문자 p, q, r등으로 표시함
-> 명제가 참 또는 거짓의 값을 가질 때 그 값은 명제의 진리값(truth value)이라고 한다.
-> 명제는 T와 F 2가지의 진리값만을 가지므로 이진논리라고 함
예제 2-1) 명제를 찾아보고 진리값을 판단해보자
(1) 바나나는 맛있다. -> 명제 X
(2) 3x+5y = 7 -> 참,거짓 구분 X (명제X)
(3) 28은 4의 배수 -> 명제 O, 참 O
(4) 지금 어디로 가는 중입니까? -> 참, 거짓 구분 X (명제X)
단순 명제 -> 하나의 문장이나 식으로 구성되어 있는 명제
(장미꽃은 빨갛다, 유채꽃은 노랗다)
합성 명제 -> 여러 개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제
(장미꽃은 빨갛고 유채꽃은 노랗다)
논리 연산자
- 단순 명제들을 연결시켜주는 역할. ∪(or), ∩(and), ~(not) 같은 연산자
합성 명제의 진리값
- 그 명제를 구성하는 단순명제의 진리값과 논리 연산자의 특성에 따라 값이 정해짐
- 합성 명제의 진리값은 복잡한 경우가 많음
- 진리표(truth table)을 사용하여 단계적으로 연산함으로써 원하는 합성명제의 진리값을 보다 쉽고 편리하게 구할 수 있음
부정 ~ NOT
논리곱 ∩ AND
논리합 ∪ OR
배타적 논리합 xor Exclusve or -> 하나만 참일 때 참
조건 -> if...then
쌍방조건 ↔ if and only if (iif)
(1) 부정
~p로 쓴다.
P의 진리값이 참 -> ~p 거짓
P 거짓 -> ~p 참
(2) 논리곱 (AND)
- 두 명제의 논리곱 p∩q는 두 명제가 모두 참인 경우에만 참이라고 함
- 그렇지 않으면 거짓의 진리값을 가짐
ex) 서울은 대한민국의 수도이고(p), 런던은 영국의 수도이다(q). (참)
(3) 논리합 (OR)
'P or q' 또는 'p 또는 q'
둘 다 거짓일때만 거짓
(4) 배타적 논리합 (Exclusive OR)
다를때만 참
TF -> T
FT -> T
TT -> F
FF -> F
(5) 조건 (Implication)
- 함축이라고 함
p(충분조건) -> q(필요조건)
p이면 q이다
if p, then q
p는 q의 충분조건, q는 p의 필요조건
p는 q를 함축한다. - 가정이 거짓이면 q와 관계없이 무조건 참. 가정이 참일 땐 결과도 참이어야 참.
(6) 쌍방조건
p ↔ q
요약
-> 명제란 어떤 사고를 나타내는 문장 중에서 참이나 거짓을 객관적이고 명확히 구분할 수 있는 문장이나 수학적 식을 말한다.
