## You are here

Homepropositional logic

## Primary tabs

# propositional logic

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.

## Mathematics Subject Classification

03B05*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections