COMP3411 Artificial Intelligence
Session 1, 2011

Tutorial - Week 9 - Logic

1. First-order logic

   Represent the following sentences in first-order logic, using a consistent vocabulary.

   1. For any natural number there is a larger natural number.
   2. Every person who buys a policy is smart, but some smart people don't buy a policy.
   3. All barbers in town shave only those men in town who do not shave themselves.

2. Models

   Consider a logic language with two object constants, a and b, and two single-argument predicates, p and r. How many models are there for the following sentences?

   1. p(a) ∨ p(b)
   2. ∀X r(X) <= p(X)
   3. (∀X∀Y r(X) <= ¬r(Y)) ∧ ∃Z ¬r(Z)

3. Logical Consequences

   Which of the following statements are true?

   1. ¬p(a) is a logical consequence of  (p(b) <= p(a)) ∧ ¬p(b).
   2. ¬p(b) is a logical consequence of  (p(b) <= p(a)) ∧ ¬p(a).
   3. ∀X∃Y p(X,Y) is a logical consequence of  ∃Y∀X p(X,Y).
   4. ∃X∀Y p(X,Y) is a logical consequence of  ∀Y∃X p(X,Y).

4. Game Description Language
   1. Download the rules for the game "tictactoe" from the Dresden General Game Playing (GGP) Server. Convince yourself that, although some of the rules differ from those for Noughts And Crosses given in the lecture, the two descriptions actually define the same game.

   2. Modify the rules for "tictactoe" so as to describe a variant of Noughts And Crosses in which the players mark cells simultaneously:
      1. In each round, both players choose to mark an empty cell.
      2. If both players choose the same cell, then the cell will be marked with x. (So the game isn't fair!)
      3. The game ends in a draw if both players complete a line at the same time.
      Download the Game Manager from the Dresden GGP Server and test your game description by running several random matches.