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

Example:

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

## 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).

page revision: 4, last edited: 17 Apr 2012 08:46