CS 327: Artificial Intelligence

Assignment 6: Representing and Reasoning about Knowledge using Logic

Each problem is worth 4 points, for a total of 20 points.

 In this homework, '^' stands for AND, 'v' stands for OR, and '~' stands for NOT.

Problem 1 - Representation in Propositional Logic

Represent each of the following sentences in propositional logic:
  1. John is working.
  2. Mary is working.
  3. Neither John nor Mary are working.
  4. Whenever John is working Mary isn't and whenever Mary is working John isn't.

Problem 2 - Truth Tables

Use truth tables to determine whether each of the following is a valid sentence in propositional logic:
  1. P => P
  2. (P v ~P) => Q
  3. (P ^ ~P) => Q
  4. (P v Q) => P
  5. (P ^ Q) => (P v Q)
  6. (P v Q) => (P ^ Q)
  7. (P => Q) <=> (~P v Q)

Problem 3 - Inference in Propositional Logic

Using the inference rules in Figure 6.13 of the textbook, show that S can be inferred if the following sentences are believed. Briefly explain your deductive steps. (See Section 6.5 for a similar example, but please use the notation for derivations used in class.)
  1. P ^ Q
  2. P v Q => R
  3. W => ~(~Z)
  4. ~R v W
  5. S v Q
  6. P ^ Z => S v ~R

Problem 4 - 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 7.3, and other portions of Chapters 7 and 8, 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 the shorthand notation "ThereExists!" for this problem.

Problem 5 - 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))


(Thanks to Jude Shavlik at University of Wisconsin-Madison for these problems)