|
수학기초론 Foundations of Mathematics |
|||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
다루는 대상과 주요 토픽 | ||
| 수리논리학 | 논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론 | ||
| 집합론 | 집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임 | ||
| 범주론 | 범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 | ||
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수 | ||
| 정리 | |||
| 드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리 | |||
| 기타 | |||
| 예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학 | |||
| 틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | ||
[clearfix]
1. 개요
論 理 函 數입력에 따라 참, 거짓 중 하나의 값을 출력하는 함수.
가령 [math(f(\rm A, B) = A \cdot B)]라고 하면(단, [math(\rm A)]와 [math(\rm B)]는 부울 변수), A와 B의 값에 따라서 f는 참(True), 거짓(False) 둘 중 하나의 값을 출력할 수 있다.
논리함수는 위와 같이 AND, OR과 같은 논리연산만으로도 이루어 질 수도 있지만, [math(f = x == 5)], [math(f = x< 3)], [math(f = \text{``오늘 비가 온다''})]와 같이 결과값이 참, 거짓으로 나오는 모든 연산과 논리로 구성될 수 있다.
당연한 것이겠지만 논리함수에 값을 집어넣으면 참 또는 거짓인 값을 출력해 낸다. 일반 함수처럼 생각하면 된다.
대표적인 예시로 지시함수가 있다. 입력값이 지정한 집합에 속해 있으면 1, 그렇지 않으면 0을 출력한다.
2. 명제화
주의할 점은, 부울 함수는 그 자체로 명제가 아니라는 것이다. 명제란 참 거짓이 명확한 문장으로써, 논리함수는 입력하는 값에 따라 참 또는 거짓이 되므로 명제가 아니다. 논리함수가 명제가 되려면 함수의 결과값으로 무조건 참이 나오거나, 무조건 거짓이 나와야 한다.그럼 논리함수를 명제화 하려면 어떻게 해야 할까? 단순히 생각하면 입력의 값을 제어하면 된다. 예를 들어 값의 범위를 지정하는 방법이 있는데, 가령 [math(f = x < 5)]라는 논리함수에서 [math(x<3)]의 범위를 지정하면 [math(f)]는 무조건 참이 된다. 이는 명제다.
3. 제한자
여기서 더 나아가 모든(Universal, [math(∀)])과 어떤(Existantial, [math(∃)])[1]이라는 제한자(quantifier)라는 것이 있다. 이것들 또한 값의 범위를 지정하는 것으로 각각 '모든 원소가', '어떤 한 원소가' 라는 뜻을 가지고 있다.가령 [math(f(x))]를 "[math(x)]는 3의 배수인 정수이다." 라고 하면, "모든 [math(x)]에 대해서 [math(f(x))]가 성립한다(= 참이다)", "어떤 [math(x)]에 대해서 [math(f(x))]가 성립한다."와 같이 제한자를 사용한다.
다만 이 제한자를 사용하기 위해서는 논리함수가 정의되는 범위(domain)가 반드시 필요하다. 가령 위에서 말한 [math(f(x))]가 '6의 배수를 모은 집합'에서 정의가 된다고 하면 모든 [math(x)]에 대해서 [math(f(x))]가 성립하지만 '모든 자연수' 에서 정의된다고 하면 모든 [math(x)]에 대해 [math(f(x))]가 성립하지는 않는다.
[1]
해당 기호는 증명 약어로 존재한다(Exist)라는 의미를 지니기도 하므로 사용에 주의가 필요하다.