|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
불 논리라는 것은 논리적 산법의 완전한 체계이다.불 논리라는 이름은 19세기 중순에 논리의 대수계를 처음으로 정의한 조지 불에서 따온 것이다. 불 논리는 전자 공학, 컴퓨터 하드웨어 및 소프트웨어 등으로 넓게 응용되고 있다. 1938년, 클로드 섀넌은 불 논리를 릴레이에 의한 전기 회로 장착 방법으로 나타냈다. 이 사실은 머지않아 전자식 컴퓨터를 만드는 데 없어서는 안 될 존재임이 밝혀졌다.
여기서는 집합 대수를 이용하고, 집합, 불 연산, 진릿값 표 등의 기본 해설과 불 논리의 응용에 대해 풀이한다. 불 대수 글에는 불 논리의 공리를 만족하는 대수 구조의 형태를 설명하고 있다. 이진수에서는 컴퓨터에서 쓰이는 이진수를 풀이하고 있다.
2. 용어
A AND B(보라색의 부분), A OR B(색이 붙어 있는 부분 모두), A XOR B(보라색 이외의 색이 붙어 있는 부분). 네모진 바깥쪽 선은 모집단(universe)2.1. 디지털 회로 설계
불 논리는 전기 공학 회로 설계에도 사용된다. 이때, 0과 1은 디지털 회로로의 비트가 다른 2개 상태를 나타내, 전압의 높낮이를 따른다. 회로는 변수를 포함한 식에서 표시된다. 입출력이 완전하면, 이를 불 논리식에서 표현할 수 있다.AND 게이트, OR 게이트, NOT 게이트와 같은 기본 논리 회로만을 사용할 수도 있지만, NAND 게이트, NOR 게이트, XOR 게이트 등도 조합해 디지털 회로를 구성할 수 있다. 조합 방법은 연산자의 우선 순위에 따라 직렬이나 병렬과 결합한다.
2.2. 데이터베이스
관계 데이터베이스에서는 쿼리를 위해 SQL 등의 데이터베이스 고유 언어를 사용하지만, 이것들은 불 논리를 포함하고 있다. 이 경우, 표 안의 레코드(record)는 「집합」 안의 「원」에 가깝다. 이를테면, SQL의 SELECT문은 데이터베이스 안의 바깥(표)으로부터 데이터를 다음과 같이 추출한다.| * SELECT * FROM EMPLOYEES WHERE LAST_NAME = 'Smith' AND FIRST_NAME = 'John' ; |
| * SELECT * FROM EMPLOYEES WHERE LAST_NAME = 'Smith' OR FIRST_NAME = 'John' ; |
| * SELECT * FROM EMPLOYEES WHERE NOT LAST_NAME = 'Smith' ; |
여러 불 연산이 있는 경우, 괄호를 사용해 연산의 순서를 제어하기도 한다:
| * SELECT * FROM EMPLOYEES WHERE (NOT LAST_NAME = 'Smith') AND (FIRST_NAME = 'John' OR FIRST_NAME = 'Mary') ; |
필요에 따라 괄호를 얼마든지 박스로 만들 수도 있다. 복수의 바깥(표)을 불 연산으로 조합하는 것을 결합이라고 한다.( 관계 대수).
2.3. 검색 엔진
이 경우, 인터넷의 각 웹페이지가 「집합」의 「원」에 가깝다. 검색 엔진에 따라 쿼리의 문법은 여러 가지이다. 여기에서는 구글의 문법을 설명한다.-
논리곱에는 기호를 사용하지 않는다. 따라서 키워드를 2개 늘어 놓았을 경우 논리곱이라고 해석된다.
:: "키워드 1" "키워드 2" -
논리합에는 "OR"를 사용한다.
:: "키워드 1" OR "키워드 2" -
마이너스 기호로 논리 부정을 나타낸다(실제로는 AND NOT).
:: "키워드 1" -"키워드 2" - 연산자의 우선순위가 정해져 있기 위해, 괄호는 사용하지 않는다.
3. 같이 보기
4. 참조
- Shannon, Claude (1938) "The Symbolic Analysis of Relay and Switching Circuits".