Laurea Laurea MAGISTRALE in MAGISTRALE in COMPUTER SCIENCECOMPUTER SCIENCE

1

Logics / 1 Logics / 1 Formal Logics Formal Logics

Laurea

Laurea MAGISTRALE in MAGISTRALE in COMPUTER SCIENCE COMPUTER SCIENCE

ARTIFICIAL INTELLIGENCE ARTIFICIAL INTELLIGENCE

Questi lucidi sono stati preparati per uso didattico. Essi contengono materiale originale di proprietà dell'Università degli Studi di Bari e/o figure di proprietà di altri autori, società e organizzazioni di cui e' riportato il riferimento. Tutto o parte del materiale può essere fotocopiato per uso personale o didattico ma non può essere distribuito per uso commerciale. Qualunque altro uso richiede una specifica autorizzazione da parte dell'Università degli Studi di Bari e degli altri autori coinvolti.

“Logics is a form of mental laziness”

M. Marchesi

●

“I remember one day finding an article on Boolean algebra. That is the type of mathematics computers use. And I learned about De Morgan’s Theorem, which is what Boolean algebra is based on. And that’s how logic became the heart of my existence […].

I decided then that I wanted to do logic and computers for fun.

By the time I designed the first […] computer, logic was my life. I know it sounds unbelievable, but I just loved logic and everything about it

… .”

●

“I remember one day finding an article on Boolean algebra. That is the type of mathematics computers use. And I learned about De Morgan’s Theorem, which is what Boolean algebra is based on. And that’s how logic became the heart of my existence […].

I decided then that I wanted to do logic and computers for fun.

By the time I designed the first […] computer, logic was my life. I know it sounds unbelievable, but I just loved logic and everything about it

… .”

●

Steve Wozniak

Introduction

●

Logics

●

Aims: describing and checking reasoning (Aristotle)‏

●

Formal Logics

●

Introduced formal methods for

–

Describing knowledge

–

Rigorously reasoning with it

Propositional Logics

●

Mathematical model allowing to reason about truth and falsity of logistic expressions

●

Definition (proposition)‏

–

Claim about which one can say, objectively and for sure, that it is true or false

●

Examples

–

Propositions:

●Rome is the capital of Italy

●Bari is a town in England –

Non-propositions:

●Picasso's paintings are beautiful

●Maybe today I will come and see you

Propositional Logics

●

Only 2 truth values permitted:

●

True (T)‏

–

Usually represented by numeric value 1

●

False (F)‏

–

Usually represented by numeric value 0

●

Frege's Thesis

●

Propositions are names

–

(of two entities, Truth and Falsity)‏

Logistic Connectives

●

Functions allowing the composition of propositions

●

Assign a specific truth value to each configuration of truth values to which they are applied

●

Can be schematized in Truth tables

–

First columns = truth values of the arguments

–

Last column = Values taken by the function in correspondence with the arguments on the same row

●

Allow to build complex expressions

●

Truth value univocally determined starting from those of the building components

Propositional Variables

●

May represent any proposition (or valid expression)‏ that has a truth value

●

Can be used in place of specific propositions

–

Take each time the truth value of the object they represent

●

Allow to perform general reasoning

● Example.

● Propositional variable P

– P = "Rome is the capital of Italy."  True – P = "Bari is a town in England."  False

● P may represent composite expressions

– P = "Rome is the capital of Italy and Bari is a town in England."  False

Logistic Connectives

●

In principle, there are

●

4 monadic operators

●

16 diadic operators

●

Some trivial

–

Always true

–

Always false

–

Return the value of (one of)‏ the arguments

●

Some more intuitive

●

Some sometimes useful

Logistic Connectives

●

The more used/intuitive

● Negation (NOT, )‏

– The negation of a false proposition is true, and vice versa

● Conjunction (AND, )‏

– The conjunction of two propositions is true if and only if both are true

● Disjunction (OR, )‏

– The disjunction of two propositions is true if and only if at least one of them is true

● Implication (IF... THEN..., )‏

– It is true that a proposition implies another if and only if, whenever the former is true, the latter is also true

● Equivalence (... IF AND ONLY IF..., )‏

– The equivalence between two propositions is true if and only if both have the same truth value

Logistic Connectives

●

Truth tables

● Notes:

● Disjunction expresses Latin vel

– True even when both propositions are true – XOR (eXclusive OR)‏ connective expresses Latin aut

● Implication has a slightly different meaning than the intuitive and common use of the term

– Defined based on the most similar available function to the represented concept

– Does not involve a causality relationship between premise and consequence, so they may be unrelated

A B A A  B A  B A  B A  B

0 0 1 0 0 1 1

0 1 1 0 1 1 0

1 0 0 0 1 0 0

1 1 0 1 1 1 1

Logistic Connectives

●

Other interesting ones

● NAND (Not AND)‏

● Takes opposite values with respect to those of the conjunction when applied to the same propositions

● NOR (Not OR)‏

● Takes opposite values with respect to those of the disjunction when applied to the same propositions

● XOR (eXclusive OR)‏

● True if and only if only one of the two propositions to which it is applied is true

A B A NAND B A NOR B A XOR B

0 0 1 1 0

0 1 1 0 1

1 0 1 0 1

1 1 0 0 0

Logistic Connectives

●

Definition (completeness)‏

●

A set of connectives is complete if all other connectives can be expressed by a suitable combination thereof

–

Negation and disjunction are a complete set

●A  B  ¬ (¬A  ¬B)‏

●A  B  ¬A  B

●A  B  (A  B)‏  (B  A)‏

–

Negation and conjunction are complete

–

NOR (alone)‏ is complete

–

NAND (alone)‏ is complete

Well-Formed Formulas (wff)‏

●

Expressions allowed by the logistic language

●

Defined recursively:

–

A proposition P is a wff;

–

If P and Q are wffs, then also

(P)‏, (P  Q)‏, (P  Q)‏, (P  Q)‏ e (P  Q)‏ are wffs

●

Computing the value of a compound expression

–

Given a truth assignment

●Associates a truth value to each variable involved in the expression

–

Partially evaluate the single logistic connectives

