# 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 $\mathcal{N}\mathcal{P}$-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 |