의미론: 도입

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

1. 문제 1이전 단원에서논리식 위의 함수는 각 변항에서의 값과, $\sigI\varphi\psi$에서의 값을 $\varphi$, $\psi$, 그리고 둘에서의 값으로부터 계산하는 규칙을 주어 정의된다. 이렇게 해서 함수가 정확히 하나 정의된다는 것을 보장하는 것은 무엇인가?

   유일 판독성. 곧 모든 복합 논리식은 첫 원판과 두 성분으로 단 한 가지 방식으로만 분해된다.

   규칙이 언제나 $0$ 또는 $1$을 돌려준다는 것.

   아무것도 없다. 논리식마다 값을 확인해야 하는데, 논리식은 무한히 많으므로 그럴 수 없다.

   약어 $\neg$, $\vee$, $\wedge$도 유일 판독성을 갖는다는 것.

2. 문제 2이전 단원에서강좌의 공식 약어에 따르면, $(\varphi \vee \varphi)$는 어떤 논리식인가?

   $\neg\neg\varphi$와 같은 기호열.

   멱등 법칙에 의해, $\varphi$ 자체.

   $(\varphi \downarrow \varphi)$.

   어느 것도 아니다. 선언에는 서로 다른 두 논리식이 필요하다.

3. 문제 3이전 단원에서모든 논리식이 어떤 성질을 가진다는 것을 복잡도에 관한 귀납법으로 증명하려면, 어떤 경우들을 다루어야 하는가?

   변항들과 유일한 형성 규칙 $\sigI\varphi\psi$, 곧 $(\varphi \downarrow \psi)$.

   변항들, 부정, 연언, 선언.

   규칙 $(\varphi \downarrow \psi)$뿐이다. 변항들은 그 특수한 경우이다.

   변항들과 여섯 연결사 $\neg$, $\vee$, $\wedge$, $\rightarrow$, $\leftrightarrow$, $\veebar$.

4. 문제 4이전 단원에서귀납법 수업의 정의에 따라 논리식 $\alpha$ 대신 논리식 $\beta$를 $\varphi$에 대입할 때, $\alpha$의 어떤 출현들이 바뀌는가?

   부분식으로서의 모든 출현이 동시에 바뀐다.

   기호열을 왼쪽에서 오른쪽으로 읽을 때 첫째 출현만.

   약어로 쓴 표기에서 보이는 출현만.

   $\alpha$의 출현들, 그리고 그다음 $\beta$의 사본에 나타나는 출현들.

5. 문제 5어떤 진리값 할당이 $p$에 값 $0$을, $q$에 값 $1$을 준다. $(\varphi \downarrow \psi)$가 값 $1$을 취하는 것이 정확히 $\varphi$와 $\psi$가 값 $0$을 취할 때라면, 논리식 $(p \downarrow (q \downarrow p))$는 어떤 값을 취하는가?

   $1$.

   $0$. $q$의 값이 $1$이기 때문이다.

   다른 변항들의 값을 모르면 계산할 수 없다.

   성분들을 어떻게 묶느냐에 달려 있다.

6. 문제 6$\not\models \varphi$는 무엇을 뜻하는가?

   어떤 진리값 할당이 $\varphi$에 값 $0$을 준다는 것. 곧 $\varphi$는 타당하지 않다.

   $\varphi$가 모순식이라는 것.

   어떤 진리값 할당도 $\varphi$를 충족하지 않는다는 것.

   $\varphi$가 강좌의 체계에서 연역되지 않는다는 것.

7. 문제 7$\Gamma \cup \{\varphi\} \models \psi$임을 알고 있다. 곧 $\Gamma$와 $\varphi$를 충족하는 모든 진리값 할당은 $\psi$를 충족한다. 무엇이 따라 나오는가?

   $\Gamma \models (\varphi \rightarrow \psi)$.

   $\Gamma \models \psi$.

   $\Gamma \models (\psi \rightarrow \varphi)$.

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

8. 문제 8논리식 $(v_{1} \vee \neg v_{1})$은 타당하다. 균일 대입 정리에 의해 타당한 것은 다음 논리식 가운데 어느 것인가?

   $(\neg v_{2} \vee \neg\neg v_{2})$.

   $(v_{1} \vee \neg v_{2})$.

   $(\neg v_{2} \vee \neg v_{3})$.

   어느 것도 아니다. 균일 대입은 어떤 변항을 다른 변항으로 바꾸는 것만 허용한다.

9. 문제 9강좌의 규약에 따르면, 괄호 없이 쓴 표현 $v_{1} \wedge v_{2} \wedge v_{3}$은 어떤 논리식을 나타내는가?

   $((v_{1} \wedge v_{2}) \wedge v_{3})$.

   $(v_{1} \wedge (v_{2} \wedge v_{3}))$.

   두 묶음 모두. 같은 기호열이기 때문이다.

   어느 것도 아니다. 괄호가 없으면 표현은 아무것도 나타내지 않는다.

10. 문제 10두 인자의 진리 함수는 값 $0$ 또는 $1$을 네 행 $(1, 1)$, $(1, 0)$, $(0, 1)$, $(0, 0)$ 각각에 배정한다. 두 인자의 진리 함수는 몇 개 있는가?

11. 문제 11변항들로부터 $\wedge$와 $\vee$만으로 쓴 논리식이 값 $0$을 취할 수 있는가? 여기서 진리값 할당은 모든 변항에 $1$을 주는 것이다.

    없다. $\wedge$와 $\vee$만으로 쓴 논리식은 모두 이 진리값 할당에서 값 $1$을 취한다.

    있다. 연언과 선언을 충분히 겹겹이 넣으면 된다.

    있다. 부정논리합 하나만으로 충분하니, 연언과 선언으로도 충분하다.

    각 논리식의 표를 써 보지 않고는 알 수 없다.

12. 문제 12리터럴은 변항이거나 변항의 부정이다. 다음 논리식 가운데 리터럴은 어느 것인가?

    $\neg v_{2}$.

    $\neg\neg v_{1}$.

    $(v_{1} \wedge v_{2})$.

    $\top$.

13. 문제 13연언 표준형 $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$는 타당한가?

    아니다. 둘째 절은 상보 쌍을 하나도 포함하지 않으며, $0$을 $v_{3}$에, $1$을 $v_{2}$에 주는 진리값 할당이 이것을 반박한다.

    그렇다. 첫째 절이 상보 쌍을 포함하며, 하나면 충분하다.

    그렇다. 충족 가능하기 때문이다.

    여덟 행의 표 없이는 결정할 수 없다.

14. 문제 14논리식을 선언 표준형으로 만들려면 연언을 선언 위에 분배한다. 올바른 규칙은 어느 것인가?

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$.

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \vee \chi))$.

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$.

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee \chi)$.

15. 문제 15어떤 회로에는 레버 $p$와 $q$의 정방향 스위치 두 개가 직렬로 연결되어 있고, 이 묶음이 레버 $r$의 정방향 스위치와 병렬로 연결되어 있다. 회로가 언제 도통하는지 말하는 논리식은 어느 것인가?

    $((p \wedge q) \vee r)$.

    $((p \vee q) \wedge r)$.

    $((p \wedge q) \wedge r)$.

    $((p \vee q) \vee r)$.