Disjunctive normal form and shannon normal form

Question

Consider the formula (( true | (a <-> b)) & ((c | b) ^ a ^ b)). transform the formula into disjunctive normal form for the variable ordering a ≤ b ≤ c ≤ d. Also transform to Shannon normal form with arbitrary ordering.

I am new to this sort of questions. I don't know how to begin to solve the question.

Answer 1

To transform the formula to DNF, go through the following steps:

1. Write a truth table which shows the function value for all $2^n$ possible input combinations
2. Take the truth table rows for which the function value is $false$
3. Invert the inputs in each of the rows from step 2.
4. The result is a set of disjunctions which together constitute a DNF

To get the Shannon normal form (commonly called if-then-else Normal Form INF), apply the Shannon expansion recursively. In your case, apply it first for variable $a$, then $b$ and so forth.

The Shannon expansion of a function $f(a, b, c)$ is written as:

$$f(a, b, c) = a \land f(a=1, b, c) \lor \bar{a} \land f(a=0, b, c)$$