Метатеория: введение

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

1. Вопрос 1Из предыдущих разделовЧто означает $\Gamma \models \varphi$?

   Что всякая оценка, выполняющая все формулы из $\Gamma$, выполняет $\varphi$.

   Что существует вывод $\varphi$ из $\Gamma$.

   Что некоторая оценка выполняет одновременно $\Gamma$ и $\varphi$.

   Что $\varphi$ следует из какой-то одной формулы из $\Gamma$, взятой отдельно.

2. Вопрос 2Из предыдущих разделовКакое из следующих утверждений равносильно $\Gamma \models \varphi$?

   Что $\Gamma \cup \{\neg\varphi\}$ невыполнимо.

   Что $\Gamma \cup \{\varphi\}$ выполнимо.

   Что $\Gamma \cup \{\neg\varphi\}$ выполнимо.

   Что $\neg\varphi$ невыполнима.

3. Вопрос 3Из предыдущих разделовЕсли оценка $v$ даёт формуле $\alpha$ значение $1$, какое значение она даёт формуле $(\alpha \downarrow \beta)$?

   $0$, каким бы ни было значение $\beta$.

   Зависит от $\beta$: значение равно $1$, если $\beta$ имеет значение $0$.

   $1 - v(\beta)$.

   $1$, потому что одна из компонент истинна.

4. Вопрос 4Из предыдущих разделовПеременные формулы $\varphi$ суть $v_{2}$ и $v_{7}$. Две оценки $v$ и $w$ дают одинаковые значения переменным $v_{2}$ и $v_{7}$ и противоположные значения всем остальным переменным. Если $v(\varphi) = 1$, что можно утверждать о $w(\varphi)$?

   Что $w(\varphi) = 1$.

   Ничего, потому что $v$ и $w$ различаются на бесконечном числе переменных.

   Что $w(\varphi) = 0$, потому что $w$ меняет на противоположные почти все значения $v$.

   Что $w(\varphi) = 1$, только если $v$ и $w$ совпадают также на $v_{1}, \ldots, v_{6}$.

5. Вопрос 5Из предыдущих разделовПусть $\Gamma$ есть бесконечное множество формул, такое что $\Gamma \vdash \varphi$. Что можно утверждать?

   Что некоторое конечное подмножество $\Gamma$ выводит $\varphi$.

   Что $\varphi$ является теоремой.

   Что вывод использует все формулы из $\Gamma$.

   Ничего без теоремы компактности, потому что $\Gamma$ бесконечно.

6. Вопрос 6Из предыдущих разделовИзвестно, что $\Gamma \cup \{p\} \vdash \chi$ и что $\Gamma \cup \{\neg p\} \vdash \chi$. Что позволяет заключить разбор случаев?

   Что $\Gamma \vdash \chi$.

   Ничего, пока неизвестно, выводит ли $\Gamma$ формулу $p$ или выводит $\neg p$.

   Что $\Gamma \vdash (p \leftrightarrow \chi)$.

   Только что $\Gamma \cup \{p, \neg p\} \vdash \chi$.

7. Вопрос 7Система курса корректна. Что утверждает это свойство?

   Что для всякого множества $\Gamma$, если $\Gamma \vdash \varphi$, то $\Gamma \models \varphi$.

   Что если $\Gamma \models \varphi$, то $\Gamma \vdash \varphi$.

   Что не существует формулы $\varphi$, для которой $\vdash \varphi$ и $\vdash \neg\varphi$.

   Что всякая истинная формула есть теорема.

8. Вопрос 8Пусть $v$ есть оценка, которая даёт $1$ переменной $p$ и $0$ переменной $q$. Что утверждает лемма Кальмара с переменными $p$ и $q$ для формулы $(p \leftrightarrow q)$?

   Что $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$.

   Что $\{p, \neg q\} \vdash (p \leftrightarrow q)$.

   Что $\{p, q\} \vdash \neg(p \leftrightarrow q)$.

   Что $\vdash \neg(p \leftrightarrow q)$.

9. Вопрос 9Может ли дедуктивная система быть корректной, не будучи полной?

   Да: система Лукасевича без правила ЗДО корректна и не выводит тавтологию $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$.

   Нет: корректность и полнота выводятся одна из другой.

   Нет: система, аксиомы которой суть тавтологии, выводит все тавтологии.

   Да, но только если система противоречива.

10. Вопрос 10Что утверждает теорема компактности?

    Что множество формул выполнимо тогда и только тогда, когда выполнимо всякое его конечное подмножество.

    Что множество формул выполнимо тогда и только тогда, когда выполнима каждая его формула.

    Что всякое бесконечное множество формул выполнимо.

    Что множество выполнимо, если выполнимо какое-нибудь его конечное подмножество.

11. Вопрос 11Пусть $\Gamma$ есть бесконечное множество формул, такое что $\Gamma \models \varphi$. Что гарантирует компактность?

    Что $\Gamma_{0} \models \varphi$ для некоторого конечного подмножества $\Gamma_{0}$ множества $\Gamma$.

    Что $\varphi$ следует из какой-то одной формулы из $\Gamma$, взятой отдельно.

    Что $\varphi$ следует из всякого конечного подмножества $\Gamma$.

    Что $\varphi$ общезначима.

12. Вопрос 12Первый урок доказывает полноту для конечных множеств посылок. Почему конечности вывода недостаточно, чтобы распространить её на бесконечное множество $\Gamma$?

    Потому что конечность говорит о $\Gamma \vdash \varphi$, а имеется $\Gamma \models \varphi$: нужно, чтобы к конечной части сводилось следование, а не вывод, и это есть компактность.

    Достаточно: если $\Gamma \models \varphi$, конечность даёт конечное $\Gamma_{0}$ с $\Gamma_{0} \models \varphi$.

    Потому что лемма Кальмара неверна для формул с бесконечным числом переменных.

    Потому что полнота ложна для бесконечных множеств посылок.

13. Вопрос 13Какова резольвента дизъюнктов $\{p, \neg q, r\}$ и $\{q, s\}$?

    $\{p, r, s\}$.

    $\{p, \neg q, r, q, s\}$.

    $\{p, r\}$.

    У них нет резольвенты, потому что у них нет общего литерала.

14. Вопрос 14Какое множество дизъюнктов пытаются опровергнуть, чтобы решить резолюцией, верно ли, что $\{(p \vee q), \neg p\} \models q$?

    $\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$.

    $\{\{p, q\}, \{\neg p\}, \{q\}\}$.

    $\{\{p, q\}, \{\neg p\}\}$.

    $\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$.

15. Вопрос 15Можно ли резолюцией породить пустой дизъюнкт $\Box$ из множества $\{\{p, q\}, \{\neg p, \neg q\}\}$?

    Нет: множество выполнимо, а резолюция корректна.

    Да, за один шаг, удалив сразу обе контрарные пары.

    Да, за два шага: сначала по $p$, затем по $q$.

    Нет, потому что ни один из двух дизъюнктов не является единичным.