Well, this comes from mathematical logic, as Wikipedia says that a predicate is a fundamental concept in first-order logic. In each "implementation" of logic, a predicate is a sentence that is either true or false, so it fits very well into programming languages.
source share