I want to bring the following formula $ F = A \land (A \lor B) \Rightarrow (B \lor C)$ into conjunctive normal form (CNF) and disjunctive normal form. Therefore, I applied the following 5 step transformation process:

  1. Step: Removing the implication:

$$ \Leftrightarrow \neg (A \land(A \lor B)) \lor (B \lor C)$$

  1. Step: Resolve the negation: $$ \Leftrightarrow \neg A \lor (\neg A \land \neg B) \lor (B \lor C)$$

  2. Step: Remove parenthesis to receive DNF $$ \Leftrightarrow \neg A \lor (\neg A \land \neg B) \lor B \lor C$$

  3. Step: Resolve the absorption based on step 2: $$ \neg A \lor (B \lor C)$$

  4. Step Removing parenthesis to have DNF as well as CNF: $$ \neg A \lor B \lor C$$

I just have three questions to my normal forms:

  1. Is this transformation process correct?
  2. Is the formula of step 3: $ \neg A \lor (\neg A \land \neg B) \lor B \lor C$ in DNF?
  3. Are DNF and CNF of step 5 correct? Is it necessary to remove the parenthesis for DNF and CNF?
  • $\begingroup$ In step 2, the $\lor$s should become $\land$s. $\endgroup$ – Joshua Tilley Jul 23 '18 at 17:20
  • $\begingroup$ @JoshuaTilley thanks for your hint! I corrected it. Could you also please answer my questions? Thanks in advance! $\endgroup$ – user3352632 Jul 24 '18 at 7:01
  • $\begingroup$ I'm not sure I know what you're asking, sorry. Also, you need to carry the change into steps 4 and 5, they should be $\sim A \lor B \lor C$ $\endgroup$ – Joshua Tilley Jul 24 '18 at 12:50
  • $\begingroup$ @JoshuaTilley thanks, I updated the equations. So the first question is answered by you. thanks a lot. I hope here is anybody who can answer the 2. one! $\endgroup$ – user3352632 Jul 24 '18 at 13:21
  • $\begingroup$ The answer to 2 is yes, since it is a disjunction of conjunctions. As for 3, the parentheses make no difference in this case, since $\lor$ is associative. $\endgroup$ – Joshua Tilley Jul 24 '18 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.