Fórmula bien formada

Fórmula lógica sintácticamente correcta

En lógica matemática , lógica proposicional y lógica de predicados , una fórmula bien formada , abreviada WFF o wff , a menudo simplemente fórmula , es una secuencia finita de símbolos de un alfabeto dado que forma parte de un lenguaje formal . ^[1]

La abreviatura wff se pronuncia "woof", o a veces "wiff", "weff" o "whiff". ^[12]

Un lenguaje formal se puede identificar con el conjunto de fórmulas que lo componen. Una fórmula es un objeto sintáctico al que se le puede dar un significado semántico mediante una interpretación . Dos usos clave de las fórmulas son la lógica proposicional y la lógica de predicados.

Introducción

Un uso clave de las fórmulas es en la lógica proposicional y la lógica de predicados, como la lógica de primer orden . En esos contextos, una fórmula es una cadena de símbolos φ para la que tiene sentido preguntar "¿es φ verdadero?", una vez que se han instanciado todas las variables libres en φ. En la lógica formal, las demostraciones se pueden representar mediante secuencias de fórmulas con ciertas propiedades, y la fórmula final en la secuencia es lo que se demuestra.

Aunque el término "fórmula" puede utilizarse para designar marcas escritas (por ejemplo, en un trozo de papel o en una pizarra), se entiende con más precisión como la secuencia de símbolos que se expresan, siendo las marcas un ejemplo simbólico de la fórmula. Esta distinción entre la noción vaga de "propiedad" y la noción inductivamente definida de fórmula bien formada tiene sus raíces en el artículo de Weyl de 1910 "Über die Definitionen der mathematischen Grundbegriffe". ^[13] Por lo tanto, la misma fórmula puede escribirse más de una vez, y una fórmula podría, en principio, ser tan larga que no se pueda escribir en absoluto dentro del universo físico.

Las fórmulas son en sí mismas objetos sintácticos. Se les asigna un significado mediante interpretaciones. Por ejemplo, en una fórmula proposicional, cada variable proposicional puede interpretarse como una proposición concreta, de modo que la fórmula general expresa una relación entre estas proposiciones. Sin embargo, no es necesario interpretar una fórmula para que se la considere únicamente como tal.

Cálculo proposicional

Las fórmulas del cálculo proposicional , también llamadas fórmulas proposicionales , ^[14] son ​​expresiones como . Su definición comienza con la elección arbitraria de un conjunto V de variables proposicionales . El alfabeto consta de las letras en V junto con los símbolos para los conectores proposicionales y los paréntesis "(" y ")", todos los cuales se supone que no están en V . Las fórmulas serán ciertas expresiones (es decir, cadenas de símbolos) sobre este alfabeto. ${\displaystyle (A\land (B\lor C))}$

Las fórmulas se definen inductivamente de la siguiente manera:

• Cada variable proposicional es, en sí misma, una fórmula.
• Si φ es una fórmula, entonces ¬φ es una fórmula.
• Si φ y ψ son fórmulas y • es cualquier conectivo binario, entonces ( φ • ψ) es una fórmula. Aquí • podría ser (pero no se limita a) los operadores habituales ∨, ∧, → o ↔.

Esta definición también puede escribirse como una gramática formal en forma Backus-Naur , siempre que el conjunto de variables sea finito:

< conjunto alfa >  ::= p | q | r | s | t | u | ... (el conjunto finito arbitrario de variables proposicionales) < forma >  ::=  < conjunto alfa > | ¬ < forma > | ( < forma > ∧ < forma > ) | ( < forma > ∨ < forma > ) | ( < forma > → < forma > ) | ( < forma > ↔ < forma > )

Usando esta gramática, la secuencia de símbolos

((( p → q ) ∧ ( r → s )) ∨ (¬ q ∧ ¬ s ))

es una fórmula, porque es gramaticalmente correcta. La secuencia de símbolos

(( p → q )→( qq )) p ))

No es una fórmula, porque no se ajusta a la gramática.

Una fórmula compleja puede ser difícil de leer, debido, por ejemplo, a la proliferación de paréntesis. Para paliar este último fenómeno, se suponen reglas de precedencia (similares al orden matemático estándar de operaciones ) entre los operadores, lo que hace que algunos operadores sean más vinculantes que otros. Por ejemplo, suponiendo la precedencia (de más vinculante a menos vinculante) 1. ¬ 2. → 3. ∧ 4. ∨. Entonces la fórmula

