Chapter 4

Question 1

Prolog is made of..

Answer 1

Knowledge bases, which… (next flashcard)

Question 2

Knowledge bases are made of…

Answer 2

clauses, which…(next flashcard)

Question 3

Clauses are made of…

Answer 3

conditionals or atoms.

Question 4

When writing a Prolog program made of clauses, we have to make sure that these clauses capture:

Answer 4

1. the truth of a sentence in the KB (Aristotelian logic)
2. the whole truth, explicitly ad implicitly!
3. In a form suitable for back-chaining –> we must write high-quality predicates!

Question 5

Saying that a program is “logically correct”, means..

Answer 5

1. correct with regard to grammar and
2. capturing the truth –> correct logical entailment
3. • back-chaining= simply correct

Question 6

Recursion in Prolog

Answer 6

Recursion breaks down a problem into smaller pieces of the same problem such that we can apply the same algorithm to each piece and then later combining the solutions for the answer

Question 7

Stack

Answer 7

Data structure that stores each “call” of a procedure: it follows a LIFO strategy

Question 8

LIFO strategy

Answer 8

Last-in, first-out strategy

Question 9

When is a predicate considered recursive in Prolog?

Answer 9

When it appears in both the head and body of the clause, but with different arguments.

Question 10

How can we write clauses in the program that handle recursion?

Answer 10

1. Write a clause that handles the n = 0 case, which is, where n is the number of intermediate “blocks” (the smallest natural number).
2. Write a clause that handles the n+1 case.

Example: if X is above Y with n+1 boxes between them, then there must be a Z that is directly below X and above Y, with n blocks between them.

Question 11

Mathematical induction

Answer 11

mathematical proof technique that aims at proving that a mathematical sentence hold for all natural numbers

Question 12

Example: prove that the sum of the natural numbers up to n is equal to one half of n times (n+1) –> sum = S(n)

Answer 12

1. Prove that S(0) is true

2. Prove that for any N, if S(n) is true, then S(n+1) is also true.

Question 13

Which one of these two sentences is “recursively correct”?

1. above (X, Y) :- on(X, Z), above(Z, Y)
2. above (X, Y) :- above(Z, Y), on(X, Z)

Answer 13

The first, because when the body of a clause contains a recursive predicate, we have to make sure that its new variables are instantiated by earlier atoms ( on(X, Z) in this case).

Question 14

What is a requirement for a problem in order for it to get solved by recursion?

Answer 14

To have a base case

Question 15

What is this query asking?

above(b1, b2) ( see slides of lecture 4)

Answer 15

Is b1 somewhere above b2?

Question 16

What is this query asking?

on(b1, b2) ( see slides of lecture 4)

Answer 16

Is b1 directly on b2?

Question 17

What is this query asking?

just_left(b1, b2) ( see slides of lecture 4)

Answer 17

Is b1 directly to the left of b2?

Question 18

What is this query asking?

left(b1, b2) ( see slides of lecture 4)

Answer 18

Is b1 somewhere to the left of b2?

Question 19

When will a recursive program terminate?

Answer 19

A recursive program terminate if the query that matches the head of a clause is always bigger (according to some size measure) than the queries from the body of the clause

Meaning: we need to make sure that every time we call the predicate again we are one step closer to meet the stopping criterion.