Predicate Logic

Date: March 9, 2016
Course: UiS DAT911 - Foundations of Computer Science (fall 2016)

Please cite, link to or credit this presentation when using it or part of it in your work.

1. Predicate Logic
DAT911 - Foundations of Computer Science
Dario Garigliotti
March 9, 2016
Dario GarigliottiPredicate Logic

2. Predicate Logic
In Propositional Logic (P.L.) we could have:
r=It is snowing in Stavanger
s=It is snowing in Oslo
t=It is snowing in Trondheim
Apredicateis a generalization of a propositional variable:
r(X) =It is snowing in X
Atomic formula:a predicate with 0+ arguments (variables or
constants)
"variables" vs "propositional variables"
0 args:m=It is Wednesday
Ground atomic formula:all arguments are constants
r(Stavanger) =It is snowing in Stavanger
Dario GarigliottiPredicate Logic

3. Predicate Logic
In Propositional Logic (P.L.) we could have:
r=It is snowing in Stavanger
s=It is snowing in Oslo
t=It is snowing in Trondheim
Apredicateis a generalization of a propositional variable:
r(X) =It is snowing in X
Atomic formula:a predicate with 0+ arguments (variables or
constants)
"variables" vs "propositional variables"
0 args:m=It is Wednesday
Ground atomic formula:all arguments are constants
r(Stavanger) =It is snowing in Stavanger
Dario GarigliottiPredicate Logic

4. Predicate Logic
In Propositional Logic (P.L.) we could have:
r=It is snowing in Stavanger
s=It is snowing in Oslo
t=It is snowing in Trondheim
Apredicateis a generalization of a propositional variable:
r(X) =It is snowing in X
Atomic formula:a predicate with 0+ arguments (variables or
constants)
"variables" vs "propositional variables"
0 args:m=It is Wednesday
Ground atomic formula:all arguments are constants
r(Stavanger) =It is snowing in Stavanger
Dario GarigliottiPredicate Logic

5. Predicates and Logical Expressions
Apredicateis a generalization of a propositional variable:
r(X) =It is snowing in X
Atomic formula:a predicate with 0+ arguments (variables or
constants)
Logical expressions
Literals:an atomic formula or its negation
p(X;a);:p(a;b)
Expressions:by using
logical operators:;_;^;=);
quantiers8;9
Dario GarigliottiPredicate Logic

6. Predicates and Logical Expressions
Apredicateis a generalization of a propositional variable:
r(X) =It is snowing in X
Atomic formula:a predicate with 0+ arguments (variables or
constants)
Logical expressions
Literals:an atomic formula or its negation
p(X;a);:p(a;b)
Expressions:by using
logical operators:;_;^;=);
quantiers8;9
Dario GarigliottiPredicate Logic

7. Quantiers
For our predicate
r(X) =It is snowing in X
if we want to express:It is snowing inat leastone city
r(Berlin)_r(London)_r(Paris)_r(Rome)_:::
we do it by
theexistential quantier:(9X)r(X)
In the case of expressingFor all the cities..., we use
the universal quantier:(8X)r(X)
Dario GarigliottiPredicate Logic

8. Quantiers
Recursive denition of logical expressions
Basis:every atomic formula is an expression
Induction:E;Flogical expressions, then so are
:E;E^F;E_F;E=)F;EF
(8X)E;(9X)E, for any variableX
A little more about quantiers
Precedenceof operators:8;9have highest precedence, then
as in P.L.::;^;_;=);
Importance oforder: (8X)(9Y) vs (9X)(8Y)
Bound and free variables
Dario GarigliottiPredicate Logic

9. Quantiers
Recursive denition of logical expressions
Basis:every atomic formula is an expression
Induction:E;Flogical expressions, then so are
:E;E^F;E_F;E=)F;EF
(8X)E;(9X)E, for any variableX
A little more about quantiers
Precedenceof operators:8;9have highest precedence, then
as in P.L.::;^;_;=);
Importance oforder: (8X)(9Y) vs (9X)(8Y)
Bound and free variables
Dario GarigliottiPredicate Logic

10. Quantiers: Bound and Free Variables
A quantier "declares" a variable within a "scope"
E.g. (8X)r(X)_(8X)s(X)
Let's think on its expression tree
_ (8X) r(X)
n
n (8X) s(X)
An occurrence of a variableXin an expressionEisboundby a
quantier (QX) if in its expression tree, (QX) is the lowest
ancestor involvingX
Otherwise, that occurrence isfree
Dario GarigliottiPredicate Logic

