Review for Test 2: Covering Chapters 6 and 7

Chapter 6

• What are some of the properties that a knowledge representation language should have?

• What does the syntax of a language specify?

• What does the semantics of a language specify?

• If the relationship between {P and Q} and R is entailment, denoted {P,Q} |= R, what does this mean?

• What does it mean to say that a sentence is unsatisfiable?

Chapter 6 (continued)

• The truth of a sentence in propositional logic depends on two things, what are they?

• What is the definition of a sound inference procedure?

• What is the definition of a complete inference procedure?

• In propositional logic, a sentence can be either ___ or ___ ?

• Sentences in propositional logic correspond to ____ in the real world.

Chapter 6 (continued)

• Propositional logic can be used to represent ____ whereas first-order predicate logic can be used to represent ____ , _____, and _____ .

• True or false, any propositional symbol is a sentence.

• Demonstrate the validity of the following statements using a truth table:
  • (P=Q) = (P->Q) ^ (Q -> P)
  • P -> Q = ~Q -> ~P
  • P ^ (Q | R) = (P ^ Q) | (P ^ R)

Chapter 6 (continued)

• What does it mean for a sentence to be valid?

• State whether each statement is True or False:
  • Q ^ R is True iff Q is True and R is True
  • Q | R is True iff Q is True or R is True but not both
  • Q => R is True iff Q is not True and R is True
  • Q = R is True iff Q is True and R is True or Q is False and R is False

• We said it would take 64 propositional logic sentences to express the simple fact “don’t go forward if the wumpus is in front of you.” Explain why it is or is not feasible to represent this fact with the sentence: WumpusAhead => ~Forward

• Does this reduce the number of sentences required?

Chapter 7

• What does a term refer to in first-order predicate logic (FOPL)?

• Give 3 examples of terms.

• Explain the difference between predicates and functions in FOPL

• Explain the meaning of the following two sentences:
  • The universal quantifier corresponds to conjunction (P holds for all values of x,y).
  • The existential quantifier corresponds to disjunction (P holds for some value of x,y).

Chapter 7 (continued)

• Define the following terms:
  • atomic sentence
  • literal
  • ground term

• Explain the difference between:
  • forall x P(x) => Q(x) and
    
    forall x P(x) ^ Q(x)

• Explain the difference between
  • exists x P(x) => Q(x) and
    
    exists x P(x) ^ Q(x)

Chapter 7 (continued)

• Write logical statements for:
  “Everybody loves somebody” and
  
  “There is somebody who is loved by everybody”

• What is the difference between FOPL and higher-order logics?

• What is an effect axiom?

• What is a frame axiom?

• Write a proof for “box c contains oranges” from the 3 mislabeled boxes puzzle given the K.B. on the next 2 slides.

Puzzle K.B. with ground terms only

• 1. contains(b,apples)
• 2. label(a,apple)
• 3. label(b,oranges)
• 4. label(c,bananas)
• 5.contains(a,apples) | contains(a,oranges) | contains(a,bananas)
• 6.contains(b,apples) | contains(b,oranges) | contains(b,bananas)
• 7.contains(c,apples) | contains(c,oranges) | contains(c,bananas)

Puzzle continued

• 8. contains(b,apples) => ~contains(a,apples) ^ ~contains(c,apples)
• 9. contains(c,oranges) => ~contains(a,oranges) ^ ~contains(b,oranges)
• 10. contains(a,bananas) => ~contains(b,bananas) ^ ~contains(c,bananas)
• 11. label(a,apples) => ~contains(a,apples)
  .
  .
  .
• 19. label(c,bananas) => ~contains(c,bananas)