Literal (mathematical logic)

In mathematical logic, a literal is an atomic formula (atom) or its negation. The definition mostly appears in proof theory (of classical logic), e.g. in conjunctive normal form and the method of resolution.

Literals can be divided into two types:

• A positive literal is just an atom.
• A negative literal is the negation of an atom.

For a literal l, the complementary literal is a literal corresponding to the negation of l, we can write $\bar{l}$ to denote the complementary literal of l. More precisely, if $l\equiv x$ then $\bar{l}$ is $\lnot x$ and if $l\equiv \lnot x$ then $\bar{l}$ is x.

In the context of a formula in the conjunctive normal form, a literal is pure if the literal's complement does not appear in the formula.

Examples

In propositional calculus a literal is simply a propositional variable or its negation.

In predicate calculus a literal is an atomic formula or its negation, where an atomic formula is a predicate symbol applied to some terms, $P(t_1,\ldots,t_n)$ with the terms recursively defined starting from constant symbols, variable symbols, and function symbols. For example, $\neg Q(f(g(x), y, 2), x)$ is a negative literal with the constant symbol 2, the variable symbols x, y, the function symbols f, g, and the predicate symbol Q.

References

• Samuel R. Buss (1998). "An introduction to proof theory". In Samuel R. Buss. Handbook of proof theory. Elsevier. pp. 1–78. ISBN 0-444-89840-9. http://math.ucsd.edu/~sbuss/ResearchWeb/handbookI/. 

This logic-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Propositional calculus Logic stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем сделать НИР Hidetoshi Mitsusada Paul F. Ryan Look at other dictionaries: Literal — may refer to:*Literal and figurative language, taken in a non figurative sense. *Literal translation, the close adherence to the forms of a source language text. *Terminal symbol in regular expressions and in descriptions of formal grammars.… …   Wikipedia Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia Mathematical beauty — An example of beauty in method a simple and elegant geometrical proof that the Pythagorean theorem is true for a particular right angled triangle. Many mathematicians derive aesthetic pleasure from their work, and from mathematics in general.… …   Wikipedia Resolution (logic) — In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem proving technique for sentences in propositional logic and first order logic. In other words, iteratively applying the… …   Wikipedia Boolean algebra (logic) — For other uses, see Boolean algebra (disambiguation). Boolean algebra (or Boolean logic) is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of… …   Wikipedia Late medieval logic — Paul Vincent Spade I Medieval logic encompassed more than what we call logic today. It included semantics, philosophy of language, parts of physics, of philosophy of mind and of epistemology. Late medieval logic began around 1300 and lasted… …   History of philosophy List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia language, philosophy of — Philosophical study of the nature and use of natural languages and the relations between language, language users, and the world. It encompasses the philosophical study of linguistic meaning (see semantics), the philosophical study of language… …   Universalium Boolean satisfiability problem — For the concept in mathematical logic, see Satisfiability. 3SAT redirects here. For the Central European television network, see 3sat. In computer science, satisfiability (often written in all capitals or abbreviated SAT) is the problem of… …   Wikipedia Propositional formula — In propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a truth value. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”