0
$\begingroup$

I'm having serious problems whenever I try to convert a formula to CNF/DNF. I can do it with easier formulas, but this one I just can't understand for some reason:

(A∧¬B→B∧¬C)→¬A∨B

I've tried removing the → operators and replacing them with other formulas, after that I've tried to apply De Morgan's laws to it, etc, like this:

1. ¬A∨B∨¬(A∧¬B→B∧¬C)
2. ¬A∨B∨¬((B∧¬C)∨¬(A∧¬B))
3. ¬A∨B∨(¬(B∧¬C)∧¬¬(A∧¬B))
4. ¬A∨B∨((¬B∨¬¬C)∧(A∧¬B))
5. ¬A∨B∨((¬B∨C)∧(A∧¬B)) 

I'm not sure if I even did one correctly, not the mention all of it, and I'm also stuck here, so I don't know how to continue..

I'd really appreciate if someone could help me solve this! Thanks!

$\endgroup$
1
$\begingroup$

So far so good!

Taking it from where you left:

$\neg A \lor B \lor ((\neg B \lor C) \land (A \land \neg B)) \overset{Association}{=}$

$(\neg A \lor B) \lor ((\neg B \lor C) \land A \land \neg B) \overset{Distribution}{=}$

$[(\neg A \lor B) \lor (\neg B \lor C)] \land [(\neg A \lor B) \lor A)] \land [(\neg A \lor B) \lor \neg B] \overset{Association}{=}$

$[\neg A \lor B \lor \neg B \lor C] \land [\neg A \lor B \lor A] \land [\neg A \lor B \lor \neg B] \overset{Association, Commutation}{=}$

$[\neg A \lor C \lor (B \lor \neg B)] \land [B \lor (A \lor \neg A)] \land [\neg A \lor (B \lor \neg B)] \overset{Complement}{=}$

$[\neg A \lor C \lor \top] \land [B \lor \top] \land [\neg A \lor \top] \overset{Annihilation}{=}$

$\top \land \top \land \top \overset{Idempotence}{=}$

$\top$

... which is both in DNF and CNF

$\endgroup$
2
  • $\begingroup$ Thank you so much! I guess I can use double "((", instead of "[" right? My teacher is pretty oldschool and it's not allowed for us, to use [ ] brackets for some reason, etc $\endgroup$ – Arany Sandor Oct 8 '19 at 21:41
  • $\begingroup$ @AranySandor You're welcome! And yes, then just use extra ( and )'s $\endgroup$ – Bram28 Oct 8 '19 at 21:43

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.