●Starting from most deeply nested parentheses

●Proceedings from inner parentheses outside as long as their values become known

Logistic Expressions

●

Priority order on connectives

●

Used to simplify notation

●

From highest to lowest:

    

–

Example

●The logic expression

(((A)‏  C)‏  (D  (B  C)‏)‏)‏

●Can be rewritten, without changing its meaning, as

A  C  D  (B  C)‏

●A  C  B  C is to be interpreted as (((A)‏  C)‏  (B  C)‏

–If the intended interpretation of the expression is different than this, parentheses must be used

Logistic Expressions

●

Equations about complete connectives claimed the following equivalences hold for any value assigned to A and B:

(A  B)‏   (A  B)‏

(A B)‏  A  B (A  B)‏  (A  B)‏  (B  A)‏

●

Can be proven using the partial evaluation technique, progressively building the associated truth tables

Logistic Expressions

●

Partial Evaluation

A B A B A  B (A  B) A  B (A  B)  (A  B)

0 0 1 1 1 0 0 1

0 1 1 0 1 0 0 1

1 0 0 1 1 0 0 1

1 1 0 0 0 1 1 1

A B A A  B A  B (A  B)  A  B )

0 0 1 1 1 1

0 1 1 1 1 1

1 0 0 0 0 1

1 1 0 1 1 1

A B A  B B  A (A  B)  (B  A) A  B (AB)  (A  B) (B  A)

0 0 1 1 1 1 1

0 1 1 0 0 0 1

1 0 0 1 0 0 1

1 1 1 1 1 1 1

Tautologies

●

Definitions

●

Tautology

–

Logistic expression which is always true, independently of the truth values taken by the involved components

●

Contradiction

–

Logistic expression which is always false, independently of the truth values taken by the involved components

●

Examples

A A A  A A  A A  A A  A

0 1 1 1 0 0

1 0 1 1 0 0

Tautologies

●

Substitution of equals by equals

●

Expressions on the right-hand-side and left-hand- side of an equivalence-based tautology can be always replaced one for the other in any expression

●

Substitution Principle

●

A tautology stays as such, whatever substitution is applied to its variables

–

A law involving propositional variables stays valid even after replacing any expression for any variable

●Of course, all occurrences of the same variable must be replaced by the same expression

Algebraic Laws

●

Comparison with Arithmetics

● Some tautologies express properties that are useful for manipulating logistic expressions

● Analogy between logistic operators , ,  and arithmetic operators +,  +, , – (sign)‏:

– (P  Q)‏  (Q  P)‏ Commutativity of  – P  (Q  R)‏  (P  Q)‏  R Associativity of  – (P  Q)‏  (Q  P)‏ Commutativity of  – P  (Q  R)‏  (P  Q)‏  R Associativity of  – P  (Q  R)‏  (P  Q)‏  (P  R)‏ Distributivity of  on 

– P  True  P Neutral element of 

– P  False  P Neutral element of 

– P  False  False Null element of 

– P  P Elimination of double negations

Algebraic Laws

●

Comparison with Arithmetics

●

Properties differentiating logistic operators ,  from arithmetic operators +, :

–

P  (Q  R)‏  (P  Q)‏  (P  R)‏ Distributivity of  on 

–

P  True  True Null element of 

–

P  P  P Idempotence of 

–

P  P  P Idempotence of 

–

P  (P  Q)‏  P

–

P  (P  Q)‏  P Subsumption

–

P  (P  Q)‏  P  Q

–

P  (P  Q)‏  P  Q Elimination of some negations

Algebraic Laws

●

De Morgan's Laws

●

(P  Q)‏  P  Q

●

(P

 P

 …  P

)‏  P

 P

 …  P

●

(P  Q)‏  P  Q

●

(P

 P

 …  P

)‏  P

 P

 …  P

●

Duality Principle

●

A tautology involving only connectives  and  stays as such if swapping such connectives

Algebraic Laws

●

Laws on equivalence

● P  P Reflexivity

● (P  Q)‏  (Q  P)‏ Commutativity

● ((P  Q)‏  (Q  R)‏)‏  (P  R)‏ Transitivity

● (P  Q)‏  (P  Q)‏ Equivalence of negated

●

Laws on implication

● ((P  Q)‏  (Q  P)‏)‏  (P  Q )‏

● ( P  Q )‏  (P  Q )‏

● (( P  Q )‏ ( Q  R )‏)‏  ( P  R )‏ Transitivity

● ( P  Q )‏  (P  Q )‏

● (P₁  P₂  …  P_k  Q )‏  (P₁  P₂  …  P_k  Q)‏

Algebraic Laws

●

Observations

●

Associativity and Commutativity of  and 

–

Allow expressinga any group of conjunctions

(disjunctions)‏, in any nidification, as a simple sequence of conjunctions (disjunctions)‏ with no intermediate

parentheses and valuable in any order

●

As regards the analogy with arithmetics

–

Conjunction is also called logistic product, and disjunction logistic sum

–

Properties for which they are different are those missing in operator  with respect to 

●Needed for the duality principle

Algebraic Laws

●

Observations

●

Subsumption:

–

In a sum of products, any product including another product may be dropped

●By replacing propositional variables in the first property by products of literals

–

In a product of sums any sum including another sum may be dropped

●By replacing propositional variables in the second property by sums of literals

–

Superfluous literals could not affect in any case the truth value taken by the expression

Proof Methods

●

Propositional Logics allows to formally and rigorously check that proof methods (used, e.g., in mathematics)‏ are correct

●

By applying those reasoning mechanisms to the given hypotheses one is guaranteed that true conclusions are drawn

–

Impossibility of building truth tables due to the large number of combinations of values to be considered

●

Calculus

●

The mechanism allowing to "reason" with logistic formulas

Proof Methods

●

Definition

●

Given a set of true expressions (hypotheses)‏, and a set of tautologies based on implication or

equivalence (inference rules)‏

–

A proof is a sequence of formulas, each of whose entries is a tautology, a hypothesis or a formula derived by two previous elements in the sequence by using an inference rule

–

