Du Calcul des prédicats vers Prolog

Models and FormalismsS. GarlattiMR2A Informatique2012

Progress

1 Introduction

2 Formal Systems

3 Propositional Logic

4 The Predicate Calculus or First Order Logic

2 / 109 SG Models and Formalisms

Introduction

Concatenation Modeling?

Answer from a logical point of view:

Conc([X|L], L1, [X|L2]) :− Conc(L, L1, L2).Conc ([], L, L).

Conc([a,b ], [c,d ], L)?


Introduction

History of Logic

Plato’s logic, Aristotle’s logic, Stoic logicMedieval logic, etc.

Rise of Modern Logic, the mid-nineteenth century:Rigorous and formalistic discipline whose exemplar was the exactmethod of proof used in mathematicsThe modern so-called "symbolic" or "mathematical" logic

Modern logic: a calculus whose rules of operation are determinedonly by the shape and not by the meaning of the symbols itemploys, as in mathematics.


Progress

1 Introduction

2 Formal Systems




Formal Systems

Formal Systems (or Formalism) consist of :

An Axiomatic Theory

A finite set of symbols for constructing formulas.A grammar to define well-formed formulas (abbreviated wff ).A set of Axioms or axiom schemata: each axiom must be a wff .A set of Inference rulesFrom Axioms and Inferences Rules, Theorems are deduced.Properties: Consistency and Decidability


Formal Systems


An Axiomatic Theory

A finite set of symbols for constructing formulas.

A grammar to define well-formed formulas (abbreviated wff ).A set of Axioms or axiom schemata: each axiom must be a wff .A set of Inference rulesFrom Axioms and Inferences Rules, Theorems are deduced.Properties: Consistency and Decidability


Formal Systems


An Axiomatic Theory

A finite set of symbols for constructing formulas.A grammar to define well-formed formulas (abbreviated wff ).

A set of Axioms or axiom schemata: each axiom must be a wff .A set of Inference rulesFrom Axioms and Inferences Rules, Theorems are deduced.Properties: Consistency and Decidability


Formal Systems


An Axiomatic Theory

A finite set of symbols for constructing formulas.A grammar to define well-formed formulas (abbreviated wff ).A set of Axioms or axiom schemata: each axiom must be a wff .

A set of Inference rulesFrom Axioms and Inferences Rules, Theorems are deduced.Properties: Consistency and Decidability


Formal Systems


An Axiomatic Theory

A finite set of symbols for constructing formulas.A grammar to define well-formed formulas (abbreviated wff ).A set of Axioms or axiom schemata: each axiom must be a wff .A set of Inference rules

From Axioms and Inferences Rules, Theorems are deduced.Properties: Consistency and Decidability


Formal Systems


An Axiomatic Theory

A finite set of symbols for constructing formulas.A grammar to define well-formed formulas (abbreviated wff ).A set of Axioms or axiom schemata: each axiom must be a wff .A set of Inference rulesFrom Axioms and Inferences Rules, Theorems are deduced.

Properties: Consistency and Decidability


Formal Systems


An Axiomatic Theory

A finite set of symbols for constructing formulas.A grammar to define well-formed formulas (abbreviated wff ).A set of Axioms or axiom schemata: each axiom must be a wff .A set of Inference rulesFrom Axioms and Inferences Rules, Theorems are deduced.Properties: Consistency and Decidability


Formal Systems

The Formal Systems MIU , Axiomatic Theory

Alphabet A = {M, I ,U}.A grammar : wff consist of all series of the three alphabetelements.A set of axioms= {MI}.A set of inference rules: Let f , g variables representing wff , gcould be empty

R1: f ` fUR2: Mf ` MffR3: fIIIg ` fUgR4: fUUg ` fg


Formal Systems

The Formal Systems MIU , Axiomatic Theory

Some Theorems:R2: MI ` MIIR1: MII ` MIIUR1: MIIU ` MIIUUR4: MIIUU ` MIIR2: MII ` MIIIIR3: MIIII ` MIU

MU is a theorem?


Formal Systems

Formal Systems consist of : A Model Theory or Semantics

A standard model M:It is a structure that gives a concrete interpretation of the theory(axiomatic theory).

For instance, M = (D, I)D is the interpretation domain.An Interpretation function I that assigns:- Let A a set of alphabet elements, (A)I : A→ D- Let F a set of wff , (F )I : F → {True,False}

Properties: consistency, soundness, completeness


Formal Systems

The Axiomatic Theory of Formal Systems pgAlphabet A = {p, g ,−}wff all series of p, g ,−

x ∈ {−,−−, ...,−n}, Axiom Schema:xp − gx−

