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 $T$ and $\bot$ (representing true and false respectively). The connectives are typically $\neg$ , $\wedge$ , $\vee$ , and $\rightarrow$ (representing negation, conjunction, disjunction, and implication), however this set is redundant, and other choices can be used ($T$ and $\bot$ can also be considered $0$ -ary connectives).

A model for propositional logic is just a truth function $\nu$ on a set of variables. Such a truth function can be easily extended to a truth function $\overline{\nu}$ on all formulas which contain only the variables $\nu$ is defined on by adding recursive clauses for the usual definitions of connectives. For instance $\overline{\nu}(\alpha\wedge\beta)=T$ iff $\overline{\nu}(\alpha)=\overline{\nu}(\beta)=T$ .

Then we say $\nu\models\phi$ if $\overline{\nu}(\phi)=T$ , and we say $\models\phi$ if for every $\nu$ such that $\overline{\nu}(\phi)$ is defined, $\nu\models\phi$ (and say that $\phi$ 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 $\mathcal{NP}$ -complete problem.