This project proceeds from the premise that the historical and logical value of Boole's logical calculus and its connection with Frege's logic remain to be recognised. It begins by discussing Gillies' application of Kuhn's concepts to the history oflogic and proposing the use of the concept of research programme as a methodological tool in the historiography oflogic. Then it analyses'the development of mathematical logic from Boole to Frege in terms of overlapping research programmes whilst discussing especially Boole's logical calculus. Two streams of development run through the project: 1. A discussion and appraisal of Boole's research programme in the context of logical debates and the emergence of symbolical algebra in Britain in the nineteenth century, including the improvements which Venn brings to logic as algebra, and the axiomatisation of 'Boolean algebras', which is due to Huntington and Sheffer. 2. An investigation of the particularity of the Fregean research programme, including an analysis ofthe extent to which certain elements of Begriffsschrift are new; and an account of Frege's discussion of Boole which focuses on the domain common to the two formal languages and shows the logical connection between Boole's logical calculus and Frege's. As a result, it is shown that the progress made in mathematical logic stemmed from two continuous and overlapping research programmes: Boole's introduction ofmathematics in logic and Frege's introduction oflogic in mathematics. In particular, Boole is regarded as the grandfather of metamathematics, and Lowenheim's theorem ofl915 is seen as a revival of his research programme.

Many formal descriptions of DPLL-based SAT algorithms either do not include all essential proof techniques applied by modern SAT solvers or are bound to particular heuristics or data structures. This makes it difficult to analyze proof-theoretic properties or the search complexity of these algorithms. In this paper we try to improve this situation by developing a nondeterministic proof calculus that models the functioning of SAT algorithms based on the DPLL calculus with clause learning. This calculus is independent of implementation details yet precise enough to enable a formal analysis of realistic DPLL-based SAT algorithms. / Viele formale Beschreibungen DPLL-basierter SAT-Algorithmen enthalten entweder nicht alle wesentlichen Beweistechniken, die in modernen SAT-Solvern implementiert sind, oder sind an bestimmte Heuristiken oder Datenstrukturen gebunden. Dies erschwert die Analyse beweistheoretischer Eigenschaften oder der Suchkomplexität derartiger Algorithmen. Mit diesem Artikel versuchen wir, diese Situation durch die Entwicklung eines nichtdeterministischen Beweiskalküls zu verbessern, der die Arbeitsweise von auf dem DPLL-Kalkül basierenden SAT-Algorithmen mit Klausellernen modelliert. Dieser Kalkül ist unabhängig von Implementierungsdetails, aber dennoch präzise genug, um eine formale Analyse realistischer DPLL-basierter SAT-Algorithmen zu ermöglichen.