Semantics: introduction

Before starting the unit, measure your starting point. It is a short self-assessment: it is not graded and its result is stored only in your browser.

1. Question 1From earlier unitsA function on formulas is defined by giving its value at each variable and a rule that computes the value of $\sigI\varphi\psi$ from $\varphi$, from $\psi$ and from the values of both. What guarantees that exactly one function is thus defined?

   Unique readability: each compound formula decomposes in only one way into its initial disk and its two components.

   That the rule always returns $0$ or $1$.

   Nothing: the value would have to be checked formula by formula, and since there are infinitely many, this cannot be done.

   That the abbreviations $\neg$, $\vee$ and $\wedge$ also have unique readability.

2. Question 2From earlier unitsWith the official abbreviations of the course, which formula is $(\varphi \vee \varphi)$?

   The same string as $\neg\neg\varphi$.

   $\varphi$ itself, by idempotence.

   $(\varphi \downarrow \varphi)$.

   None: a disjunction requires two different formulas.

3. Question 3From earlier unitsTo prove by induction on complexity that all formulas have a certain property, which cases must be treated?

   The variables and the single formation rule, $\sigI\varphi\psi$, that is, $(\varphi \downarrow \psi)$.

   The variables, negation, conjunction and disjunction.

   Only the rule $(\varphi \downarrow \psi)$: the variables are a particular case.

   The variables and the six connectives $\neg$, $\vee$, $\wedge$, $\rightarrow$, $\leftrightarrow$ and $\veebar$.

4. Question 4From earlier unitsWhen substituting the formula $\alpha$ by the formula $\beta$ in $\varphi$, according to the definition of the lesson on induction, which occurrences of $\alpha$ are changed?

   All its occurrences as a subformula, at once.

   Only the first, reading the string from left to right.

   Only those visible in the abbreviated writing.

   Those of $\alpha$ and, afterwards, those that appear in the copies of $\beta$.

5. Question 5A valuation gives $p$ the value $0$ and $q$ the value $1$. If $(\varphi \downarrow \psi)$ has the value $1$ exactly when $\varphi$ and $\psi$ have the value $0$, what value does the formula $(p \downarrow (q \downarrow p))$ take?

   $1$.

   $0$, because $q$ has the value $1$.

   It cannot be calculated without knowing the values of the other variables.

   It depends on how the components are grouped.

6. Question 6What does $\not\models \varphi$ mean?

   That some valuation gives $\varphi$ the value $0$: $\varphi$ is not valid.

   That $\varphi$ is a contradiction.

   That no valuation satisfies $\varphi$.

   That $\varphi$ is not derivable in the course system.

7. Question 7It is known that $\Gamma \cup \{\varphi\} \models \psi$: every valuation that satisfies $\Gamma$ and $\varphi$ satisfies $\psi$. What follows?

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

   $\Gamma \models \psi$.

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

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

8. Question 8The formula $(v_{1} \vee \neg v_{1})$ is valid. Which of the following formulas is valid by the uniform substitution theorem?

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

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

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

   None: uniform substitution only allows variables to be changed into other variables.

9. Question 9By the convention of the course, which formula does the expression $v_{1} \wedge v_{2} \wedge v_{3}$, written without parentheses, designate?

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

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

   Both groupings, because they are the same string.

   None: without parentheses the expression designates nothing.

10. Question 10A truth function of two arguments assigns a value, $0$ or $1$, to each of the four rows $(1, 1)$, $(1, 0)$, $(0, 1)$ and $(0, 0)$. How many truth functions of two arguments are there?

11. Question 11Can a formula written only with $\wedge$ and $\vee$ from the variables have the value $0$ in the valuation that gives $1$ to all the variables?

    No: every formula written only with $\wedge$ and $\vee$ has the value $1$ in that valuation.

    Yes, if enough conjunctions and disjunctions are nested.

    Yes: since joint denial suffices by itself, conjunction and disjunction also suffice.

    It cannot be known without writing the table of each formula.

12. Question 12A literal is a variable or the negation of a variable. Which of the following formulas is a literal?

    $\neg v_{2}$.

    $\neg\neg v_{1}$.

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

    $\top$.

13. Question 13Is the conjunctive normal form $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$ valid?

    No: the second clause contains no complementary pair, and the valuation that gives $0$ to $v_{3}$ and $1$ to $v_{2}$ refutes it.

    Yes: the first clause contains a complementary pair, and one is enough.

    Yes, because it is satisfiable.

    It cannot be decided without an eight-row table.

14. Question 14To bring a formula to disjunctive normal form, conjunction is distributed over disjunction. Which is the correct rule?

    $(\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. Question 15A circuit has two direct switches, of the levers $p$ and $q$, joined in series, and that block is in parallel with a direct switch of the lever $r$. Which formula says when it conducts?

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

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

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

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