1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ But you can use Material Implication directly on 1st line to get 3rd $\endgroup$ – Mauro ALLEGRANZA Jun 17 '20 at 12:29
  • 1
    $\begingroup$ I'm slightly confused: commonly, associativity is something only concerning one type of operation not two; could you state the laws/interfer rules you used as their formulation might differ from source to source. $\endgroup$ – mrtaurho Jun 17 '20 at 12:34
  • $\begingroup$ The associative law is a tad confusing. What is meant is $$a\Rightarrow (b\lor c) \equiv \neg a\lor (b\lor c) \equiv (\neg a \lor b) \lor c $$ $\endgroup$ – Alvin Lepik Jun 17 '20 at 13:02
3
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ What is the benefit of copy-pasting what the OP has already written ? $\endgroup$ – Mauro ALLEGRANZA Jun 17 '20 at 12:59

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.