

Propositions (truth variables):
 p, q, nice, etc.

Operators:

and (&, ×, .),
or (∨, +),
not (¬),
=> (implies, ⇒),
<= (if, implied by, ⇐),
<=> (iff, if and only if, ⇔)

 e.g., p and q => p.
Predicate Logic

Predicates (truth functions):
 p(), q(), odd(), parent(,), etc.

Operators:

and (&, ×, .),
or (∨, +),
not (¬),
=>, <=, <=>

Quantifiers:

∀ (forall),
∃ (there exists)

Logical variables:
 X, Y, Child, Parent, etc.

Constants:
 123, charles, etc.

Function names:
 f(), hcf(,), etc.

 e.g., ∀ C, P, GP,
parent(C,P) and parent(P,GP) => grandParent(C,GP).

 Prolog (Programming in Logic)
is a programming language based on Predicate Logic;
its restricted syntax is that of Horn Clauses:

facts, e.g.,
 parent(charles, elizabeth).
odd(1).

rules, e.g.,
 grandParent(C,GP) <= parent(C,P) and parent(P,GP).
odd(s(s(N))) <= odd(N).

queries, e.g.,
 ?grandparent(henry, GP).


Each rule has exactly one predicate on its LHS, and
a conjunction (and) of predicates and/or negated predicates
on its RHS.
A query is to be answered (yes or no)
given a list of facts and rules which are to be taken as true.

 [Prolog interpreter]

 Example:
witch(X) <= burns(X) and female(X).
burns(X) <= wooden(X).
wooden(X) <= floats(X).
wooden(woodBridge).
stone(stoneBridge).
floats(bread).
floats(apple).
floats(cherry).
floats(X) <= sameweight(duck, X).
female(girl). {by observation}
sameweight(duck,girl). {by experiment }
? witch(girl).
{ After Monty Python (Sir Bedevere). }

 Commonly,
 ':' is used for '<=', and
 ',' is used for 'and' in queries and in the RHS of rules.

 All of the variables in a fact, or in a rule, are
universally (∀) quantified, and
all of the variables in a query are
existentially (∃)
quantified, so the quantifiers are taken as givens and are omitted.