x , y , z ∈ {−,−−, ...,−n},Inference Rules :xpygz ` xpy − gz−


Formal Systems

The Model Theory of the formal system pg

An Interpretation function I that assigns:(p)I : plus, (g)I : equal , (−n)I : n

(−−−p −−g −−−−−)⇒ (3 plus 2 equal 5) ⇒

(−−−p −−g −−−−)I = True

(−−−p − g −−−−−)⇒ (3 plus 1 equal 5) ⇒

(−−−p − g −−−−−)I = False


Formal Systems

Axiomatic and model theory and their properties:

Model TheorySatisfiabilityTruthValidity

Axiomatic TheoryAxiomsInference rulesDeductionTheorems

Completeness

Soundness


Progress

1 Introduction

2 Formal Systems




The Propositional Logic

The Language and the well-formed formulae or wff

A set of propositional symbols SA set of connectors: ¬,→,↔,∨,∧Let p, q, r ∈ S, p, q, r are atomsAn atom is a wff , then p, q, r are wffLet P be a wff , then ¬P is a wffLet P,Q be wff , then (P → Q), (P ↔ Q), (P ∨ Q), (P ∧ Q)

All wff are generated by applying the above rules


The Model Theory of Propositional Logic

In Propositional logic, I is an Interpretation function that assigns:A truth value in {T ,F}, to an atom or a well-formed formula,

Let P,Q be wff , assignment of Truth Values are made as follows:

P Q ¬P (P ∧ Q) (P ∨ Q) (P → Q)T T F T T TT F F F T FF T T F T TF F T F F T

The Interpretation function I is truth-functional: the truth orfalsity of a well-formed formula is determined by the truth or falsityof its components.


Truth, Validity

A wff P is said to be True under an interpretation I iff P isevaluated to T in the interpretation;

Otherwise, P is said to be False under the interpretation.

A wff is said to be Valid iff it is true under all its interpretations

A wff is said to be Inconsistent or Unsatisfiable iff it is falseunder all its interpretations

A wff is said to be Consistent or Satisfiable iff it is notInconsistent


Truth, Validity

Examples of Valid or inconsistent formulae(P ∧ ¬P)

(P → P)

((P ∧ ¬P)→ Q)

(P ∨ ¬P)


Outline1 Introduction2 Formal Systems3 Propositional Logic

The Axiomatic TheoryPropositional Logic PropertiesResolution Principles

4 The Predicate Calculus or First Order LogicThe Model Theory or SemanticsThe Axiomatic TheoryPredicate Calculus PropertiesResolution PrinciplesResolution StrategyProlog Modeling


Axiomatic Theory

An axiomatic theory is composed of:A language and wffA set of axiomsInference rules


Axioms

Let P,Q,R be wff

A1 : (P → (Q → P))A2 : (P → (Q → R))→ ((P → Q)→ (P → R)))A3 : (¬P → ¬Q)→ ((¬P → Q)→ P))

One inference ruleModus Ponens: P, (P → Q) ` Q

From hypothesis P and (P → Q), Q is deduced


Deduction

Theorem demonstration: ` (A→ A)

A′1 :` (A→ ((A→ A)→ A))A′2 :` ((A→ ((A→ A)→ A))→((A→ (A→ A)→ (A→ A))))

A′1,A′2 ` ((A→ (A→ A))→ (A→ A))

A1” :` (A→ (A→ A))A1”, ((A→ (A→ A))→ (A→ A)) ` (A→ A)

` (A→ A)


Deduction

Theorem demonstration: ` (A→ A)

A′1 : (A→ ((A→ A)→ A))

A′2 : ((A→ ((A→ A)→ A))→ ((A→ (A→ A)→ (A→ A))))((A→ (A→ A))→ (A→ A))

A1” : (A→ (A→ A)) ((A→ (A→ A))→ (A→ A))(A→ A)


Theorems

Some theorems

The law of noncontradiction: ` ¬(P ∧ ¬P)

Or ` ((P ∧ ¬P)→ Q)

The law excluded middle: ` (P ∨ ¬P)






Propositional Logic Properties

Completeness Theorem

Every Valid formula of the predicate calculus is a theorem.- if |= F then ` F

Soundness Theorem

Every theorem of the predicate calculus is a Valid formulaif ` F then |= F

The propositional Logic is decidable


Propositional Logic Properties




` ≡ |=

Completeness

Soundness






Resolution Principles

Normal FormsDefinition: A Literal is an atomic formula or Atom or thenegation of an Atom

A Formula F is called a Clause if and only if F is composed of adisjunction of literals, (F1 ∨ F2, ... ∨ Fn), n > 1

An empty clause, denoted �, is unsatisfiable or alwaysinterpreted as False, (deduced from the conjunction of twocomplementary literals P and ¬P)



Normal Forms