11. Quantiers: Bound and Free Occurrences of Variables
An occurrence of a variableXin an expressionEisboundby a
quantier (QX) if in its expression tree, (QX) is the lowest
ancestor involvingX
Otherwise, that occurrence isfree
Another example:r(X)_(9X)s(X)
_ r(X)
n
n (9X) s(X)
Then we mean: bound and freeoccurrencesof variables
Dario GarigliottiPredicate Logic

12. Interpretations
An example:Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
AninterpretationforEis dened by:
aninterpretationIfor the predicate based on the assignment
of values inDto its arguments, e.g.I1:p(U;V)U<V
adomainDfrom which to select values for the variables, e.g.
D=R
avalueinDfor each free occurrences of variables givenI1withD, we can dene innite interpretations such
thatEis true
what if we useI2by deningD=Z? Ealways true except for those in whichY=X+ 1
Dario GarigliottiPredicate Logic

13. Interpretations
An example:Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
AninterpretationforEis dened by:
aninterpretationIfor the predicate based on the assignment
of values inDto its arguments, e.g.I1:p(U;V)U<V
adomainDfrom which to select values for the variables, e.g.
D=R
avalueinDfor each free occurrences of variables givenI1withD, we can dene innite interpretations such
thatEis true
what if we useI2by deningD=Z? Ealways true except for those in whichY=X+ 1
Dario GarigliottiPredicate Logic

14. Interpretations
An example:Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
AninterpretationforEis dened by:
aninterpretationIfor the predicate based on the assignment
of values inDto its arguments, e.g.I1:p(U;V)U<V
adomainDfrom which to select values for the variables, e.g.
D=R
avalueinDfor each free occurrences of variables givenI1withD, we can dene innite interpretations such
thatEis true
what if we useI2by deningD=Z? Ealways true except for those in whichY=X+ 1
Dario GarigliottiPredicate Logic

15. Interpretations
An example:Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
AninterpretationforEis dened by:
aninterpretationIfor the predicate based on the assignment
of values inDto its arguments, e.g.I1:p(U;V)U<V
adomainDfrom which to select values for the variables, e.g.
D=R
avalueinDfor each free occurrences of variables givenI1withD, we can dene innite interpretations such
thatEis true
what if we useI2by deningD=Z? Ealways true except for those in whichY=X+ 1
Dario GarigliottiPredicate Logic

16. Interpretations
An example:Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
AninterpretationforEis dened by:
aninterpretationIfor the predicate based on the assignment
of values inDto its arguments, e.g.I1:p(U;V)U<V
adomainDfrom which to select values for the variables, e.g.
D=R
avalueinDfor each free occurrences of variables givenI1withD, we can dene innite interpretations such
thatEis true
what if we useI2by deningD=Z? Ealways true except for those in whichY=X+ 1
Dario GarigliottiPredicate Logic

17. Interpretations
An example:Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
AninterpretationforEis dened by:
aninterpretationIfor the predicate based on the assignment
of values inDto its arguments, e.g.I1:p(U;V)U<V
adomainDfrom which to select values for the variables, e.g.
D=R
avalueinDfor each free occurrences of variables givenI1withD, we can dene innite interpretations such
thatEis true
what if we useI2by deningD=Z? Ealways true except for those in whichY=X+ 1
Dario GarigliottiPredicate Logic

18. Interpretations
An example:Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
AninterpretationforEis dened by:
aninterpretationIfor the predicate based on the assignment
of values inDto its arguments, e.g.I1:p(U;V)U<V
adomainDfrom which to select values for the variables, e.g.
D=R
avalueinDfor each free occurrences of variables givenI1withD, we can dene innite interpretations such
thatEis true
what if we useI2by deningD=Z? Ealways true except for those in whichY=X+ 1
Dario GarigliottiPredicate Logic

19. Interpretations
We can give a denition of the interpretation of an expressionE,
by induction in its expression tree
Ep(X1; :::;Xn)
EE1^E2
EE1_E2
E :E1
E(9X)E1
E(8X)E1
Dario GarigliottiPredicate Logic

