Tutorial List 5

title: From TA
You cannot use natural deduction to prove something is invalid, only using truth tables, hence if you are asked to prove using natural deduction, chances are that it is valid.

1

Let $P$ be that Lynn works part time. test Let $F$ be that Lynn works full time. Let $T$ be that Lynn plays on the team. Let $B$ be that Lynn is busy.

Determine whether $P\vee F,\neg T\to \neg P,T\to B,\neg F⊢B$ is valid.

$$\begin{array}{rlrlrl}& 1.& & P\vee F& & \text{data}\\ & 2.& & \neg T\to \neg P& & \text{data}\\ & 3.& & T\to B& & \text{data}\\ & 4.& & \neg F& & \text{data}\\ & 5.& & P& & \text{from }(1.),(4.)\text{ and }(\vee E2)\\ & 6.& & P\to T& & \text{from }(2.)\text{ and }(CL)\\ & 7.& & T& & \text{from }(5.),(6.)\text{ and }(\to E)\\ & 8.& & B& & \text{from }(3.),(7.)\text{ and }(\to E)\end{array}$$

Instead of CL:

$$\begin{array}{l}\begin{array}{rlrlrl}& 6.& & P\to T& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{l}\begin{array}{rlrlrlrl}& & & & & & & \underline{T}\\ & 6.1& & P& & \text{assumption}& & \\ & 6.2& & \neg T\to P& & \text{subcomputation}& & \end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{P}\\ & \mathrm{6.2.1}& & \neg T& & \text{assume}& & \\ & \mathrm{6.2.2}& & P& & \text{from }(6.1)& & \end{array}}\\ \begin{array}{rlrlrl}& 6.3& & T& & \text{from }(2.),(6.2),\text{ and }(\neg E)\end{array}\end{array}}\end{array}$$

interpretation	$a$	$b$	$\neg a$	$\neg b$	$\neg a\to \neg b$	$b\to a$
$v_0$	0	0	1	1	1	1
$v_1$	0	1	1	0	0	0
$v_2$	1	0	0	1	1	1
$v_3$	1	1	0	0	1	1

Hence the argument is valid.

title: Correct answer.

2

Let $R$ be that it is raining. Let $W$ be that they work in the yard. Let $L$ be that they go to the library.

Show that $R\vee W,\neg R\vee L⊢W\vee L$ using natural deduction.

$$\begin{array}{l}\begin{array}{rlrlrl}& 1.& & R\vee W& & \text{data}\\ & 2.& & \neg R\vee L& & \text{data}\\ & 3.& & \neg R\to (W\vee L)& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{W\vee L}\\ & 3.1& & \neg R& & \text{assumption}& & \\ & 3.2& & L& & \text{from }(2.),(3.1)\text{ and }(\vee E1)& & \\ & 3.3& & W\vee L& & \text{from }(3.2)\text{ and }(\vee I)& & \end{array}}\\ \begin{array}{rlrlrl}& 4.& & R\to (W\vee L)& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{W\vee L}\\ & 4.1& & R& & \text{assumption}& & \\ & 4.2& & W& & \text{from }(1.),(4.1)\text{ and }(\vee E1)& & \\ & 4.3& & W\vee L& & \text{from}(4.2)\text{ and }(\vee I)& & \end{array}}\\ \begin{array}{rlrlrl}& 5.& & W\vee L& & \text{from }(3.),(4.)\text{ and }(\neg E2)\end{array}\end{array}$$

title: Seems correct but their solution is different.
$$
	\begin{array}{l}
		\begin{aligned}
			&1. &&R \lor W &&\text{data} \\
			&2. &&\neg R \lor L &&\text{data} \\
			&3. &&\neg R \rightarrow (W \lor L) &&\text{subcomputation}
		\end{aligned} \\
		\boxed{
			\begin{aligned}
				& && && &&\underline{W \lor L} \\
				&3.1 &&\neg R &&\text{assumption} \\
				&3.2 &&L &&\text{from } (2.), (3.1) \text{ and } (\lor E1) \\
				&3.3 &&W \lor L &&\text{from } (3.2) \text{ and } (\lor I)
			\end{aligned}
		} \\
		\begin{aligned}
			&4. &&L \rightarrow (W \lor L) &&\text{subcomputation}
		\end{aligned} \\
		\boxed {
			\begin{aligned}
				& && && &&\underline{W \lor L} \\
				&4.1 &&L &&\text{assumption} \\
				&4.2 &&W \lor L &&\text{from} (4.1) \text{ and } (\lor I)
			\end{aligned}
		} \\
		\begin{aligned}
			&5. &&W \lor L &&\text{from } (2.), (3.), (4.) \text{ and } (\lor E)
		\end{aligned}
	\end{array}
$$

3

Let $G$ be that they graduate this semester. Let $P$ be that they pass physics. Let $S$ be that they study physics for 10 hours a week. Let $V$ be that they play volleyball.

Demonstrate the validity of $G\to P,\neg S\to \neg P,S\to \neg V⊢V\to \neg G$.

