As far as I understand it, once a subexpression gets replaced, it can't get replaced again. Try this:

    a*b /. {a -> a, a -> 1, b -> c}

resulting in

    a*c

The first replacement just replaces `a` with `a`, but since that expression has already been changed, it is ignored after that. So the `Rule` `a -> 1` is only applied to *other* parts of the expression (in this case the `b`), and those other parts don't depend on `a`, so nothing changes. Finally, `b` gets replaced with `c`. (By the way, in somewhat-advanced *Mathematica* programming, this fact can be taken advantage of in many clever ways. I'll try to find an example at some point and link to it.)

So you're kind of right and kind of not. The `Rule`s *are* applied sequentially, but the rules are *not* applied to the *new* expressions resulting from previous replacements.

Here's another interesting example:

    a b c /. {a -> b, b -> c, c -> d}
    % /. {a -> b, b -> c, c -> d}
    % /. {a -> b, b -> c, c -> d}
    (* b c d *)
    (* c d^2 *)
    (* d^3 *)

In the first case, the `a` instance is replaced by `b`, but it is not in turn replaced by `c`. However, the original `b` *is* replaced by `c`. And so on. To do all of them at once, use `ReplaceRepeated`:

    a b c //. {a -> b, b -> c, c -> d}
    (* d^3 *)

(Be careful of this one, because it can run into infinite recursions.) For completeness, note that `ReplaceRepeated` does *not* act the same as a sequence of `ReplaceAll`s if the list of `Rule`s are different:

    a b c //. {a -> b, c -> d, b -> c}
    a b c /. {a -> b} /. {c -> d} /. {b -> c}
    (* d^3 *)
    (* c^2 d*)

Finally, as noted by [Daniel Lichtblau][1] in a comment, if you *do* want to apply the two rules to get different expressions, do this:

    2 x + y /. {{x -> 3}, {x -> 4}}
    (* {6 + y, 8 + y} *)

Alternatively, do

    2 x + y /. # &/@ {x -> 3, x -> 4}

or

    2 x + y /. List/@{x -> 3, x -> 4}



  [1]: http://mathematica.stackexchange.com/users/51/daniel-lichtblau