# sorting network as boolean circuit in exams

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?

+1 vote

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.
by (162k points)
selected by
good to hear. Yeah, normalized it is way nicer to argue, why it is no sorting networks.
Thanks