Predicate logic is formal logic where the alphabet includes quantifiers (, …), variables (x, y, z…), and predicate symbols (P, Q…) that can relate variables or constant terms.
For example, is a sentence in predicate logic, meaning: “for all x, there exists some y, such that either P(x, y) holds, or Q(y, x) does not hold.”
In this case, P and Q are “non-logical symbols” standing for some relations, and x and y are variables ranging over some implicit domain. The precise relations and domain are opaque to the rules of predicate logic — the point of formal logic is arguably to state inferences like without worrying about what x and P stand for — but can be assigned meaning when combined with some interpretation or model for the logic.
Even in its simplest form, predicate logic can be used to model many statements in natural language, where the predicate symbols and constants/terms are taken to model verbs relating nouns:
Every person who lives in Perth lives in Australia.
Toaq is based on this formalism. Its content words are explicitly n-ary predicates:
poq: ___ is a person.
bua: ___ lives in ___.
It allows for slots that themselves accept other predicates/relations, meaning Toaq is really based on higher-order logic:
cheo: ___ all satisfy binary relation ___ among each other.
This connection between predicate logic and natural language has been explored since the 1970s by Montague (Montague grammar on Wikipedia).