Completeness theory for propositional logics

More about the book

Completeness is a crucial concept in logic and the foundations of mathematics, with various definitions explored in literature. This discussion focuses on the variants of completeness defined in propositional logic. Completeness refers to the ability to derive all correct and reliable inference schemata through logical methods. The term 'all' is significant here, as it highlights a key distinction. According to E. Post's definition, completeness can be viewed globally, where reliability pertains solely to syntactic means of logic, leaving only inconsistent inference schemata outside the realm of correctness. However, local aspects cannot be ignored when relating completeness to specific notions of truth. This perspective sees completeness as the adequacy of logic concerning particular semantics, indicating that changes in logic necessitate changes in semantics. J. Łukasiewicz effectively utilized this understanding, while A. Tarski and A. Lindenbaum investigated it more broadly, laying strong foundations for logic research, particularly regarding consequence operations defined by logical systems. The selection of logical means for representing inferences is also critical, with most completeness theory definitions and results initially developed within propositional logic, which has numerous applications in logic and theoretical computer science.