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

769 questions

886 answers

1.3k comments

424 users

0 votes

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

(a&d<->b<->c)|(a<->a)&!b<->!(c<->(a->a))
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&d)<->b)<->c)|((a<->a)&!b))<->!(c<->(a->a))

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

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

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 (117k points)

Related questions

Imprint | Privacy Policy
...