Converting infinite conjunctive normal form to disjunctive norm form

33 Views Asked by At

In general we can convert $\bigwedge_{i=1}^n(p_i\vee q_i)$ into a disjunctive norm form $\bigvee_{j=1}^m(P_j\wedge Q_j)$ where $P_j$ and $Q_j$ are possibly tautologies or finite conjunctions of $p_i$'s and $q_i$'s respectively. Moreover, $m\leq 2^n$. (sketch proof by induction: this is trivial when $n=1$. Suppose it is true for any $i\leq k$. Then \begin{align*} \bigwedge_{i=1}^{k}(p_i\vee q_i)\wedge(p_{k+1}\vee q_{k+1})&=(\bigvee_{j=1}^mP_j\wedge Q_j)\wedge(p_{k+1}\vee q_{k+1})\\ &=\bigvee_{j=1}^m(P_j\wedge Q_j\wedge p_{k+1})\vee (P_j\wedge Q_j\wedge q_{k+1})\\ &=\bigvee_{j=1}^m(P_j'\wedge Q_j)\vee (P_j\wedge Q_j')\\ &=\bigvee_{j=1}^m'(P_j\wedge Q_j) \end{align*} with $m'\leq 2m$. Since $m\leq 2^n$, $m'\leq 2^{n+1}$.) Now I am curious if a similar result is true with respect to (countably) infinite conjunctive normal forms. My current conjecture is that there is no guarantee that a countably infinite conjunctive normal form can be converted to a countably infinite disjunctive normal form, we might need uncountably many disjuncts. But I haven't been able to find a concrete counterexample or proven this using rigorous reasoning.