Proving a tautology using logical equivalences

Question

Can somebody show me how can I prove that this proposition is a tautology using logical equivalences?

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

I already did:

1. $\lnot(\lnot p \land (p \lor q)) \lor q \quad$ definition of the arrow

2. $(\lnot\lnot p \lor \lnot(p \lor q)) \lor q$

But at this point if I continue following this path I'll reach a dead end...

Answer 1

$$(¬p ∧ (p ∨ q)) → q \tag{given}$$

$$\equiv [\underbrace{(\lnot p \land p)}_{\bot} \lor (\lnot p \land q)] \to q\tag{distributive law}$$

$$\equiv \bot \lor (\lnot p \land q) \to q $$

$$\equiv (\lnot p \land q) \to q$$

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

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

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

$$p \lor \top$$

$$\top$$

Can you supply the reasoning here?

Answer 2

We can exhaust all options in the truth table. If $p$ is true the antecedent of $\to$ is false, and it implies anything. If $p$ is false the antecedent is equivalent to $q$, since $p\lor$, $\neg p\land$ each reduce to the identity.

Answer 3

You don't reach a dead end at all! Starting where you left off:

$$(\neg \neg p \lor \neg (p \lor q)) \lor q \Leftrightarrow$$

$$p \lor \neg (p \lor q) \lor q \Leftrightarrow$$

$$(p \lor q) \lor \neg (p \lor q) \Leftrightarrow$$

$$\top$$