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


538 users

0 votes

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? 

in * TF "Emb. Sys. and Rob." by (810 points)

1 Answer

+1 vote
Best answer
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 (166k points)
selected by
good to hear. Yeah, normalized it is way nicer to argue, why it is no sorting networks.

Related questions

Imprint | Privacy Policy