Whatever the structure is, we can assume that there are relations that can be tested, for example "formula_1 is true iff there is an edge from to " (in case of the structure being a graph), or "formula_2 is true iff the th letter of the string is 1." These relations are the predicates for the first-order logic system. We also have constants, which are special elements of the respective structure, for example if we want to check reachability in a graph, we will have to choose two constants "s" (start) and "t" (terminal).