While internally computing all the answers, and then using a mux to select among them will work, it certainly is not a minimal design.
Consider that you can bit-slice the problem; instead of a single block of logic with two 8 bit inputs, you could partition this as two 4-bit sections, as long as you can link them to get a correct overall result. Fortunately, linking the slices is no worse than a single bit, which in the case of addition represents the carry bit. So each 4-bit slice has a carry-in bit and a carry-out bit. (Note that logicals like AND and NOR won't even need this, though if later on you implement left/right shifts, this bit is easily re-purposed).
Carried to an extreme you could use 8 slices of 1-bit each. It's useful to think about the 1-bit slices, because it makes it easier to think about an approach that scales back up to larger slices. So with a 1-bit slice, you have just 7 inputs: the 4 bit function code, a bit from input A, a bit from input B, and a carry-in bit. You also have just two outputs: function out, and carry out. So now you can write the two output functions in terms of just 7 inputs, which is within the realm of human ability to reasonably reduce. You'll end up with a handful of gates that won't necessarily always compute all the functions, but it doesn't matter what happens within the slice, only that it produces the correct result when viewed from outside.
Now you can go a couple of ways. One way is to simply use 8 of these 1-bit slices and you're done. Another way is to make larger slices and then use those. Going from 1-bit to 2-bits, the equations go from 7 inputs to 9, and 4-bits will require functions of 13 inputs. It's not necessarily easy, but will give more compact results than the compute-everything-then-mux approach. Besides, if you look at the internals of a 74181 4-bit ALU slice, you won't see a mux in there.
The bottom of page 7-799 of the linked datasheet gives the thresholds for low and high input voltages given a couple of different supply voltages. As long as the voltage on the input is at most/least that value when referenced to ground the input is considered low/high regardless of what you tie it to.
Best Answer
The chip does not care, it reacts to voltage levels, not to logic signals.
This chip has two tables that describe the logic function it implements. The first one shows the functions when YOU define low = 1, high = 0:
The second table describes the same logical circuits, but now using the (common) convention high = 1, low = 0:
To illustrate the point, look at the last-but-one row, second column. In the first table (active low logic) it states F = AB, which is the math notation for the AND function. In the second table the same entry states F = A + B, which is the logical (inclusive) OR function. This all makes perfect sense: the common OR port IS AN AND PORT FOR 0's.