Fórmula bem formada

Esse diagrama mostra as entidades sintáticas que podem ser construidas da linguagem formal. Os símbolos e as cadeias de caracteres podem ser formulações sem sentido ou fórmulas bem formadas. Uma linguagem formal pode ser interpretada como sendo o conjunto de suas fórmulas bem formadas. O conjunto de fórmulas bem formadas pode ser dividido em teoremas e não-teoremas.

Em lógica matemática, uma fórmula bem formada, abreviadamente fbf, é uma expressão (por exemplo, uma sequência finita de símbolos de determinado alfabeto) que é parte de uma Linguagem formal.^[1] Uma linguagem formal pode ser considerada como um conjunto contendo todas e apenas suas fórmulas.

Uma fórmula bem formada é um objeto formal sintático a que se pode dar um significado semântico.

Uma utilização chave das fórmulas bem formadas está na lógica proposicional e na lógica de predicados, tal como na lógica de primeira ordem. Nesses contextos, uma fórmula bem formada é um conjunto de símbolos φ que para cada um faz sentido perguntar "φ é verdadeiro?", uma vez que cada variável livre em φ tenha sido instanciada. Em lógica formal, provas podem ser representadas como sequências de fórmulas bem formadas com certas propriedades, e a última fórmula da sequência é o que está provado.

Embora o termo "fórmula" possa ser usada para marcas escritas (por exemplo, em um pedaço de papel ou num quadro-negro), ele é mais precisamente entendido como a sequência que está sendo expressa, com as marcas sendo um evento ou um caso (token) da fórmula. Não é necessária para a existência da fórmula que haja tokens reais dela. Uma linguagem formal pode, assim, ter um número infinito de fórmulas independentemente de cada fórmula ter um token. Além disso, uma mesma fórmula pode ter mais de um token, se ela for escrita mais de uma vez.

Fórmulas bem formadas são muitas vezes interpretadas como proposições (como, por exemplo, em Lógica proposicional). Porém, fórmulas bem formadas são entidades sintáticas e, assim devem ser especificadas numa linguagem formal sem levar em conta nenhuma interpretação. Uma fórmula interpretada pode ser o nome de algo, um adjetivo, um advérbio, uma preposição, uma frase, sentença imperativa, um conjunto de sentenças, um conjunto de nomes, etc. Uma fórmula pode até mesmo se tornar sem sentido se os símbolos da linguagem são especificados para que isso aconteça. Além disso, uma fórmula não precisa receber nenhuma interpretação.

Lógica proposicional

As fórmulas da lógica proposicional, também chamadas de fórmulas proposicionais,^[2] são expressões como

${\displaystyle (A\land (B\lor C))}$

Suas definições começam com a escolha arbitrária de um conjunto V de variáveis proposicionais. O alfabeto consiste das letras em V juntamente com os símbolos para os conectivos e parênteses "(" e ")" - todos os quais, presume-se, não estão contidos em V. As fórmulas serão determinadas expressões (isto é, cadeias de símbolos) sobre este alfabeto.

As fórmulas são indutivamente definidas como se segue:

• Cada variável proposicional é, por si só, uma fórmula.
• Se φ é uma fórmula, então ${\displaystyle \lnot }$φ é uma fórmula.
• Se φ e ψ são fórmulas, e • é um conectivo binário, então ( φ • ψ) é uma fórmula. Aqui, • pode ser (mas não se limita a ser) os operadores ∨, ∧, →, ou ↔.

Essa definição também pode ser escrita como uma gramática formal na notação de Backus-Naur, desde que o conjunto de variáveis seja finito:

<conjunto alpha> ::= p | q | r | s | t | u | ... (o conjunto arbitrário finito de variáveis proposicionais)

<forma> ::= <conjunto alpha> | ${\displaystyle \neg }$<forma> | (<forma>${\displaystyle \wedge }$<forma>) | (<forma>${\displaystyle \vee }$<forma>) | (<forma>${\displaystyle \rightarrow }$<forma>) | (<forma>${\displaystyle \leftrightarrow }$<forma>)

Usando essa gramática, a sequência de símbolos