Definition: A formula F is in a Conjunctive Normal Form ifand only if F has the following form (F1 ∧ F2, ... ∧ Fn), n > 1,where each of F1,F2, ...,Fn is a disjunction of literals or a clause.

Any formula can be transformed into a normal forms



One possible resolution rule: the Cut Elimination Rule ofGentzen

Let D and E be clauses without any occurrence of literals P or¬P

(¬P ∨ E ), (P ∨ D) ` (E ∨ D)

The clause (E ∨ D) is called the resolvent

This rule is a generalization of the Modus Ponens Rule (obtainedby elimination of the clause D)



Let F be a set of clauses and A be a clause

To demonstrate F ` ABy means of the Cut Elimination Rule, the goal is to show that{F ,¬A} is unsatisfiable.It is a refutation

Demonstration of the unsatisfiability of {F ,¬A}Obtain a resolvent equal to the empty clause �, by eliminationof complementary literals in two different clauses.



Example : let F be a conjunctive normal form as follows:

F = ((P ∨ Q) ∧ (¬P ∨ Q) ∧ (P ∨ ¬Q) ∧ (¬P ∨ ¬Q))

F unsatisfiable?

(P ∨ Q) (¬P ∨ Q)Q

(P ∨ ¬Q) (¬P ∨ ¬Q)¬Q

�


Progress

1 Introduction

2 Formal Systems




The Predicate Calculus

Predicate calculus (first-order logic): an extension of thepropositional logic

The LanguageA set of Constants CA set of Variables VA set of function symbols FA set of Terms TA set of predicate symbols PA set of connectors: ¬,→,↔,∨,∧A set of Quantifiers: ∀,∃


The Language

The TermsA Constant a is a termA Variable x is a termif t1, t2, ..., tn ∈ T , (n > 0), then f (t1, t2, .., tn) ∈ Twhere f is a function symbol of arity n.

Well-Formed Formula or wffIf P is a predicate symbol and if t1, t2, . . . , tn ∈ T (n > 0) thenP(t1, t2, ..., tn) is an atomic formulaIf G and H are wff then(G → H), (G ↔ H), (G ∨ H), (G ∧ H), ¬G ,∀xG(x) and ∃xG(x)are wff .


The Language

Quantification theoryScope of quantifiersFree and bound variables

Examples of wff :∀x∃y(P(x , a, f (y), z)→ ∀yQ(y , g(x , a)))(P(x , f (z)) ∨ ∀xQ(x , z))∀z(∃yP(y , b) ∧ Q(y , f (a, z))


The Language

Quantification theory∀x∃y(P(x , a, f (y), z)→ ∀yQ(y , g(x , a)))

x, y are bound variables, z is a free variable, the second variable yis bound to the quantification forally , a is a constant, f and g arefunctional symbols.

(P(x , f (z)) ∨ ∀xQ(x , z))the first occurrence of x is free, the second is bound, the twooccurrences of z are free, but they do not represent the samevariable.

∀z(∃yP(y , b) ∧ Q(y , f (a, z))The second occurrence of y is free, the first one bound, z is bound.






Standard Model

A standard model is a structure M = (D, I) Where

D is a nonempty set called the Interpretation DomainI is an Interpretation function that assigns:

A truth value in {T ,F}, to a well-formed formula,A n-place relation to a nary predicate symbol,An n-place operation to a nary function symbolAn element of D to a constantAn element of D to variableAn element of D to a nary functional term

The interpretation function I is also Truth-Functional


Satisfiability, Truth, Models, Validity

Let s be a denumerable sequence of D elements, s = (s1, s2, ..., sn)

The idea is: from a sequence s, the corresponding n-tuple< s1, s2, ..., sn > will satisfy a wff F with free variables(x1, x2, ..., xn)

For instance, the sequence s = (s1, s2, ..., sn) of elements of theDomain D will satisfy the wff F (x2, x5)

if the ordered pair < s2, s5 > is in the relation (F )I assigned tothe predicate symbol F by the interpretation I.



An Interpretation I:

a ∈ C , (a)I : C → D

x ∈ V , (x)I : V → D

t1, t2, . . . , tn and f (t1, t2, .., tn) are terms, f ∈ F ,

(f (t1, t2, .., tn))I : Dn → D

with (f (t1, t2, .., tn))I ≡ ((f )I((t1)I, (t2)I, .., (tn)I))

if ti is the variable xi , (t)I is equal to the sequence element si



SatisfiabilityIf F (t1, t2, .., tn) is an atomic formula and (F )I is thecorresponding n-place relation then the sequences = (s1, s2, ..., sn) satisfies F (t1, t2, .., tn) if and only if(F )I((t1)I, (t2)I, .., (tn)I)), that is to say the n-tuple< s1, s2, ..., sn > is in (or verify) the relation (F )I.s satisfies ¬F if and only if s does not satisfies Fs satisfies (F → G) if and only if s does not satisfy F or ssatisfies Gs satisfies ∀xiF if and only if every sequence s that differs from sin at most the i th component satisfies F



Let F be the set of wff , S be the set of denumerable sequencesA wff F is true for the interpretation I (written |=I F ) if andonly if every sequence in S satisfies F .

F is said to be false for the interpretation I if and only if nosequence in S satisfies F .

An interpretation I is said to be a model for a set F of wff ifand only if every wff is true for I.

A wff F is valid (written |= F ) if and only if F is true for allinterpretation I, over all domains.






Axiomatic Theory

An axiomatic theory is composed of:A language and wffA set of axiomsInference rules


Axioms

Let P,Q,R be wff and x be a variable

A1 : (P → (Q → P))A2 : (P → (Q → R))→ ((P → Q)→ (P → R)))A3 : (¬P → ¬Q)→ ((¬P → Q)→ P))

