Jogo de fórmula
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2021) |
Um Jogo de fórmula é um jogo artificial representado por uma fórmula booliana completamente quantificada. Jogadores alternam seus turnos e o escopo de movimentos possíveis é definido pelas variáveis ligadas. Se uma variável é universalmente quantificada, a fórmula seguinte a ela deve possuir o mesmo valor verdade que a fórmula, iniciando com o quantificador universal independentemente do movimento jogado. Se uma variável é existencialmente quantificada, a fórmula seguinte a ela deve possuir o mesmo valor verdade que a fórmula, iniciando com o quantificador existencial por ao menos um movimento disponível durante o turno. Os turnos alternam, e um jogador perde se ele não pode mover durante o seu turno. Na teoria da complexidade computacional, a linguagem JOGO-DE-FORMULA é definida como todas as formulas que causam o primeiro jogador ter uma estratégia vencedora no jogo representado por . JOGO-DE-FORMULA é PSPACE-completa.
Referências[editar | editar código-fonte]
- Sipser, Michael. (2006). Introduction to the Theory of Computation. Boston: Thomson Course Technology.