[Math] Proving a tautology using logical equivalences

discrete mathematicslogicpropositional-calculus

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…

Best Answer

$$(¬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?

Related Question