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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.