Proof by contradiction for q $\Rightarrow (p \land $ $\neg p)$

Question

Hi everyone I'm doing an exercise of logic from the Science of programming book of David Gries, one of the exercises says:

Prove that from $\neg q$ follows q $\Rightarrow (p \land $ $\neg p)$

I proved that in the following way:

From $\neg q$ infer $q \Rightarrow (p \land $ $\neg p)$

1. $\neg q$ Preposition 1.

2. from q infer p.

   2.1. q Preposition 1.

   2.2 From $\neg p$ infer q $\land$ $\neg q$

   2.2.1 q $\land$ $\neg$q ($\land$-I, 1, 2.1).

   2.3 p ($\neg$-E, 2.2)

3. from q infer $\neg$ p.

   3.1. q Preposition 1.

   3.2 From p infer q $\land$ $\neg q$

   3.2.1 q $\land$ $\neg$q ($\land$-I 1, 3.1).

   3.3 $\neg$p ($\neg$-I, 3.2)

4. p $\land$ $\neg$p ($\land$-I,2,3).

5. q $\Rightarrow (p \land $ $\neg p)$. ($\Rightarrow$-I, 2, 4).

From my understading ths proof indicates that if q is false then q $\Rightarrow (p \land $ $\neg p)$ is true.

The doubt I have is with this proof:

Prove that from q follows q $\Rightarrow (p \land $ $\neg p)$

that I proved in this way:

From q infer $q \Rightarrow (p \land $ $\neg p)$

1. q Preposition 1.

2. from $\neg q$ infer p.

   2.1. $\neg q$ Preposition 1.

   2.2 From $\neg p$ infer q $\land$ $\neg q$

   2.2.1 q $\land$ $\neg$q ($\land$-I, 1, 2.1).

   2.3 p ($\neg$-I, 2.2)

3. from $\neg q$ infer $\neg$ p.

   3.1. $\neg q$ Preposition 1.

   3.2 From p infer q $\land$ $\neg q$

   3.2.1 q $\land$ $\neg$q ($\land$-I 1, 3.1).

   3.3 $\neg$p ($\neg$-I, 3.2)

4. p $\land$ $\neg$p ($\land$-I,2,3).

5. q $\Rightarrow (p \land $ $\neg p)$. ($\Rightarrow$-I, 1, 2, 4).

I'm not sure if that last proof is correct, because for q $\Rightarrow (p \land $ $\neg p)$ to be true q has to be true and p $\land$ $\neg$ p has to be true, but p $\land$ $\neg$ p is a contradiction, this never can be true, however my proof indicates that q $\Rightarrow (p \land $ $\neg p)$ can be infered from q, what I'm doing wrong?

These are the inference rules I'm using:

And this is the deductive system I'm using:

Answer 1

Yes, your first proof is fine; see (3.3.13) page 41:

From $p, \lnot p$ infer $q$.

Thus, strating with premises $\lnot q$ and $q$ we have a 1st sub-proof: From $\lnot q, q$ infer $p$.

In the same way, we have a 2nd sub-proof: From $\lnot q, q$ infer $\lnot p$.

From them $(p \land \lnot p)$ follows using $(\land \text {-I})$ and we conclude with $q \to (p \land \lnot p)$ using $(\to \text {-I})$.

In conclusion we have:

From premise $\lnot q$, the conclusion $q \to (p \land \lnot p)$ follows.

---

Regarding your second attempt, you have $q$ as premise and you have derived the contradiction $(p \land \lnot p)$ assuming also $\lnot q$.

Thus, when you conclude with $q \to (p \land \lnot p)$, there is still the premise $\lnot q$.

Obviously, we cannot prove $q \to (p \land \lnot p)$ because it is not a tautology.

Formula $(p \land \lnot p)$ does not follows from $\lnot q$ alone (neither from $q$ alone) [see logical consequence] because $(p \land \lnot p)$ is a contradiction, i.e. a formula that is always false, and there is an interpretation where $\lnot q$ is false but also an interpretation where $\lnot q$ is true.