구조 (논리학)

틀:위키데이터 속성 추적 모형 이론에서 구조(構造, 틀:Llang)는 어떤 주어진 1차 논리 언어의 해석을 갖춘 집합이다.

정의

자연수(음이 아닌 정수)의 집합을 $ℕ$ 이라고 쓰자.

부호수(符號數, 틀:Llang) $(F, R, {arity}_{F}, {arity}_{R})$ 는 다음과 같은 튜플이다.

$F$ 는 집합이다. $F$ 의 원소를 연산(演算, 틀:Llang)이라고 한다.
$R$ 는 집합이다. $R$ 의 원소를 관계(關係, 틀:Llang)라고 한다.
${arity}_{F} : F \to ℕ$ 는 함수이다. $f \in F$ 에 대하여 ${arity}_{F} (f) = n$ 이라면, $f$ 를 $n$ 항 연산(틀:Llang)이라고 한다.
${arity}_{R} : R \to ℕ$ 는 함수이다. $r \in R$ 에 대하여 ${arity}_{R} (r) = n$ 이라면, $r$ 를 $n$ 항 관계(틀:Llang)라고 한다.

부호수 $(F, R, {arity}_{F}, {arity}_{R})$ 의 구조 $(M, F_{M}^{n}, R_{M}^{n})_{n \in ℕ}$ 는 다음과 같은 튜플이다.

$M$ 은 집합이다. 이를 구조의 전체(全體, 틀:Llang)라고 한다.
각 $n \in ℕ$ 에 대하여, $F_{M}^{n} : {arity}_{F}^{- 1} (n) \to M^{M^{n}}$ 이다. $f \in {arity}_{F}^{- 1} (n)$ 에 대하여, $F_{M}^{n} (f) : M^{{arity}_{F} (f)} \to M$ 을 보통 $f_{M}$ 이라고 쓰며, $n$ 항 연산 $f$ 의 $M$ 에서의 해석(解釋, 틀:Llang)이라고 한다.
각 $n \in ℕ$ 에 대하여, $R_{M}^{n} : {arity}_{R}^{- 1} (n) \to 𝒫 (M^{n})$ 이다. $r \in {arity}_{R}^{- 1} (n)$ 에 대하여, $R_{M}^{n} (r) \subset M^{{arity}_{R} (r)}$ 을 보통 $r_{M}$ 이라고 쓰며, $n$ 항 관계 $r$ 의 $M$ 에서의 해석(解釋, 틀:Llang)이라고 한다.

관계를 포함하지 않는 부호수를 대수적 부호수(틀:Llang)라고 하고, 대수적 부호수의 구조를 대수 구조라고 한다.

언어

부호수 $(F, R, {arity}_{F}, {arity}_{R})$ 의 (1차 논리) 언어(言語, 틀:Llang) $ℒ$ 은 공식(公式, 틀:Llang)과 항(項, 틀:Llang)으로 구성된다. $ℒ$ 의 항은 다음과 같이 재귀적으로 정의된다.

변수 $x_{i}$ 는 항이다 ( $i \in ℕ$ ).
항 $t_{1}, \dots, t_{n}$ 및 $n$ 항 연산 $f \in F$ 에 대하여, $f (t_{1}, \dots, t_{n})$ 은 항이다.

$ℒ$ 의 공식은 다음과 같이 재귀적으로 정의된다.

항 $t_{1}, \dots, t_{n}$ 및 $n$ 항 관계 $r \in R$ 에 대하여, $r (t_{1}, \dots, t_{n})$ 는 공식이다.
항 $t_{1}, t_{2}$ 에 대하여, $t_{1} = t_{2}$ 는 공식이다.
공식 $ϕ$ 에 대하여, $\neg ϕ$ 는 공식이다.
공식 $ϕ$ 및 $ψ$ 에 대하여, 만약 $ϕ$ 에 등장하는 제한 변수가 $ψ$ 에 등장하지 않으며, 마찬가지로 $ψ$ 에 등장하는 제한 변수가 $ϕ$ 에 등장하지 않는다면, $ϕ \land ψ$ 는 공식이다.
변수 $x_{i}$ 및 공식 $ϕ$ 에 대하여, 만약 $ϕ$ 가 이미 $\forall x_{i} :$ 를 포함하지 않는다면, $\forall x_{i} : ϕ$ 는 공식이다.

