| 수리논리학 Mathematical Logic | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#6600ff><colcolor=#fff,#fff> 형식 체계 | 형식 언어(알파벳) · 시그니처 · 항 · 논리식 · 명제 · 명제 논리{조건문(역 · 이 · 대우) · 공허참 · 논리 연산 · 드모르간 법칙 · 논리함수} · 술어 논리{일차 논리(완전성 정리) · 고차 논리 · 같음} |
| 증명 이론 | 공리 · 정리(보조정리) · 증명 · 귀류법 · 수학적 귀납법 · 괴델의 불완전성 정리(괴델 부호화) · 굿스타인 정리 · 자동정리증명 · 증명보조기 | |
| 모델 이론 | 이론(theory) · 모델 · 뢰벤하임-스콜렘 정리 · 비표준 해석학 | |
| 계산가능성 이론 | 계산 · 오토마타 · 튜링 머신 · 바쁜 비버 · 정지 문제 · 재귀함수 | |
| 기타 | 예비사항 · 수학·과학 표기법 · 수학기초론 · 메타수학 · 수학철학(힐베르트 프로그램) · 거짓말쟁이의 역설 · 타입 이론 · 양상논리 · 동형(수학) · 퍼스의 법칙 · 퍼지 논리 | |
| 틀:논리학 · 틀:집합론 · 틀:범주론 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보 | }}}}}}}}} | |
1. 개요
formula, formulae복수형, logical formula, [math(L)]-formula / 論理式본 문서는 수리논리학, 특히 모델 이론에서 주어진 시그니처(signature)와 여기서 생성되는 형식 언어(formal language)를 구성하는 논리식을 다룬다.
흔히 생각하는 AND([math(\land)]), OR([math(\lor)]), NOT([math(\neg)]) 등으로 결합된 식을 생각했다면 논리 연산이나 명제 논리를 참고하자. formal한 관점에서 이런 식의 결합식도 논리식의 일종이나, 본 문서는 그보다 훨씬 넓은 범위를 다루며, 무엇보다 순수 [math(L)]-formula의 성질만 다루며 어떠한 자연 연역 및 추론 규칙 체계, 및 ad hoc한 이론(theory)도 다루지 않는다.
2. 형식 언어에서 구성
특정 signature [math(\sigma)] 및 여기서 생성되는 형식 언어 [math(L)]을 생각하자. 선행되는 지식은 각 문서를 참고하자. 기본적으로 변수는 [math(x_1, x_2, \dots)]인 것으로 생각하자.2.1. 시그니처(수리논리학)
signature#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[시그니처(수리논리학)#s-|]]번 문단을#!if 문단 == null & 앵커 != null
{{{#!if 문서명 = 문서명 != null ? 문서명 : calleeTitle
의 [[시그니처(수리논리학)#|]] 부분을}}} 참고하십시오.2.2. 변수 집합
variables흔히 잊혀지곤 하는데, 변수 또한 엄밀히는 signature나 logical symbol과 완전히 독립적으로 존재하며 최종 alphabet을 구성하는 대상 중 하나이다.
다만 편의상 서로 다른 변수까지 생각하면 끝이 없고, 때문에 보통 아주 특정한 변수 집합 하나를 [math(X)]로 고정하고 implicit하게 사용한다. 기본적으로 모든 문자열은 유한수열이므로 변수도 무한할 필요는 없으나, 여러 귀찮은 면이 있으므로 그냥 countably many한 집합을 떠올리는 편이 많다.
본 문서는 변수 집합 [math(X)]를 가정하고 모든 변수가 [math(x_1)], [math(x_2)], ... 식으로 [math(x_n)] 꼴임을 가정한다.
2.3. 항
term#!if (문단 == null) == (앵커 == null)
를#!if 문단 != null & 앵커 == null
의 [[항(수리논리학)#s-|]]번 문단을#!if 문단 == null & 앵커 != null
{{{#!if 문서명 = 문서명 != null ? 문서명 : calleeTitle
의 [[항(수리논리학)#|]] 부분을}}} 참고하십시오.2.4. 논리 기호
logical symbolssignature는 개별 언어마다 다르지만, 이건 어떤 signature를 쓰더라도 똑같은 기호들이다. 보통 다음이 있다.
- [math(\top)], [math(\bot)], [math(\neg)], [math(\land)], [math(\lor)], [math(\to)], [math(\leftrightarrow)], [math(\forall)], [math(\exists)], [math(=)]
[math(=)]가 들어가는지 아닌지를 매우 주의해서 볼 필요가 있는데, 일반적인 많은 논리 체계는 사실 암묵적으로 논리 수준의 같음(equality) 개념 및 rule을 가지고 있다. 자세한 내용은 같음 문서의 FOL= 참고.
물론 [math(\phi \leftrightarrow \psi)] 등은 [math(( \phi \to \psi ) \land ( \psi \to \phi ))] 등으로 쓸 수 있으니 굳이 따로 정의하지 않기도 한다. 이를 생각하면 표준 논리에서 할 수 있는 온갖 트릭을 다 써서 [math(\neg)], [math(\land)], [math(\forall)] 등으로 golfing할 수도 있겠으나 본 문서는 편의상 위 기호를 사용한다.
2.5. 원자식
atomic formula기본적으로 같음이 있는 체계를 가정한다.
- [math(\top)], [math(\bot)]은 atomic formula다.
- [math(t_1, t_2)]가 [math(L)]-term이라면 [math(t_1 = t_2)]는 atomic formula다.
- [math(r)]이 [math(\sigma)]에서 [math(n)]-ary relation symbol이고 [math(t_1, \dots, t_n)]이 [math(L)]-term이라면 [math(r ( t_1, \dots, t_n ))]은 atomic formula다. 이를 관계식이라고 한다.
2.6. 논리식
- [math(\phi)]가 atomic formula라면 [math(L)]-formula다.
- [math(\phi)]가 [math(L)]-formula라면 [math(\neg \phi)]는 [math(L)]-formula다.
- [math(\phi)], [math(\psi)]가 [math(L)]-formula라면 [math(\phi \land \psi)]는 [math(L)]-formula다.
- [math(\phi)], [math(\psi)]가 [math(L)]-formula라면 [math(\phi \lor \psi)]는 [math(L)]-formula다.
- [math(\phi)], [math(\psi)]가 [math(L)]-formula라면 [math(\phi \to \psi)]는 [math(L)]-formula다.
- [math(\phi)], [math(\psi)]가 [math(L)]-formula라면 [math(\phi \leftrightarrow \psi)]는 [math(L)]-formula다.
- [math(\phi)]가 [math(L)]-formula고 [math(x)]가 변수라면 [math(\forall x \phi)]는 [math(L)]-formula다.
- [math(\phi)]가 [math(L)]-formula고 [math(x)]가 변수라면 [math(\exists x \phi)]는 [math(L)]-formula다.
3. presentation
사실 term에만 적용될 것처럼 보이지만 당연하게도(...) relational formula 및 logical symbol 수준에서도 적용이 가능하다. 가령 ZFC 공리계에서 쓰는 formal language [math(L_\mathrm{ ZFC })]를 [math(\sigma = ( ; 2 ))]에서 생성된다 하고 '공집합이 존재한다'는 말을 [math(L_\mathrm{ ZFC })]-formula로 써보자.
<tableclass=disp> |
<tableclass=disp> |