A4 : ∀xP(x)→ P(x)A5 : ∀x(P → Q)→ (P → ∀xQ)

where P contains no free occurrence of x .


Inference Rules

Two rules

Modus Ponens

P, (P → Q) ` Q

- from hypothesis P and (P → Q), Q is deduced

Generalization Rule

P(x) ` ∀P(x)

- from hypothesis P(x), ∀P(x) is deduced


Theorems

Some theorems

The law of noncontradiction: ` ¬(P ∧ ¬P)

Or ` ((P ∧ ¬P)→ Q)

The law excluded middle: ` (P ∨ ¬P)

` (¬∀xP(x)→ ∃x¬P(x))

` (¬∃xP(x)→ ∀x¬P(x))






Predicate Calculus Properties

Completeness Theorem

Every Valid formula of the predicate calculus is a theorem.- if |= F then ` F

Soundness Theorem

Every theorem of the predicate calculus is a Valid formulaif ` F then |= F



Decidability : the Predicate Calculus is undecidable

There is no decision procedure to determine whether arbitraryformulas are theorems (Church, Turing, Post, Markov).

Nevertheless, if a formula F is valid, there is a constructive proofthat F is valid.

- From the soundness theorem, we can conclude that F is a theorem.

- The predicate calculus is semidecidable.






` ≡ |=

Completeness

Soundness







For predicate calculus, the resolution is as follows:Conjunctive normal forms are usedIt is a refutation demonstrating that a set of clauses isunsatisfiable

Conjunctive normal forms : 3 stages are necessary to deal withquantifiers and variables

1. Prenex normal formsA formula F is in Prenex Normal Form if and only if the formulais in the form of (Q1x1)(Q2x2), ..., (Qnxn)(M) where- (Qixi), i = 1, ..., n, is either (∀xi) or (∃xi)- M is a formula containing no quantifiers



2. Skolem Standard FormsA formula F is in Skolem Normal Form iff the formula is in theform of (∀x1)(∀x2), ..., (∀xn)(M) where M is a formula containingno quantifier

In a Prenex Standard Form, for an existential quantifier (∃x)having n universal quantifiers on variables (x1, x2, ..., xn) appearingbefore, all occurrences of x are replaced by a n-place functionf (x1, x2, ..., xn) and (∃x) is eliminated.

If n = 0, all occurrences of x are replaced by a constant.

3. Conjonctive Normal Form: a Skolem Standard Form is rewrittento obtain a Conjunctive Normal Form



The Herbrand Universe of a set of clauses

A set F of clauses is unsatisfiable if and only if it is false underall interpretations I over all domains

Impossible to consider all interpretations I over all domains

There is a special domain H , called the Herbrand Universe of F ,"replacing all domains"



H , the Herbrand Universe of a set of clauses

1. H0 is the set of constants appearing in F . If no constant isappearing in F , H0 is to consist to a single constant, H0 = {a}

2. Hi+1 be the union of Hi and the set of all terms of the formf n(t1, t2, ..., tn) for all n-place functions f n occurring in F , wheret1, t2, ..., tn ∈ Hi

3. H∞ is the Herbrand Universe of F

4.



H , the Herbrand Universe of a set of clausesF = {P(a),¬P(x) ∨ P(f (x))}

1. H0 = {a}2. H1 = {a, f (a)}3. H2 = {a, f (a), f (f (a))}4. H3 = {a, f (a), f (f (a)), f (f (f (a)))}5. ..6. ...7. H∞ = {a, f (a), f (f (a)), f (f (f (a))), .....}



Herbrand’s Theorem

Definition: A ground instance of a clause C of a set of clauses Fis a clause obtained by replacing variables in C by members of the

Herbrand Universe of F .