만약 $ϕ$ 속에 변수 $x_{i}$ 가 등장하지만 $\forall x_{i} :$ 가 등장하지 않는다면, $x_{i}$ 를 자유 변수(自由變數, 틀:Llang)라고 하고, $\forall x_{i} :$ 가 등장한다면 $x_{i}$ 를 제한 변수(制限變數, 틀:Llang)라고 한다. 자유 변수가 없는 공식을 문장(文章, 틀:Llang)이라고 한다. 문장들의 집합을 이론(理論, 틀:Llang)이라고 한다.

만족

부호수 $σ$ 의 언어에 속하는 공식 $ϕ$ 가 $n$ 개의 자유 변수 $\vec{x} = (x_{1}, \dots, x_{n})$ 을 갖는다고 하자. 부호수 $σ$ 의 구조 $M$ 및 $\vec{a} \in M^{n}$ 에 대하여, 다음과 같이 재귀적으로 정의되는 조건이 성립한다면, $M$ 이 $ϕ$ 를 치환 $\vec{x} \mapsto \vec{a}$ 아래 만족시킨다(滿足시킨다, 틀:Llang)고 하고, $M ⊨ ϕ [\vec{a} / \vec{x}]$ 라고 쓴다. 여기서 부호수의 언어의 논리 기호 $=$ , $\neg$ , $\land$ , $\forall$ 은 메타 언어의 논리 기호와 구별하기 위하여 괄호 $⟨ \dots ⟩$ 속에 적었다.

$M ⊨ ⟨ t_{1} = t_{2} ⟩ [\vec{a} / \vec{x}] ⟺ t_{1} [\vec{a} / \vec{x}] = t_{2} [\vec{a} / \vec{x}]$ . 여기서 $t [\vec{a} / \vec{x}]$ 는 항 $t$ 속에 등장하는 모든 변수 $x_{i}$ 를 이에 대응하는 $a_{i}$ 로 치환하고, $t$ 속에 등장하는 모든 연산 $f \in F$ 를 $f_{M}$ 으로 치환하여 얻은 원소 $\in M$ 이다.
$M ⊨ ⟨ R (t_{1}, \dots, t_{n}) ⟩ [\vec{a} / \vec{x}] ⟺ R_{M} (t_{1} [\vec{a} / \vec{x}], \dots, t_{n} [\vec{a} / \vec{x}])$
$M ⊨ ⟨ ϕ \land χ ⟩ ⟺ (M ⊨ ϕ) \land (M ⊨ χ)$
$M ⊨ ⟨ \neg ϕ ⟩ ⟺ \neg (M ⊨ ϕ)$
$M ⊨ ⟨ \forall y : ϕ (y) ⟩ [\vec{a} / \vec{x}] ⟺ \forall b \in M : M ⊨ ϕ [(\vec{a}, b) / (\vec{x}, y)]$

부호수 $σ$ 의 언어에서, $n$ 개의 자유 변수 $\vec{x}$ 를 갖는 공식 $ϕ$ 에 대하여, 만약 $M ⊨ ϕ [\vec{a} / \vec{x}]$ 인 $σ$ -구조 $M$ 및 $\vec{a} \in M^{n}$ 이 존재한다면, $ϕ$ 를 만족 가능 공식(滿足可能命題, 틀:Llang)이라고 한다.

이론 $𝒯$ 의 모형(模型, 틀:Llang)은 모든 $ϕ \in 𝒯$ 에 대하여 $M ⊨ ϕ$ 인 $σ$ -구조 $M$ 이다. 모형을 갖는 이론을 만족 가능 이론(滿足可能理論, 틀:Llang)이라고 한다. (이는 만족 가능 문장들로 구성된 이론보다 강한 조건이다.)

참고 문헌

외부 링크

구조 (논리학)

목차

정의

언어

만족

참고 문헌

외부 링크

둘러보기 메뉴

구조 (논리학)

정의

언어

만족

참고 문헌

외부 링크

둘러보기 메뉴

검색