PAC learning boolean conjunctions
The first positive example will remove enough literals so that the conjunction will become satisfiable.  For example if the first positive example is $x_1\overline{x_2}x_3$ this removes $\overline{x_1}$, $x_2$ and $\overline{x_3}$. So the only time you will end up with an unsatisfiable clause is if you get only negative examples, which is okay, as the correct thing to do is to classify everything as negative anyway.

Also remember that in PAC learning, the learner gets to choose how many examples to see -- so you generally don't have to worry about "not getting enough examples" (as long as you need a number of examples polynomial in the number of relevant parameters).