also contains a variable from B if and only if every prime implicate of Σ contains a variable from B (since Var(Σ) = A ∪ B ) if and only if Σ is strictly relevant to B

## - Strict Relevance (Lakemeyer, 1997)

- Membership: Straightforward from Propositions 27 and  10. - Hardness: By exhibiting a polynomial reduction from SAT-UNSAT to STRICT REL-
EVANCE OF A FORMULA TO A SUBJECT MATTER. To any pair (¢,¥) of propositional formulas, let rename (ψ) be a formula obtained from ψ by renaming its variables. Obviously,
(i) rename(ψ) is satisfiable if and only if ψ is. Now, let new be a new variable, let Σ = φ Λ π ew Λ − r ename(ψ)
and V = Var(φ) ∪ { new }. By Proposition 8, Σ is Var-dependent on V if and only if there is a prime implicant of Σ mentioning a variable from V, i.e., if and only if φ ∧ ¬ rename(ψ) is satisfiable, thus, using (i):
(ii) E is Var-dependent on V if and only if both φ and ¬ψ are satisfiable. Then, again after Proposition 8, E is Var-independent from Var(E) \ V =
Var(rename(ψ)) if and only if no prime implicant of Σ mentions a variable from Var (rename(ψ)), i.e., if and only if rename (ψ) is unsatisfiable, thus, using
(i):
(iii) Σ is Var-independent from Var(Σ)\ V if and only if ψ is satisfiable.

Thus, from Proposition 27, (ii) and (iii), we get that Σ is strictly relevant to V
if and only if φ is satisfiable and rename (ψ) is not.