Herbrand’s Theorem: A set F of clauses is unsatisfiable if and onlyif there is a finite unsatisfiable set F ′ of ground instances of clauses

of F .



Definition: A substitution is a finite set of the form{t1/x1, ..., tn/xn} where every ti is a term and every xi is a variable

Definition: Let θ = {t1/x1, ..., tn/xn} be a substitution et E be anexpression, Eθ is an expression obtained from E by replacing

simultaneously each occurrence of the variable xi(1 ≤ i ≤ n) bythe term ti in E . Eθ is called an instance of E .

The instance definition is compatible with that of ground instanceof a clause.















A Substitution{f (y)/y , a/z , f (g(b))/x}

An instanceθ = {a/x , f (b)/y , b/z},E = Q(x , y) ∨ P(y , z)Then, Eθ = Q(a, f (b)) ∨ P(f (b), b)



Definition: Composition of substitutions

Let θ = {t1/x1, ..., tn/xn} and λ = {u1/y1, ..., um/ym} be twosubstitutions;

then, the substitution composed of θ et λ, denoted by θ ◦ λ, that isobtained from the set {t1λ/x1, ..., tnλ/xn, u1/y1, ..., um/ym}

by deleting any element tiλ/xi for which tiλ = xi and any elementuj/yj such that yj is among{x1, x2, ..., xn}



Composition of Substitutions

θ = {t1/x1, t2/x2} = {f (y)/x , z/y}

λ = {u1/y1, u2/y2, u3/y3} = {a/x , b/y , y/z}

{t1λ/x1, ..., tnλ/xn, u1/y1, ..., um/ym} ={f (b)/x , y/y , a/x , b/y , y/z}

After deletions: θ ◦ λ = {f (b)/x , y/z}

Comments: θ ◦ (λ ◦ β) = (θ ◦ λ) ◦ β; ε ◦ β = β ◦ ε with ε theempty substitution.



Definition: UnifierA substitution θ is called a unifier for a set {E1,E2, ...,Ek} ifand only if E1θ = E2θ = ... = Ekθ. The set {E1,E2, ...,Ek} issaid to be unifiable if there is a unifier for it.

Several unifiers may be exist for a set F of formulae

Definition: Most General UnifierA unifier σ for a set {E1,E2, ...,Ek} of formulae is a MostGeneral Unifier if and only if each unifier θ there is asubstitution λ such that θ = σ ◦ λ



Let P(g(y)) et P(x) be formulae, σ, λ, θ can be defined as follows:θ = {g(a)/x}, λ = {a/y}, σ = {g(y)/x}σ is the most general substitution

Most General UnifierLet U be the set of unifiers, F be a set of formulae and S be theset of substitutions on F .∀α ∈ U ,∃β ∈ S such that α = β ◦ σ

The most general unifier (when it exists), denoted MGU (MostGeneral Unifier) is the most general substitution that matchformulae and it is unique.



The resolution principle is composed of two inference rules: theresolution rule and the reduction rule

Resolution Rule: the formula C is the resolvent of the two clausesA and B if and only ifA = P ∨ DB = P1 ∨ EC = (Dθ ∨ E )σ

θ is a renaming substitution so that Dθ and E are formulae withdisjoint variables. σ is the most general unifier of P et P1 suchthat P et P1 are complementary literals (or complementary pairs)



The resolution rule can be rewrite as follows:

P ∨ D,P1 ∨ E ` (Dθ ∨ E )σ

ExampleLet A = P(x , c) ∨ R(x) and B = ¬P(c , c) ∨ Q(x)Let D = R(x) and E = Q(x)

C = R(c) ∨ Q(x) with θ = {y/x} in A and σ = {c/y}



Reduction ruleLet A = P ∨ P1 ∨ B be a clause, C is the resolvent of A if and onlyif:Pσ = P1σ, σ Most General Unifier of P et P1

C = Pσ ∨ BσThe rule may be rewrite as follows:P ∨ P1 ∨ B ` Pσ ∨ Bσ with Pσ = P1σ

ExampleLet A = P(x , g(y)) ∨ P(f (c), z) ∨ R(x , y , z)C = R(f (c), y , g(y)) ∨ P(f (c), g(y)) withσ = {f (c)/x , g(y)/z}



Theorem: a set F of clauses is unsatisfiable if and only if there is adeduction of the empty clause from F .

Properties: the resolution principle is sound and complete, that isto say:If F is satisfiable, the empty clause cannot be deducedvide.If F is unsatisfiable, the empty clause is deduced






Resolution Strategy

The two main methods are: the management of a set of clausesand the exploration of deduction tree.

We focus on the later. Two possible choices are available for thisstrategy:Selection of a sub-tree of the deduction tree, limitation of thepossible deductions

