Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers


543 users

0 votes

Can you convert to CNF and explain associattivity in each step with brackets. Thank you.

in # Mandatory Modules Bachelor by (290 points)

1 Answer

0 votes

First of all, <-> is associative, so that it does not matter for its semantics how we parse a sequence of this operator. According to the lecture, we defined this operator however as being left associative, so that we get the following expression with full use of brackets:


A CNF obtained by the BDD of this formula is for instance the following one:

    (!a|!b|!d) & (b|!c)

Before starting any computation, we first simplify the formula by replacing a<->a with true and propagating the boolean constants so that we get


Next, we make a Shannon decomposition: Starting with variable b (it has two occurrences and thus more than variable a), we get the following cofactors:

  • b=0: !c
  • b=1: (a&d<->c)<->!c

Thus, our formula is equivalent to (b -> (a&d<->c)<->!c) & (!b -> !c) which yields 

    (!b | ((a&d<->c)<->!c)) & (b|!c)

It remains to convert (a&d<->c)<->!c) to a CNF, so we make a Shannon decomposition with c:

  • c=0: !(a&d)
  • c=1: !(a&d)

That makes it simple, since the formula  (a&d<->c)<->!c) is equivalent to !(a&d). Hence, we get the following formula:

    (!b | !(a&d)) & (b|!c)

which has the following CNF:

    (!b|!a|!d) & (b|!c)

by (166k points)

Related questions

Imprint | Privacy Policy