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 , su opuesto o complementario se puede expresar como , o bien como
De manera más precisa, si , entonces es , y si , entonces es .
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 , un literal es puro si en ese conjunto no hay cláusulas con la forma .
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 y son complementarios si .
En lógica de primer orden
En la lógica de primer orden o lógica de predicados, dos literales y son complementarios si y 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, , 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, es un literal negativo con los siguientes símbolos:
- De constante: 2
- De variables: ,
- De funciones: ,
- De predicado:
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é[1] (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). 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,[2] 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.[3] (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