(((p ${\displaystyle \rightarrow }$ q) ${\displaystyle \wedge }$ (r ${\displaystyle \rightarrow }$ s)) ${\displaystyle \vee }$ (${\displaystyle \neg }$q ${\displaystyle \wedge }$ ${\displaystyle \neg }$s))

é uma fórmula bem formada, porque é gramaticalmente correta. A sequência de símbolos

((p ${\displaystyle \rightarrow }$ q)${\displaystyle \rightarrow }$(qq))p))

não é uma fórmula bem formada, porque não obedece à gramática.

Uma fórmula complexa pode ser difícil de ser lida, devido a, por exemplo, a proliferação de parênteses. Para aliviar este último fenômeno, regras de precedência (semelhante à ordem matemática de execução de operações) são assumidas entre os operadores, tornando alguns operadores mais vinculativos que outros. Por exemplo, assumindo a precedência (do mais vinculativo ao menos vinculativo) 1. ${\displaystyle \neg }$   2. ${\displaystyle \rightarrow }$  3. ${\displaystyle \wedge }$  4. ${\displaystyle \vee }$. Então a fórmula

(((p ${\displaystyle \rightarrow }$ q) ${\displaystyle \wedge }$ (r ${\displaystyle \rightarrow }$ s)) ${\displaystyle \vee }$ (${\displaystyle \neg }$q ${\displaystyle \wedge }$ ${\displaystyle \neg }$s))

pode ser abreviada como

p ${\displaystyle \rightarrow }$ q ${\displaystyle \wedge }$ r ${\displaystyle \rightarrow }$ s ${\displaystyle \vee }$ ${\displaystyle \neg }$q ${\displaystyle \wedge }$ ${\displaystyle \neg }$s

Isto é, porém, apenas uma convenção usada para simplificar a representação escrita da fórmula. Se a precedência for assumida, por exemplo, para ser esquerda-direita, na ordem: 1. ${\displaystyle \neg }$   2. ${\displaystyle \wedge }$  3. ${\displaystyle \vee }$  4. ${\displaystyle \rightarrow }$, então a mesma fórmula acima (sem parênteses) poderia ser reescrita como

(p ${\displaystyle \rightarrow }$ (q ${\displaystyle \wedge }$ r)) ${\displaystyle \rightarrow }$ (s ${\displaystyle \vee }$ ((${\displaystyle \neg }$q) ${\displaystyle \wedge }$ (${\displaystyle \neg }$s)))

Lógica de primeira ordem

A definição de fórmula bem formada em lógica de primeira ordem ${\displaystyle {\mathcal {QS}}}$ é semelhante à assinatura da teoria. Essa assinatura especifica as constantes, símbolos de relação, e símbolos de função dessa teoria, juntamente com suas aridades.

A definição de uma fórmula vem de partes individuais. Primeiro, o conjunto dos termos é definido recursivamente. Termos, informalmente, são expressões que representam objetos do domínio do discurso.

1. Qualquer variável é um termo.
2. Qualquer constante da assinatura é um termo.
3. Uma expressão da forma f(t₁,...,t_n), onde f é uma n-ária função, e t₁,...,t_n são termos , é, novamente, um termo.

O próximo passo é definir as fórmulas atômicas.

1. Se t₁ e t₂ são termos, então t₁=t₂ é uma fórmula atômica
2. Se R é um n-ário símbolo de relação, e t₁,...,t_n são termos, então R(t₁,...,t_n) é uma fórmula atômica

Finalmente, o conjunto de fórmulas é definindo como sendo o menor conjunto contendo o conjunto de fórmulas atômicas tal que seguem as seguintes regras:

1. ${\displaystyle \neg \phi }$ é uma fórmula quando ${\displaystyle \ \phi }$ é uma fórmula
2. ${\displaystyle (\phi \land \psi )}$ e ${\displaystyle (\phi \lor \psi )}$ são fórmulas quando ${\displaystyle \ \phi }$ e ${\displaystyle \ \psi }$ são fórmulas;
3. ${\displaystyle \exists x\,\phi }$ é uma fórmula quando ${\displaystyle \ x}$ é uma variável e ${\displaystyle \ \phi }$ é uma fórmula;
4. ${\displaystyle \forall x\,\phi }$ é uma fórmula quando ${\displaystyle \ x}$ éuma variável e ${\displaystyle \ \phi }$ é uma fórmula (alternativamente, ${\displaystyle \forall x\,\phi }$ pode ser definido como uma abreviação para ${\displaystyle \neg \exists x\,\neg \phi }$).

