Семантика: введение

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

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)$.