Algoritmo de Wang – Wikipédia a enciclopédia livre

Prévia do material em texto

Algoritmo de Wang
Origem: Wikipédia, a enciclopédia livre.
O algoritmo de Wang é um algoritmo desenvolvido por Hao Wang que testa se dadas conclusões são
consequência lógica de determinadas premissas. Em lógica proposicional, pode-se dizer que é uma
simplificação do método dos tablôs analíticos.
Índice
1 Algoritmo
1.1 Fórmulas tipo "alfa"
1.2 Fórmulas tipo "beta"
2 Referências
Algoritmo
Uma dedução natural qualquer pode ser escrita como:
Numa dedução natural, toda a vez que as premissas forem simultaneamente verdadeiras, as conclusões também
devem ser. Afirmam-se as premissas como verdadeiras, e as conclusões como falsas: se dessa forma
obtiverem-se contradições em todas as "colunas" do desenvolvimento, a dedução é válida. Uma única coluna
em que não haja contradição torna a dedução inválida.
Nessa notação, os parênteses à esquerda representam fórmulas verdadeiras e os da esquerda, falsas. A partir
daí, há algumas regras de desenvolvimento, que podem ser do tipo α ou β. As fórmulas devem conter apenas
os operadores ∧, ∨ e ¬.
Fórmulas tipo "alfa"
São fórmulas que têm única solução possível. Ou seja, a partir da informação a respeito de uma fórmula ser
válida ou não, pode-se chegar a uma única conclusão.
Se diz-se que ¬a é uma fórmula verdadeira, então a é falso.
Se diz-se que ¬a é uma fórmula falsa, então a é verdadeiro.
Se diz-se que a ∧ b é uma fórmula verdadeira, então a e b são verdadeiros simultaneamente.
Se diz-se que a ∨ b é uma fórmula falsa, então a e b são falsos simultaneamente.
Fórmulas tipo "beta"
São fórmulas que têm duas soluções possíveis, que devem ser desenvolvidas à parte.
Se diz-se que a ∧ b é uma fórmula falsa, então ou a é falso ou b é falso.
Se diz-se que a ∨ b é uma fórmula verdadeira, então ou a é verdadeiro ou b é verdadeiro.
Referências
Monard, M.C., Nicoletti, M.C.: Método sintático de prova de teoremas: algoritmo de Wang.
Wang, Hao: Toward Mechanical Mathematics
(http://www.research.ibm.com/journal/rd/041/ibmrd0401B.pdf) .
Obtida de "http://pt.wikipedia.org/w/index.php?title=Algoritmo_de_Wang&oldid=14431342"
Categoria: Lógica matemática
Menu de navegação
Esta página foi modificada pela última vez à(s) 19h27min de 2 de março de 2009.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.