Construct NP-complete languages A and B such that A ∪ B = {0, 1}*

Question

I have attempted to prove this problem, but I am not confident in my solution. Can someone please review my proof and let me know if there are any errors, or provide a correct proof if mine is incorrect?

1. Let SAT be the language of satisfiable Boolean formulas. That is, SAT = {φ | φ is a satisfiable Boolean formula}. SAT is a well-known NP-complete language.
2. Let A be the language of all strings that can be obtained by replacing each variable in a formula in SAT by either 0 or 1, while preserving the structure of the formula. Formally, A = {w | ∃φ ∈ SAT suchthatwisobtainedf romφbyreplacingeachvariableinφbyeither0or1}.
3. Let B be the language of all strings that can be obtained by replacing each variable in a formula in SAT by either 1 or 0, while negating each literal (i.e., replacing each occurrence of a variable by its negation and vice versa), and preserving the structure of the formula. Formally, B = {w | ∃φ ∈ SAT suchthatwisobtainedf romφbyreplacingeachvariableinφbyeither1or0, andnegatingeachliteral}. It is easy to see that A and B are both in NP, since given a string w, we can check if it can be obtained from a formula in SAT by the prescribed substitution rules in polynomial time. Moreover, it is clear that A ∪ B = {0, 1}∗, since any string in {0, 1}∗ can be obtained by either replacing each variable in a satisfiable formula in SAT by either 0 or 1, or by replacing each variable in a satisfiable formula in SAT by either 1 or 0, and negating each literal. To see that A and B are NP-complete, we need to reduce SAT to both A and B. Given a formula φ in SAT , we can construct a formula φ′ in A by replacing each variable in φ by a new variable Xi, and adding the clauses Xi = 0 and Xi = 1 for each variable Xi in φ. It is easy to check that φ is satisfiable if and only if there exists a string w in A that corresponds to a satisfying assignment for φ. Similarly, we can construct a formula φ′′ in B by replacing each variable in φ by a new variable Yi, and adding the clauses Yi = 1 or Yi = 0 for each variable Xi in φ, depending on whether the occurrence of Xi in φ is negated or not. It is easy to check that φ is satisfiable if and only if there exists a string w in B that corresponds to a satisfying assignment for φ. Therefore, A and B are both NP-complete languages, and A ∪ B = {0, 1}∗.