Understanding the pseudocode of uniform-cost search from the book "Artificial Intelligence: A Modern Approach"
I think this is a problem with missing brackets in pseudocode &mdash; clearly the state is only added to the frontier if it hasn't been explored already, so it would be:

if not [contains(frontier, state) OR contains(explored, state)] then


which is equivalent to your interpretation of

if not [contains(frontier, state)] AND not [contains(explored, state)] then


(according to De Morgan's Laws)

Being half-way between a programming language and natural language, this is a case where pseudocode is not quite precise enough.