[Math] Don’t really understand the absorption law

discrete mathematicslogicpropositional-calculus

I don't really get the absorption law, specifically in this case:

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

The absorption law is used here: $ (\lnot p \land q) \lor (q\land \lnot r) $

I don't really understand the use of absorption law in this case, and if someone could explain it to me on a similar example or something, that would be highly appreciated.

Best Answer

With :

$(¬p∧¬r)∨(¬p∧q)∨(q∧¬r)∨(q∧q)$

you first apply $(q \land q) \equiv q$ to simplify it :

$(¬p∧¬r)∨(¬p∧q)∨(q∧¬r)∨q$.

Consider now : $(q∧¬r)∨q$; applying Absorption Laws : $p∨(p∧q) \equiv p$, we have that it is equivalent to $q$.

Thus :

$[(¬p∧¬r)∨(¬p∧q)]∨[(q∧¬r)∨q] \equiv (¬p∧¬r)∨(¬p∧q)∨q$.

Apply it again to : $(¬p∧q)∨q$, which is again equivalent to $q$, to get :

$(¬p∧¬r)∨[(¬p∧q)∨q] \equiv (¬p∧¬r)∨q$.

Regarding absorption :

$p∨(p∧q) \equiv p$

you can prove it with Natural Deduction or verify it via truth table :

  • if $p$ is TRUE, then $p \lor (p \land q)$ is TRUE, by truth table for $\lor$;

  • if $p$ is FALSE, then $(p \land q)$ is FALSE, by truth table for $\land$; so both $p$ and $(p \land q)$ are FALSE, and thus $p∨(p∧q)$ is FALSE, by truth table for $\lor$.

Related Question