Suppose we want to learn the Boolean function in instance space $X=\{0,1\}^3$. We are given two models to examine: $H_1$ is a set of all logical functions in the conjunctive normal form (CNF), $H_2$ is a set of logical functions which can be displayed in Horn clause (disjunction of literals with at most one positive). Explain what is the relation between $H_1$ and $H_2$, and which sort of inductive bias is implemented in those models.

I apologize in advance if I translated something poorly.
This is my idea. Since CNF holds all logical expressions, that would imply that it can also hold all logical functions, because every expression which is not in CNF can be converted to a CNF. Since CNF can hold all logical function wouldn't it imply that it can hold all sets of Boolean function, and given that $H_2$ is a special case, which is smaller than $H_1$ wouldn't it apply that all solutions can be found in $H_2$.

That's what I got so far, can someone confirm this or deny it, or how much off am I? Any tips would be appreciated!

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.