A formula is proven starting from the set of hypotheses (through the inference rules)‏ if a proof including them can be built

Proof Methods

●

Main ones

●

Analysis by cases

–

If a conclusion can be drawn both from a proposition and from its negation, then the conclusion is always true

(P  Q )‏  (P  Q )‏  Q

●Generalization of the Law of excluded middle P  P  True

●also considering that a proposition and its negation cannot be both true at the same time

P  P  False

Proof Methods

●

Main ones

●

Modus Ponens

–

If the premises of an implication are true, then also its conclusions are

(P  (P  Q )‏)‏  Q

●

Proof by contraposition (Modus Tollens)‏

–

When a proposition is true only if another one is true, if it's not true, than neither the other is

(P  Q )‏  (Q  P )‏

Proof Methods

●

Main ones

●

Proof ad absurdum

–

If from a proposition one can deduce falsity (contradiction)‏, then its negation must be true

(P  False)‏  P

●

Reduction to True

–

A tautology can be transformed into True through a substitution of equals by equals

(P  True)‏  P

Propositional Logics

●

Limitations

●

Propositional Calculus considers each proposition as a whole, based on its truth value

–

It cannot capture relations between different propositions

●Example Given propositions:

–Roma is in Italy –Milano is in Italy –Torino is in Italy –Napoli is in Italy

●One knows they are all true, but cannot capture the connection that relates the towns (i.e., their being located in the same Nation)‏

Propositional Logics

●

Limitations

●

Limitations are overcome by Predicate Logics

–

An extension so-called due to the fact that it "predicates", i.e., it says something about one or many objects

●Example (previous one)‏: by extracting the objects about which the propositions are one obtains the following general sentences:

–... is in Italy.

–Rome is in ....

–... is in....

●By replacing the empty spaces obtained in this way by objects, one obtains several propositions whose truth value depends on the applied substitution

Predicate Logics

●

Definition (predicate)‏

●

Proposition from which one or many objects have been removed

–

Replaced by variables, each of which may take a value taken from a set to which it is associated (its domain)‏

●May depend on the value of other objects, even from different domains, through the use of functions

–

The number of variables appearing in a predicate or function is called its arity

–

A predicate or function having arity n is said to be n-ary

Predicate Logics

●

Definition (term)‏

●

<term> ::= <constant> | <variable>|

<n-ary function> ( <term>,…,<term> )‏

n

●

Definition Atomic Formula (or atom)‏

●

<atomic formula> ::=

<n-ary predicate> ( <term>,…,<term> )‏

n

Predicate Logics

●

Example

●

… is in … = is_in/2 => x is in y  P(x,y)‏.

–

Binary predicate (whose variables range, respectively, in the domain of towns and in the domain of Nations)‏

●x = Rome, y = Italy: Rome is in Italy  True

●x = Bari, y = England: Bari is in England  False

●

county seat of ... = county seat of z  f(z)‏

–

