Proof of The Law of Detachment (Propositional Logic)

Question

Let me state the reasoning that I used to prove that the following compound statement, composed of two primitive propositions p and q, is a tautology:

(p $\land$ (p $\Rightarrow$ q)) $\Rightarrow$ q

Now, the above statement is going to be false iff q is false and (p $\land$ (p $\Rightarrow$ q)) is true. The latter statement is true iff p is true and p $\Rightarrow$q is true. Since q is false, p must be false as well (ex falso quodlibet). Thus, we have shown that p is both true and false. That is an absurdity as p is a proposition and propositions cannot be both true and false. Hence, the compound statement cannot be false. It will always be true and so, we have proven that it is a tautology.

So, the above paragraph constitutes the reasoning that I have used. The book that I'm using, Fundamentals of Mathematics by Bernd Schroder, proves the tautology by looking at the individual cases. Of course, that's rather understandable but I'm wondering if my proof above counts as a valid one. The thing that I'm afraid of is that it looks like a Proof by Contradiction, which is proof method that is shown to be valid through the use of another tautology. I will require assistance in verifying the validity of the reasoning that I have used above.

MASSIVE EDIT BELOW:

I've been looking at the problem and trying to find other ways to prove the given compound statement. I was thinking of writing it out as disjunction of conjunctions. Let me write out the proof that I was considering as follows:

p $\Rightarrow$ q = ( p $\land$ q ) $\lor$ ( $\lnot$p $\land$ q ) $\lor$ ( $\lnot$p $\land$ $\lnot$q )

Now, we can see that the first two conjunctions can be simplified using the distributive law of Boolean Algebra. Of course, I'm also going to be using the commutative law for the conjunction operator. Hence:

( q $\land$ p ) $\lor$ ( q $\land$ $\lnot$p ) = q $\land$ ( q $\lor$ $\lnot$q).

Now, the disjunction of a proposition and its negation is going to be trivially true. Hence, the original implication can be reduced to the following statement:

p $\Rightarrow$ q = q $\lor$ ( $\lnot$p $\land$ $\lnot$q )

By the distributive law, we have:

p $\Rightarrow$ q = ( q $\lor$ $\lnot$p ) $\land$ ( q $\lor$ $\lnot$q )

Once again, we can see that the disjunction of a proposition and its negation is trivially true. Hence, we conclude that:

p $\Rightarrow$ q = ( q $\lor$ $\lnot$p )

Now, we consider the full antecedent of the compound statement from before, which is:

p $\land$ ( q $\lor$ $\lnot$p )

We can simplify it using the distributive law:

p $\land$ ( q $\lor$ $\lnot$p ) = ( p $\land$ q ) $\lor$ ( p $\land$ $\lnot$p )

The latter is an absurdity so it can be disregarded as well. Hence, we have:

( p $\land$ q ) $\Rightarrow$ q

Now, we can simplify this once more so that it is a series of conjunctions and disjunctions. After doing that, we should get:

( ( p $\land$ q ) $\Rightarrow$ q ) = ( q $\lor$ $\lnot$ ( p $\land$ q ) )

Using De Morgan's Law, we conclude that:

( ( p $\land$ q ) $\Rightarrow$ q ) = ( q $\lor$ $\lnot$p $\lor$ $\lnot$q ) = ( q $\lor$ $\lnot$q ) $\lor$ ( $\lnot$p )

We can see that the disjunction is ALWAYS true because there is a tautology embedded in it as a statement. The truth values of p and q are entirely irrelevant. Since the statement above is equivalent to the compound statement we wanted to study, we have shown that that statement is a tautology.

Once again, the above is a separate proof that I have come up with and I'd greatly appreciate any form of criticism to the proof above (assuming it is a proof).

Answer 1

"Ex falso quodlibet" is the principle that "from falsity we can infer anything."   If you have derived a contradiction, then you may infer anything.   You did not derive a contradiction at this point, so this is not a rule you could use.   Indeed, you did not use it.

The rule you actually used is called "modus tolens" or "denying the consequent".   If you have derived a conditional and the negation of its consequent, then you may infer the negation of its antecedent.

$$[~\Sigma\vdash p\to q~]~\&~[~\Sigma\vdash \neg q~]\implies[~\Sigma\vdash \neg p~]$$

You could have instead used "modus ponens", or "affirming the antecedent". If you have derived that a conditional and its antecedent are true, then you may infer the consequent is true too.

$$[~\Sigma\vdash p \to q~]~\&~[~\Sigma\vdash p~]\implies[~\Sigma\vdash q~]$$

Either method will leave you with a contradiction in any evaluation where $p\wedge(p\to q)$ is true and $q$ is false. Thus completing your proof by contradiction.

---

Otherwise your proof is okay, though perhaps it could use a little polishing. Since you are using Rules of Inference, this is a valid Syntactic derivation.

Technically you do not need a proof by contradiction, as you merely need to show that $q$ is entailed by $p\wedge(p\to q)$, then use deduction theory.

• Assume $p\wedge (p\to q)$.
• From this $p$ and $p\to q$ may be derived (by rule of $\wedge$-elimination, also known as "simplification").
• From that $q$ may also be derived (by rule of $\to$-elimination, or "modus ponens".
• By discharging the assumption, we deduce that $(p\wedge(p\to q))\to q$ is true.
• Because there are no undischarged assumptions, therefore the statement is a tautology.

Fundamentals of Mathematics by Bernd Schroder, proves the tautology by looking at the individual cases.

Something like:

• If we value $q$ as true, then we value $(p\wedge(p\to q))\to q$ as true whatever the value we assign to $p$.

• If we value $q$ as false, and $p$ as true, then we value $p\to q$ as false, and so $p\wedge (p\to q)$ as false, which values $(p\wedge(p\to q))\to q$ as true.

• Finally if we value both $q$ and $p$ as false, then we value $p\wedge (p\to q)$ as false and therefore $(p\wedge(p\to q))\to q$ as true.

• Therefore in all valuations of the literals $\{p,q\}$ we value $(p\wedge(p\to q))\to q$ as true. Thus the statement is a tautology.

Since this argues strictly from valuations of the literals, this is a Semantic proof.

Answer 2

Your proof looks fine. Good work. Here is an alternate proof:

$1$. $\big[ p \wedge (p \rightarrow q) \big] \rightarrow q$

$\Leftrightarrow$ $\neg \big[ p \wedge (p \rightarrow q) \big] \vee q$ ---- implication law

$\Leftrightarrow$ $\neg p \vee \neg (p \rightarrow q) \vee q$ ---- DeMorgan's law

$\Leftrightarrow$ $\neg (p \rightarrow q) \vee \neg p \vee q$ ---- commutative law

$\Leftrightarrow$ $\neg (p \rightarrow q) \vee (p \rightarrow q)$ ---- implication law

$\Leftrightarrow$ $T$ ---- negation law