20. Tautologies - Substitutions and Equivalences
Eis atautologyif its value is true for every interpretation ofE
The previous example is not:
Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
E.g. of a tautology:q(X)_ :q(X)
Thesubstitution principleallows to obtain tautologies in
predicate logic from propositional tautologies
E.g. the latter, after replacing inp_ :p
We can say thatEandFareequivalentifEFis a tautology
Then, by substitution, ifE1E2, and we replace inF1one by
another, we obtain an expressionF2such thatF1F2
Dario GarigliottiPredicate Logic

21. Tautologies - Substitutions and Equivalences
Eis atautologyif its value is true for every interpretation ofE
The previous example is not:
Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
E.g. of a tautology:q(X)_ :q(X)
Thesubstitution principleallows to obtain tautologies in
predicate logic from propositional tautologies
E.g. the latter, after replacing inp_ :p
We can say thatEandFareequivalentifEFis a tautology
Then, by substitution, ifE1E2, and we replace inF1one by
another, we obtain an expressionF2such thatF1F2
Dario GarigliottiPredicate Logic

22. Tautologies - Substitutions and Equivalences
Eis atautologyif its value is true for every interpretation ofE
The previous example is not:
Ep(X;Y) =)(9Z)(p(X;Z)^p(Z;Y))
E.g. of a tautology:q(X)_ :q(X)
Thesubstitution principleallows to obtain tautologies in
predicate logic from propositional tautologies
E.g. the latter, after replacing inp_ :p
We can say thatEandFareequivalentifEFis a tautology
Then, by substitution, ifE1E2, and we replace inF1one by
another, we obtain an expressionF2such thatF1F2
Dario GarigliottiPredicate Logic

23. Tautologies Involving Quantiers
Let's describe two techniques for tautologies with quantiers
1
Rectifying expressions
Variable renaming: (QX)E(QX)E
0
, whereE
0
is obtained
fromEby replacing all occurrences of boundXfor a fresh
(not free inE)Y
Rectied expression by renaming it without repeating variables
2
Moving quantiers outside
:((8X)E)(9X)(:E)
:((9X)E)(8X)(:E)
(E^(QX)F)(QX)(E^F) (Xnot free inE)
(E_(QX)F)(QX)(E_F) (Xnot free inE)
Dario GarigliottiPredicate Logic

24. Tautologies Involving Quantiers
Let's describe two techniques for tautologies with quantiers
1
Rectifying expressions
Variable renaming: (QX)E(QX)E
0
, whereE
0
is obtained
fromEby replacing all occurrences of boundXfor a fresh
(not free inE)Y
Rectied expression by renaming it without repeating variables
2
Moving quantiers outside
:((8X)E)(9X)(:E)
:((9X)E)(8X)(:E)
(E^(QX)F)(QX)(E^F) (Xnot free inE)
(E_(QX)F)(QX)(E_F) (Xnot free inE)
Dario GarigliottiPredicate Logic

25. Tautologies Involving Quantiers
With those two steps, we can get an equivalentquantier-free
expression(or prenex-form expression) of the shape
(Q1X1)(Q2X2):::(QkXk)E
E.g. fromE(8X)p(X)_ :(8X)p(X)
Rectifying expression: (8X)p(X)_ :(8Y)p(Y) Moving Qs outside: (8X)p(X)_(9Y):p(Y) Moving Qs outside: (8X)(9Y)(p(X)_ :p(Y))
Dario GarigliottiPredicate Logic

26. Tautologies Involving Quantiers
With those two steps, we can get an equivalentquantier-free
expression(or prenex-form expression) of the shape
(Q1X1)(Q2X2):::(QkXk)E
E.g. fromE(8X)p(X)_ :(8X)p(X)
Rectifying expression: (8X)p(X)_ :(8Y)p(Y) Moving Qs outside: (8X)p(X)_(9Y):p(Y) Moving Qs outside: (8X)(9Y)(p(X)_ :p(Y))
Dario GarigliottiPredicate Logic

27. Tautologies Involving Quantiers
With those two steps, we can get an equivalentquantier-free
expression(or prenex-form expression) of the shape
(Q1X1)(Q2X2):::(QkXk)E
E.g. fromE(8X)p(X)_ :(8X)p(X)
Rectifying expression: (8X)p(X)_ :(8Y)p(Y) Moving Qs outside: (8X)p(X)_(9Y):p(Y) Moving Qs outside: (8X)(9Y)(p(X)_ :p(Y))
Dario GarigliottiPredicate Logic

