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 $\perp$ (representing true and false respectively). The connectives are typically $\mathrm{\neg }$, $\wedge$, $\vee$, and $\to$ (representing negation, conjunction, disjunction, and implication), however this set is redundant, and other choices can be used ($T$ and $\perp$ 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 \vDash \varphi$ if $\overline{\nu }(\varphi )=T$, and we say $\vDash \varphi$ if for every $\nu$ such that $\overline{\nu }(\varphi )$ is defined, $\nu \vDash \varphi$ (and say that $\varphi$ 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.

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