Propositional logic Glossary


Propositional logic is the part of first order logic in which there are no quantifiers or variables. This means it is the logic of connectives only.


Semantically, propositional logic is described by the truth tables for the connectives. Since there are no quantifiers, the more complicated parts of the theory of interpretations are not needed.

Because the internal structure of atoms does not matter to propositional logic, we usually write the atoms just as 'p', 'q, etc.

Although it is so simple, propositional logic is not trivial. The problem of deciding whether a given (finite) sequent is provable or not is generally thought to be intractable: in the jargon of computer science, recognising satisfiable formulae is NP-complete. This means that while we have quite easy ways to decide short sequents, these techniques cannot scale up smoothly to much larger ones.