28. Tautologies Involving Quantiers
With those two steps, we can get an equivalentquantier-free
expression(or prenex-form expression) of the shape
(Q1X1)(Q2X2):::(QkXk)E
E.g. fromE(8X)p(X)_ :(8X)p(X)
Rectifying expression: (8X)p(X)_ :(8Y)p(Y) Moving Qs outside: (8X)p(X)_(9Y):p(Y) Moving Qs outside: (8X)(9Y)(p(X)_ :p(Y))
Dario GarigliottiPredicate Logic

29. Proofs in Predicate Logic: Basics
Given some hypothesesE1;E2; :::;Ek, aproofis a sequence of
expressions such that each of them
either is one if theEi's
or follows from 0+ previous expressions by some rule of
inference
Arule of inferenceis of the shape (F1^F2^:::^Fn) =)F
Then, thelaw of variable substitution: givenEasserted,
E=)sub(E) is a tautology
E.g.p(X;Y) =)p(U;V)
E.g.p(X;Y) =)p(1;2)
Dario GarigliottiPredicate Logic

30. Proofs in Predicate Logic: From Rules and Facts
Two main kind of hypotheses:
Facts: ground atomic formulas, e.g.p(1)
Rules: "if-then" expressions, with abodyofsubgoalsand a
head, e.g.p(X)^q(Y) =)r(X)
Then, a proof can be build in this way, e.g.
1
p(X)^q(Y) =)r(X)
2
p(1)
3
q(3)
4
p(1)^q(3)
5
p(1)^q(3) =)r(1)
6
r(1)
Dario GarigliottiPredicate Logic

31. Proofs in Predicate Logic: From Rules and Facts
Two main kind of hypotheses:
Facts: ground atomic formulas, e.g.p(1)
Rules: "if-then" expressions, with abodyofsubgoalsand a
head, e.g.p(X)^q(Y) =)r(X)
Then, a proof can be build in this way, e.g.
1
p(X)^q(Y) =)r(X)
2
p(1)
3
q(3)
4
p(1)^q(3)
5
p(1)^q(3) =)r(1)
6
r(1)
Dario GarigliottiPredicate Logic

32. Proofs in Predicate Logic: From Rules and Facts
Two main kind of hypotheses:
Facts: ground atomic formulas, e.g.p(1)
Rules: "if-then" expressions, with abodyofsubgoalsand a
head, e.g.p(X)^q(Y) =)r(X)
Then, a proof can be build in this way, e.g.
1
p(X)^q(Y) =)r(X)
2
p(1)
3
q(3)
4
p(1)^q(3)
5
p(1)^q(3) =)r(1)
6
r(1)
Dario GarigliottiPredicate Logic

33. Proofs in Predicate Logic: From Rules and Facts
Two main kind of hypotheses:
Facts: ground atomic formulas, e.g.p(1)
Rules: "if-then" expressions, with abodyofsubgoalsand a
head, e.g.p(X)^q(Y) =)r(X)
Then, a proof can be build in this way, e.g.
1
p(X)^q(Y) =)r(X)
2
p(1)
3
q(3)
4
p(1)^q(3)
5
p(1)^q(3) =)r(1)
6
r(1)
Dario GarigliottiPredicate Logic

34. Proofs in Predicate Logic: From Rules and Facts
Two main kind of hypotheses:
Facts: ground atomic formulas, e.g.p(1)
Rules: "if-then" expressions, with abodyofsubgoalsand a
head, e.g.p(X)^q(Y) =)r(X)
Then, a proof can be build in this way, e.g.
1
p(X)^q(Y) =)r(X)
2
p(1)
3
q(3)
4
p(1)^q(3)
5
p(1)^q(3) =)r(1)
6
r(1)
Dario GarigliottiPredicate Logic

35. Provability and Truth
Idea ofmodel: an interpretation which makes an expression
true
Similarly, a model of a collection of expressionsfE1;E2; :::;Eng
Entailment or satisfaction:E1;E2; :::;Enj=Eif every model
for the collection is also a model forE
Provability:E1;E2; :::;En`E
Consistencyof a proof system: provability =)entailment
Completenessof a proof system: entailment =)provability
Dario GarigliottiPredicate Logic

36. Predicate Logic
Thanks!
Questions?
Dario GarigliottiPredicate Logic