Paradoxo do barbeiro
Origem: Wikipédia, a enciclopédia livre.
O paradoxo do barbeiro é um paradoxo que relaciona lógica matemática e teoria de conjuntos. O paradoxo considera uma aldeia onde um barbeiro faz a barba todos os dias a todos os homens que não se barbeiam a si próprios, e a mais ninguém. Ora tal aldeia não pode existir:
- Se o barbeiro não se barbeia a si mesmo, então terá de fazer a barba a si mesmo.
- Se ele se barbear a si mesmo, de acordo com a regra ele não se poderá barbear a si mesmo.
A regra resulta numa situação indecidível.
O paradoxo é atribuído a Bertrand Russell, um matemático britânico que em 1901 elaborou o paradoxo de Russell para demonstrar a natureza auto-contraditória da teoria de conjuntos de Georg Cantor. O paradoxo é também usado no teorema da incompletude de Gödel bem como na prova da indecidibilidade do problema de paragem de Alan Turing.
Em Prolog, o paradoxo do barbeiro pode ser expresso pela cláusula auto-referente:
barbeia(barbeiro,X) :- homem(X), not barbeia(X,X). homem(barbeiro).
onde a negação como falha é pressuposta.
[editar] Variante: morte por enforcamento ou decapitação
Uma outra versão conta a história de um filósofo que cometeu algum crime muito grave (por exemplo, olhou para uma das esposas do Rei), e deve ser executado. O Generoso Rei, porém, permite que ele escolha se quer ser enforcado ou decapitado, desde que ele diga, respectivamente, uma verdade ou uma mentira. O filósofo, então, diz eu serei decapitado.
