Literal (lógica matemática)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En lógica matemática, un literal es una fórmula atómica o su negación. La definición del concepto se halla sobre todo en la teoría de la demostración perteneciente al campo de la lógica clásica, como en la forma normal conjuntiva y en el método de resolución.

Se pueden considerar dos tipos de variables:

  • Positivo: un átomo (entendiéndose por tal una fórmula atómica).
  • Negativo: la negación de un átomo.

Se dice que dos literales son opuestos o complementarios si uno de ellos es la negación del otro. Si un literal se expresa como l, su opuesto o complementario se puede expresar como \bar{l}, o bien como l^{op}

De manera más precisa, si l\equiv x, entonces \bar{l} es \lnot x, y si l\equiv \lnot x, entonces \bar{l} es x.

Literales puros[editar]

Con respecto a una fórmula expresada según la forma normal conjuntiva, se dice que un literal es puro si no aparece su complementario en esa fórmula.

Dicho de otra manera, en un conjunto de cláusulas S, un literal es puro si en ese conjunto no hay cláusulas con la forma D \vee l^{op} \vee E.

En un lenguaje menos formal, Un literal en una fórmula en CNF es puro si aparece o bien siempre negado o bien siempre sin negar. Además, se dice que una cláusula C es redundante si contiene al menos un paralelo puro.

Literales en lógica proposicional y en lógica de primer orden[editar]

En lógica proposicional[editar]

En la lógica proposicional, un literal es una variable proposicional. Dos literales l_1 y l_2 son complementarios si l_1 \equiv \lnot l_2.

En lógica de primer orden[editar]

En la lógica de primer orden o lógica de predicados, dos literales l_1 y l_2 son complementarios si l_1 y \lnot l_2 son unificables.

Un literal es una fórmula atómica o su negación, entendiéndose por fórmula atómica un símbolo de predicado aplicado a algunos términos, P(t_1,\,t_n), expresados mediante definición repercusiva (llamada también inductiva) a partir de símbolos de constante, símbolos de variable y símbolos de función. Por ejemplo, \neg Q(f(g(x), y, 2), x) es un literal negativo con los siguientes símbolos:

  • De constante: 2
  • De variables: x, y
  • De funciones: f, g
  • De predicado: Q

Véase también[editar]

Bibliografía[editar]

  • QUINE, W. v. O., 1950: Los métodos de la lógica (Methods of Logic).

puch

Notas[editar]

Con el significado que se trata en el presente artículo, el término «literal» fue empleado por primera vez en este otro:

  • QUINE, W. v. O.: "A way to simplify truth functions" (Manera de simplificar las funciones de verdad), en The American Mathematical Monthly (Mensuario Matemático Estadounidense), vol. 62, 1955, pp. 627 - 631.

El uso del término se consolidó a partir de otro más:

En una de sus ediciones, este artículo de la Wikipedia en español es resultado de la traducción parcial de los correspondientes de las Wikipedias en inglés, francés y portugués.

Referencias[editar]