Negative Boolean Constraints Kim Marriott and Martin Odersky Technical Report 94/203 Monash University, Department of Computer Science Systems of Boolean Constraints which allow negative constraints such as $f \not\subseteq g$ are investigated. The results form a basis for algorithms to determine satisfiability, validity, implication, equivalence and variable elimination for such systems. These algorithms have applications in spatial query decomposition, machine reasoning, and constraint logic programming. Proofs of the results rely on independence of inequations, which enables results for systems with a single inequation to be lifted to systems with many inequations.