Generalisation of DNF to CNF for DNF of m choose l clauses

133 Views Asked by At

Given two values $m$ and $l$, I can create corresponding DNF formula which is a disjunction of all $m \choose l$ combinations, where each number corresponds to a variable. Each combination is, in itself, a conjunction. For example, when $m=4$ and $l=3$, the corresponding DNF formula is:

$$ (v_1 \wedge v_2 \wedge v_3) \vee (v_1 \wedge v_2 \wedge v_4) \vee (v_2 \wedge v_3 \wedge v_4) \vee (v_1 \wedge v_3 \wedge v_4) $$

Now, I want to convert this to CNF. When I do, I get a conjunction of all $4 \choose 2$ combinations, where each combination is a disjunctive clause. For different values of $m$ and $l$, the CNF seems to be a conjunction of some $m \choose x$ combinations.

My problem is that I am unable to find a pattern for the value of $x$ for different $m$s and $l$s so that I can generalise my conversion. I understand that DNF $\to$ CNF conversion is in Co-NP, but this specific instance seems to show some kind of pattern that I cannot spot.

EDIT: Eric has stated that $x = m+1-l$, which aligns with all of the examples I've tried. Is anyone able to explain, mathematically, why this pattern holds?