Regla de formación

En lógica matemática , las reglas de formación son reglas para describir qué cadenas de símbolos formadas a partir del alfabeto de un lenguaje formal son sintácticamente válidas dentro del lenguaje. ^[1] Estas reglas solo abordan la ubicación y manipulación de las cadenas del lenguaje. No describen nada más sobre un lenguaje, como su semántica (es decir, lo que significan las cadenas). (Véase también gramática formal ).

Un lenguaje formal es un conjunto organizado de símbolos cuya característica esencial es que puede definirse con precisión en términos de las formas y ubicaciones de esos símbolos. Un lenguaje de este tipo puede definirse, por tanto, sin ninguna referencia a ningún significado de ninguna de sus expresiones; puede existir antes de que se le asigne ninguna interpretación , es decir, antes de que tenga algún significado. Una gramática formal determina qué símbolos y conjuntos de símbolos son fórmulas en un lenguaje formal.

Un sistema formal (también llamado cálculo lógico o sistema lógico ) consiste en un lenguaje formal junto con un aparato deductivo (también llamado sistema deductivo ). El aparato deductivo puede consistir en un conjunto de reglas de transformación (también llamadas reglas de inferencia ) o un conjunto de axiomas , o tener ambos. Un sistema formal se utiliza para derivar una expresión a partir de una o más expresiones. Los cálculos proposicionales y de predicados son ejemplos de sistemas formales.

Las reglas de formación de un cálculo proposicional pueden, por ejemplo, tomar una forma tal que;

• Si tomamos Φ como una fórmula proposicional también podemos tomar Φ como una fórmula;${\estilo de visualización \neg}$
• Si tomamos Φ y Ψ como fórmulas proposicionales, también podemos tomar (Φ Ψ), (Φ Ψ), (Φ Ψ) y (Φ Ψ) como fórmulas.${\displaystyle \cuña}$${\displaystyle \to}$${\displaystyle \lor}$${\displaystyle \leftrightarrow }$

Un cálculo de predicados generalmente incluirá las mismas reglas que un cálculo proposicional, con el agregado de cuantificadores tales que si tomamos Φ como una fórmula de lógica proposicional y α como una variable , entonces podemos tomar ( α)Φ y ( α)Φ cada uno como fórmulas de nuestro cálculo de predicados. ${\displaystyle \forall }$${\displaystyle \exists }$

• Autómata de estados finitos