Question

This question is about the game Noughts-and-Crosses (Tic-Tac-Toe). The game is played on a $3 \\times 3$ grid by two players, Crosses (X) and Noughts (O), who take turns placing their symbol in an empty cell. A player wins when they have three of their symbols in a horizontal, vertical, or diagonal line. If all cells are occupied and no one has won, the game is a Draw.

The variable P always stands for a position in the game. The state of the game determines whose turn it is:

• If the number of Crosses equals the number of Noughts, it is Crosses' turn.
• If the number of Crosses is one more than the number of Noughts, it is Noughts' turn.

A winning move is a move by a player that immediately wins the game.

We use the following variables, predicates, and function:

• CrossesWins(P): True if, in position P, there is a line of three Crosses and no line of three Noughts.
• NoughtsWins(P): True if, in position P, there is a line of three Noughts and no line of three Crosses.
• CrossesToMove(P): True if it is Crosses' turn to move in position P.
• NoughtsToMove(P): True if it is Noughts' turn to move in position P.
• ResultingPosition(P, M): A function that returns the position produced by starting with position P and then playing move M. A move M is specified by the player and the cell.

---

Using quantifiers and the variables, predicates, and function described above, write statements in predicate logic with each of the following meanings.

(a) Crosses has a winning move in position P.

(b) Noughts has a winning move in position P.

(c) For each of the statements you wrote for (a) and (b), determine whether the statement is True or False when P is the following position:

  X O
X X O
O

(d) A losing move is a move that gives the opponent an immediate win. In Noughts-and-Crosses, this never happens. Write a predicate logic statement to say that losing moves are impossible.

(e) Crosses has a strategy for winning within three moves from position P (where the three moves are one by Crosses, one by Noughts, and another by Crosses).

(f) Crosses does not have a strategy for winning within three moves from position P. For this question, you must ensure that no logical negation occurs immediately in front of any quantifier.

(g) Crosses has a winning strategy from the initial position $P\_0$ (an empty grid).

(h) Noughts has a winning strategy from the initial position $P\_0$.

(i) With best possible play from both sides from the initial position $P\_0$, the game ends in a Draw.

(j) It is possible for Noughts to win from the initial position $P\_0$.

---

Answer

(a) A logical statement for "Crosses has a winning move in position P" is:

$$\text{CrossesToMove}(P) \wedge \exists M (\text{CrossesWins}(\text{ResultingPosition}(P, M)))$$

(b) A logical statement for "Noughts has a winning move in position P" is:

$$\text{NoughtsToMove}(P) \wedge \exists M (\text{NoughtsWins}(\text{ResultingPosition}(P, M)))$$

(c) For the position P:

  X O
X X O
O

In this position, there are 4 Crosses and 3 Noughts. According to the rules, "if the number of Crosses is one greater than the number of Noughts... the next player to move must be Noughts". Therefore, NoughtsToMove(P) is True.

• The statement from (a) is False. Its first part, CrossesToMove(P), is false.
• The statement from (b) is True. It is Noughts' turn (NoughtsToMove(P) is True), and a move M exists (placing an O in the bottom-right cell) that makes NoughtsWins(ResultingPosition(P, M)) true.

(d) A logical statement for "losing moves are impossible" is:

$$\forall P \forall M ( (\text{CrossesToMove}(P) \wedge \text{NoughtsWins}(\text{ResultingPosition}(P, M))) \rightarrow \text{NoughtsWins}(P) ) \\ \wedge ( (\text{NoughtsToMove}(P) \wedge \text{CrossesWins}(\text{ResultingPosition}(P, M))) \rightarrow \text{CrossesWins}(P) )$$

This means that if a player's move results in a win for the opponent, the opponent must have already won in the position before the move was made.

(e) Crosses has a strategy for winning within three moves from P:

$$\text{CrossesToMove}(P) \wedge \exists M_{C1} \forall M_{N1} \exists M_{C2} (\text{CrossesWins}(\text{ResultingPosition}(P, M_{C1}, M_{N1}, M_{C2})))$$

(f) Crosses does not have a strategy for winning within three moves from P:

$$\text{CrossesToMove}(P) \rightarrow \forall M_{C1} \exists M_{N1} \forall M_{C2} (\neg\text{CrossesWins}(\text{ResultingPosition}(P, M_{C1}, M_{N1}, M_{C2})))$$

(g) Crosses has a winning strategy from the initial position $P\_0$. This means Crosses can force a win regardless of how Noughts plays. It can be expressed as a disjunction of winning at each possible opportunity:

$$\exists M_1 \forall M_2 \exists M_3 \forall M_4 \exists M_5 (\text{CrossesWins}(\dots)) \lor \dots \lor \exists M_1 \dots \exists M_9 (\text{CrossesWins}(\dots))$$

(h) Noughts has a winning strategy from the initial position $P\_0$:

$$\forall M_1 \exists M_2 \forall M_3 \exists M_4 (\text{NoughtsWins}(\dots)) \lor \dots \lor \forall M_1 \dots \forall M_7 \exists M_8 (\text{NoughtsWins}(\dots))$$

(i) With best play, the game is a draw. This means neither player has a winning strategy.

$$\neg(\text{Statement from (g)}) \wedge \neg(\text{Statement from (h)})$$

(j) It is possible for Noughts to win from the initial position $P\_0$. This means there exists at least one sequence of moves (implying Crosses does not play optimally) that leads to a Noughts win.

$$\exists M_1 \exists M_2 \exists M_3 \exists M_4 (\text{NoughtsWins}(\dots)) \lor \dots \lor \exists M_1 \dots \exists M_8 (\text{NoughtsWins}(\dots))$$

Changelog

9/7/25, 2:51 AM

View All Changelog

• 87c17-web-deploy(Auto): Update base URL for web-pages branchon 9/7/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)