1
$\begingroup$

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.

$\endgroup$

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.