Hello,

I was reading through the introduction ofIntroduction to the Theory of Computation, 2nd Edition, International Editionand I came across the part where the author demonstrates what a predicate is. I am having trouble understanding how the notation used to describe predicates as sets actually works. In the book, on page 9 the author describes it like so:

Here's what I understand:Quote:

Example 0.10

In a children's game called Scissors-Paper-Stone, the two players simultaneously select a member of the set {SCISSORS, PAPER, STONE} and indicate their selections with hand signals. If the two selections are the same, the game starts over. If the selections differ, one player wins, according to the relationbeats.

beatsSCISSORS PAPER STONE SCISSORS FALSE TRUE FALSE PAPER FALSE FALSE TRUE STONE TRUE FALSE FALSE

From this table we determine that SCISSORSbeatsPAPER is TRUE and that PAPERbeatsSCISSORS is FALSE.

Sometimes describing predicates with sets instead of functions is more convenient. The predicate P: D --> {TRUE, FALSE} may be written (D, S), where S = {a $\displaystyle \in$ D | P(a) = TRUE}, or simply S if the domain is obvious from the context. Hence the relation beats may be written

{(SCISSORS, PAPER), (PAPER, STONE), (STONE, SCISSORS)}

The set described at the very end is the set of pairs that result in the predicate being true. That set is in fact S. At first this wasn't exactly clear to me, but after rereading it a couple of times I realized that the phrase "or simply S if the domain is obvious from the context" could be applied to thebeatsrelation.

What I can't really see is, if the members of D are every possible pair resulting from the set {SCISSORS, PAPER, STONE}, how would the answer look like if it were expressed as (D, S)?

({(SCISSORS, SCISSORS), (SCISSORS, PAPER), (SCISSORS, STONE), (PAPER, SCISSORS), (PAPER, PAPER), (PAPER, STONE), (STONE, SCISSORS), (STONE, PAPER), (STONE, STONE)}, {(SCISSORS, PAPER), (PAPER, STONE), (STONE, SCISSORS)})?