Se uma fórmula não tem ocorrências de ${\displaystyle \exists x}$ ou ${\displaystyle \forall x}$, para qualquer variável ${\displaystyle \ x}$, então ela é chamada livre de quantificadores. Uma fórmula existencial é uma fórmula começando com uma sequência de quantificação existencial seguida por uma fórmula livre de quantificadores.

Fórmulas atômicas e abertas

Ver artigo principal: Fórmula atômica

Uma fórmula atômica é aquela que não contém conectivos lógicos nem quantificadores, ou seja, uma fórmula que não contém sub-fórmulas.

A forma exata das fórmulas atômicas depende do sistema formal considerado; para a lógica proposicional, por exemplo, as fórmulas atômicas são as variáveis proposicionais. Para lógica de predicados, os átomos são símbolos de predicados juntamente com seus argumentos - cada argumento sendo um termo.

De acordo com a terminologia, uma fórmula aberta é formada mediante a combinação de fórmulas atômicas, usando-se apenas conectivos lógicos, para a exclusão dos quantificadores.^[3] Isso não deve ser confundido com uma fórmula que não está fechada.

Fórmulas fechadas

Uma fórmula fechada, também conhecida como fórmula de átomo básico ou sentença, é uma fórmula onde não há ocorrências livres de nenhuma variável. Se A é uma fórmula de uma linguagem de primeira ordem na qual as variáveis v₁, ..., v_n tem ocorrências livres, então A precedida por v₁ ... v_n é um encerramento de A.

Propriedades aplicáveis ​​às fórmulas

• Uma fórmula A numa linguagem ${\displaystyle {\mathcal {Q}}}$ é válida se for verdadeira para toda interpretação de ${\displaystyle {\mathcal {Q}}}$.
• Uma fórmula A numa linguagem ${\displaystyle {\mathcal {Q}}}$ é satisfatível se ela for verdadeira para alguma interpretação de ${\displaystyle {\mathcal {Q}}}$.
• Uma fórmula A da linguagem aritmética é decidível se representa um conjunto decidível, isto é, se há algum método efetivo no qual, dada uma substituição de variáveis livres de A, tanto o resultado de A é provável como sua negação o é.

Uso da terminologia

Em trabalhos anteriores sobre lógica matemática (por exemplo, Church, [1996], (1944)^[4]), fórmulas se referiam a quaisquer cadeias de símbolos e, entre essas cadeias, fórmulas bem formadas eram as cadeias que seguiam as regras de formação de fórmulas (corretas).

Vários autores dizem simplesmente "fórmula".^[5][6][7][8] Usos modernos (especialmente no contexto de ciência da computação com softwares matemáticos tais como verificadores de modelo, provadores automáticos de teoremas) tendem a reter da noção de fórmula apenas o conceito algébrico e deixar a questão da boa formação, isto é, da concreta representação de cadeia de fórmulas (usando este ou aquele símbolo como conectivos e quantificadores, usando esta ou aquela oderm de operações, usando notação polonesa ou notação infixa, etc.) como um mero problema de notação.

Entretanto, a "expressão fórmula bem formada" ainda pode ser encontrada em diversos trabalhos,^[9][10][11] em que os autores usam o termo "fórmula" ou "bem formada" sem opor necessariamente esses termos à antiga noção de fórmula como uma cadeia arbitrária de símbolos de modo que não é mais comum em lógica matemática referir-se a cadeias arbritárias de símbolos no antigo sentido de "fórmulas".

