Learning And Logic Programming

Logic Programming

Logic Programming is essentially using logic for programming. It is restricted to the form:

G if G1 and G2 … and Gn

Propositional Logic

Truth tables and/or/not/ etc.

Propositional Variables: P, Q, R, X, Y… etc
Negation: ¬S,¬T
Logical Connective: V, ^, ←, ↔
Well-Formed Formulae: P V Q, (¬R ∧ S) → T, etc

Inference Rules:

  • modus ponens: Given B and that A ← B, infer A
  • modus tollens: Given ¬A and that A ← B, infer ¬B

Valid instances are those with correct statements
Sound instances are valid instances which are actually true

Meaning in Propositional Logic

Propositional variables stand for statements (declarative sentences of properties).
e.g. P = the paper is red, Q = the solution is acid
We can use P → Q as a potentially useful inference.

Truth tables are a way of understanding meanings of formulae.

Models in Propositional Logic

A model is an arbitrary subset of the proposition symbols.
When M is a model for a sentence s the following are true:

  • M is a model for a proposition iff s is in M
  • M is a model for $\neg s$ if it's not a model for s
  • M is a model for $s \text{^} t$ iff M is a model for both separately
  • M is a model for $s \vee t$ iff M is a model for at least one of them
  • M is a model for t implies s iff M is a model for s whenever it's a model for t
  • M is a model for s iff t iff M is a model for s only when t is.

If all models of a sentence r also satisfy s then s is a logical consequence of r.

First-Order Predicate Logic

First order logic is a formal system, useful for computer science.

The arity of a function or predicate is the number of arguments that can be supplied to it.

  • Variables can be upper case in GDL, or lower case as standard
  • Constant symbols: P, Q, Jane, Fred
  • Function Symbols: Cons, Implies, F
  • Predicate Symbols: Likes, Binds
  • Logical Connectives are $\neg, \wedge, \vee, \implies, \iff$
  • Quantifiers are $\forall, \exists$
  • Atoms are functions of the form P(x) or x = y
  • Literals are atoms and negated atoms
  • Sentences are all types of functions


init(control(xplayer)); // init = predicate
legal (P, mark(M,b)); // mark = function, b = constant, M = variable

Meaning in First-Order Logic

Meaning in first order logic is similar to propositional logic, but slightly more complicated. We give meaning to first-order logic formulae by interpretation with respect to a given domain D:
We associate

  • Each constant symbol with an element of D
  • Each n-ary function symbol with some function from Dn to D
  • Each n-ary predicate symbol with some relation in Dn.

Interpretation is association of a formula with a truth-valued statement about the domain.

Importance of First Order Logic

Rules so far have allowed only comparisons of a variable with a constant value (e.g., sky = sunny, temperature < 45). These are propositional representations – have same expressive power as propositional logic

To express more powerful concepts, say involving relationships between example objects, propositional representations are insufficient, and we need a more expressive representation
E.g., to classify X depending on it’s relation R to another object Y

Learning First Order Rules


Herbrand Universe

The Herbrand Universe for a logic language is the set of all terms without variables. As in, just constants and functions and all combinations thereof.

Herbrand Base

The Herbrand Base for a logic language is all variable-free atoms.

Models in First Order Logic

Models are arbitrary subsets of the Herbrand Base. In first order logic models are the same as in Propositional Logic, with two additions:

  • M is a model for all x in s iff M is a model for s{x=z} (where z is all terms in the Herbrand Universe)
  • M is a model for each x in s iff M is a model for s{x=z} (where z is some terms in the Herbrand universe

(s{x=z} means replace each occurrence of x with z).