Regra de formação

Na lógica matemática, regras de formação são regras que descrevem quais sequências de símbolos formados a partir do alfabeto da lógica formal são sintáticamente validos dentro da linguagem.Essas regras tratam apenas na posição e da manipulação das sequências de caracteres.Elas não descrevem nada mais da linguagem,como a semantitica(i.e.significado da palavra).(Veja também gramática formal).

Linguagem Formal

Uma linguagem formal é um conjunto organizado de símbolos tendo como característica essencial que ela pode ser precisamente definida em função das formas e das localizações desses símbolos. Tal linguagem pode ser definida sem nenhuma referencia a qualquer tipo de significado de qualquer uma de suas expressões, ela pode existir antes de qualquer interpretação.Uma gramática formal determina que símbolos e conjuntos de símbolos são formulas em uma linguagem formal.

Sistemas Formais

Um sistema formal(também chamado de calculo lógico ou sistema lógico) consiste em uma linguagem formal junto com uma forma de dedução(também chamado de sistema dedutivo).A forma de dedução consiste em um conjunto de regras de transformação(também chamado de regras de inferência) ou conjunto de axiomas, ou ambos.Um sistema formal é usado para derivar uma expressão de outra ou mais expressões.Calculo proposicional e calculo de predicados são exemplos de sistemas formais.

Lógica Proposicional e Lógica de Predicados

As regras de formação do calculo proposicional devem, por exemplo, estar na seguinte forma:

• • Se Φ for uma fórmula proposicional, temos que ¬Φ também é uma fórmula;
•  • Se Φ e Ψ são fórmulas proposicionais temos que (Φ & Ψ), (Φ → Ψ), (Φ $\lor$ Ψ) e (Φ $\leftrightarrow$ Ψ) também são formulas. 

As regras de formação do calculo de predicados incluem as mesmas regras do calculo proposicional mais os quantificadores de forma que se temos uma formula Φ e uma variável α podemos dizer que ($\forall$α)Φ e ($\exists$α)Φ também são fórmulas da lógica de predicados.

Veja também

• Máquina de estados finita