Selection of an exploration strategy of a sub-tree (Depth- firstsearch, Breadth-first search, ...)


Resolution Strategy

Linear Strategy

Definition: Let S be a set of clauses and C0 a clause in S, a lineardeduction of Cn from S with C0 as initial clause has the followingproperties: Ci+1 is the resolvent of Ci and Bi (resolution rule) withBi ∈ S or Bi = Cj such that 1 ≤ i ≤ n − 1, j < i .


Resolution Strategy

Linear deduction properties (cf. Chang and Lee or Loveland):

If there is a deduction of the empty clause for S, then there is alinear deduction of the empty clause for S.

Moreover, if S = S ′ ∪ {C0} with S ′ satisfiable and S unsatisfiablethen there is a linear deduction from S having C0 as initial clause.

Breadth-first exploration strategy: the linear deduction is soundand complete.Depth-first exploration strategy: the linear deduction is sound,but not complete.


Resolution Strategy

Input Strategy

Definition: Let S be a set of clauses and C0 be a clause in S, anInput deduction of Cn from S with C0 as initial clause has thefollowing properties: Ci+1 is a resolvent obtained by the applicationof the rule resolution and Bi with Bi ∈ S such that 1 ≤ i ≤ n − 1.

Even, with a Breadth-first exploration strategy, an Inputdeduction is not complete.

The Input deduction tree does not contain the empty clause. butthe tree of all deductions contain the empty clause.


Resolution Strategy

Input Strategy

Nevertheless, there is an interesting result in a particular case::If S = S ′ ∪ {C0} is unsatisfiable, C0 is a negative clause thatonly contains negative literals and S ′ only contains clauses withexactly one positive literal (Horn clauses) then there is an inputdeduction with C0 as initial clause which gives the empty clauseclause and does not use the reduction rule.


Resolution Strategy

Ordered Strategy

Definition: An ordered resolution between two ordered clauses(without common variables) C1 and C2 deduces the ordered clauseC with the following conditions:C1 = L1 ∨ L2 ∨ ... ∨ LnC2 = ¬L′1 ∨ L′2 ∨ ... ∨ L′mC = (L2 ∨ ... ∨ Ln ∨ L′2 ∨ ... ∨ L′m)θ avec θ Most General Unifierof L1 and ¬L′1

The clause C is ordered: the clause containing the positive literal islocated at the beginning of the resolvent and the respective ordersof the two clauses are kept


Resolution Strategy

Definition: Let S be a set of clauses and C0 be a clause in S, alinear ordered deduction of Cn from S with C0 as initial clause is adeduction obtained by applying n ordered resolutions.

Linear ordered StrategyDefinition: Let S be a set of clauses and C0 be a clause in S, anordered deduction of Cn from S with C0 as initial clause has thefollowing properties: Ci+1 is an ordered resolvent of ordered clausesCi and Bi (ordered resolution) with Bi ∈ S or Bi = Cj such that1 ≤ i ≤ n1, j < i .


Resolution Strategy

A linear ordered refutation is a linear ordered deduction of theempty clause.

With a Breadth-first exploration strategy, the linear ordereddeduction is sound and complete.

The most important result is as follows:If S = S ′ ∪ {C0} is unsatisfiable, C0 is a negative literal and S ′does not have clauses with exactly one positive literal (Hornclauses) then there is an input and linear ordered with the initialclause C0 leading to the empty clause.


Resolution Strategy

SLD Resolution

A SLD resolution is a linear resolution with a selection function ona set of Horn clauses.

Definition: a SLD refutation of P ∪ {¬G} is a finite SLD deductionof P ∪ {¬G} of the empty clause via a selection function.


Resolution Strategy

SLD Resolution

Definition of Derivation: Let Gi be a goal such thatA1, ...,Am, ...Ak → Gi , the clause Ci+1 such that B1, ...,Bq → Aand a selection function R . The derivation of the goal Gi+1 isobtained from Gi with Ci+1 by using the MGU θi+1 via R if thefollowing conditions are filled:Am is an atom selected by a selection functionAmθi+1 = Aθi+1 tel que θi+1 is the MGU of A et Am

Gi+1 = (A1, ...,Am−1,B1, ...,Bq,Am+1, ...,Ak)θi+1Gi+1 is the resolvent of Gi et Ci+1. Ci+1 is a variant of A that isto say a clause such that all variables of A has been renamed.


Resolution Strategy

SLD ResolutionDefinition: a SLD derivation of P ∪ {¬G} is composed of a finititeor infinite serie G0,G1,G2, ... of goals, a serie C0,C1,C2, ... ofclauses’ variants of the program P and a serie θ1, θ2, ... of MGUsuch that Gi+1 is derived of Gi and Ci+1 and uses θi+1 via R .

