(Thanks to Murali for the solution!)
Let the inputs be x, y, z.
Consider the circuits that generate one or two ones, two or three ones, etc.
2or3 = xy + yz + zx
0or1 = not 2or3
1or3 = 0or1.(x + y + z) + xyz
0or2 = not 1or3
With this you can find out exactly how many ones are there:
Exact0 = 0or1.0or2
Exact1 = 0or1.1or3
Exact2 = 2or3.0or2
Exact3 = 2or3.1or3
From this you can figure out which exact output signal is high:
Neg x is high only when exact0 is high or when exact1 is high and y or z
is high or when exact2 is high and both y and z are high. That is
Neg x = exact0 + exact1.(y+z) + exact2.(yz)
Similarly for others based on symmetry.