# 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.

 Title propositional logic Canonical name PropositionalLogic Date of creation 2013-03-22 13:04:01 Last modified on 2013-03-22 13:04:01 Owner Henry (455) Last modified by Henry (455) Numerical id 6 Author Henry (455) Entry type Definition Classification msc 03B05 Related topic Implication Related topic Biconditional   Related topic Conjunction Related topic Disjunction Related topic PropositionalCalculus Related topic ExclusiveOr Related topic InterpretationOfPropositions Defines proposition