Unary function (given an object from the set of regions in which a Nation is partitioned, returns the name of its county seat

●

The county seat of z is in y  P(f(z)‏, y)‏.

Expressions

●

A proposition can be seen as a predicate with zero arguments

●

Definition

–

An atom is an n-ary predicate applied to n terms as arguments

●Corresponds to "propositional variable" in propositional logics

●

As in propositional logics, complex expressions can be built using logistic connectives

●

A literal is an atom (positive literal)‏ or a negated atom (negative literal)‏

●

An atom, a literal or an expression is ground if it does not involve any variable

Expressions

●

Example

●

father(X, Stefano)‏

– Is an atomo (thus, also a literal and an expression)‏

●

 black(Y)‏

– Is a literal (thus, also an expression)‏

●

white(X)‏  colored(X)‏

– Is an expression

●

father(Carlo, Stefano)‏

– Is a ground atom

●

 black(snow)‏

– Is a ground literal

●

white(dress)‏  colored(dress)‏

– Is a ground expression

Quantifiers

●

A predicate needs to be turned into a proposition in order for it to take a truth value

●

By assigning each of its variables a value from the corresponding domain

●

Often, when reasoning, one does not refer to a specific object

●

“For all objects …”, “There exists an object …”

●

To allow this, two symbols corresponding to these phrases were added (quantifiers)‏

●

Existential quantifier $ (“there Exists”)‏

●

Universal quantifier " (“for All”)‏

Quantifiers

●

Definitions

●

A quantified variable is bound (otherwise it is free)‏

–

It is as if it was assigned a specific value

●In order to assign a truth value to a predicate, each of its variables must be assigned a specific value taken from the corresponding domain, or it must be quantified

●

An expression not involving free variables is said to be closed

Quantifiers

●

Example

●

“The cube of any positive number is positive”

–

Let us define

●cube(x)‏: function returning the cube of any real number

and a predicate

●P(y,z)‏ = If y is greater than zero, then also z is greater than zero, where y and z range in the domain of real numbers

●

"x P(x,cube(x)‏)‏. surely true

–

If quantifiers did not exist, this claim should be repeated for each real number!

Quantifiers

●

Quantifiers are operators:

●

" corresponds to conjunction

●

$ corrisponds to disjunction

●

of all atoms that can be obtained by replacing the quantified variable with any possible value in its domain

–

Example. P(x)‏, x  {aa

1

, …, a

}

●("x)‏P(x)‏  P(a₁)‏  …  P(a_n)‏

●($x)‏P(x)‏  P(a₁)‏  …  P(a_n)‏

●

If E is a wff of predicate logics, then also ( "x)‏E and ($x)‏E are

●

Highest priority among all operators

Quantifiers

●

("x)‏P(x)‏  ($x)‏(P(x)‏)‏

●

If a property is true for any value in the domain, there is no value for which it is not true

●

($x)‏(P(x)‏)‏  ("x)‏(P(x)‏)‏

●

If a value in the domain makes a property true, not all values in the domain do not make it true

●

The scope of a quantifier (i.e., the portion of expression on whose variables it has effect)‏, is the one immediately following it

●

Example. "x (P(x)‏  Q(a)‏  ($y (P(y)‏  R(x)‏)‏)‏)‏

– Scope of """: (P(x)‏  Q(a)‏  ($y (P(y)‏  R(x)‏)‏)‏)‏

– Scope of "$": (P(y)‏  R(x)‏)‏

Quantifiers

●

A variable falling in the scope of many

quantifiers is assumed to be associated to the most inner one

●

Esempio. "x (P(x)‏  Q(a)‏  ($x (P(b)‏  R(x)‏)‏)‏)‏

–

x in R(x)‏ is associated to “$”

–

it is a different variable than x in P(x)‏, quantified by “"”

●

Standardizing apart: assigning each quantifier a variable that is different from all the others

●

Example. The expression in the previous example, after standardization apart, becomes

–

"x (P(x)‏  Q(a)‏  ($z (P(b)‏  R(z)‏)‏)‏)‏

Skolemization

●

Allows elimination of existential quantifiers

●

"y [$x P(x,y)‏] "For all y there esists an x, possibly depending on x, such that P(x,y)‏"

●

The dependence of x on y may be expressed by a Skolem function g(y)‏

–

Ideally returns for each value of y the value of x that

"exists"

●"y P(g(y)‏,y)‏

–

If the existential quantifier to be eliminated is not in the scope of any universal quantifier, a constant is used

Skolemization

●

Symbols in Skolem functions must be fresh

●

Not already appearing in the wff

●

Examples

–

["w Q(w)‏]  "x {a"y {a$z [P(x,y,z)‏  "u R(x,y,u,z)‏]}}

becomes

["w Q(w)‏]  "x"y [P(x,y,g(x,y)‏)‏  "u R(x,y,u, g(x,y)‏)‏]

–

$x P(x)‏

becomes P(a)‏

Interpretations

●

In order to assign a truth value to a predicate, all of its variables must have been bound

●

Definition

●

An interpretation of an n-ary predicate P is a function that, for any possible combination of values taken from its arguments (each in its own domain)‏, assigns the resulting atom value True or False

–

Corresponds to truth assignment in propositional calculus

●Here it depends on the objects the claim refers to

Interpretations

●

Example.

●

P(x,y)‏, x  {a0, 1, 2} and y  {aa, b}

–

A possible interpretation is --->

–

It suffices listing the combinations of values for which the predicate is true

●Assuming all the others make it false –{a (0,a)‏, (0,b)‏, (1,a)‏, (2,a)‏ }

●

Expressions are interpreted as in propositional logics, once the interpretations of the single predicates involved are defined

True a 0

x y P(x,y)

0 b True

1 a True

1 b False

2 a True

2 b False

Interpretations

●

Through interpretations one can also reason about consistency of sets of expressions (theories)‏

●

A set of expressions is said to be satisfiable if there exists at least one interpretation that makes them true at the same time, or unsatisfiable otherwise

●

An interpretation that makes true a set of formulas is said to be a model for that set

●

A set of formulas is valid if any interpretation is a model for it

–

It makes true all expressions in the set

Interpretations

●

Herbrand

●

Universe

–

The set of all terms that can be built in the language

●

Base

–

The set of all ground atoms that can be built from the Universe

●

Interpretation

–

Meaning of symbols = the symbols themselves

●

Least Model

–

Intersection of all Herbrand models

Tautologies

●

Definition

●

An expression in predicate logics is a tautology if it is true for any possible interpretation

–

Analogous definition to that for propositional logics

●

To this purpose, free variables (if any)‏ are to be interpreted as if they were universally quantified

Tautologies

●

All tautologies from propositional logics stay valid also for predicates

●

Once interpreted, they become propositions

●

Substitution principle stays valid

–

For any interpretation, the predicate takes a truth value independent of its position in the expression, and so it will be the same for all of its occurrences

●

Substitution of equals by equals can be used

–

Replacing any sub-expression with an expression that, based on some tautology, we know is equivalent to it

Tautologies

●

Tautologies involving quantifiers

●

Let E and F be two expressions

–

("x)‏E  ("y)‏E’ ($x)‏E  ($y)‏ E’

●where E' is obtained from E by replacing y to all occurrences of x bound by the quantifier under consideration

–

(("x)‏E)‏  ($x)‏(E)‏ (($x)‏ E)‏ ("x)‏(E)‏

–

(E  ("x)‏F)‏  ("x)‏(E  F)‏ (E  ($x)‏F)‏  ($x)‏(E  F)‏

–

(E  ("x)‏F)‏  ("x)‏(E  F)‏ (E  ($x)‏F)‏  ($x)‏(E  F)‏

–

("x)‏("y)‏ E  ("y)‏("x)‏ E ($x)‏($y)‏E  ($y)‏($x)‏E

●Any formula can be rewritten in such a way that all quantifiers are at its beginning, and that their effect is independent on the order in which they appear

–This is fundamental in order to transform expressions in clausal form

Proofs

●

Goal:

●

Answer questions about a knowledge base expressed in a logic-based formalism

–

E.g.: predicate calculus

●

Example

–

"Whoever can read is a literate" "x (R(x)‏  L(x)‏)‏

–

"Dolphins are not literate” "x (D(x)‏  L(x)‏)‏

–

"Some dolphins are intelligent” $x (D(x)‏  I(x)‏)‏

–

Question:

–

"There do exist intelligent beings that canno read?”

$x (I(x)‏  R(x)‏)‏

Proofs

●

Problem:

●

Some – even quite simple – conclusions may require many proof steps

–

The situation is even worse for expressions involving several connectives and/or quantifiers within the scope of other connectives and/or quantifiers

●

Example

–

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  "y [Q(x,y)‏  P(y)‏] }}

Proofs

●

As in propositional logics, plus...

●

Variable substitution Law

–

In the proof sequence it is possible to add an expression obtained by replacing in a previous expression in the sequence all occurrences of a free variable by another variable or a constant

●

Inference Rule: E  subst(E)‏

–

where subst is a function binding each free variable in an expression E

●a constant from its domain, or

●a variable

–possibly the variable itself

Proofs

●

Example

●

If expression

–

P(x,y)‏ v ($z)‏Q(x,z)‏

belongs to the proof sequence,

–

assuming we are dealing with closed expressions, this formula is assumed to be preceded by ("x)‏("y)‏

then also expression

–

P(a,b)‏ v ($z)‏Q(a,z)‏

can be added to the sequence

Proofs

●

A particular kind of proof is that in which hypotheses are in one of two forms:

●

facts (ground atoms)‏

–

Claims about the objects in the world, known to be true

●

rules (implication-type expressions)‏

–

General principles that may be applied to known facts to deduce more true facts

●

If all premises in a rule are true

●

by hypothesis or proven

it is possible to deduce its consequence

●

Add it to the proof sequence

Clausal Logics

●

Definition (clause)‏

●

A disjunction of literals, whose variables are assumed to be universally quantified

–

Can be represented as a logistic expression:

●A₁  A₂  …  A_n  B₁  B₂  …  B_m

or as a set of literals:

●{aA₁, A₂, …, A_n, B₁, B₂, …, B_m}

or as an inference rule:

●A₁, A₂, ..., A_n :– B₁, B₂, ..., B_m –

It is to be interpreted as

●B₁  B₂  ...  B_m  A₁  A₂  ...  A_n

Clausal Logics

●

The B

j

’s are called body (or premises)‏ and the A

’s head (or consequences)‏

●

A clause is a Horn clause if it has at most one literal in its head

●

Any wff of predicate logics can be transformed into a set of clauses, to be interpreted as a conjunction thereof

●

Operators NOT and OR (the only ones appearing in clauses)‏ are complete

–

The two languages are totally equivalent

Transforming wffs into clauses

Example

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  "y [Q(x,y)‏  P(y)‏] } }

●

Remove implication symbols

–

By replacing all occurrences of p  q by p  q

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  "y [Q(x,y)‏  P(y)‏] } }

●

Reduce the scope of 

–

So that it applies at most to an atomic formula. Use of laws:

●(p)‏ = p

●(p  q)‏ = p  q (p  q)‏ = p  q

●"x P(x)‏ = x P(x)‏ $x P(x)‏ = x P(x)‏

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  $y [Q(x,y)‏  P(y)‏] } }

Transforming wffs into clauses

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  $y [Q(x,y)‏  P(y)‏] } }

●

Standardize apart variables

–

A variable bound by a quantifier is fictitious

●Can be uniformly replaced by any other variable (not occurring in the expression)‏ along the whole scope of the quantifier, without changing the truth value of the expression itself

–

After this step, each quantifier has its own fictitious variable

–

Example

●"x [P(x)‏  $x Q(x)‏] is rewritten as "x [P(x)‏  $y Q(y)‏]

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  $w [Q(x,w)‏  P(w)‏] } }

Transforming wffs into clauses

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  $w [Q(x,w)‏  P(w)‏] } }

●

Remove existential quantifiers

–

Replace each occurrence of each quantified variable by a suitable Skolem function

whose arguments are the variables bound by universal quantifiers including in their scope

the existential quantifier to be removed

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  [Q(x,g(x)‏)‏  P(g(x)‏)‏] } }

●

where g(x)‏ is a Skolem function

Transforming wffs into clauses

"x {aP(x)‏  {a"y [P(y)‏  P(f(x,y)‏)‏]  [Q(x,g(x)‏)‏  P(g(x)‏)‏] } }

●

Turn the formula in prenex form

–

Move all quantifiers in the left-hand-side part of the formula, without changing their mutual order

●There is no conflict among variable names

–

The resulting wff consists of a string of quantifiers (prefix)‏

followed by a formula with no quantifiers (stub)‏

"x "y {aP(x)‏  {a [P(y)‏  P(f(x,y)‏)‏]  [Q(x,g(x)‏)‏  P(g(x)‏)‏] } }

Transforming wffs into clauses

"x "y {aP(x)‏  {a [P(y)‏  P(f(x,y)‏)‏]  [Q(x,g(x)‏)‏  P(g(x)‏)‏] } }

●

Turn the stub in normal conjunctive form

–

Conjunction of disjunctions of atoms or negated atoms

●Distributive property p  (q  r)‏ = (p  q)‏  (p  r)‏

"x"y {a [P(x)‏  P(y)‏  P(f(x,y)‏)‏]  [P(x)‏  Q(x,g(x)‏)‏]  [P(x)‏  P(g(x)‏)‏] }

●

Remove universal quantifiers

–

All remaining variables at this point are universally quantified

–

The order of universal quantifications is not important [P(x)‏  P(y)‏  P(f(x,y)‏)‏]  [P(x)‏  Q(x,g(x)‏)‏]  [P(x)‏  P(g(x)‏)‏]

Transforming wffs into clauses

[P(x)‏  P(y)‏  P(f(x,y)‏)‏]  [P(x)‏  Q(x,g(x)‏)‏]  [P(x)‏  P(g(x)‏)‏]

●

Remove  symbols

–

Replace expressions in the form p  q by the set of wffs {ap, q}

P(x)‏  P(y)‏  P(f(x,y)‏)‏

P(x)‏  Q(x,g(x)‏)‏

P(x)‏  P(g(x)‏)‏

Transforming wffs into clauses

P(x)‏  P(y)‏  P(f(x,y)‏)‏

P(x)‏  Q(x,g(x)‏)‏

P(x)‏  P(g(x)‏)‏

●

Rename variables

–

No variable symbol must appear in more than one clause

●"x [P(x)‏  Q(x)‏] is equivalent to "x P(x)‏  y Q(y)‏

P(x’)‏  P(y)‏  P(f(x’,y)‏)‏

P(x’’)‏  Q(x’’,g(x’’)‏)‏

P(x’’’)‏  P(g(x’’’)‏)‏

●By replacing terms not involving variables to the variables in an atomic expression, one obtain ground instances of the atom

Resolution

●

Inference rule

●

Operates only on clausal formulas

–

Ground clauses

(P

 P

2

 …  P

n

)‏  (P

1

 Q

2

 …  Q

m

)‏  (P

 …  P

n

 Q

2

 …  Q

m

)‏

●

Where the P

’s and the Q

’s are all distinct literals

–

Premises are called parents

–

The consequence is called resolvent

–

P

and P

are the literals resolved upon

Resolution

●

Used to solve those AI problems that can be reduced to theorem proof in First Order Logics

●

The set of wffs from which a theorem is to be proven is first turned into clauses

–

If a wff A logically follows from a set of wffs S, then it logically follows from the set of clauses obtained by turning the wffs in S into clausal form

●

Encloses several other inference rules

●

Analysis by cases, Modus ponens, Modus tollens, ...

Resolution

●

Example

●

Hypotheses: {aP, P  Q, Q  R}.

●

Prove R.

–

P hypothesis

–

P  Q hypothesis

–

Q  R hypothesis

–

Q resolution of 1, 2

–

P  R resolution of 2, 3

–

R resolution of 1, 5 or of 3, 4

Resolution

●

Definition (empty clause)‏

●

A clauses having no head nor body

–

Symbol: □

–

Denotes a contradiction

●Not including any literal, cannot ever be made true

●

A set of hypotheses from which the empty clause may be proven by resolution is inconsistent

Resolution

●

If the claim to be proven is known, one may proceed in a focused manner

●

Instead of going forward by trial, hoping to prove it

●

Proof by Refutation

●

Assume the negation of the thesis is true

●

Show that such a negation, along with the hypotheses, leads to a contradiction

–

by proving the empty clause

●

Conclude that the theorem is true

Proof by Refutation

●

Example

●

Hypotheses {aP, P  Q, Q  R}.

●

Prove R  Hypotheses {aP, P  Q, Q  R, R}

–

P hypothesis

–

P  Q hypothesis

–

Q  R hypothesis

–

R hypothesis

–

Q resolution of 1, 2

–

P  R resolution of 2, 3

–

R resolution of 1, 6 or of 3, 5

–

□ resolution of 4, 7

Resolution

●

Resolution was defined for propositional calculus

●

Can be applied to ground clauses

●

Problem: applying resolution to clauses involving variables

–

Not always easy to determine whether two atoms cannot be true at the same time

●In predicates, variables do not allow to understand immediately whether two atoms are complementary

–Example: P(x,f(a)‏)‏ v P(x, f(y)‏)‏ v Q(y)‏ and P(z, f(a)‏)‏ v Q(z)‏

●

Solution: Look for substitutions of terms to the variables involved in the parent clauses such that these will contain complementary atoms

Resolution

●

Extension to predicate logics

●

Assuming the two parent clauses are standardized apart

●

Substitution law: look for a substitution that makes complementary a literal in the former with a literal in the latter (unifier of the two literals)‏

●

Apply it to both expressions

●

Resolve the two resulting formulas

Substitutions

●

Definition (substitution)‏

●

Function from variables to terms

–

Denoted by symbols , , , ….

●A substitution  in which (x)‏ is bound to g(h(a)‏,a)‏ and (y)‏ is bound to h(a)‏ can be written as:

● = {a xg(h(a)‏,a)‏, yh(a)‏ } –

This set of bindings is usually finite

●

Application of a substitution to an expression is denoted (E)‏

●

The expression in which each variable x

in E has been replaced by (x

)‏

Resolution

1. computer(x)‏ :- part_of(x,y)‏, keyboard(y)‏, part_of(x,z)‏, printer(z)‏. Hyp.

2. printer(w)‏ :- has_head(w)‏. Hyp.

3. part_of(a,b)‏. Hyp.

4. part_of(a,c)‏. Hyp.

5. has_head(c)‏. Hyp.

6. keyboard(b)‏. Hyp.

Goal: prove that object a is a computer

7. ¬ computer(a)‏. or, in clausal form, :- computer(a)‏. Th.

Let us try to prove the empty clause

8. :- part_of(a,y)‏, keyboard(y)‏, part_of(a,z)‏, printer(z)‏. 1 (a/x)‏, 7 9. :- keyboard(b)‏, part_of(a,z)‏, printer(z)‏. 8 (b/y)‏, 3

10. :- part_of(a, z)‏, printer(z)‏. 9, 6

11. :- printer(c)‏. 10 (c/z)‏, 4

12. :- has_head(c)‏. 11, 2 (c/w)‏

13. □ 12, 5

Unification & Pattern Matching

●

In Artificial Intelligence, most knowledge-based systems supports a basic operation:

●

Comparison of (symbolic)‏ descriptions

–

Unification

–

Matching

●

“Unification is to AI (and to symbolic

computation)‏ what addition and multiplication represent to numeric calculus”

[Siekmann, 1990]

Unification

●

An essential part of more complex operations

●

resolution, search, control, ...

●

The fundamental problem for systems that carry out inferences

●

Expert systems, automatic theorem provers, problem solvers, learning systems, production systems, …

●

Estimated that in most production systems 90%

of total computation time is devoted to matching operations

Unification & Pattern Matching

●

The problem was formulated, faced and studied by different researchers in different ways

●

Today, on most machines dedicated to AI, unification is implemented by specialized hardware or by means of a set of quick instructions

●

CPU in V generation computers

–

Warren abstract machine

●Descriptions to be compared are compiled in the instruction set of the machine

Pattern Matching

●

Cross-cutting issue, common to many branches of AI

●

logic programming, intelligent databases, natural language processing, machine learning, …

●

As a consequence, the search for efficient matching techniques is of utmost importance to all those who operate in AI

Unification & Pattern Matching

●

Unification Theory

●

Unification is the procedure by which 2 or more structures are compared to discover their similarities or differences

●

The structures can be expressed in different formalisms

–

Propositional logics, feature vectors, rules, frame-like structures, FOPL, graphs, semantic nets, …

●

We will focus on:

●

Well-formed formulas (wff)‏ in FOL

Unification

●

Problem:

●

“Given 2 terms, s and t, there exist terms that can be substituted to the variables occurring in s and t, such that the terms so obtained are identical?”

Unification & Pattern Matching

●

More formally

●

Let:

●

FU

= {a a, b, c, … } be a set of constants;

●

VAR = {a x

, x

, x

,…} be a set of variables;

●

FU

= {a f, g, h,…}, n=1,2,…

be a set of n-ary functions

●

Let us denote by t

1

,t

2

,t

3

,… the terms built starting from the previous sets, according to the definition of a term as previously provided

●

TERM = {a t

,t

,t

,…}

Substitutions

●

Def. 3 Substitutions

●

A substitution  is a function from variables to terms

 : VAR  TERM Expressed as:

 = {a (t

/x

)‏ | x

 VAR, t

 TERM } or:

 = {a x

 t

| x

 VAR, t

 TERM }

●

For convenience, we also define the extensions of

 to TERM and to the set of WFFs of the language

–

We will still denote such functions by 

Substitutions

●

By applying  to a term t, involving variables x

, it yields a new term, (t)‏, obtained by replacing all occurrences of variables x

i

by the corresponding terms t

j

●

In addition to (t)‏, an instance of a substitutions is denoted by t or t.

●

WARNING!

●

It is not permitted to replace a variable with a term involving that very variable

–

Unless we admit INFINITE TERMS

Substitutions

●

Example of (permitted)‏ substitution

●

Let t = f (g(a,b)‏, x, y)‏ be a term in the language and

 = {a g(a)‏/x, c/y, y/z } a substitution

●

From the given definitions, one has:

●

(t)‏ = f(g(a,b)‏,g(a)‏,c)‏

Substitutions

●

Def. 4 Composite substitution

●

Given two substitutions,  and , the composite substitution of  and , denoted by (  )‏, is the substitution obtained from  and  as follows:

–

(1)‏ By modifying  so that substitution  is applied to its terms;

–

(2)‏ By adding to  the (term/variable)‏ pairs in  concerning variables not occurring in .

Substitutions

●

Theorem 1

●

Arbitrarily fixed a term t and two substitutions  and

, it holds:

●

(  )‏ (t)‏ = ((t)‏)‏

●

Proof (Exercise)‏

Substitutions

●

Example

●

Let t = f(x,y)‏

–

 = {ag(y,z)‏/x, a/y}  = {ab/y, c/z}

●

From rules (1)‏ and (2)‏ for susbtitution composition, we have:

–

     = {a g(b,c)‏/x, a/y, c/z }

●

It is easily checked that:      (t)‏ = ((t)‏

–

Indeed:

●    (t)‏ = f(g(b,c)‏,a)‏

●   ( f(g(y,z)‏,a)‏ )‏ = f(g(b,c)‏,a)‏

–

While:

●  (f(x,b)‏)‏ = f(g(y,z)‏,b)‏ ≠ f(g(b,c)‏,a)‏ = 

Substitutions

●

Theorem 2

●

Substitution composition operation is associative, but it is not commutative, i.e., given 3 substitutions

, , , we have:

●

                

●

        ≠ 

Unification

●

Def. 5 Unifiable terms – Unifier – Unification

●

Two terms, s and t, are unifiable if there exists a substitution  such that:

●

(s)‏ = (t)‏

●

In such a case, we say that  is a unifier of s and t and (s)‏ (or (t)‏)‏ is a unification of s and t

Unification

●

Example 2

●

Are the two terms:

●

s = f (g(y,b)‏, x)‏ t = f(x, g(a,b)‏)‏

unifiable?

●

 = {a g(a,b)‏/x, a/y } is a unifier of s and t;

●

We have indeed:

●

(s)‏ = f( g(a,b)‏, g(a,b)‏ )‏ = (t)‏

●

And thus s and t are unifiable

Unification

●

Example 3

●

The two terms s = f(x,g(y)‏)‏ t = f(x,g(b)‏)‏

●

Are unifiable and  = {a b/y } is a unifier

●

But... is it the only unifier of s and t?

–

Also  = {a a/x, b/y } is a unifier of s and t

–

Moreover, it is easily checked that there exist many other unifiers of s and t.

●

Anyway, however we choose a unifier for s and t, we realize that  turns out to be the simplest. We have indeed:

●

 = {a     where  = {a a/x }

Unification

●

Moreover, it can be proved that, if  is a unifier of s and t, there exists a substitution  such that:

●

       ( is an instance of )‏

Unification

●

Def. 6 Most General Unifier (MGU)‏ or Simplest Unifier

●

Given two terms, s and t, and a unifier  thereof, we say that  is the most general unifier of s and t if, for any other unifier  of s and t, there exists a

substitution  such that:

●

    

●

(Chang and Lee, 73; Lloyd, 84)‏

Unification

●

Intuitively, we may think to the MGU as the

“simplest” among all unifiers of two given terms

●

Unification problem:

●

Finding (if any)‏ the MGU of two terms

Unification and Computability Theory

●

Theorem 3

●

The unification problem is decidable in first-order theories

●

Theorem 4 (Goldfarb, 1981)‏

●

The unification problem is undecidable in theories of order ,  ≥ 2

–

Reduction to the X problem of Hilbert

–

In 1972 C.L. Lucchesi, and in 1973 G.P. Huet, already independently discovered indecidability of the problem for

 ≥ 3

Unification

●

Theorem 5

●

The MGU of two terms of the language of a first- order theory, if any, is unique (unitary theory)‏

●

Proof (exercise)‏

●

Note:

●

Theorem 5 does not hold if the function symbols occurring in the terms fulfil at least one of the following properties:

–

(C)‏ f(x,y)‏ = f(y,x)‏ Commutativity

–

(A)‏ f(f(x,y)‏,z)‏ = f(x,f(y,z)‏)‏ Associativity

Unification

●

In other words, in an equational theory in which to the axioms of a first-order theory

●

(absolutely free term algebra)‏

●

At least one of equations (C)‏ or (A)‏ is added, there may exist different MGUs of two terms

Unification of WFF

●

Def. Permutation

●

Given A = {a k  ℕ | 1  k  n }, a permutation p of A is any bijective function

●

p: A  A.

●

Def. Literal

●

<literal>::=

<atomic formula> | <atomic formula>

Unification

●

Unifiable Atomic Formulae

●

Definition

–

Two atoms a = P(t

1

,t

2

,…,t

n

)‏ and a’ = Q(t’

1

,t’

2

,…,t’

m

)‏

unify if there exists a substitution  such that:

(a)‏ = (a’)‏.

●

This condition is equivalent to the following set of conditions:

–

1)‏ P = Q

–

2)‏ n = m

–

3)‏ there exists a substitution  such that ∀i  {a1,2,…,n} : (t

)‏ = (t’

i

)‏

Unification

●

Observation

●

If P is commutative

–

i.e., the order of terms in predicate P does not matter (e.g. “equal”)‏,

the definition of unification between atoms is modified as follows:

–

a and a’ unify if:

●1)‏ P = Q

●2)‏ n = m

●3)‏ there exist a permutation p of the first n natural numbers and a substitution  such that ∀i  {a1,2,…,n} : (t_i)‏ = (t’_p(i)‏)‏.

Unification

●

Unifiable literals

●

Definition

–

Two literals l and l’ unify if there exists a substitution  such that: (l)‏ = (l’)‏

●

Example

–

l1 = went(John,south(x)‏)‏

–

l2 = went(y,south(America)‏)‏

unify and their unifier (which is also the MGU)‏ is:

 = {a America/x, John/y }

Unification

●

Unifiability of Conjucts of Literals

●

Definition

–

Two conjuncts of literals:

c = l

∧ l

∧ … l

and c’= l’

∧ l’

∧ … l’

unify if there exists a substitution  such that:

(c)‏ = (c’)‏.

●

The above condition is equivalent to the following set of conditions:

–

k = h and

–

There exist a permutation p of the first k natural numbers and a substitution  such that ∀i  {a1,2,…,k} : (l

)‏ =

(l’

)‏.

Unification

●

Example

●

c1 = P(f(x1)‏,h(x2,f(x1)‏)‏ ∧ Q(h(x2)‏,x3)‏

●

c2 = Q(h(g(x4)‏)‏,g(x4)‏)‏ ∧ P(x5,h(g(x4)‏,x5)‏)‏

unify, and their MGU is:

●

 = {a g(x4)‏/x2, g(x4)‏/x3, f(x1)‏/x5 }

●

Observation

●

The conditions for two conjuncts of literals to be unifiable are not equivalent to those required for the unifiability of two sets of literals

Unification

●

Unification of sets of literals

●

Definition

–

Two sets of literals L = {a l

,l

,…,l

} and L’ = {a l’

,l’

,…,l’

} are unifiable if there exists a substitution  such that:

(L)‏ = (L’)‏

●

Example

–

c = P(f(x)‏,y)‏ ∧ P (f(a)‏,b)‏ L = {a P(f(x)‏,y)‏, P(f(a)‏,b)‏ }

–

c' = P(f(z)‏,w)‏ L = {a P(f(z)‏,w)‏ }

–

There exists  = {a a/x, b/y, a/z, b/w } such that:

(L)‏ = (L’)‏ = {a P (f(a)‏,b)‏ }

–

while c and c’, according to the definition of unifiability for conjuncts of literals, are not unifiable because k  h.

Unification

●

Unifiability of WFFs in Normal Disjunctive Form

●

Definition.

–

Two WFFs in normal disjunctive form:

d = c

 c

2

 … c

m

and d’= c’

 c’

2

 … c’

n

unify if there exists a substitution  such that:

(d)‏ = (d’)‏

●

Analogously to what previously said, the above condition is equivalent to requiring that:

–

1)‏ m = n

–

2)‏ there exist a permutation p of the first m natural numbers and a substitution   ∀i  {a1,2,…,m} : (c

)‏ =

(c’

)‏.

Unification

●

Example

●

d = red(x1)‏ v ontop(x2,x3)‏

●

d’ = ontop(head(x4)‏,neck)‏ v red(car(John)‏)‏

●

Unify and their MGU is:

●

 = {a head(x4)‏/x2, neck/x3, car(John)‏/x1 }

Unification

●

Exercise

●

Determine whether the following pairs of WFFs unify. If so, provide their MGU, otherwise briefly explain why they do not unify

–

Color (Tweety, Yellow)‏ Color(x,y)‏

–

Color (Tweety, Yellow)‏ Color(x,x)‏

–

Color(Hat(Postman)‏,Blue)‏ Color(Hat(y)‏,x)‏

–

R(F(x)‏,b)‏ R(y,z)‏

–

R(F(y)‏,x)‏ R(x,F(B)‏)‏

–

R(F(y)‏,y,x)‏ R(x,F(A)‏,F(v)‏)‏

–

Loves(x,y)‏ Loves(y,x)‏

Unification Algorithm

●

The discovery of the close relationship between logic deduction and computation gave

motivation to research: logics plays in computer science a role which is analogous to analysis in physics. Predicate logics is a programming language (Kowalski, 1979)‏

●

V generation computers

●

Machines to run languages for Logic Programming

–

CPU is a Unification Algorithm (in HW or in SW)‏

●Speed in KLIPS: Kilo-Logical Inference Per Second

Representation of Terms (Data Structures)‏

●

String representation

●

A term is represented as a linear array, whose elments are: function symbols, variables, constants, commas and parentheses

–

(Robinson, 1965)‏

●

Example

●

s = p(g(f(x)‏)‏, h(f(x)‏)‏)‏

)‏

)‏

)‏

x ( f ( h , )‏

)‏

x ( f ( g ( p

Representation of Terms (Data Structures)‏

●

Tree representation

●

Term = tree

●

Function symbols = roots of subtrees

–

Offspring = function’s arguments

●

Leaves = Variables and constants occurring in the term

●

Esempio

p

g h

f f

x x

Representation of Terms (Data Structures)‏

●

String and Tree representations are used for applications of unification that handle not too much complex terms, i.e., short and with little nesting

●

Disadvantage

–

They ignore common structures (subterms)‏

●

Example

–

In trying to unify:

●s = p(g(f(x)‏)‏, h(f(x)‏)‏ and t = p(g(f(a)‏)‏,h(f(a)‏)‏)‏

–

There is no need to process the latter occurrence of f(x)‏

and of f(a)‏, once the substitution {aa/x} has been fixed

●Thus, we need a more compact representation