07 Closure of NP under positive Boolean combination

Theorem

Suppose $L_{1}, L_{2} \in NP$ . Then also:

$L_{1} \cup L_{2} \in NP$

$L_{1} \cap L_{2} \in NP$

Let $A_{1} (x, y), A_{2} (x, y)$ and $p_{1} (n)$ , $p_{2} (n)$ be the verifiers provers for $L_{1}, L_{2}$ respectively

Proof of $L_{1} \cup L_{2} \in NP$

x \in L_{1} \cup L_{2} ⟺ x \in L_{1} or x \in L_{2} ⟺ \exists y_{1} \cdot (∣ y_{1} ∣ < p_{1} (∣ x ∣) and A_{1} (x, y_{1}) accepts) or \exists y_{2} \cdot (∣ y_{2} ∣ < p_{2} (∣ x ∣) and A_{2} (x, y_{2}) accepts) ⟺ \exists y (∣ y ∣ < polynomial p_{1} (∣ x ∣) + p_{2} (∣ x ∣) and \in P verifier (A_{1} (x, y) accepts or A_{2} (x, y) accepts))

For the proof of 2nd theorem, just use and instead of that or.