Literal (mathematical logic)

Short description: In mathematical logic, an atomic formula or its negation

In mathematical logic, a literal is an atomic formula (also known as an atom or prime formula) 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 (e.g., [math]\displaystyle{ x }[/math]).
• A negative literal is the negation of an atom (e.g., [math]\displaystyle{ \lnot x }[/math]).

The polarity of a literal is positive or negative depending on whether it is a positive or negative literal.

In logics with double negation elimination (where [math]\displaystyle{ \lnot \lnot x \equiv x }[/math]) the complementary literal or complement of a literal [math]\displaystyle{ l }[/math] can be defined as the literal corresponding to the negation of [math]\displaystyle{ l }[/math]. We can write [math]\displaystyle{ \bar{l} }[/math] to denote the complementary literal of [math]\displaystyle{ l }[/math]. More precisely, if [math]\displaystyle{ l\equiv x }[/math] then [math]\displaystyle{ \bar{l} }[/math] is [math]\displaystyle{ \lnot x }[/math] and if [math]\displaystyle{ l\equiv \lnot x }[/math] then [math]\displaystyle{ \bar{l} }[/math] is [math]\displaystyle{ x }[/math]. Double negation elimination occurs in classical logics but not in intuitionistic logic.

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.

In Boolean functions, each separate occurrence of a variable, either in inverse or uncomplemented form, is a literal. For example, if [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] and [math]\displaystyle{ C }[/math] are variables then the expression [math]\displaystyle{ \bar{A}BC }[/math] contains three literals and the expression [math]\displaystyle{ \bar{A}C+\bar{B}\bar{C} }[/math] contains four literals. However, the expression [math]\displaystyle{ \bar{A}C+\bar{B}C }[/math] would also be said to contain four literals, because although two of the literals are identical ([math]\displaystyle{ C }[/math] appears twice) these qualify as two separate occurrences.

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, [math]\displaystyle{ P(t_1,\ldots,t_n) }[/math] with the terms recursively defined starting from constant symbols, variable symbols, and function symbols. For example, [math]\displaystyle{ \neg Q(f(g(x), y, 2), x) }[/math] 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

• Ben-Ari (2001). Mathematical Logic for Computer Science (2nd ed.). Springer. ISBN 1-85233-319-7. 

• Buss, Samuel R. (1998). "An Introduction to Proof Theory". in Buss, Samuel R.. Handbook of Proof Theory. Amsterdam: Elsevier. pp. 1–78. ISBN 0-444-89840-9. https://mathweb.ucsd.edu/~sbuss/ResearchWeb/handbookI/ChapterI.pdf. 

• Godse, Atul P.; Godse, Deepali A. (2008). Digital Logic Circuits. Technical Publications. ISBN 9788184314250. https://books.google.com/books?id=fig900Q1eJ0C&q=literal. 

• Rautenberg, Wolfgang (2010). A Concise Introduction to Mathematical Logic. Universitext (3rd ed.). Springer. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.