((( p → q ) ∧ ( r → s )) ∨ (¬ q ∧ ¬ s ))

puede abreviarse como

p → q ∧ r → s ∨ ¬ q ∧ ¬ s

Sin embargo, esto es sólo una convención utilizada para simplificar la representación escrita de una fórmula. Si se asumiera, por ejemplo, que la precedencia es asociativa de izquierda a derecha, en el siguiente orden: 1. ¬ 2. ∧ 3. ∨ 4. →, entonces la misma fórmula anterior (sin paréntesis) se reescribiría como

( p → ( q ∧ r )) → ( s ∨ (¬ q ∧ ¬ s ))

Lógica de predicados

La definición de una fórmula en lógica de primer orden es relativa a la firma de la teoría en cuestión. Esta firma especifica los símbolos de constante, predicado y función de la teoría en cuestión, junto con las aridades de la función y los símbolos de predicado. ${\displaystyle {\mathcal {QS}}}$

La definición de una fórmula consta de varias partes. En primer lugar, se define recursivamente el conjunto de términos . Los términos, informalmente, son expresiones que representan objetos del dominio del discurso .

1. Cualquier variable es un término.
2. Cualquier símbolo constante de la firma es un término
3. una expresión de la forma f ( t ₁ ,..., t _n ), donde f es un símbolo de función n -aria, y t ₁ ,..., t _n son términos, es nuevamente un término.

El siguiente paso es definir las fórmulas atómicas .

1. Si t ₁ y t ₂ son términos entonces t ₁ = t ₂ es una fórmula atómica
2. Si R es un símbolo de predicado n -ario, y t ₁ ,..., t _n son términos, entonces R ( t ₁ ,..., t _n ) es una fórmula atómica

Finalmente, el conjunto de fórmulas se define como el conjunto más pequeño que contiene el conjunto de fórmulas atómicas tales que se cumple lo siguiente:

1. ${\displaystyle \neg \phi }$es una fórmula cuando es una fórmula ${\displaystyle \phi }$
2. ${\displaystyle (\phi \land \psi )}$y son fórmulas cuando y son fórmulas; ${\displaystyle (\phi \lor \psi )}$ ${\displaystyle \phi }$ ${\displaystyle \psi }$
3. ${\displaystyle \exists x\,\phi }$es una fórmula cuando es una variable y es una fórmula; ${\displaystyle x}$ ${\displaystyle \phi }$
4. ${\displaystyle \forall x\,\phi }$es una fórmula cuando es una variable y es una fórmula (alternativamente, podría definirse como una abreviatura de ). ${\displaystyle x}$ ${\displaystyle \phi }$ ${\displaystyle \forall x\,\phi }$ ${\displaystyle \neg \exists x\,\neg \phi }$

Si una fórmula no tiene ocurrencias de o , para ninguna variable , entonces se llama ${\displaystyle \exists x}$ ${\displaystyle \forall x}$ ${\displaystyle x}$fórmula sin cuantificadores . Una fórmula existencial es una fórmula que comienza con una secuencia de cuantificación existencial seguida de una fórmula sin cuantificadores.

Fórmulas atómicas y abiertas

Una fórmula atómica es una fórmula que no contiene conectores lógicos ni cuantificadores , o equivalentemente una fórmula que no tiene subfórmulas estrictas. La forma precisa de las fórmulas atómicas depende del sistema formal en consideración; para la lógica proposicional , por ejemplo, las fórmulas atómicas son las variables proposicionales . Para la lógica de predicados , los átomos son símbolos de predicado junto con sus argumentos, siendo cada argumento un término .

Según cierta terminología, una fórmula abierta se forma combinando fórmulas atómicas utilizando únicamente conectivos lógicos, con exclusión de cuantificadores. ^[15] Esto no debe confundirse con una fórmula que no es cerrada.

Fórmulas cerradas

Una fórmula cerrada , también fórmula fundamental u oración , es una fórmula en la que no hay ocurrencias libres de ninguna variable . Si A es una fórmula de un lenguaje de primer orden en el que las variables v ₁ , …, v _n tienen ocurrencias libres, entonces A precedido por ∀ v ₁ ⋯ ∀ v _n es una clausura universal de A .

