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

Exercise sheet 1

Reading and writing formulas

Parentheses, precedence, syntax trees, and the boundary between formulas and statements about formulas. Chapter 1.

The conventions are those of chapter 1: $\lnot > \land > \lor > \to > \leftrightarrow$, and $\to$ associates to the right.

Solution
  1. $\lnot\lnot p \to q \lor r$
  2. $\lnot(\lnot p \to q \lor r)$. The negation applies to the whole implication: its parentheses stay.
  3. $p \land q \lor r \to p \to q$. All the parentheses go: since $\to$ associates to the right, $\ldots \to p \to q$ does read as $\ldots \to (p \to q)$. The trap is to believe they are needed; the tree settles it.
  4. $(p \to q) \to r$. Here the parentheses are compulsory: $p \to q \to r$ would read $p \to (q \to r)$.
  5. $\lnot(p \land q) \leftrightarrow \lnot p \lor \lnot q$
Solution
  1. $(((p \to (q \lor r)) \land (q \to r)) \to (p \to r))$. Main connective: the middle $\to$.
  2. $((((\lnot p) \land q) \to r) \leftrightarrow ((\lnot r) \to ((\lnot q) \lor p)))$. Main connective: $\leftrightarrow$, the one with the lowest precedence.
  3. $(p \to (q \to (r \to s)))$. Main connective: the first $\to$.
Solution
  1. Root $\to$; on the left $\lnot$ above $\land(p, q)$; on the right $\lor$ above $\lnot p$ and $\lnot q$.
  2. $A$, $\lnot(p \land q)$, $p \land q$, $\lnot p \lor \lnot q$, $\lnot p$, $\lnot q$, $p$, $q$ (the occurrences of $p$ and of $q$ give the same subformulas).
  3. Connectives: $\to, \lnot, \land, \lor, \lnot, \lnot$, that is 6, of which 3 are binary. Occurrences of variables: 4. In a tree where each binary connective has two children, there is always one more leaf than there are binary connectives: $4 = 3 + 1$. The $\lnot$ do not change this count.
Solution
  1. Formula.
  2. Statement, true: every model of $p$ makes $p \lor q$ true.
  3. Statement, false: the right-hand side is equivalent to $q$, and $p \not\equiv q$. The formula that was probably meant is $p \leftrightarrow (p \land q) \lor (\lnot p \land q)$; one can ask whether it is valid.
  4. Statement, true: the right-hand side is equivalent to $p \lor q$.
  5. Neither: no rule produces $p \land \lor q$.
  6. Statement, true: $p \to p$ is valid.
Solution
  1. $p \to q$
  2. $r \to p$ (“only if”: the necessary condition is on the right).
  3. $\lnot\lnot p \to q$, that is $p \to q$: the same thing as sentence 1.
  4. $\lnot p \land r$
  5. $\lnot r \land \lnot q$