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:

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.

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.