Em
lógica, o termo
decidível se refere a um
problema de decisão, ou seja, a questão da existência de um
método efetivo para determinar a pertinência em um conjunto de fórmulas.
Sistemas lógicos, tais como a
lógica proposicional, são decidíveis se a pertinência em seu conjunto de fórmulas logicamente válido pode ser efetivamente determinado. Uma
teoria (conjunto de fórmulas fechada sob a consequência lógica) em um sistema lógico fixo é decidível se existe um algoritmo eficiente para determinar se fórmulas arbitrárias pertencem a ela. Muitos problemas importantes são
indecidíveis.