No, logic operations aren't "recognized as necessary". For instance, the IBM 1401—the most popular computer of the early 1960s—did not have logic operations. (This was very annoying when I implemented Bitcoin mining on it.)
The reason that the 4004 is considered a CPU and the 74181 is not a CPU is that the 4004 contains the control logic, while the 74181 is only the ALU.
Of course, "microprocessor" and "CPU" are social constructs, not objective definitions. (For instance, bit-slice processors like the Am2901 were considered microprocessors in Russia.) So you can craft your own definition if you want to declare a particular processor first. cough MP944 cough
The reason that the 4004 is considered a CPU and the 74181 is not a CPU is that the 4004 contains the control logic, while the 74181 is only the ALU.
Of course, "microprocessor" and "CPU" are social constructs, not objective definitions. (For instance, bit-slice processors like the Am2901 were considered microprocessors in Russia.) So you can craft your own definition if you want to declare a particular processor first. cough MP944 cough