Formal logic, knowledge representation and symbolic reasoning

Prolog is a declarative programming language that allows you to create a knowledge base by writing first-order logic sentences, and then pose queries to that knowledge base. The language itself takes care of performing the necessary inference; your role is primarily that of correctly specifying the problem and the query you need answered.

You may use any implementation of Prolog for this question. SWI-Prolog is recommended as it is very straightforward to install and use. A current stable version for your platform can be freely downloaded from www.swi-prolog.org/, where you will also find comprehensive documentation.

a) Explain, in your own words, what is meant by the following terms, in the context of formal logic:

1. Soundness.

2. Completenes.

3. Consistency.

4. Validity.

b) For this question you should use reasoning patterns which are either explicitly listed in the subject guide, pp.2022, or can be produced using the logical equivalences in Figure 4.1. Show which literals can be inferred from the following knowledge bases, using both reasoning patterns and truth tables. Show all steps in your reasoning and explain your answers.

1. P Q

Q (R S)

P S

2. (P Q) P v Q

Q R

R

3. (A v B) C

(B C)

c) Represent the following statements as formulas in Predicate Calculus, stating the intended interpretation of any predicates and constants that you use. You should give two versions of each formula, one using the existential quantifier and one using the universal quantifier

(plus any Boolean connectives required in each case).

1. A musician is someone who plays a musical instrument or sings.

2. Pianos, trumpets, guitars, saxophones and trombones are musical instruments.

3. Trumpets, saxophones and trombones are kinds of horn. [note: jazz parlance]

4. Not all musical instruments are horns.

5. Some singers play the trumpet.

d) Encode the following facts about jazz and blues performers as Prolog clauses. Note: you may need to code more than one clause for each numbered sentence. You should keep the queries (ivi) below in mind when deciding how to structure your clauses.

1. Billie Holiday, Bessie Smith, Chet Baker and Louis Armstrong were all singers.

2. Chet Baker, Louis Armstrong and Dizzy Gillespie played the trumpet.

3. Count Basie, Thelonious Monk, Duke Ellington and Mary Lou Williams played the piano.

4. Count Basie, Duke Ellington and Chick Webb were big-band leaders.

5. Charlie Parker, John Coltrane and Lester Young played the saxophone.

6. Chick Webb was a drummer.

7. Django Reinhardt, Wes Montgomery, Robert Johnson and BB King played guitar.

8. Robert Johnson, BB King, Bessie Smith and Billie Holiday were blues artistes.

9. Charlie Parker, Dizzy Gillespie, Thelonious Monk and Mary Lou Williams played in the bebop style.

Use your Prolog implementation to derive answers to the following queries, based on the information given in (19) above. You may need to encode some additional common sense inferences and/or other reasonable general statements as Prolog clauses. Explain your results.

1. List all the musicians in your knowledge base.

2. Give the name of a bebop trumpeter.

3. Was Count Basie a trumpeter?

4. List all non-bebop saxophonists.

5. List all big-band leaders who played the piano.

6. Give the names of singers who played an instrument.

Answers will be marked on the following criteria:

• Clear and correct solutions returned to queries.

• Compact, well-structured and readable code.

• Clear and accurate explanations.