Literal (mathematical logic)

In mathematical logic, a literal is an atomic formula (also known as an atom or prime formula) or its negation.^[1][2] 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:^[2]

• 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].^[3] 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.^[4]

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. 

Notes

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Literal (mathematical logic). Read more