  We study the model checking problem, for fixed structures A, over positive
equality-free first-order logic -- a natural generalisation of the non-uniform
quantified constraint satisfaction problem QCSP(A). We prove a complete
complexity classification for this problem when A ranges over 1.) boolean
structures and 2.) digraphs of size (less than or equal to) three. The former
class displays dichotomy between Logspace and Pspace-complete, while the latter
class displays tetrachotomy between Logspace, NP-complete, co-NP-complete and
Pspace-complete.
