Literal (lógica matemática)

En lógica matemática, una fórmula atómica o su negación.

En lógica matemática , un literal es una fórmula atómica (también conocida como átomo o fórmula 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 sólo un átomo (por ejemplo, ). ${\displaystyle x}$
• Un literal negativo es la negación de un átomo (p. ej., ). ${\displaystyle \lnot 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 la doble negación ocurre en la lógica clásica pero no en la lógica intuicionista . ${\displaystyle \lnot \lnot x\equiv x}$ ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle {\bar {l}}}$ ${\displaystyle l}$ ${\displaystyle l\equiv x}$ ${\displaystyle {\bar {l}}}$ ${\displaystyle \lnot x}$ ${\displaystyle l\equiv \lnot x}$ ${\displaystyle {\bar {l}}}$ ${\displaystyle x}$

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

En las funciones booleanas , cada aparición separada 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 ( aparece dos veces), estos califican como dos apariciones separadas. ^[4] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle {\bar {A}}BC}$ ${\displaystyle {\bar {A}}C+{\bar {B}}{\bar {C}}}$ ${\displaystyle {\bar {A}}C+{\bar {B}}C}$ ${\displaystyle C}$

Ejemplos

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

En 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 constantes, símbolos variables y símbolos de funciones . Por ejemplo, es un literal negativo con el símbolo constante 2, los símbolos de variable x , y , los símbolos de función 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)}$

Referencias

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

• Buss, Samuel R. (1998). "Una introducción a la teoría de la prueba" (PDF) . En Buss, Samuel R. (ed.). Manual de teoría de la prueba. Ámsterdam: Elsevier. págs. 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 introducción concisa a la lógica matemática . Universitext (3ª ed.). Saltador. doi :10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6.

Notas

1. Rautenberg (2010, p. 57): "Se dice que las fórmulas obtenidas por (F1) y (F2) son fórmulas primas o atómicas , o simplemente se llaman primas . Como en la lógica proposicional, las fórmulas primas y sus negaciones se llaman literales . "
2. Ben-Ari (2001, p. 30): "Un literal es un átomo o una negación de un átomo. Un átomo es un literal positivo y la negación de un átomo es un literal negativo ".
3. Ben-Ari (2001, p. 69): "Si es literal, es su complemento. Esto significa que si , entonces y si entonces ". ${\displaystyle l}$ ${\displaystyle l^{c}}$ ${\displaystyle l=p}$ ${\displaystyle l^{c}={\bar {p}}}$ ${\displaystyle l={\bar {p}}}$ ${\displaystyle l^{c}=p}$
4. Dios y Dios 2008.