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

Exercise sheet 3

Normal forms

Putting formulas into CNF and DNF, by computation and by truth table, and expressing constraints with only three connectives. Chapter 3.

Solution
  1. $\lnot(p \to q) \lor \lnot\lnot(r \lor s) \equiv (p \land \lnot q) \lor r \lor s$.
  2. $\lnot(\lnot p \lor \lnot q \lor \lnot r) \equiv p \land q \land r$.
Solution
  1. Distribution: $(p \lor \lnot p \lor q) \land (p \lor r)$. The first clause is a tautology: CNF $p \lor r$.
  2. Distribution: $(\lnot p \lor p \lor \lnot q) \land (q \lor p \lor \lnot q)$. Both clauses are tautologies: the formula is valid, its CNF is the empty conjunction, $\top$ (one can write the clause $p \lor \lnot p$).
  3. $(p \land \lnot q) \lor p \lor q \equiv p \lor q$ (absorption of $p \land \lnot q$ by $p$). CNF $p \lor q$.
Solution
  1. $\lnot p \lor \lnot(q \land r) \lor s \equiv \lnot p \lor \lnot q \lor \lnot r \lor s$: four monomials of one literal each.
  2. $(\lnot p \land q) \land (\lnot s \lor t) \equiv (\lnot p \land q \land \lnot s) \lor (\lnot p \land q \land t)$.
  3. $(\lnot p \lor \lnot q) \land (p \lor q)$, then distribution: $(\lnot p \land p) \lor (\lnot p \land q) \lor (\lnot q \land p) \lor (\lnot q \land q)$. The contradictory monomials drop out: $(\lnot p \land q) \lor (p \land \lnot q)$, exclusive or.
Solution
  1. True for 011, 101, 110, 111 (in the order $p, q, r$).
  2. DNF: $(\lnot p \land q \land r) \lor (p \land \lnot q \land r) \lor (p \land q \land \lnot r) \lor (p \land q \land r)$. CNF from the rows at 0 (000, 001, 010, 100): $(p \lor q \lor r) \land (p \lor q \lor \lnot r) \land (p \lor \lnot q \lor r) \land (\lnot p \lor q \lor r)$.
  3. $(p \land q) \lor (p \land r) \lor (q \land r)$. The CNF simplifies likewise into $(p \lor q) \land (p \lor r) \land (q \lor r)$.
Solution
  1. $(p \land \lnot q) \lor (\lnot p \land q)$, in CNF $(p \lor q) \land (\lnot p \lor \lnot q)$.
  2. DNF: $(A \land \lnot B \land \lnot C) \lor (\lnot A \land B \land \lnot C) \lor (\lnot A \land \lnot B \land C)$. CNF: $(A \lor B \lor C) \land (\lnot A \lor \lnot B) \land (\lnot A \lor \lnot C) \land (\lnot B \lor \lnot C)$.
  3. One “at least one” clause and one clause per pair, that is $1 + \frac{n(n-1)}{2}$.
Solution
  1. $\lnot p \equiv p \uparrow p$; $p \land q \equiv \lnot(p \uparrow q) \equiv (p \uparrow q) \uparrow (p \uparrow q)$; $p \lor q \equiv \lnot p \uparrow \lnot q \equiv (p \uparrow p) \uparrow (q \uparrow q)$.
  2. $\{\lnot, \land, \lor\}$ is complete (every formula has a DNF), and each of its connectives can be written with $\uparrow$.