Propiedades aplicables a las fórmulas

• Una fórmula A en un idioma es válida si es verdadera para cada interpretación de . ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathcal {Q}}}$
• Una fórmula A en un idioma es satisfacible si es verdadera para alguna interpretación de . ${\displaystyle {\mathcal {Q}}}$ ${\displaystyle {\mathcal {Q}}}$
• Una fórmula A del lenguaje de la aritmética es decidible si representa un conjunto decidible , es decir, si existe un método efectivo que, dada una sustitución de las variables libres de A , dice que o bien la instancia resultante de A es demostrable o bien su negación lo es.

Uso de la terminología

En trabajos anteriores sobre lógica matemática (por ejemplo, de Church ^[16] ), las fórmulas se referían a cualquier cadena de símbolos y, entre estas cadenas, las fórmulas bien formadas eran las cadenas que seguían las reglas de formación de fórmulas (correctas).

Varios autores simplemente dicen fórmula. ^{[17] [18] [19] [20]} Los usos modernos (especialmente en el contexto de la ciencia informática con software matemático como verificadores de modelos , demostradores de teoremas automatizados , demostradores de teoremas interactivos ) tienden a retener de la noción de fórmula solo el concepto algebraico y dejar la cuestión de la buena formación , es decir, de la representación de cadena concreta de fórmulas (usando este o aquel símbolo para conectivos y cuantificadores, usando esta o aquella convención de paréntesis , usando notación polaca o infija , etc.) como un mero problema de notacional.

La expresión "fórmulas bien formadas" (WFF, por sus siglas en inglés) también se ha infiltrado en la cultura popular. WFF es parte de un juego de palabras esotérico utilizado en el nombre del juego académico "WFF 'N PROOF: The Game of Modern Logic", de Layman Allen, [ 21 ] ^desarrollado mientras estaba en la Facultad de Derecho de Yale (más tarde fue profesor en la Universidad de Michigan ). La serie de juegos está diseñada para enseñar los principios de la lógica simbólica a los niños (en notación polaca ). ^[22] Su nombre es un eco de whiffenpoof , una palabra sin sentido utilizada como un grito de alegría en la Universidad de Yale que se hizo popular en The Whiffenpoof Song y The Whiffenpoofs . ^[23]

Véase también

• Portal de filosofía

• Expresión fundamental
• Expresión bien definida
• Lenguaje formal
• Glosario de lógica
• WFF y prueba

Notas

1. Las fórmulas son un tema estándar en la lógica introductoria y están cubiertas en todos los libros de texto introductorios, incluidos Enderton (2001), Gamut (1990) y Kleene (1967).
2. Gensler, Harry (11 de septiembre de 2002). Introducción a la lógica. Routledge. pág. 35. ISBN 978-1-134-58880-0.
3. Hall, Cordelia; O'Donnell, John (17 de abril de 2013). Matemáticas discretas mediante una computadora. Springer Science & Business Media. pág. 44. ISBN 978-1-4471-3657-6.
4. Agler, David W. (2013). Lógica simbólica: sintaxis, semántica y demostración. Rowman & Littlefield. pág. 41. ISBN 978-1-4422-1742-3.
5. Simpson, RL (17 de marzo de 2008). Fundamentos de lógica simbólica - Tercera edición. Broadview Press. pág. 14. ISBN 978-1-77048-495-5.
6. Laderoute, Karl (24 de octubre de 2022). Una guía de bolsillo para la lógica formal . Broadview Press. pág. 59. ISBN 978-1-77048-868-7.
7. Maurer, Stephen B.; Ralston, Anthony (21 de enero de 2005). Matemáticas algorítmicas discretas, tercera edición. CRC Press. pág. 625. ISBN 978-1-56881-166-6.
8. Martin, Robert M. (6 de mayo de 2002). Diccionario del filósofo, tercera edición. Broadview Press. pág. 323. ISBN 978-1-77048-215-9.
9. Date, Christopher (14 de octubre de 2008). Diccionario de bases de datos relacionales, edición ampliada. Apress. p. 211. ISBN 978-1-4302-1042-9.
10. Date, CJ (21 de diciembre de 2015). El nuevo diccionario de bases de datos relacionales: términos, conceptos y ejemplos. "O'Reilly Media, Inc.", pág. 241. ISBN 978-1-4919-5171-2.
11. Simpson, RL (10 de diciembre de 1998). Fundamentos de lógica simbólica. Broadview Press. pág. 12. ISBN 978-1-55111-250-3.
12. • "guau" ^{[2] [3] [4] [5]}
    • "olor" ^{[6] [7] [8]}
    • "weff" ^{[9] [10]}
    • "olor" ^[11]
    Todas las fuentes respaldaron la pronunciación de "woof". Las fuentes citadas para "wiff", "weff" y "whiff" dieron estas pronunciaciones como alternativas a "woof". La fuente de Gensler da "wood" y "woofer" como ejemplos de cómo pronunciar la vocal en "woof".
