Logic gates like AND, OR, NOT, and so on are not discretised in time, they don't handle time in steps. At every moment they reflect the input at some earlier moment (a few nanoseconds ago, usually). For various reasons signals can get delayed for a tiny moment of time (line length, capacitance, etc), and as a result for similarly tiny lengths of time your output could reflect a state where one input has changed and another not (yet). These are known as hazards.
If hazards will be a problem on your output, you need to design around them. For counting, for example, consider using Gray code which cycles through all values while only ever changing one bit at a time (but is a bit of a pain to generate in hardware, software has no problems).
Alternatively, start using clocks and flip-flops and allow settle time. Don't be overly cautious. Often, very large systems of gates (eg a whole ALU) can be activated simultaneously and all kinds of hazards generated. As long as enough time is allowed for the value to settle before latching into a flip-flop, then it's not a problem.
The problem is similar to bounce in switches and races in software. Always remove hazards from outputs driving power devices: it's an easy way to screw whatever is connected to the output. Either latch the output with a clocked flip-flop, or use a capacitor, to remove hazards in this case.