Prolog

New Programming Paradigm: Logical Programming. 💃

Components:

• Knowledge Base: specified by programmer. Logical statements.
• Inference Engine: Given. Derives new knowledge from the knowledge base.

Horn Clauses

Logical statements in Prolog are restricted to horn clauses.

Horn Clause

A disjunction (or) of literals with at most 1 positive literal.

For example: $\mathrm{\neg }p\vee \mathrm{\neg }q\vee r$.

This is equivalent to a conjunction of atoms as the antecedent and a single atom as the conclusion.

Forward Chaining

Apply modus ponens to see what can be derived from a set of rules and atomic propositions.

Example

Knowledge Base: $b\wedge c⟹a$$d⟹b$$d$$c$

Forward Chaining: $b$ (d, is true and d implies b.) $a$ (b and c are true which implies a.)

Backward Chaining

Starting from the goal and reason backwards. Used In Prolog !

Example

Knowledge Base: $a⟸b\wedge c$$b⟸d$$d$$c$

Backward Chaining

1. a. (a is the goal, what we want to prove)
2. a is true if b and c are true.
3. d implies b
4. d is true and c is true.
5. done.

Backwards Chaining is based on the resolution rule:

Example

Knowledge Base$a\vee \mathrm{\neg }b\vee \mathrm{\neg }c$$b\vee \mathrm{\neg }d$$d$$c$

Resolution$\mathrm{\neg }a$ add the negation of the goal we want to prove to the knowledge base. $\mathrm{\neg }b\vee \mathrm{\neg }c$ a and negation of a cancel out. $\mathrm{\neg }d\vee \mathrm{\neg }c$ b and negation of b cancel out. $\mathrm{\neg }c$ d and negation of d cancel out empty clause, c and negation of c cancel out.

Prolog Syntax

Two types of statements:

• Facts: horn clauses consisting of a single positive literal
  • ex: p, q
• Rules: horn clauses with one positive literal and one or more negative literals.
  • ex: $\mathrm{\neg }p\vee \mathrm{\neg }q\vee r$
  • in rule form $(p\wedge q)⟹r$

Syntax

• All statements end with a dot .
• Implication ($⟸$) is represented with :-
• Conjunction denoted as comma ,

Example: $(p\wedge q)⟹r\equiv r⟸(p\wedge q)$ Denoted as: r :- p, q.

% knowledge base
a :- b,c.
b :- d.
d.
c.

prompt: ?- a.

output: true.