Вывод: введение

Перед началом раздела оцени свою отправную точку. Это короткая самопроверка: она не оценивается, а результат хранится только в твоём браузере.

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$ суть различные формулы. Какую формулу позволяет записать modus ponens, применённый к этим двум строкам?

   Никакую: modus ponens требует антецедента $\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$, если применить modus ponens дважды.

   $(\chi \rightarrow \varphi)$.

   $(\varphi \wedge \chi)$.

8. Вопрос 8Правило замены двойного отрицания (ЗДО) меняет в строке только одно вхождение подформулы и действует на цепочку базового языка. Сколько вхождений подформулы $\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)$.