Tutorial list 2

1

Truth table for $p|p$:

interpretation	$p$	$p\Vert p$
$v_0$	0	1
$v_1$	1	0

• Let $\neg A$ be $A|A$.

  $A$	$\neg A$
  0	1
  1	0

• Let $A\wedge B$ be $(A|B)|(A|B)$.

  $A$	$B$	$A|B$	$(A|B)|(A|B)$
  0	0	1	0
  0	1	1	0
  1	0	1	0
  1	1	0	1

• Let $A\vee B$ be $(A|A)|(B|B)$.

  $a$	$b$	$b|b$	$a|a$	$(a|a)|(b|b)$
  0	0	1	1	0
  0	1	0	1	1
  1	0	1	0	1
  1	1	0	0	1

• Let $A\to B$ be $A|(B|B)$.

  $a$	$b$	$b|b$	$a|(b|b)$
  0	0	1	1
  0	1	0	1
  1	0	1	0
  1	1	0	1

2

Consider $(p\vee (\neg r))\to (\neg ((\neg q)\vee r))$

interpretation	$p$	$r$	$q$	$\neg q$	$(\neg q)\vee r$	$\neg ((\neg q)\vee r)$	$\neg r$	$p\vee (\neg r)$	$(p\vee (\neg r))\to (\neg ((\neg q)\vee r))$
$v_0$	0	0	0	1	1	0	1	1	0
${\text{v}}_1$	0	0	1	0	0	1	1	1	1
${\text{v}}_2$	0	1	0	1	1	0	0	0	1
${\text{v}}_3$	0	1	1	0	1	0	0	0	1
$v_4$	1	0	0	1	1	0	1	1	0
${\text{v}}_5$	1	0	1	0	0	1	1	1	1
$v_6$	1	1	0	1	1	0	0	1	0
$v_7$	1	1	1	0	1	0	0	1	0

i

a. Write in CNF:

$$\begin{array}{rl}& \neg ((\neg p\wedge \neg r\wedge \neg q)\vee (p\wedge \neg r\wedge \neg q)\vee (p\wedge r\wedge \neg q)\vee (p\wedge r\wedge q))\\ & =\neg ((\neg r\wedge \neg q)\vee (p\wedge r))\\ & =\neg (\neg (r\vee q)\vee \neg \neg (p\wedge r))\\ & =\neg (\neg (r\vee q)\vee \neg (\neg p\vee \neg r))\\ & =\neg \neg ((r\vee q)\wedge (\neg p\vee \neg r))\\ & =(r\vee q)\wedge (\neg p\vee \neg r)\end{array}$$

b. Write in DNF:

$$\begin{array}{rl}(\neg P\wedge \neg Q\wedge R)\vee (\neg P\wedge Q\wedge \neg R)\vee (\neg P\wedge Q\wedge R)\vee (P\wedge Q\wedge \neg R)& \\ & \\ & (\neg p\wedge \neg r\wedge q)\vee (\neg p\wedge r\wedge \neg q)\vee (\neg p\wedge r\wedge q)\vee (p\wedge \neg r\wedge q)\\ & =(\neg p\wedge ((\neg r\wedge q))\vee (r\wedge \neg q)\vee (r\wedge q))\vee (p\wedge \neg r\wedge q)\\ & =(\neg r\wedge q)\vee r\vee (p\wedge \neg r\wedge q)\\ & =(\neg r\wedge q)\vee r\end{array}$$

ii

Rewrite $(p\vee (\neg r))\to (\neg ((\neg q)\vee r))$ to DNF using the rewrite rules.

$$\begin{array}{rl}(P\vee Q\vee R)\wedge (\neg P\vee Q\vee R)\wedge (\neg P\vee Q\vee \neg R)\wedge (\neg P\vee \neg Q\vee \neg R)& \\ & \\ p\vee \neg r& \to \neg (\neg q\vee r)\\ p\vee \neg r& \to \neg \neg q\wedge \neg r\\ p\vee \neg r& \to q\wedge \neg r\\ \neg (p\vee \neg r)& \vee (q\wedge \neg r)\\ (\neg p\wedge r)& \vee (q\wedge \neg r)\end{array}$$

3

Rewrite the following propositional formula:

$$(P\to Q)\wedge \neg (S\to R)$$

i. In CNF:

$$\begin{array}{rl}(P\to Q)& \wedge \neg (S\to R)\\ \neg P\wedge Q& \wedge \neg (\neg S\vee R)\\ \neg P\wedge Q& \wedge S\wedge \neg R\end{array}$$

ii. In DNF:

$$\begin{array}{rl}(P\to Q)& \wedge \neg (S\to R)\\ \neg P\wedge Q& \wedge S\wedge \neg R\\ (\neg P\wedge S\wedge \neg R)& \vee (Q\wedge S\wedge \neg R)\end{array}$$

See Distributive laws (Logic).