The Barber paradox is a paradox that relates to mathematical logic and set theory. The paradox considers a town with a male barber who shaves daily every man who does not shave himself, and no one else. Such a town cannot exist:

• If the barber does not shave himself, he must abide by the rule and shave himself.
• If he does shave himself, according to the rule he will not shave himself.

Thus the rule results in an impossible situation.

This paradox is attributed to Bertrand Russell, a British logician who in 1901 constructed Russell's paradox to demonstrate the self-contradictory nature of Georg Cantor's naïve set theory by formalizing the Barber paradox. The paradox also underlies the proof of Gödel's incompleteness theorem as well as Alan Turing's proof of the undecidability of the halting problem. The paradox is an instance of the proof technique known as diagonalization.

In Prolog, one aspect of the Barber paradox can be expressed by a self-referencing clause:

 shaves(barber,X) :- male(X), not shaves(X,X).
 male(barber).

where negation as failure is assumed. If we apply the stratification test known from Datalog, the predicate shaves is exposed as unstratifiable since it is defined recursively over its negation.

In his book Alice in Puzzleland, the logician Raymond Smullyan had the character Humpty Dumpty explain the apparent paradox to Alice. Smullyan argues that the paradox is akin to the statement "I know a man who is both five feet tall and six feet tall," in effect claiming that the "paradox" is merely a contradiction, not a true paradox at all, as the two axioms above are mutually exclusive.

And in fact the Barber paradox is indeed merely a contradiction. As shown in the "impossible situation" analysis above, if the given definition of this barber can be used in a logical analysis, then one is led to the contradiction that the barber both does shave himself and does not shave himself. Thus it must be the case that the given definition cannot be used in a logical analysis. The actual contradiction in the Barber paradox, following Prior's analysis, is in the implicit assertion that the flawed definition of the barber can be used in a logical analysis.