propositional logic


A propositional logicPlanetmathPlanetmath 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 relationsMathworldPlanetmath, functions, or quantifiersMathworldPlanetmath except for the constants T and (representing true and false respectively). The connectivesMathworldPlanetmath are typically ¬, , , and (representing negationMathworldPlanetmath, conjunctionMathworldPlanetmath, disjunctionMathworldPlanetmath, and implicationMathworldPlanetmath), however this set is redundant, and other choices can be used (T and can also be considered 0-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 formulasMathworldPlanetmath which contain only the variables ν is defined on by adding recursive clauses for the usual definitions of connectives. For instance ν¯(αβ)=T iff ν¯(α)=ν¯(β)=T.

Then we say νϕ if ν¯(ϕ)=T, and we say ϕ if for every ν such that ν¯(ϕ) is defined, νϕ (and say that ϕ is a tautologyMathworldPlanetmath).

Propositional logic is decidable: there is an easy way to determine whether a sentenceMathworldPlanetmath is a tautology. It can be done using truth tablesMathworldPlanetmath, 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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath problem of whether a formula is satisfiableMathworldPlanetmath (that is, whether its negation is a tautology) is a canonical example of an 𝒩𝒫-completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath 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 BiconditionalMathworldPlanetmathPlanetmath
Related topic Conjunction
Related topic Disjunction
Related topic PropositionalCalculus
Related topic ExclusiveOr
Related topic InterpretationOfPropositions
Defines proposition