A selection function is an application of a set of goals to a set ofatoms, such that the function value for a goal is alsways an atom.The later is called the selected atom.

Independence of the function selection: if P ∪ {¬G} isunsatisfiable then there is always a SLD refutation that will usethis function selection. The space search traversed by a SLDrefutation is called a SLD tree.


Resolution Strategy

SLD Resolution

Let P be a program, G be a goal and R a selection fucntion, theSLD tree for P ∪ {¬G} via R is defined as follows:Each tree node is a goal (possibly empty)The root is GLet A1,A2, ...,Ak → Gi , (k ≥ 1) be a tree node and Am be theselected atom via R , this node is a descendant for each clauseB1, ...,Bq → A such that Am et A is unifiable. the descendant is(A1, ...,Am−1,B1, ...,Bq,Am+1, ...,Ak)θi+1 where θi+1 is theMGU of Am and AThe empty nodes do not have descendant


Resolution Strategy

SLD ResolutionThe soundness of the SLD refutation rely upon the unification.Thus, if it unifies non unifiable terms, the result will be wrong.Occur check:test ← P(x , x)P(x , f (x))← P(x , x))

The unification algorithm has to made the occur check. Let x be avariable that must be unified with the term t1, the ccur check aimat detecting the presence of x into the term t1. If one consider theabove mentioned example, for demonstrating test it is necessary tounify P(x , x) with P(y , f (y)) - after renaming the variables. Thesetwo terms are not unifiale because x 6= f (x). Without the occurcheck, the algorithm will unify the two terms.






Prolog Modeling

Concatenation Program


Conc([a,b ], [c,d ], L)?


Prolog Modeling

Ancestor Program, Version 1Ancestor(X,Y) :− Parents(X,Z), Ancestor(Z,Y).Ancestor(X,Y) :− Parents(X,Y).Parents(X,Y) :− Father(X,Y).Parents(X,Y) :− Mother(X,Y).Version 2Ancestor(X,Y) :− Parents(X,Y).Ancestor(X,Y) :− Parents(X,Z), Ancestor(Z,Y).Version 3Ancestor(X,Y) :− Ancestor(Z,Y), Parents(X,Z).Ancestor(X,Y) :− Parents(X,Y).


Prolog Modeling

Eight Queens’ Problem

1 2 3 4 5 6 7 81 X2 X3 X4 X5 X6 ? ? ?7 ? ? ?8 ? ? ?


Prolog Modeling

Eight Queens’ ProgramPut(Listdd , Listdg ,Col ,8, Result ).

Put(Listdd , Listdg ,Col,Row,Result) :−Row_1 is Row + 1,column(I), not(member(I,Col)),Dd is Row_1 + I, Dg is I − Row_1,not(member(Dd,Listdd)),not(member(Dg,Listdg)),Put([Dd|Listdd ],[ Dg|Listdg ],[ I |Col ], Row_1,[[Row_1,I]|Result ]).

Column(1). Column(2). Column(3). Column(4).Column(5). Column(6). Column(7). Column(8).


Prolog Theorem Proving

Concatenation Program


Conc([a,b ], [c,d ], L)?

∀X , L, L1, L2 (Conc(f (X , L), L1, f (X , L2)) ∨ ¬Conc(L, L1, L2))∧∀L (Conc(f (empty), L, L)∧∀L ¬Conc(f (a, f (b, f (empty))), f (c , f (d , f (empty))), L)



Concatenation Demonstration

¬Conc(f (a, f (b, f (empty))), f (c , f (d , f (empty))), L′)Conc(f (X , L), L1, f (X , L2)) ∨ ¬Conc(L, L1, L2))¬Conc(f (b, f (empty)), f (c , f (d , f (empty))), L2)

σ ={a/X , f (b, f (empty))/L, f (c , f (d , f (empty)))/L1, f (a, L2)/L′}

Resolvent : ¬Conc(f (b, f (empty)), f (c , f (d , f (empty))), L2)




¬Conc(f (b, f (empty)), f (c , f (d , f (empty))), L2)Conc(f (X , L), L1, f (X , L2′)) ∨ ¬Conc(L, L1, L2′)¬Conc(f (empty), f (c , f (d , f (empty))), L2′)

σ = {b/X , f (empty)/L, f (c , f (d , f (empty)))/L1, f (b, L2′)/L2}

Resolvent : ¬Conc(f (empty), f (c , f (d , f (empty))), L2′)




¬Conc(f (b, f (empty)), f (c , f (d , f (empty))), L2)Conc(f (X , L), L1, f (X , L2′)) ∨ ¬Conc(L, L1, L2′)¬Conc(f (empty), f (c , f (d , f (empty))), L2′)

