연역: 도입

단원을 시작하기 전에 출발점을 확인해 보세요. 짧은 자기 평가입니다. 점수가 매겨지지 않으며 결과는 브라우저에만 저장됩니다.

1. 문제 1이전 단원에서기호열 $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$은 $\sigI\varphi\psi$ 꼴의 복합 논리식이다. 그 성분 $\varphi$와 $\psi$는 무엇인가?

   $\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$, $\psi = \sigO\sigI$.

   $\varphi = \sigI\sigO\sigI$, $\psi = \sigO\sigO\sigI\sigO\sigI$.

   첫 원판 뒤에서 기호열을 어디서 자르느냐에 따라 두 가지 분해를 허용한다.

   $\varphi$는 첫 원판 뒤에 오는 기호열 전체이고, $\psi$는 빈 기호열이다.

2. 문제 2이전 단원에서모든 자연수 $n$이 성질 $P(n)$을 가짐을 강한 귀납법으로 증명할 때, $P(n)$을 증명하는 단계에서 무엇을 가정할 수 있는가?

   $P(m)$이 모든 자연수 $m$(단, $n$보다 작은 것)에 대해 성립한다는 것.

   $P(n - 1)$이 성립한다는 것만.

   $P(m)$이 모든 자연수 $m$(단, $n$ 이하인 것)에 대해 성립한다는 것.

   $P(1)$과 $P(2)$를 따로 증명하기 전에는 아무것도 가정할 수 없다.

3. 문제 3이전 단원에서이 강좌의 공식 약어로, $(\varphi \rightarrow \psi)$는 부정논리합과 부정으로 쓰면 어떤 논리식을 나타내는가?

   $\neg(\neg\varphi \downarrow \psi)$.

   $(\neg\varphi \downarrow \psi)$.

   $\neg(\varphi \downarrow \neg\psi)$.

   특정한 논리식은 없다. 어떻게 읽기로 정하느냐에 달려 있다.

4. 문제 4도식 A1은 $(\varphi \rightarrow (\psi \rightarrow \varphi))$이다. 논리식 $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$은 A1의 대입례인가?

   아니다. $\varphi$의 첫 출현과 마지막 출현에는 같은 논리식이 대입되어야 하는데, 여기서는 그것이 $v_{1}$과 $v_{3}$이다.

   그렇다. $\varphi := v_{1}$, $\psi := v_{2}$로 하면 된다.

   그렇다. 후건이 또 다른 함의인 함의는 모두 A1의 대입례이기 때문이다.

   아니다. 도식의 대입례는 변항을 포함할 수 없기 때문이다.

5. 문제 5어떤 연역에 행 $\psi$와 $(\varphi \rightarrow \psi)$가 이미 있으며, 여기서 $\varphi$와 $\psi$는 서로 다른 논리식이다. 이 두 행에 전건 긍정식을 적용하면 어떤 논리식을 쓸 수 있는가?

   없다. 전건 긍정식은 전건 $\varphi$를 요구하는데, 가진 것은 후건이다.

   $\varphi$.

   $(\psi \rightarrow \varphi)$.

   $\neg\varphi$.

6. 문제 6$\{\varphi\} \vdash \psi$, 곧 $\psi$의 연역으로서 유일한 전제가 $\varphi$인 것이 있다는 것이 알려져 있다. 그러면 연역 정리는 무엇을 주장하는가?

   $\vdash (\varphi \rightarrow \psi)$라는 것. 그 함의는 정리이다.

   $\vdash \psi$라는 것. 전제는 그냥 지워도 된다.

   $\vdash (\psi \rightarrow \varphi)$라는 것.

   $\{\psi\} \vdash \varphi$라는 것.

7. 문제 7다른 전제 없이 집합 $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$에서 무엇이 연역되는가?

   $(\varphi \rightarrow \chi)$.

   전건 긍정식을 두 번 적용하여, $\chi$.

   $(\chi \rightarrow \varphi)$.

   $(\varphi \wedge \chi)$.

8. 문제 8이중 부정 대체 규칙(RDN)은 한 행에서 부분식의 단 한 출현만 바꾸며, 기본 언어의 기호열에 작용한다. 부분식 $\neg v_{1}$은 $(v_{1} \rightarrow v_{2})$가 나타내는 기호열 안에 몇 번 나타나는가?

   두 번.

   한 번, 전건에 해당하는 것.

   한 번도 없다. 그 논리식은 부정을 포함하지 않는다.

   네 번.

9. 문제 9$(\neg\varphi \rightarrow \psi)$에서 대우로, 이중 부정을 덧붙이지 않고, 어떤 논리식을 얻는가?

   $(\neg\psi \rightarrow \varphi)$.

   $(\psi \rightarrow \neg\varphi)$.

   $(\varphi \rightarrow \neg\psi)$.

   $(\neg\psi \rightarrow \neg\varphi)$.

10. 문제 10$(\varphi \vee \psi)$와 $(\neg\varphi \rightarrow \psi)$는 같은 논리식을 나타내는가?

    아니다. 앞의 것은 $\neg(\varphi \downarrow \psi)$이고 뒤의 것은 $\neg(\neg\neg\varphi \downarrow \psi)$이다. 서로 다른 논리식이며, 증명 가능하게 동치이다.

    그렇다. 함의의 정의에 의해.

    그렇다. 둘 다 “$\varphi$ 또는 $\psi$”로 읽히기 때문이다.

    아니다. 그리고 어느 쪽도 다른 쪽에서 연역되지 않는다.

11. 문제 11$\varphi \dashv\vdash \varphi'$, 곧 각각이 다른 것에서 연역된다는 것이 알려져 있다. $\neg\varphi \dashv\vdash \neg\varphi'$이기도 하다는 것을 무엇이 정당화하는가?

    하나의 정리, 곧 동치 대체이며, 이것은 연역 정리와 대우로 증명된다.

    특별한 정당화는 필요 없다. 동치의 “양변을 부정하기”만으로 충분하다.

    부정의 정의. $\neg\varphi$는 $(\varphi \downarrow \varphi)$이기 때문이다.

    아무것도 정당화하지 않는다. 그것은 참이 아니기 때문이다. 부정은 동치인 논리식들을 갈라놓을 수 있다.

12. 문제 12전제 집합 $\Gamma \cup \{\neg\varphi\}$에서 논리식 $\chi$와 그 부정 $\neg\chi$가 연역된다. 무엇을 결론지을 수 있는가?

    $\Gamma \vdash \varphi$.

    $\Gamma \vdash \neg\varphi$.

    $\Gamma$에서 임의의 논리식이 연역된다는 것.

    아무것도 없다. 모순에 이르는 연역은 아무것도 증명하지 않는다.

13. 문제 13함의의 부정 $\neg(\varphi \rightarrow \psi)$는 어떤 논리식과 동치인가?

    $(\varphi \wedge \neg\psi)$와 동치이다.

    $(\neg\varphi \rightarrow \neg\psi)$와 동치이다.

    $(\varphi \rightarrow \neg\psi)$와 동치이다.

    $(\neg\varphi \wedge \psi)$와 동치이다.