propositional logic

A propositional logic^{👁 Planetmath
👁 Planetmath}
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^{👁 Mathworld
👁 Planetmath}
, functions, or quantifiers^{👁 Mathworld
👁 Planetmath}
except for the constants and (representing true and false respectively). The connectives^{👁 Mathworld
👁 Planetmath}
are typically , , , and (representing negation^{👁 Mathworld
👁 Planetmath}
, conjunction^{👁 Mathworld
👁 Planetmath}
, disjunction^{👁 Mathworld
👁 Planetmath}
, and implication^{👁 Mathworld
👁 Planetmath}
), however this set is redundant, and other choices can be used ( and can also be considered -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^{👁 Mathworld
👁 Planetmath}
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^{👁 Mathworld
👁 Planetmath}
).

Propositional logic is decidable: there is an easy way to determine whether a sentence^{👁 Mathworld
👁 Planetmath}
is a tautology. It can be done using truth tables^{👁 Mathworld
👁 Planetmath}
, 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^{👁 Mathworld
👁 Planetmath
👁 Planetmath
👁 Planetmath
👁 Planetmath}
problem of whether a formula is satisfiable^{👁 Mathworld
👁 Planetmath}
(that is, whether its negation is a tautology) is a canonical example of an -complete^{👁 Planetmath
👁 Planetmath
👁 Planetmath
👁 Planetmath
👁 Planetmath
👁 Planetmath}
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👁 Mathworld 👁 Planetmath 👁 Planetmath
Related topic	Conjunction
Related topic	Disjunction
Related topic	PropositionalCalculus
Related topic	ExclusiveOr
Related topic	InterpretationOfPropositions
Defines	proposition