$(P \land \neg Q) \lor P \equiv P$ How is this proved using theorems?

128 Views Asked by At

I have tried my best by using all possible ways but failed!

  1. Commutative laws: $p \land q \equiv q \land p$ and $p \lor q \equiv q \lor p$

  2. Associative laws: $(p \land q) \land r \equiv p \land (q \land r)$ and $(p \lor q) \lor r \equiv p \lor (q \lor r)$

  3. Distributive laws: $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ and $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

  4. Identity laws: $p \land \top \equiv p$ and $p \lor \bot \equiv p$

  5. Negation laws: $p \lor \neg p \equiv \top$ and $p \land \neg p \equiv \bot$

  6. Double negative law: $\neg (\neg p) \equiv p$

  7. Idempotent laws: $p \land p \equiv p$ and $p \lor p \equiv p$

  8. Universal bound laws: $p \lor \top \equiv \top$ and $p \land \bot \equiv \bot$

  9. De Morgan’s laws: $\neg (p \land q) \equiv \neg p \lor \neg q$ and $\neg (p \lor q) \equiv \neg p \land \neg q$

  10. Absorption laws: $p \lor (p \land q) \equiv p$ and $p \land (p \lor q) \equiv p$

  11. Negations of $\top$ and $\bot$: $\neg \top \equiv \bot$ and $\neg \bot \equiv \top$

1

There are 1 best solutions below

5
On BEST ANSWER

It can be proved from the absorption law that you list with a variable substitution. Let $Q'=\neg Q$. Then by the absorption law, $(P \wedge Q') \vee P \equiv P$.