2
$\begingroup$

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...

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.