σ = {b/X , f (empty)/L, f (c , f (d , f (empty)))/L1, f (b, L2′)/L2}

Resolvent : ¬Conc(f (empty), f (c , f (d , f (empty))), L2′)




¬Conc(f (empty), f (c , f (d , f (empty))), L2′))Conc(f (empty), L, L)

�

σ = {f (c , f (d , f (empty)))/L, f (c , f (d , f (empty)))/L2′}

Resolvent : �



Ancestor ProgramAncestor(X,Y) :− Parents(X,Z), Ancestor(Z,Y).Ancestor(X,Y) :− Parents(X,Y).Parents(X,Y) :− Father(X,Y).Parents(X,Y) :− Mother(X,Y).Father(a,b). Father(b,c ). Father(d, f ). Father(e,g).Mother(a,d). Mother(d,e). Mother(a,h). Mother(b,i ).

Ancesotr(X,Y) ?



Ancestor Program∀X ,Y ,Z(Ancestor(X ,Y ) ∨ ¬Parents(X ,Z ) ∨ ¬Ancestor(Z ,Y )∧∀X ,Y (Ancestor(X ,Y ) ∨ ¬Parents(X ,Y )∧∀X ,Y (Parents(X ,Y ) ∨ ¬Father(X ,Y )∧∀X ,Y (Parents(X ,Y ) ∨ ¬Mother(X ,Y )∧Father(a, b) ∧ Father(b, c) ∧ Father(d , f ) ∧ Father(e, g)∧Mother(a, d) ∧Mother(d , e) ∧Mother(a, h) ∧Mother(b, i)∧¬Ancestor(X ,Y )



Ancestor Demonstration

¬Ancestor(T ,U)(Ancestor(X ,Y ) ∨ ¬Parents(X ,Z ) ∨ ¬Ancestor(Z ,Y )

¬Parents(T ,Z ) ∨ ¬Ancestor(Z ,U)

σ = {T/X ,U/Y }

Resolvent : ¬Parents(T ,Z ) ∨ ¬Ancestor(Z ,U)







¬Parents(T ,Z ) ∨ ¬Ancestor(Z ,U)(Parents(X ,Y ) ∨ ¬Father(X ,Y )¬Father(T ,Z ) ∨ ¬Ancestor(Z ,U)

σ = {T/X ,Z/Y }

Resolvent : ¬Father(T ,Z ) ∨ ¬Ancestor(Z ,U)







¬Father(T ,Z ) ∨ ¬Ancestor(Z ,U)Father(a, b)

¬Father(a, b) ∨ ¬Ancestor(b,U)

σ = {a/T , b/Z}

Resolvent : ¬Father(a, b) ∨ ¬Ancestor(b,U)







¬Father(a, b) ∨ ¬Ancestor(b,U)(Ancestor(X ,Y ) ∨ ¬Parents(X ,Z ) ∨ ¬Ancestor(Z ,Y )¬Father(a, b) ∨ ¬Parents(b,Z ) ∨ ¬Ancestor(Z ,U)

σ = {b/Y ,U/Y }

Resolvent : ¬Father(a, b) ∨ ¬Parents(b,Z ) ∨ ¬Ancestor(Z ,U)







¬Father(a, b) ∨ ¬Parents(b,Z ) ∨ ¬Ancestor(Z ,U)(Parents(X ,Y ) ∨ ¬Father(X ,Y )

¬Father(a, b) ∨ ¬Father(b,Z ) ∨ ¬Ancestor(Z ,U)

σ = {b/X ,U/Y }

Resolvent : ¬Father(a, b) ∨ ¬Father(b,Z ) ∨ ¬Ancestor(Z ,U)







¬Father(a, b) ∨ ¬Father(b,Z ) ∨ ¬Ancestor(Z ,U)Father(b, c)

¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Ancestor(c ,U)

σ = {c/Z}

Resolvent : ¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Ancestor(c ,U)







¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Ancestor(c ,U)Ancestor(X ,Y ) ∨ ¬Parents(X ,Z ) ∨ ¬Ancestor(Z ,Y )

¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Parents(c ,Z ) ∨ ¬Ancestor(Z ,U)

σ = {c/X ,U/Y }

Resolvent : ¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Parents(c ,Z ) ∨¬Ancestor(Z ,U)




¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Parents(c ,Z ) ∨ ¬Ancestor(Z ,U)Parents(X ,Z ′) ∨ ¬Father(Z ′,Y )

¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Father(c ,U) ∨ ¬Ancestor(Z ′,U ′)

σ = {c/X ,Z/Z ′}

Resolvent : ¬Father(a, b) ∨ ¬Father(b, c) ∨ ¬Father(c ,U ′) ∨¬Ancestor(Z ′,U ′)


Science

Du Calcul des prédicats vers Prolog