I want to create an algorithm for a CNF formula with clause length n on m literals that is mistake bound by $m^{O(n)}$.
I know that I want to take the input and use feature expansion to create a conjunction, and then using De Morgan's law change it into a disjunction. From there I can use the basic disjunction mistake bound learning model. If I take an example of:
$f = \{(x_1 \lor x_2) \land (x_3 \lor x_4)\}$
$y_1 = (x_1 \lor x_2)$ and $y_2=(x_3 \vee x_4)$
then I can use feature expansion to get: $f=\{y_1 \land y_2\} \Rightarrow \{(y_1 \land y_2) \lor (\neg y_1 \land y_2) \lor (y_1 \land \neg y_2) \lor (\neg y_1 \land \neg y_2)\}$
So I have my conjunction but I'm stuggling on how to get it into a simple disjunction using De Morgan's laws. I know it has something to do with getting the negation normal form but I don't really understand how to do this.
Thanks in advance for the help.