# 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
*D*to D^{n} - Each n-ary predicate symbol with some
*relation*in*D*.^{n}

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