Tutorial list 3

1

Consider $\downarrow$ defined by:

interpretation	$p$	$q$	$p\downarrow q$
$v_0$	0	0	1
$v_1$	0	1	0
$v_2$	1	0	0
$v_3$	1	1	0

1. Show that $P\downarrow Q$ is logically equivalent to $\neg (P\vee Q)$

   interpretation	$p$	$q$	$p\vee q$	$\neg (p\vee q)$
   $v_0$	0	0	0	1
   $v_1$	0	1	1	0
   $v_2$	1	0	1	0
   $v_3$	1	1	1	0

title: Correct answer.

2. Show that $P\downarrow P$ is logically equivalent to $\neg P$.

   interpretation	$p$	$p\downarrow p$	$\neg p$
   $v_0$	0	1	1
   $v_1$	1	0	0

title: Correct answer.

3. Show that the connective $\downarrow$ is adequete for propositional logic.

   We have already shown that $\neg P\equiv P\downarrow P$. We need to show that $a\wedge b$ and $a\vee b$ can be represented using $\downarrow$.

   $$\begin{array}{rl}a\wedge b& =\neg a\downarrow \neg b\\ & =(a\downarrow a)\downarrow (b\downarrow b)\end{array}$$

   interpretation	$a$	$b$	$b\downarrow b$	$a\downarrow a$	$(a\downarrow a)\downarrow (b\downarrow b)$	$a\wedge b$
   $v_0$	0	0	1	1	0	0
   $v_1$	0	1	0	1	0	0
   $v_2$	1	0	1	0	0	0
   $v_3$	1	1	0	0	1	1

   $$\begin{array}{rl}a\vee b& =\neg (\neg a\wedge \neg b)\\ & =\neg (((a\downarrow a)\downarrow (a\downarrow a))\downarrow ((b\downarrow b)\downarrow (b\downarrow b)))\\ & =\neg ((a\downarrow a\downarrow a\downarrow a)\downarrow (b\downarrow b\downarrow b\downarrow b))\\ & =\neg ((a\downarrow a)\downarrow (b\downarrow b))\\ & =((a\downarrow a)\downarrow (b\downarrow b))\downarrow ((a\downarrow a)\downarrow (b\downarrow b))\end{array}$$

title: We can instead show completeness by only finding $\{ \neg, \lor \}$ from $\{ \downarrow \}$
 
$$
	\begin{aligned}
		\neg P &\equiv P \downarrow P \\
		\neg (P \lor Q) &\equiv P \downarrow Q \\
		P \lor Q &\equiv \neg (P \downarrow Q) \\
		P \lor Q &\equiv P \downarrow Q \downarrow P \downarrow Q
	\end{aligned}
$$

2

Let $W$ be $P\to (Q\to P)$.

1. Formula is a substitution instance given by $W(P/\neg R,Q/R)$
2. Not a substitution instance. Substitution instance given by $W(P/\neg R,Q/\neg r)$.
3. Not a substitution instance.
4. Formula is a substitution instance given by $W(P/P\wedge Q\to P,Q/Q\to P)$.
5. It is not a direct substitution instance but $(P\to P)\to P$ and $P\to (P\to P)$ are logically equivalent, so you can find it by manipulating the formula given by $W(P/P\to (P\to P),Q/P)$. Not a substitution instance.

title: Mostly correct.

3

Given formula $(P\vee \neg R)\to \neg (\neg Q\vee R)$, find Quine’s tree and its DNF.

digraph A {
	{
		node[shape="rect"]
		root[label="(p or r') implies (q' or r)'"]
		PT[label="(T or r') implies (q' or r)"]
		PT2[label="T implies (q' or r)"]
		PT3[label="q' or r"]
		
		PF[label="(F or r') implies (q' or r)"]
		PF2[label="r' implies (q' or r)"]
		PFRT[label="T' implies (q' or T)"]
		PFRT2[label="F implies (q' or T)"]
		PFRT3[label="T"]
		PFRF[label="F' implies (q' or F)"]
		PFRF2[label="T implies (q' or F)"]
		PFRF3[label="q'"]
	}
	
	root->PT [label = "   P = 1"]
	PT->PT2
	PT2->PT3
	
	root->PF [label = "   P = 0"]
	PF->PF2
	PF2->PFRT [label = "   R = 1"]
	PFRT->PFRT2
	PFRT2->PFRT3
	PF2->PFRF [label = "   R = 0"]
	PFRF->PFRF2
	PFRF2->PFRF3
}

Hence the formula is true when:

• $P=1,Q=0,R=0$
• $P=0,R=1$
• $P=0,R=0,Q=0$

Hence we find the formula in DNF: $(P\wedge \neg Q\wedge \neg R)\vee (\neg P\wedge R)\vee (\neg P\wedge \neg R\wedge \neg Q)$

title: Incorrect; missing negation on $\rightarrow \textbf{B}$.

4

Determine whether the following statements are consistent.

Whenever the system software is being upgraded, users cannot access the file system. If users can access the file system, then they can save new files. If users cannot save new files, then the system software is not being upgraded.

Let $u$ be that system software is being upgraded. Let $f$ be that users can access the file system. Let $s$ be that users can save new files.

Formal definition of statements:

• $u\to \neg f$
• $f\to s$
• $\neg s\to \neg u$

interpretation	$u$	$f$	$s$	$u\to \neg f$	$f\to s$	$\neg s\to \neg u$
$v_0$	0	0	0	1	1	1
$v_1$	0	0	1	1	1	1
$v_2$	0	1	0	1	0	1
$v_3$	0	1	1	1	1	1
$v_4$	1	0	0	0	1	0
$v_5$	1	0	1	0	1	1
$v_6$	1	1	0	1	0	0
$v_7$	1	1	1	1	1	1

As there is at least one interpretation where all formulas are true, the given statements must be consistent.