1
$\begingroup$

could someone please be so kind to answer this question and explain the answer? Which of the following formulas are in CNF?

  1. ¬(A∨B∨C)∧(A∨B)
  2. (A∧B∧C)∨(A∧B)
  3. (A∨B∨¬C)∧(A∨B)
  4. (A∧B∧¬C)∨(A∧B)
$\endgroup$
  • $\begingroup$ $1$ and $3$ are in CNF, Since they connected with $\wedge$ $\endgroup$ – Manx Sep 24 '19 at 20:22
  • $\begingroup$ @Manx Option 1 is not in CNF as there is a negation of the disjunction $A \vee B \vee C$. $\endgroup$ – RyRy the Fly Guy Sep 24 '19 at 21:16
  • $\begingroup$ I see, thank you sir :) $\endgroup$ – Manx Sep 24 '19 at 22:12
3
$\begingroup$

CNF is when a Boolean expression is written as a conjunction of clauses, where a clause is defined as a disjunction of literals. And... a literal is either a simple proposition or its negation. In other words, the expression must be a conjunction of disjunctions of some combination of the variables $p,q,r,...$ or their negations. Think of CNF as a chain of conjunctions (ANDs) that join chains of disjunctions (ORs) which join propositions or their negations. As a helpful mnemonic, CNF is conjunctions of disjunctions.

For example, the following is in CNF:

$(p \vee q) \wedge s \wedge (\neg a \vee b \vee \neg c) \wedge t \wedge \neg w$

Options 2 and 4 are disjunctions of conjunctions, so they are not in CNF. Option 1 seems to be a good candidate, but if you inspect it carefully you will notice there is a negation of a set of parentheses and not a simple proposition. If a negation is present, then it must be the negation of a simple proposition. If you were to apply DeMorgan's rule (by distributing the negation and changing the disjunctions in the parantheses to conjunctions), then 1 would be in CNF.

Option 3 is the only option composed of pure literals written in terms of conjunctions of disjunctions, so...

3 is in CNF.

$\endgroup$

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.