$$\begin{array}{l}\begin{array}{rlrlrl}& 1.& & G\to P& & \text{data}\\ & 2.& & \neg S\to \neg P& & \text{data}\\ & 3.& & S\to \neg V& & \text{data}\\ & 4.& & P\to S& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{l}\begin{array}{rlrlrlrl}& & & & & & & \underline{S}\\ & 4.1& & P& & \text{data}& & \\ & 4.2& & \neg S\to P& & \text{subcomputation}& & \end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{P}\\ & \mathrm{4.2.1}& & \neg S& & \text{assumption}& & \\ & \mathrm{4.2.2}& & P& & \text{from }(4.1)& & \end{array}}\\ \begin{array}{rlrlrl}& 4.3& & S& & \text{from }(2.),(4.2),\text{ and }(\neg E)\end{array}\end{array}}\\ \begin{array}{rlrlrl}& 5.& & G\to \neg V& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{\neg V}\\ & 5.1& & G& & \text{assumption}& & \\ & 5.2& & P& & \text{from }(1.),(5.1),\text{ and }(\to E)& & \\ & 5.3& & S& & \text{from }(4.),(5.2),\text{ and }(\to E)& & \\ & 5.4& & \neg V& & \text{from }(3.),(5.3),\text{ and }(\to E)& & \end{array}}\\ \begin{array}{rlrlrl}& 6.& & V\to \neg G& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{l}\begin{array}{rlrlrlrl}& & & & & & & \underline{\neg G}\\ & 6.1& & V& & \text{assumption}& & \\ & 6.2& & G\to V& & \text{subcomputation}& & \end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{V}\\ & \mathrm{6.2.1}& & G& & \text{assumption}& & \\ & \mathrm{6.2.2}& & V& & \text{from }(6.1)& & \end{array}}\\ \begin{array}{rlrlrl}& 6.3& & \neg G& & \text{from }(5.),(6.2),\text{ and }(\neg I)\end{array}\end{array}}\end{array}$$

title: Worked through this with solutions.

4.1

Show that the following hold:

1. $P\to Q,\neg Q⊢\neg P$ $$\begin{array}{rlrlrl}& 1.& & P\to Q& & \text{data}\\ & 2.& & \neg Q& & \text{data}\\ & 3.& & \neg P\vee Q& & \text{from }(1.)\text{ and }(\to E1)\\ & 4.& & \neg P& & \text{from }(2.),(3.)\text{ and }(\vee E2)\end{array}$$

title: Reached conclusion but they avoided using variant rules.

4.2

2. $(P\to Q)\to Q,Q\to P⊢P$ $$\begin{array}{l}\begin{array}{rlrlrl}& 1.& & (P\to Q)\to Q& & \text{data}\\ & 2.& & Q\to P& & \text{data}\\ & 3.& & \neg P\to P& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{l}\begin{array}{rlrlrlrl}& & & & & & & \underline{P}\\ & 3.1& & \neg P& & \text{assumption}& & \\ & 3.2& & P\to Q& & \text{subcomputation}& & \end{array}\\ \boxed{\begin{array}{l}\begin{array}{rlrlrlrl}& & & & & & & \underline{Q}\\ & \mathrm{3.2.1}& & P& & \text{assumption}& & \\ & \mathrm{3.2.2}& & \neg Q\to P& & & & \end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{P}\\ & \mathrm{3.2.2.1}& & \neg Q& & \text{assumption}& & \\ & \mathrm{3.2.2.2}& & P& & \text{from }(\mathrm{3.2.1})& & \end{array}}\\ \begin{array}{rlrl}& \mathrm{3.2.3}& & \neg Q\to \neg P\end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{\neg P}\\ & \mathrm{3.2.3.1}& & \neg Q& & \text{assumption}& & \\ & \mathrm{3.2.3.2}& & \neg P& & \text{from }(3.1)& & \end{array}}\\ \begin{array}{rlrlrl}& \mathrm{3.2.4}& & Q& & \text{from }(\mathrm{3.2.2}),(\mathrm{3.2.3}),(\neg E)\end{array}\end{array}}\\ \begin{array}{rlrlrl}& 3.3& & Q& & \text{from }(1.),(3.2),\text{ and }(\to E)\\ & 3.4& & P& & \text{from }(2.),(3.3),\text{ and }(\to E)\end{array}\end{array}}\\ \begin{array}{rlrlrl}& 4.& & \neg P\to \neg P& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{\neg P}\\ & 4.1& & \neg P& & \text{assumption}& & \\ & 4.2& & \neg P& & \text{from }(4.1)& & \end{array}}\\ \begin{array}{rlrlrl}& 5.& & P& & \text{from }(3.),(4.),\text{ and }(\neg E)\end{array}\end{array}$$

title: Worked with solutions.

4.3

3. $\neg (P\wedge \neg Q)⊢P\to Q$ $$\begin{array}{l}\begin{array}{rlrlrl}& 1.& & \neg (P\wedge \neg Q)& & \text{data}\\ & 2.& & P\to Q& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{l}\begin{array}{rlrlrlrl}& & & & & & & \underline{Q}\\ & 2.1& & P& & \text{assumption}& & \\ & 2.2& & \neg Q\to (P\wedge \neg Q)& & \text{subcomputation}& & \end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{P\wedge \neg Q}\\ & \mathrm{2.2.1}& & \neg Q& & \text{assumption}& & \\ & \mathrm{2.2.2}& & P\wedge \neg Q& & \text{from }(2.1),(\mathrm{2.2.1}),\text{ and }(\wedge I)& & \end{array}}\\ \begin{array}{rlrlrl}& 2.3& & \neg Q\to \neg (P\wedge \neg Q)& & \text{subcomputation}\end{array}\\ \boxed{\begin{array}{rlrlrlrl}& & & & & & & \underline{\neg (P\wedge \neg Q)}\\ & & & & & & & \\ & \mathrm{2.3.1}& & \neg Q& & \text{assumption}& & \\ & \mathrm{2.3.2}& & \neg (P\wedge \neg Q)& & \text{from }(1.)& & \end{array}}\\ \begin{array}{rlrlrl}& 2.4& & Q& & \text{from }(2.2),(2.3),\text{ and }(\neg E)\end{array}\end{array}}\end{array}$$

title: Correct answer.

5 (optional)

Prove using natural deduction that the variant rules can be obtained from the basic ones. For each variant rule, provide a natural proof deduction proof of its conclusion from its premises using only the basic rules.