A expressão "fórmula bem formada" também acabou entrando na cultura popular. De fato, fórmula bem formulada é parte de uma trocadilho esotérico usado no nome de um jogo acadêmico WFF 'N PROOF: The Game of Modern Logic, desenvolvido por Layman Allen,^[12] enquanto ele estava na Escola de Direito de Yale (mais tarde, ele seria professor na Universidade de Michigan). A sequência de jogos foi concebida para ensinar os princípios da lógica simbólica para crianças (em notação polonesa).^[13] O nome do jogo é uma alusão a whiffenpoof, uma palavra nonsense usada como um grito de guerra na Universidade Yale e que se tornou popular na Whiffenpoof Song e de um grupo musical formado por graduandos de Yale, The Whiffenpoofs.^[14]

Ver também

• Átomo básico

Notas e referências

1. Fórmulas bem formadas são um tema padrão na introdução à lógica, e são cobertas por vários livros introdutórios, incluindo Enderton (2001), Gamut (1990), and Kleene (1967)
2. Lógica de primeira ordem e teorema de prova automatizado, Melvin Fitting, Springer, 1996 [1]
3. Handbook of the history of logic. Vol 5 - Logic from Russell to Church, "Tarski's logic" por Keith Simmons, D. Gabbay e J. Woods Eds, p.568 [2].
4. Alonzo Church, [1996] (1944), Introduction to mathematical logic, p. 49
5. Hilbert, David; Ackermann, Wilhelm (1950) [1937], Principles of Mathematical Logic, New York: Chelsea
6. Hodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 978-0-521-58713-6
7. Barwise, Jon, ed. (1982), Handbook of Mathematical Logic, Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN 978-0-444-86388-1
8. Cori, Rene; Lascar, Daniel (2000), Mathematical Logic: A Course with Exercises, Oxford University Press, ISBN 978-0-19-850048-3
9. Enderton, Herbert [2001] (1972), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3
10. R. L. Simpson (1999), Essentials of Symbolic Logic, page 12
11. Mendelson, Elliott [2010] (1964), An Introduction to Mathematical Logic (5th ed.), London: Chapman & Hall
12. Ehrenburg 2002
13. Mais apropriadamente, trata-se de lógica proposicional com o uso do estilo de Fitch.
14. Allen (1965) agradece o trocadilho.

Referências

• Allen, Layman E. (1965), «Toward Autotelic Learning of Mathematical Logic by the WFF 'N PROOF Games», Mathematical Learning: Report of a Conference Sponsored by the Committee on Intellective Processes Research of the Social Science Research Council, Monographs of the Society for Research in Child Development, 30 (1): 29–41 
• Boolos, George; Burgess, John; Jeffrey, Richard (2002), Computability and Logic, ISBN 978-0-521-00758-0 (pb.) Verifique |isbn= (ajuda) 4th ed. , Cambridge University Press 
• Ehrenberg, Rachel (primavera de 2002). «He's Positively Logical». Michigan Today. University of Michigan. Consultado em 19 de agosto de 2007 
• Enderton, Herbert (2001), A mathematical introduction to logic, ISBN 978-0-12-238452-3 2nd ed. , Boston, MA: Academic Press 
• Gamut, L.T.F. (1990), Logic, Language, and Meaning, Volume 1: Introduction to Logic, ISBN 0-226-28085-3, University Of Chicago Press 
• Hodges, Wilfrid (2001), Goble, Lou, ed., The Blackwell Guide to Philosophical Logic, ISBN 978-0-631-20692-7, Blackwell 
• Hofstadter, Douglas (1980), Gödel, Escher, Bach: An Eternal Golden Braid, ISBN 978-0-14-005579-5, Penguin Books 
• Kleene, Stephen Cole (2002) [1967], Mathematical logic, ISBN 978-0-486-42533-7, New York: Dover Publications, MR 1950307 
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic, ISBN 978-1-4419-1220-6 3rd ed. , New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3 

Ligações externas

• «Well-Formed Formula for First Order Predicate Logic». - inclui um quiz sobre Java. 
• «Well-Formed Formula at ProvenMath» 
• «WFF N PROOF game site» 
• Types and Tokens. Por Linda Wetzel. The Stanford Encyclopedia of Philosophy (Spring 2011 Edition), Edward N. Zalta (ed.).

• Portal da matemática