sorting network as boolean circuit in exams

Question

I wondered for this question typ:
"Due to the 0/1 principle, the following comparator network can be read as a boolean circuit, i.e., considering the inputs x0, x1, x2, x3 to be true or false, the outputs y0, y1, y2, y3 can be expressed as boolean functions over the variables x0, x1, x2, x3. List the boolean formulas for all outputs, e.g., y0 := x0 ∧ x1 ∨ x2."
in which form the boolean formula can be written for full marks:
1) non Normalform formula: So plugging each intermediate equation in each other to get one formula for y0 to yn
Or 2) Is a Normalform (DNF/KNF) required? 

Answer 1

If no special normal form is required (that is usually the case), it is sufficient to write down the and/or gate representation of the comparators. However, if next you need to decide whether it is a sorting network, you have to check whether the functions are the threshold functions. To that end, a bit normalization is often useful.

Comments

good to hear. Yeah, normalized it is way nicer to argue, why it is no sorting networks.
Thanks