Given a set of values of instances from a concept class, we say that we PAC-learn the concept class if we can find a function that, with high probability, evaluates random instances from that concept class with small error. We describe algorithms for the PAC-learnability of decision trees, DNF formulas and small degree polynomials. We show a connection between automatizability and PAC-learnability of DPLL versus decision trees, resolution versus DNF formulas, and polynomial calculus versus small degree polynomials.Proof systems are a method of proving unsatisfiability of CNF formulas, based on the syntactic form of the CNF, rather than the semantic one. Automatizability of a proof system implies an algorithm that finds a proof in that proof system in time polynomial in the size of the shortest proof.In the end, we give a somewhat simpler proof of [AR01] that resolution is not automatizable under complexity assumptions.