Literal (lógica matemática)

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.

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 opuesto

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

En lógica proposicional

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

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

Forma normal disyuntiva

Bibliografía

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

CORI, René y LASCAR, Daniel: Logique mathématique I. Calcul propositionnel, algèbres de Boole, calcul des prédicats (Lógica matemática. I: Cálculo preposicional, álgebras de Boole, cálculo de predicados). Col. Axiomes (Axiomas). Masson, 1993. ISBN 2-225-84079-2
- Sobre las ediciones de esa obra; en la Wikipedia en francés.

puch

Notas

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:

DAVIS, M. y PUTNAM, H.: A computing procedure for quantification theory (Un procedimiento de computación para la teoría de la cuantificación), Journal of the ACM, vol. 7, 1960, pp. 201 - 215.

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

BUSS, Samuel R. (ed.): An introduction to proof theory (Introducción a la teoría de la demostración), en Handbook of proof theory (Manual de teoría de la demostración), 1998, Elsevier, pp. 1-78. ISBN 0-444-89840-9
- Texto parcial en inglés.
- Texto parcial en inglés.

Datos: Q14235582

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.