Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in

Exercise sheet 2

Truth, models, consequence

Truth tables, models, classifying a formula, and proving properties of logical consequence. Chapter 2.

Solution
  1. $p \to q$ is 0 only for $p = 1, q = 0$. When $p$ is false, the implication asserts nothing: it is not contradicted, hence true.
  2. See chapter 2.
  3. The two sides have the same column (1, 1, 0, 1 in the order 00, 01, 10, 11), so the formula is 1 everywhere: it is valid, and $p \to q \equiv \lnot q \to \lnot p$ (contrapositive).
Solution
  1. A model of $A$ is an interpretation in which $A$ is true.
  2. $(p \lor q) \land \lnot(p \land q)$: exactly one of the two is true, so two models, $p = 1, q = 0$ and $p = 0, q = 1$. $(p \to q) \land (q \to r) \land p$: $p = 1$ forces $q = 1$, which forces $r = 1$. A single model: everything at 1.
Solution
  1. $\lnot p \to q \equiv p \lor q$, and $(p \land q) \lor p \lor q \equiv p \lor q$ (absorption). Satisfiable, not valid: false for $p = q = 0$.
  2. $\equiv \lnot(p \lor q) \lor r \equiv (\lnot p \land \lnot q) \lor r$. Satisfiable, not valid: false for $p = 1, r = 0$.
  3. $q \to (p \to q)$ is valid: if $q = 1$, $p \to q$ is 1. An implication whose consequent is valid is valid. Valid.
  4. $\lnot(p \to q) \equiv p \land \lnot q$ and $\lnot q \to \lnot p \equiv p \to q$. We have $(p \land \lnot q) \land (p \to q)$: $p = 1, q = 0$ makes $p \to q$ false. Unsatisfiable.
  5. $(p \land q) \lor (\lnot p \land q) \equiv q$ (distributivity then excluded middle), so the formula is $\equiv p \leftrightarrow q$. Satisfiable, not valid.
  6. The consequent lists the three rows where $p \lor q$ is true: it is $\equiv p \lor q$. The formula is $\equiv p \lor q \to p \lor q$. Valid.
  7. First bracket: $q \lor (r \land \lnot q) \equiv q \lor r$, and $\lnot r \land q$ is absorbed by $q$: $\equiv q \lor r$. Second: $(s \lor p) \lor \lnot(s \lor p) \equiv \top$. Formula $\equiv q \lor r$. Satisfiable, not valid.
  8. Countermodel sought: antecedent true, consequent false. If $p \land s$ is true, $p \lor q$ and $s \lor r$ are too; if $q \land r$ is true, likewise. Failure. Valid.
  9. $\lnot(p \land q) \to r \equiv (p \land q) \lor r$. With $p = q = 1, r = 0$: antecedent true, consequent $0 \lor 0$ false. And it is true for $r = 1$. Satisfiable, not valid.
  10. Countermodel: we would need $q = 0$ and the antecedent true, hence $p = 1$, $r = 0$; but then $q \lor r$ is false. Failure. Valid. (The antecedent is even unsatisfiable: $\lnot r$ and $q \lor r$ force $q$, and $q \to \lnot p$ contradicts $p$.)
Solution
  1. A formula with no model: false in every interpretation.
  2. $p \land \lnot p$; $\lnot(p \lor \lnot p)$; $(p \to q) \land p \land \lnot q$.
  3. If $A$ is satisfiable, $\lnot A$ is not valid (it is false in a model of $A$); nothing more can be said: $\lnot p$ is satisfiable, $\lnot(p \lor \lnot p)$ is not. If $A$ is valid, $\lnot A$ is unsatisfiable.
Solution
  1. Forward direction: let $v$ be a model of $\Sigma$. If $v \vDash A$, $v$ is a model of $\Sigma \cup \{A\}$, so $v \vDash B$, and $A \to B$ is true. Otherwise $A$ is false and $A \to B$ is true. Converse: let $v$ be a model of $\Sigma \cup \{A\}$; then $v \vDash A \to B$ and $v \vDash A$, so $v \vDash B$.
  2. Let $v$ be a model of $\Sigma$: $v \vDash A$ and $v \vDash A \to B$, so $v \vDash B$ by the table of $\to$.
  3. The “$\Leftarrow$” direction is true: if every model of $\Sigma$ makes $A$ true, it makes $A \lor B$ true. The “$\Rightarrow$” direction is false: with $\Sigma = \emptyset$, $A = p$, $B = \lnot p$, we have $\vDash p \lor \lnot p$, but neither $\vDash p$ nor $\vDash \lnot p$.
Solution
  1. sat(P) = not valid(¬P). Indeed $P$ is satisfiable if and only if $\lnot P$ is not valid (chapter 2).
  2. valid(P) = not sat(¬P): $P$ is valid if and only if $\lnot P$ is unsatisfiable. The two problems are therefore as hard as each other.