 Semantic entailment

A propositional formula $\phi$ semantically entails $\psi$ when every Boolean valuation satisfying $\phi$ satisfies $\psi$. Equivalently, $\phi \wedge \neg \psi$ is an unsatisfiable Boolean formula. Deciding semantic entailment is co-NP-complete: a counterexample Boolean valuation certifies failure in polynomial time, while $\theta \mapsto ⟨\theta ,p\wedge \neg p⟩$ reduces unsatisfiability to semantic entailment.