이어지는 벤슨 메이츠 <기호논리학> 3장 해답입니다. 아래는 다른 장들의 해답입니다.
그리고 벤슨 메이츠 <기호논리학> 영문판 pdf는 여기를 클릭해 주세요. 그럼 시작합니다.
1. 식(a formula), 문장(a sentence), 원자문장(an atomic sentence), 보편문장(a general sentence), 분자문장(a molecular sentence)로 번역했습니다. 'a general sentence'는 문장 전제를 속박하는 보편 혹은 존재양화사로 문장이 시작하는 경우로 판단했습니다.
| 문제 번호 | 식인가? | 문장인가? | 원자/양화/분자? | 'x'는 자유로운가? | 'x'는 속박되었나? |
| (1) | 예 | 아니오 | 해당없음 | 예 | 아니오 |
| (2) | 예 | 예 | 보편문장 | 아니오 | 예 |
| (3) | 예 | 예 | 원자문장 | 아니오 | 아니오 |
| (4) | 예 | 예 | 보편문장 | 아니오 | 예 |
| (5) | 아니오 | 아니오 | 해당없음 | 아니오 | 아니오 |
| (6) | 예 | 예 | 분자문장 | 아니오 | 예 |
| (7) | 아니오 | 아니오 | 해당없음 | 아니오 | 아니오 |
| (8) | 예 | 예 | 분자문장 | 아니오 | 예 |
| (9) | 예 | 아니오 | 해당없음 | 예 | 예 |
| (10) | 예 | 예 | 보편문장 | 아니오 | 예 |
| (11) | 예 | 예 | 분자문장 | 아니오 | 아니오 |
| (12) | 예 | 예 | 분자문장 | 아니오 | 예 |
| (13) | 예 | 아니오 | 해당없음 | 예 | 아니오 |
| (14) | 아니오 | 아니오 | 해당없음 | 아니오 | 아니오 |
2. $F^1 b$, $((x)F^{1}_{1}x \rightarrow F^{1}_{1}a)$, $((x)F^1 x \lor -F^1 b)$, $(P \rightarrow (x)P)$, $(((F^1 a \leftrightarrow F^1 b)\leftrightarrow F^1 a)\leftrightarrow F^1 b)$.
3. (a) $(F^1 x \wedge G^1 y)$.
(b) $(x)F^1 x$.
(c) $((F \lor -G) \wedge (-F \lor G))$.
(d) $F$.
(e) $(x)(\exists y)(F^1 x \rightarrow G^1 y)$.
(f) $(((x)F^1 x \lor (y) G^1 y)\rightarrow H^1 z)$.
(g) $(x)(F^1 x)$.
4. Although '$\alpha$' is not a variable of $\mathfrak{L}$ and '$\beta$' is not an individual symbol of $\mathfrak{L}$, there are $\alpha$, $\beta$, and $\varphi$ such that '$\alpha$' is a variable of $\mathfrak{L}$, '$\beta$' is an individual constant of $\mathfrak{L}$, '$\varphi$' is a formula of $\mathfrak{L}$, and '$\varphi \alpha / \beta$' is the same as $\varphi$.
5. (a) $\varphi := F^1 a$.
$\psi := F^1 x$.
(b) $\varphi := (F^1 a \lor G^1 a)$.
$\psi := (F^1 a \lor G^1 x)$.
(c) $\varphi := (F^1 y \lor G^1 y)$.
$\psi := (F^1 x \lor G^1 y)$.
6. 쉬운 방식으로는 적형식의 규정을 이용해서 위계 0일 때(induction basis), 괄호가 없으니 왼쪽-오른쪽 괄호의 수가 같음을 알 수 있습니다. 귀납 가정 단계에서는, 임의의 $k$ 보다 작은 위계의 문장이 동일한 수의 왼쪽 오른쪽 괄호를 지닌다고 가정하고 $k$ 위계의 문장이 부정 연산자를 지닐 때, 연언-선언-조건문을 지닐 때 그리고 양화사를 지닐 때 귀납 가정에 의해 괄호의 수가 같음을 보이면 됩니다.
세부적인 증명을 위해 임의의 식 $\varphi$에 대한 위계 $o(\varphi)$는 다음과 같이 귀납적 방식으로 정의합니다.
(1) $\varphi$가 원자식인 경우, $o(\varphi) = 0$,
(2) $\square$에 들어가는 논리연산자가 $\wedge$, $\lor$, $\rightarrow$일 때, $o((\varphi \square \psi))=max(o(\varphi), o(\psi))+1$,
(3) $\square$에 들어가는 논리연산자가 $\neg$, $\forall$, $\exists$일 때, $o((\square \varphi))=o(\varphi)+1$.
위 정의에서 $max(o(\varphi), o(\psi))$는 $\varphi$의 위계와 $\psi$의 위계 중 가장 큰 위계를 값으로 제시하는 함수입니다. 그리고 왼쪽 괄호의 수에 관한 함수 $l$과 오른쪽 괄호의 수에 관한 함수 $r$을 정의합니다. 먼저 임의의 식 $\varphi$의 왼쪽 괄호의 수에 관한 함수 $l(\varphi$는 다음과 같이 정의됩니다.
(1) $\varphi$가 원자식인 경우, $l(\varphi)=0$,
(2) $l((\neg \varphi))=l(\varphi) + 1$,
(3) $\square$에 들어가는 논리연산자가 $\forall$, $\exists$인 경우, $l((\square)\varphi) = l(\varphi) +1$,
(4) $\square$에 들어가는 논리연산자가 $\wedge$, $\lor$, $\rightarrow$일 때, $l((\varphi \square \psi))=l(\varphi)+l(\psi)$.
마찬가지로 임의의 식 $\varphi$의 오른쪽 괄호의 수에 관한 함수 $r(\varphi)$도 다음과 같이 정의됩니다.
(1) $\varphi$가 원자식인 경우, $r(\varphi)=0$,
(2) $r((\neg \varphi))=r(\varphi) + 1$,
(3) $\square$에 들어가는 논리연산자가 $\forall$, $\exists$인 경우, $r((\square)\varphi) = r(\varphi) +1$,
(4) $\square$에 들어가는 논리연산자가 $\wedge$, $\lor$, $\rightarrow$일 때, $r((\varphi \square \psi))=r(\varphi)+r(\psi)$.
이제 증명을 시작합니다. 임의의 두 식 $\varphi$, $\psi$와 이들의 위계 $o(\varphi)$ 및 $o(\psi)$에 대해, $o(\varphi), o(\psi)<\varphi$이고 $l(\varphi)=r(\varphi)$이며 $l(\psi)=r(\psi)$라고 합시다. 그리고 $\rho$를 위계가 $k$인 식이라고 합시다. (다시 말해, $o(\rho)=k$.)
(i) $\rho$가 $\neg \varphi$이면, $l((\neg \varphi))=l(\varphi)+1$이고 $r((\neg \varphi))=r(\varphi)+1$입니다. $l(\varphi)=r(\varphi)$이므로 $l((\neg varphi))=r((\neg \varphi))$가 됩니다.
(ii) $\rho$가 $\varphi \square \psi$이면 $l((\varphi \square \psi))=l(\varphi)+l(\psi)+1$이고 $r((\varphi \square \psi))=r(\varphi)+r(\psi)+1$입니다. 위 1과 같은 이유에서 $l((\varphi \square \psi))=r((\varphi \square \psi))$가됩니다.
(iii) $\rho$가 $(\square)\varphi$이면 $l((\square)\varphi) = l(\varphi) +1$이고 $r((\square)\varphi) = r(\varphi) +1$이다. $l(\varphi)=r(\varphi)$이므로 $l((\square)\varphi) = r((\square)\varphi)$가됩니다.
(i), (ii), (iii)을 얻었으므로 강한 귀납에 의해 모든 식 $\varphi$는 같은 수의 왼쪽 및 오른쪽 괄호를 지닙니다.
7. 우선 'proper segment'가 무엇인지 'initial segment'가 무엇인지를 형식적으로 잘 정의하는게 중요하다고 생각됩니다. 책을 찾아 봤지만 명확하게 정의하지는 않고 있고요. 문제가 묻는 것은 식이 지니고 있는 마지막 괄호 하나만 빠져도 적형식(well-formed formula)이 되지 않음을 말하는 것으로 보입니다. 6의 결과를 이용해, '모든 적형식은 같은 수의 괄호를 가진다'를 명제로 생각하겠습니다.
명제. 술어 논리의 언어 L의 모든 적형식은 같은 수의 괄호를 가진다. (임의의 식 $\varphi$에 대해, $\varphi$가 적형식이라면 $\varphi$는 같은 수의 괄호를 가진다.)
이제 $\varphi '$을 $\varphi$가 지닌 마지막 괄호를 하나 뺀 식이라고 하자. 그러면 $\varphi '$은 같은 수의 괄호를 가지지 않는다. 위 명제의 후건 부정 형식에 의해 $\varphi '$는 적형식이 아니다.
6번 문제와 유사한 방식으로 $\varphi$가 부정문인지 연언문인지 선언문인지 조건문인지 양화 문장인지에 따라 위 논리로 귀납법을 적용해서 증명을 할 수 있겠습니다.
8. 문제가 요구하는 것은 자유변항을 제외하고 나머지는 같은 두 식을 묘사하는 조건 (a)와 (b)가 같은 조건임을 수학적 귀납법을 통해 보이라는 것으로 보입니다. 각 종류별 식이 자유변항 x를 지니고 있다고 가정하고 위계에 관한 귀납법을 써서 부정문, 조건문, 연언문, 선언문, 양화문장의 경우를 고려해 하나씩 풀어보면 쉽게 답이 나오리라 생각됩니다.
그럼 3장 해설을 마칩니다. 꾸뻑!
댓글