Use the laws of logic to show that $[a\Rightarrow(b\lor c)]\Leftrightarrow[(a\land\lnot b)\Rightarrow c]$

discrete mathematicslogicpropositional-calculus

I am trying to prove that $[a\Rightarrow(b\lor c)]\Leftrightarrow[(a\land\lnot b)\Rightarrow c]$.

My proof is the following:

  • $a\Rightarrow(b\lor c)~$ Premise
  • $(a\Rightarrow b)\lor c~$ Associative Law
  • $(\lnot a\lor b)\lor c~$ Material Implication
  • $\lnot(a\lor\lnot b)\lor c~$ De Morgan's Law
  • $(a\land\lnot b)\Rightarrow c~$ Material Implication

I'm having doubts about my second step. I tried to check for the validity of my step using truth table, and the statements in the first and second steps are logically equivalent. Is my application of associative law legal?

Best Answer

Yes it is logically equivalent. See that you can go directly from first line to third line by material implication

$$ a \rightarrow (b \lor c) \iff \neg a \lor (b \lor c) \iff (\neg a \lor b) \lor c $$

Assuming you know how to go from step 2 to 3, then you should know how to go from step 3 to step 2.

Also, see Material Implication. As a rule of thumb to look at boolean algebra, remove that arrow!

Related Question