2차 논리 - 위키백과, 우리 모두의 백과사전 2차 논리 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 수리논리학에서, 2차 논리 ( 二 [UNK] 論 理, 영어 : second - order logic ) 는 임의의 다항 관계 및 다항 연산에 대한 변수 및 이에 대한 전칭 · 존재 기호를 사용할 수 있는 논리이다. 1차 논리에서 변수는 사용하는 모형의 원소만을 지칭하지만, 2차 논리에서는 모형 속의 임의의 부분 집합에 대하여 언급할 수 있다. 이에 따라 2차 논리는 1차 논리보다 더 다양한 개념들에 대하여 논할 수 있다. 그러나 2차 논리는 1차 논리와 달리 완전한 증명 체계를 갖지 못하며, 콤팩트성 정리나 뢰벤하임 - 스콜렘 정리와 같은 중요한 성질들이 성립하지 않는다. 목차 1 정의 1. 1 문법 1. 2 의미론 2 성질 3 역사 4 참고 문헌 5 외부 링크 정의 [ 편집 ] 문법 [ 편집 ] 2차 논리의 문법은 다음과 같은 기호들로 구성된다. 2차 논리의 변수 ( 영어 : variable ) 들은 다음과 같은 가산 무한 개의 종류 ( 영어 : sort ) 에 속한다. 각 자연수 n [UNK] N { [UNK] displaystyle n [UNK] in [UNK] m
) 라고 한다. 여기서 " 증명 " 이란 ( 주어진 알파벳에 대한 ) 일련의 문자열을 뜻한다. 괴델의 불완전성 정리에 따라, 2차 논리의 증명 체계는 다음 세 조건을 동시에 만족시킬 수 없다. ( 정당성 영어 : soundness ) 증명 체계가 증명할 수 있는 모든 명제는 2차 논리의 모든 ( 표준 ) 모형에서 참이다. ( 완전성 영어 : completeness ) 증명 체계는 2차 논리의 모든 ( 표준 ) 모형에서 참인 2차 논리 명제를 증명할 수 있다. ( 유효성 영어 : effectiveness ) 증명들의 집합은 재귀적 집합이다. 즉, 주어진 문자열이 어떤 명제의 증명인지 여부를 항상 종료하는 알고리즘으로 판별할 수 있다. 반면, 1차 논리의 경우 위 세 조건을 만족시키는 증명 체계가 존재한다 ( 괴델의 완전성 정리 ). 2차 논리에서는 또한 콤팩트성 정리와 뢰벤하임 - 스콜렘 정리가 성립하지 않는다. ( 위 성질들은 2차 논리의 표준 의미론에 대한 것이다. [UNK] 의미론을 사용하면 이는 1차 논리와 같은 성질들을 갖는다. ) 역사 [ 편집 ] 고틀로프 프레게는 1879년에 출판된 《 개념 표기법 》 [ 2 ] 에서 오늘날의 2차 논리와 유사한 논리 체계
의미론은 흔히 2차 논리의 모형으로 주어진다. 이 경우, 모형 [UNK] X,... [UNK] { [UNK] displaystyle [UNK] langle X, [UNK] dots [UNK] rangle } 가 주어졌을 때, n { [UNK] displaystyle n } 항 연산 변수는 X { [UNK] displaystyle X } 위의 모든 ( 외적 관점에서의 ) 연산 X X n { [UNK] displaystyle X ^ { X ^ { n } } } 의 값을 가질 수 있으며, n { [UNK] displaystyle n } 항 관계 변수는 X { [UNK] displaystyle X } 위의 모든 ( 외적 관점에서의 ) 관계 P ( X n ) { [UNK] displaystyle { [UNK] mathcal { P } } ( X ^ { n } ) } 의 값을 가질 수 있다. 특히, 1항 관계 변수는 X { [UNK] displaystyle X } 의 모든 부분 집합의 값을 가질 수 있다. 반면, 1차 논리 모형에서는 ( 집합론의 언어를 사용할 경우, 추이적 모형의 경우 ) 1차 논리 언어로 정의 가능한 X { [UNK] displaystyle X } 의 부분 집합만을 다룰 수 있다. 2차 논리의 경우, 위와 같은 표준적인 의미론 대신 [UNK] 의미론 ( 영어 : Henkin semantics ) 을 사용할 수 있
t - { 1 }, t - { 2 }, [UNK] dots, t - { n } } 에 대하여, f i n ( t 1, t 2,..., t n ) { [UNK] displaystyle f - { i } ^ { n } ( t - { 1 }, t - { 2 }, [UNK] dots, t - { n } ) } 은 항이다. ( 편의상 n = 0 { [UNK] displaystyle n = 0 } 일 때 괄호 f i 0 { [UNK] displaystyle f - { i } ^ { 0 } } 를 생략하여 f i 0 { [UNK] displaystyle f - { i } ^ { 0 } } 로 쓴다. ) n { [UNK] displaystyle n } 항 연산 f { [UNK] displaystyle { [UNK] mathsf { f } } } 와 n { [UNK] displaystyle n } 개의 항 t 1, t 2,..., t n { [UNK] displaystyle t - { 1 }, t - { 2 }, [UNK] dots, t - { n } } 에 대하여, f ( t 1, t 2,..., t n ) { [UNK] displaystyle { [UNK] mathsf { f } } ( t - { 1 }, t - { 2 }, [UNK] dots, t - { n } )
le { [UNK] mathsf { f } } } 및 n { [UNK] displaystyle n } 항 관계 R { [UNK] displaystyle { [UNK] mathsf { R } } }. 예를 들어, 집합론의 언어는 하나의 2항 관계 [UNK] { [UNK] displaystyle [UNK] in } 를 갖는다. 다른 예로, 순서체의 언어는 2항 연산 { [UNK] displaystyle } 와 [UNK] { [UNK] displaystyle [UNK] cdot }, 1항 연산 - { [UNK] displaystyle - }, 0항 연산 0 { [UNK] displaystyle 0 } 과 1 { [UNK] displaystyle 1 }, 그리고 2항 관계 [UNK] { [UNK] displaystyle [UNK] leq } 를 갖는다. 2차 논리의 항 ( 영어 : term ) 은 다음 문법을 따라야 한다. n { [UNK] displaystyle n } 항 연산 변수 f i n { [UNK] displaystyle f - { i } ^ { n } } 과 n { [UNK] displaystyle n } 개의 항 t 1, t 2,..., t n { [UNK] displaystyle t - { 1 }, t - { 2 }, [UNK] dots, t - { n } } 에 대하여, f i n ( t 1, t 2,..., t n ) { [UNK] dis
{ 1 } = t - { 2 } } 는 논리식이다. 논리식 [UNK] { [UNK] displaystyle [UNK] phi } 와 [UNK] { [UNK] displaystyle [UNK] phi } 에 등장하는 n { [UNK] displaystyle n } 항 자유 연산 변수 f i n { [UNK] displaystyle f - { i } ^ { n } } 에 대하여, [UNK] f i n [UNK] { [UNK] displaystyle [UNK] forall f - { i } ^ { n } [UNK] phi } 와 [UNK] f i n [UNK] { [UNK] displaystyle [UNK] exists f - { i } ^ { n } [UNK] phi } 는 논리식이다. 논리식 [UNK] { [UNK] displaystyle [UNK] phi } 와 [UNK] { [UNK] displaystyle [UNK] phi } 에 등장하는 n { [UNK] displaystyle n } 항 자유 관계 변수 R i n { [UNK] displaystyle R - { i } ^ { n } } 에 대하여, [UNK] R i n [UNK] { [UNK] displaystyle [UNK] forall R - { i } ^ { n } [UNK] phi } 와 [UNK] R i n [UNK] { [UNK] displaystyle [UNK] exists R - { i } ^ { n } [UNK] phi } 는 논리식이다. 두 논리식 [UNK] { [UNK] displaystyle [UNK] phi } 와 [UNK] { [UNK] dis
Herbert B. ( 2009년 3월 4일 ). " Second - order and higher - order logic ". 《 The Stanford Encyclopedia of Philosophy 》 ( 영어 ). Uzquiano, Gabriel ( 2014년 9월 3일 ). " Quantifiers and quantification ". 《 The Stanford Encyclopedia of Philosophy 》 ( 영어 ). " Second - order logic ". 《 nLab 》 ( 영어 ). " Higher - order logic ". 《 nLab 》 ( 영어 ). 원본 주소 " " 분류 : 수리논리학숨은 분류 : CS1 - 영어 인용 ( en ) CS1 - 독일어 인용 ( de ) 영어 표기를 포함한 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 [UNK] 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 [UNK] 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어
- { 2 } ^ { n }, [UNK] dots }. 특히, n = 1 { [UNK] displaystyle n = 1 } 일 때, f 0 1, f 1 1,... { [UNK] displaystyle f - { 0 } ^ { 1 }, f - { 1 } ^ { 1 }, [UNK] dots } 는 1차 논리 변수들의 집합에 해당한다. 변수 밖에도 다음과 같은 논리 기호들이 사용된다. ( 이들은 1차 논리와 같다. ) 전칭 기호 [UNK] { [UNK] displaystyle [UNK] forall } 와 존재 기호 [UNK] { [UNK] displaystyle [UNK] exists } 등호 = { [UNK] displaystyle = } 명제 논리 기호 [UNK] { [UNK] displaystyle [UNK] land } ( 논리곱 ), [UNK] { [UNK] displaystyle [UNK] lor } ( 논리합 ), [UNK] { [UNK] displaystyle [UNK] lnot } ( 부정 ) 등 괄호 { [UNK] displaystyle } 및 반점, { [UNK] displaystyle, } 등 주어진 n { [UNK] displaystyle n } 항 연산 f { [UNK] displaystyle { [UNK] mathsf { f } } } 및 n { [UNK] displaystyle n } 항 관계 R { [UNK] displaystyle { [UNK] mathsf { R } } }. 예
playstyle [UNK] exists R - { i } ^ { n } [UNK] phi } 는 논리식이다. 두 논리식 [UNK] { [UNK] displaystyle [UNK] phi } 와 [UNK] { [UNK] displaystyle [UNK] chi } 에 대하여, [UNK] [UNK] [UNK] { [UNK] displaystyle [UNK] phi [UNK] land [UNK] chi } 와 [UNK] [UNK] [UNK] { [UNK] displaystyle [UNK] phi [UNK] lor [UNK] chi } 및 [UNK] { [UNK] displaystyle [UNK] phi } 에 대하여, [UNK] [UNK] { [UNK] displaystyle [UNK] lnot [UNK] phi } 는 논리식이다. 여기서, 논리식 [UNK] { [UNK] displaystyle [UNK] phi } 에 등장하는 연산 변수 또는 관계 변수 x { [UNK] displaystyle x } 가 자유 변수 ( 영어 : free variable ) 라는 것은 [UNK] { [UNK] displaystyle [UNK] phi } 에 [UNK] x { [UNK] displaystyle [UNK] forall x } 나 [UNK] x { [UNK] displaystyle [UNK] exists x } 가 포함되지 않는 것을 의미한다. 의미론 [ 편집 ] 2차 논리의 의미론은 흔히 2차 논리의 모형으로 주어진다. 이 경우, 모형 [UNK] X,... [UNK] { [UNK] displaystyle [UNK] langle X, [UNK] dots [UNK] rangle } 가
와 같은 성질들을 갖는다. ) 역사 [ 편집 ] 고틀로프 프레게는 1879년에 출판된 《 개념 표기법 》 [ 2 ] 에서 오늘날의 2차 논리와 유사한 논리 체계를 도입하였다. [ 3 ] : 295 그러나 프레게는 1차 논리와 고차 논리를 구분하지 않았다. 이후 찰스 샌더스 퍼스가 1차 논리와 2차 논리를 구분하였으며, " 2차 논리 " 라는 용어를 도입하였다. [ 3 ] : 296 [UNK] 의미론은 리언 앨버트 [UNK] ( 영어 : Leon Albert Henkin, 1921 ~ 2006 ) 이 1950년에 도입하였다. [ 4 ] 2차 논리에 대하여 윌러드 밴 오먼 콰인은 ( [UNK] 우화에 빗대어 ) " 양의 탈을 쓴 집합론 " ( 영어 : set theory in sheep's clothing ) 이라고 평하였다. [ 5 ] : 66, Chapter 5 즉, 2차 논리로는 집합론에 해당하는 여러 개념들 ( [UNK] 등 ) 을 정의할 수 있으며, 또한 적절한 증명 이론을 제시할 수 없으므로, 1차 논리와 달리 2차'논리'는 사실 논리가 아니라는 것이다. 반면, 조지 불로스 ( 영어 : George Boolos ) [ 6 ] 를 비롯한 다른 수리철학자들은 [ 1 ]
수리논리학에서 2차 논리(二次論理, 영어: second-order logic)는 임의의 다항 관계 및 다항 연산에 대한 변수 및 이에 대한 전칭·존재 기호를 사용할 수 있는 논리이다. 1차 논리에서 변수는 사용하는 모형의 원소만을 지칭하지만, 2차 논리에서는 모형 속의 임의의 부분 집합에 대하여 언급할 수 있다. 이에 따라 2차 논리는 1차 논리보다 더 다양한 개념들에 대하여 논할 수 있다. 그러나 2차 논리는 1차 논리와 달리 완전한 증명 체계를 갖지 못하며, 콤팩트성 정리나 뢰벤하임-스콜렘 정리와 같은 중요한 성질들이 성립하지 않는다.