Formal Logic

Logic is—arguably—all about proving, but proofs can be “costly,” often impossibly so, and today most are delegated to (partly) automatic provers, namely by so-called SAT solvers, software based on the (Boolean) satisfiability problem, or SAT. This is the dual of the (Boolean) validity problem, or VAL, at the core of the conception of the digital computer via Hilbert’s Entscheidungsproblem and the Universal Turing Machine. While these problems—VAL significantly less so than SAT—feature in introductory logic textbooks aimed at computer science students, they are largely or wholly absent from textbooks targeting a mathematical or philosophical studentship. 

Formal logic: Classic problems and proofs corrects this—in our view—misguided state of affairs by providing the basics of formal classical logic from the central viewpoint of a formal, or computer, language that distinguishes itself from the other formal or computer languages by its ability to preserve truth, thus potentially providing solutions to decision problems formulated in terms of VAL and/or SAT. This fundamental aspect of classical logic, truth-preservation, is elaborated on from three main formal semantics, to wit, Tarskian, Herbrand, and algebraic (Boolean) semantics, which, in turn, via the adequateness results for the standard first-order logic, underlie the main proof systems of direct and indirect, or refutation, proofs, associated to VAL and SAT, respectively.

Not focusing on the history of classical logic, this book nevertheless provides discussions and quotes central passages on its origins and development, namely from a philosophical perspective. Not being a book in mathematical logic, it takes formal logic from an essentially mathematical perspective.  Biased towards a computational approach, with SAT and VAL as its backbone, this is thus an introduction to logic that covers essential aspects of the three branches of logic, to wit, philosophical, mathematical, and computational.