CS 327: Artificial Intelligence

First-Order Logic / Inferencing

Problem 1 - Representation in FOPC

Give one (1) predicate calculus representation for each of the following English sentences. If you feel a sentence is ambiguous, provide a more detailed sentence that better captures the version represented by your FOPC. Choose (and briefly define) reasonable constants, predicates. and functions - the predicate thereAreNoWhiteUnicorns is not an acceptable answer to the first question. (Section 8.2, and other portions of Chapters 8 and 9, contain related examples.)
  1. There are no white unicorns.
  2. Not all students take both History and Biology.
  3. Everyone loves someone.
  4. Patients with red eyes and runny noses should take aspirin.
  5. Exactly one of Mary's dog's teeth is missing.
You cannot use an exclamation point after the existential quantifier (ThereExists) as shorthand to mean "There exists a unique...".

Problem 2 - Unification

For each of the following pairs of sentences, state the most general unifier, or say that it does not exist and explain why. The most general unifier is the one that leaves as few variables bound to constants (or functions) as possible. Terms starting with lowercase letters are variables, otherwise they are constants (or functions).
      1. P(x, y, y)
    		and
    		P(A, F(B), F(z))
      2. P(x, F(x), A)
    		and
    		P(y, y, z)
      3. P(x, y, z)
    		and
    		Q(A, B, B)
      4. Q(x, F(y, A), z)
    		and
    		Q(A, F(A, A), x)
      5. Q(x, G(y, y), w, F(z, z))
    		and
    		Q(H(u, v), v, A, F(x, y))

Problem 3 - Resolution

(a) A set is normal if it is not an element of itself.  Using n(x) to mean that x is normal and e(x,y) to mean that x is an element of y, write down a definition of normality.

(b) Write down in first-order logic the claim that there is a set s such that the elements of s are exactly all the normal sets.

(c) Use resolution to show that the claim in (b) is false.


(Thanks to Jude Shavlik and Stuart Russell)