Lesson 5

Problem. Synthesize a circuit of size \(3\) over \(\{\operatorname{NAND}_{2}, \operatorname{INV}_{1}, \operatorname{AND}_{2}, \operatorname{OR}_{2}\}\) computing the parity of two bits: \(\operatorname{XOR}_{2}(x_{1}, x_{2}) = x_{1} \oplus x_{2}\).