대학교에 와서 여러가지 공부를 하고 있는 Net_SU입니다.
대학교에 와서 수학이란 과목을 배우게 되었는데 그것도 이산수학!
이산수학이란?
이산수학(Discrete mathematics, 離散數學)은 이산적인 수학 구조에 대해 연구하는 학문으로, 연속되지 않는 공간을 다룬다. 유한수학이라고도 하며, 전산학적인 측면을 강조할 때는 전산수학이라고도 한다.
주로 정수, 유한 그래프, 형식 언어 같이 가산집합에 속하는 개념을 다룬다.
이산수학은 전산학의 기초가 되는데, 이것은 컴퓨터에서 다루는 자료형이 이산적이라는 것에서 기인한다. 이산수학에서 나온 개념과 기호는 컴퓨터 알고리즘과 프로그래밍 언어의 문제나 대상들을 연구하는 데 유용하다.
http://ko.wikipedia.org/wiki/%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99
결국 이공계열쪽에서 공부하는 분들이라면 한번쯤은 공부할 과목? 인것 같습니다.
학과에서 수업중인 '수학으로 이해하는 디지털 논리' 라는 책을 날짜별로 정리 해가도록 하겠습니다.
수학으로 이해하는 디지털 논리.
이산수학
박주미 지음, 한빛아카데미
01. 명제와 논리
02. 증명
03. 집합
04. 수의 표현
05. 행렬
06. 관계
07. 함수
08. 그래프
09. 트리
10. 순열, 조합, 확률
11. 부울대수와 논리게이트
12. 알고리즘
---------------------------------------------------------------------------------------<주차>
1)명제 8/25
2)논리적 동치
3)변수를 포함한 명제와 한정자
4)논리
1)명제
-명제의 정의
1-1 명제(ProPosition)
: 참(T)이나 거짓(F)으로 구분할 수 있는 문장이나 수식 ⇒ 영어 소문자 p,q,r,...로 표현
ex) 서울은 대한민국의 수도이다. ∴ 명확하게 참이라 판별할 수 있으므로 명제이다.
1-2 진릿값(Truth Value)
: 참(T)이나 거짓(F)을 가리키는 값 ⇒ T, F 또는 0, 1
ex) 미국의 수도는 뉴욕이다. ∴ 거짓(F):미국의 수도는 워싱턴D.C
-논리 연산자(명제의 결합)
1-3 부정(Negation) NOT
: 문장 p가 명제일 때 “p가 아니다”도 명제 : ￢p 또는 ∼p
ex) 부정 연산 NOT을 이용해 “4는 양수다”라는 명제 p의 부정을 구하고 진릿값을 구하라.
∴ ￢p : 4는 양수가 아니다. “4는 양수가 아니다”라는 말은 4가 0이거나 음수임을 의미함.
￢p의 진릿값은 거짓(F)이 된다.
p | ￢p |
T | F |
F | T |
1-4 논리곱(Conjunction) AND
: 문장 p,q가 명제일 때 p,q의 진릿값이 모두 참(T)일 때만 참(T)이 되고,
그렇지 않을 때는 거짓(F)이 되는 명제 ⇒ p∧q
ex) 두 명제의 논리곱을 작성하고, 진릿값을 구하라.
p : 4는 양수다. q : 2+6=0
∴ p∧q : 4는 양수고, 2+6=0이고, 진릿값은 거짓(F)이다.
p | q | p∧q |
T | T | T |
T | F | F |
F | T | F |
F | F | F |
1-5 논리합(Disjunction) OR
: 문장 p,q가 명제 일 때 p,q의 진릿값이 모두 거짓(F)일 때만 거짓(F)이 되고,
그렇지 않으면 참(T)이 되는 명제 ⇒ p∨q
ex) 두 명제의 논리합을 작성하고, 진릿값을 구하라.
p : 4는 양수다. q : 2+6=0
∴ 논리합 p∨q는 “4는 양수거나 2+6=0이다”, 진릿값은 참(T)이다.
p | q | p∨q |
T | T | T |
T | F | T |
F | T | T |
F | F | F |
1-6 배타적 논리합(Exclusive OR) XOR
: 문장 p,q가 명제일 때 p,q의 두 진릿값 중 하나만 참(T)일 때 참(T)이 되고,
그렇지 않으면 거짓(F)이 되는 명제 ⇒ p⊕q
p | q | p⊕q |
T | T | F |
T | F | T |
F | T | T |
F | F | F |
-합성명제(명제의 합성)
1-7 합성명제(Compound Proposition)
: 하나 이상의 명제들이 결합되어 만들어진 명제로, AND, OR, NOT 등의
논리 연산자(Logical Operators)를 이용해 명제를 결합.
논리 연산자의 우선순위 | |
우선순위 | 논리 연산자 |
1 | ￢ |
2 | ∨, ∧ |
3 | →, ↔ |
1-8 항진명제(Tautology) T
|
항진명제 | ||
|
p |
￢p |
p∨￢p |
|
T |
F |
T |
|
F |
T |
T |
: 합성명제를 구성하는 단일 명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 참(T)인 명제
1-9 모순명제(Contradiction) F
|
모순명제 | ||
|
p |
￢p |
p∧￢p |
|
T |
F |
F |
|
F |
T |
F |
: 합성명제를 구성하는 단일 명제의 진릿값에 상관없이 합성명제의 진릿값이 항상 거짓(F)인 명제
1-10 사건명제(Contingency)
|
사건명제 | |
|
p |
￢p |
|
T |
F |
|
F |
T |
: 항진명제도, 모순명제도 아닌 명제
-함축(조건명제)
1-11 함축(Implication) / 조건명제(Conditional Proposition) p→q
: 문장 p,q가 명제일 때, 명제 p가 조건 또는 원인으로 제시되고,
명제 q가 결론 또는 결과로 제시되는 명제
·p implies q : p는 q를 함축한다.
·if p then q 또는 p only if q : p면 q다.
|
함축 p→q의 진리표 | ||
|
p |
q |
p→q |
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
T |
|
F |
F |
T |
Cf) 함축 p→q는 조건이 되는 명제 p가 참(T)이고 결론이 되는 명제 q가 거짓(F)인 경우에만 거짓(F)이 되고,
그 외의 경우에는 참(T)이 된다. 특히 명제 p가 참(T)일 때 반드시 명제 q가 참(T)인 경우 p⇒q로 표기하고
“p는 q의 충분조건이다(p implies q)”혹은 “q는 p의 필요조건이다(q is necessary for p)”라고 한다.