13. W. Dean, S. Walsh, La prehistoria de los subsistemas de la aritmética de segundo orden (2016), pág. 6
14. Lógica de primer orden y demostración automática de teoremas, Melvin Fitting, Springer, 1996 [1]
15. Manual de la historia de la lógica, (Vol 5, Lógica desde Russell hasta Church), Lógica de Tarski por Keith Simmons, D. Gabbay y J. Woods Eds, p568 [2].
16. Alonzo Church, [1996] (1944), Introducción a la lógica matemática, página 49
17. Hilbert, David ; Ackermann, Wilhelm (1950) [1937], Principios de lógica matemática, Nueva York: Chelsea
18. Hodges, Wilfrid (1997), Una teoría de modelos más breve, Cambridge University Press, ISBN 978-0-521-58713-6 
19. Barwise, Jon , ed. (1982), Manual de lógica matemática, Estudios de lógica y fundamentos de las matemáticas, Ámsterdam: Holanda Septentrional, ISBN 978-0-444-86388-1 
20. Cori, Rene; Lascar, Daniel (2000), Lógica matemática: un curso con ejercicios, Oxford University Press, ISBN 978-0-19-850048-3 
21. Ehrenburg 2002
22. Más técnicamente, lógica proposicional utilizando el cálculo estilo Fitch .
23. Allen (1965) reconoce el juego de palabras.

Referencias

• Allen, Layman E. (1965), "Hacia el aprendizaje autotélico de la lógica matemática mediante los juegos WFF 'N PROOF", Aprendizaje matemático: Informe de una conferencia patrocinada por el Comité de Investigación de Procesos Intelectuales del Consejo de Investigación de Ciencias Sociales , Monografías de la Sociedad para la Investigación en Desarrollo Infantil, 30 (1): 29–41
• Boolos, George ; Burgess, John; Jeffrey, Richard (2002), Computabilidad y lógica (4.ª ed.), Cambridge University Press , ISBN 978-0-521-00758-0
• Ehrenberg, Rachel (primavera de 2002). "He's Positively Logical". Michigan Today . Universidad de Michigan. Archivado desde el original el 8 de febrero de 2009. Consultado el 19 de agosto de 2007 .
• Enderton, Herbert (2001), Una introducción matemática a la lógica (2.ª ed.), Boston, MA: Academic Press , ISBN 978-0-12-238452-3
• Gamut, LTF (1990), Lógica, lenguaje y significado, volumen 1: Introducción a la lógica , University Of Chicago Press, ISBN 0-226-28085-3
• Hodges, Wilfrid (2001), "Lógica clásica I: lógica de primer orden", en Goble, Lou (ed.), The Blackwell Guide to Philosophical Logic , Blackwell, ISBN 978-0-852-3-3 978-0-631-20692-7
• Hofstadter, Douglas (1980), Gödel, Escher, Bach: Una eterna trenza dorada , Penguin Books , ISBN 978-0-14-005579-5
• Kleene, Stephen Cole (2002) [1967], Lógica matemática , Nueva York: Dover Publications , ISBN 978-0-486-42533-7, Sr.  1950307
• Rautenberg, Wolfgang (2010), Una introducción concisa a la lógica matemática (3.ª ed.), Nueva York: Springer Science+Business Media , doi :10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6

Enlaces externos

• Fórmula bien formada para la lógica de predicados de primer orden: incluye un breve cuestionario de Java .
• Fórmula bien formada en ProvenMath