A propositional logic is a logic in which the only objects are propositions, that is, objects which themselves have truth values. Variables represent propositions, and there are no relations, functions, or quantifiers except for the constants and (representing true and false respectively). The connectives are typically , , , and (representing negation, conjunction, disjunction, and implication), however this set is redundant, and other choices can be used ( and can also be considered 0-ary connectives).

A model for propositional logic is just a truth function on a set of variables. Such a truth function can be easily extended to a truth function on all formulas which contain only the variables is defined on by adding recursive clauses for the usual definitions of connectives. For instance iff .

Then we say if , and we say if for every such that is defined, (and say that is a tautology).

Propositional logic is decidable: there is an easy way to determine whether a sentence is a tautology. It can be done using truth tables, since a truth table for a particular formula can be easily produced, and the formula is a tautology if every assignment of truth values makes it true. It is not known whether this method is efficient: the equivalent problem of whether a formula is satisfiable (that is, whether its negation is a tautology) is a canonical example of an -complete problem.