Exercise $3$ Prove that every CNF formula equivalent to

$($P$1$ Q$1)($P$2$ Q$2)...($Pn $$ Qn$)$

must have at least $2^$n clauses. $($Hint: Show that for every assignment of either P or Q to each of the subscripts $\{1,2,...,$ n$\}$ there is a clause in the CNF which has exactly one of Pi$,$ Qi for each i$,$ according to whether P or Q is assigned to i$.$ For example, if n $=3,$ then there must be a clause whose positive literals are exactly $\{$Q$1,$ P$2,$ Q$3\}.)($A literal is positive if it has no $.)$