Literal (lógica matemática)

En lógica matemática , un literal es una fórmula atómica (también conocida como fórmula atómica o prima) o su negación . ^{[1] [2]} La definición aparece principalmente en la teoría de la prueba (de la lógica clásica ), por ejemplo, en la forma normal conjuntiva y el método de resolución .

Los literales se pueden dividir en dos tipos: ^[2]

• Un literal positivo es simplemente un átomo (por ejemplo, ).${\estilo de visualización x}$
• Un literal negativo es la negación de un átomo (por ejemplo, ).${\displaystyle \lno x}$

La polaridad de un literal es positiva o negativa dependiendo de si es un literal positivo o negativo.

En lógicas con eliminación de doble negación (donde ) el literal complementario o complemento de un literal se puede definir como el literal correspondiente a la negación de . ^[3] Podemos escribir para denotar el literal complementario de . Más precisamente, si entonces es y si entonces es . La eliminación de doble negación ocurre en lógicas clásicas pero no en lógica intuicionista . ${\displaystyle \lno \lno x\equiv x}$${\estilo de visualización l}$${\estilo de visualización l}$${\displaystyle {\bar {l}}}$${\estilo de visualización l}$${\displaystyle l\equiv x}$${\displaystyle {\bar {l}}}$${\displaystyle \lno x}$${\displaystyle l\equiv \lno x}$${\displaystyle {\bar {l}}}$${\estilo de visualización x}$

En el contexto de una fórmula en la forma normal conjuntiva , un literal es puro si el complemento del literal no aparece en la fórmula.

En las funciones booleanas , cada ocurrencia independiente de una variable, ya sea en forma inversa o no complementada, es un literal. Por ejemplo, si , y son variables, entonces la expresión contiene tres literales y la expresión contiene cuatro literales. Sin embargo, también se diría que la expresión contiene cuatro literales, porque aunque dos de los literales son idénticos ( aparecen dos veces), estos califican como dos ocurrencias independientes. ^[4]${\estilo de visualización A}$${\estilo de visualización B}$${\estilo de visualización C}$${\displaystyle {\bar {A}}BC}$${\displaystyle {\bar {A}}C+{\bar {B}}{\bar {C}}}$${\displaystyle {\bar {A}}C+{\bar {B}}C}$${\estilo de visualización C}$

En el cálculo proposicional, un literal es simplemente una variable proposicional o su negación.

En el cálculo de predicados, un literal es una fórmula atómica o su negación, donde una fórmula atómica es un símbolo de predicado aplicado a algunos términos , con los términos definidos recursivamente a partir de símbolos de constantes, símbolos de variables y símbolos de funciones . Por ejemplo, es un literal negativo con el símbolo de constante 2, los símbolos de variables x , y , los símbolos de funciones f , g y el símbolo de predicado Q . ${\displaystyle P(t_{1},\ldots ,t_{n})}$${\displaystyle \neg Q(f(g(x),y,2),x)}$

• Ben-Ari, Mordechai (2001). Lógica matemática para la informática (2.ª ed.). Springer. ISBN 1-85233-319-7.

• Buss, Samuel R. (1998). "Introducción a la teoría de la prueba" (PDF) . En Buss, Samuel R. (ed.). Manual de teoría de la prueba. Ámsterdam: Elsevier. pp. 1–78. ISBN 0-444-89840-9.

• Godse, Atul P.; Godse, Deepali A. (2008). Circuitos lógicos digitales. Publicaciones técnicas. ISBN 9788184314250.

• Rautenberg, Wolfgang (2010). Una breve introducción a la lógica matemática . Universitext (3.ª ed.). Springer. doi :10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.