COMP2022|2922 Models of Computation
Lesson 3: Predicate Logic Presented by
Sasha Rubin
School of Computer Science
The world has many objects, some of which are related to each other. These can be modeled by predicate logic.
1/42
In predicate logic we will be able to represent formulas like the following:1
∀x∀y (x + y = y + x)
This is not a proposition since whether or not it is true depends on missing information: the type of the variables x, y and the meaning of the symbol +.
– If x and y are integer variables and + means ordinary addition, then the formula is true.
– If x and y are string variables and + means concatenation, then the formula is false.
“hello” + “world” != “world” + “hello”
1The symbol ∀ is read “for all”.
2/42
So, in order to give meaning to formulas of predicate logic, we first have to fix the possible values that variables can take, as well as the interpretation of symbols like +.
Structure = Domain + Functions + Predicates + Constants
3/42
Background: domains
When we reason about objects, we have in mind a certain domain of discourse.
1. In programming, the domain may be the integers, or strings, or both, etc.
2. In the world, the domain includes people, animals, etc.
For us, a domain is simply a non-empty set D.
– The set Z of integers is a domain.
– The set S of binary strings is a domain. – The set H of humans is a domain.
In predicate logic, variables x, y, z, . . . vary over elements of the domain.
4/42
Background: functions
Mappings from several objects in a domain to a single object of the domain are called functions.
1. Here are some functions in the domain Z: add, double.
2. Here are some functions in the domain S: concat, reverse. 3. Here is a functions in the domain H: mother_of
So mother_of(x) is the mother of x.
The number of arguments of a function is called its arity.
By the way, it is traditional in logic to use notation like f(x,y) or even add(x, y) instead of infix notation like x + y.
5/42
Background: predicates
Properties of objects in a domain, as well as relations between objects in a domain, are called predicates (sometimes also called relations).
1. Here are some predicates in the domain Z: is_even, is_odd, is_bigger_than.
2. Here is a predicate in the domain S: is_longer_than. 3. Here is a predicate in the domain of H: loves
loves(x,y) says that x loves y.
6/42
Background: arity
– Predicates (like functions) take some number of arguments, and so we write is_even(x) and is_bigger_than(x,y).
– The number of arguments is called the arity of the predicate.
– is_even takes one argument, so it is called a unary predicate.
– is_bigger_than takes two arguments, so it is called a binary predicate.
7/42
Background: constants
Single elements of the domain are called constants.2
1. Here are some constants in the domain Z: 0, 1, 2, 3 and −3. 2. Here are some constants in the domain S: 0, 1, 10 and 11. 3. Here are some constants in the domain H: Sasha and Paul.
2They may also be seen as functions of arity zero, i.e., functions that take no arguments and always return the same element.
8/42
Background: structures
Definition
A structure A consists of a domain D, functions on D, predicates on D, and constants from D.
Examples
– Z = (Z,add,eq,0,1) where Z is the set of integers, add is integer addition (a binary function) , eq is equality of integers (a binary predicate), and 0, 1 are constants.
– S = (S, add, eq, 0, 1) where S is the set of binary strings, add is string concatenation (a binary function), eq is equality of strings (a binary predicate), and 0, 1 are constants.
– H = (H, loves, mother_of) where loves is a binary predicate and mother_of is a unary function.
9/42
Background: structures
Important notation
– We have conflicting notation: e.g., which function is add? Integer addition or string concatenation?
– To distinguish these, we may superscript with the name of the structure: so addZ is the integer-addition function, and addS is the string-concatenation function.
– So, if we want to be precise, we should write the structures before as:
and
Z = (Z,addZ,eqZ,0Z,1Z) S = (S,addS,eqS,0S,1S)
10/42
Background: structures
Important notation
– Soifaddisnotafunction,whatisit,andhowdoweuseit?
– It is just a name, it is just a symbol.
– Just as different people may have the same name, so too different functions (addZ and addS) can have the same name (add).
– Why do we need the names at all? We can use names in formulas of predicate logic to talk about multiple structures!
– Consider the formula ∀x∀y eq(add(x, y), add(y, x)) that says that addition is commutative.
– This formula makes sense about integers and about strings!
– It happens to be true about the integers but false about
strings.
11/42
Plan
What makes up a logic?
1. Syntax tells us the structure of expressions, or the rules for putting symbols together to form an expression.
2. Semantics refers to the meaning of expressions, or how they are evaluated.
3. Deduction is a syntactic mechanism for deriving new true expressions from existing true expressions.
12/42
Syntax + Semantics: In a nutshell
The Predicate-Logic Formulas for a structure A are built from:
1. symbols for the functions, predicates and constants of A;
called the vocabulary of A,
2. the usual connectives ¬, ∧, ∨,
3. variables x,y,z,…, and
4. the quantifier symbols ∀ (read “for all”) and ∃ (read “exists”).
13/42
Syntax + Semantics: In a nutshell
What is the vocabulary of the following structures?
1. The vocabulary of Z = (Z,addZ,eqZ,0Z,1Z) consists of
add, eq, 0, 1
2. The vocabulary of S = (S,addS,eqS,0S,1S) consists of
add, eq, 0, 1
3. The vocabulary of H = (H, lovesH, mother_ofH) consists of loves, mother_of.
14/42
Syntax + Semantics: In a nutshell
– Variables x, y, z, . . . vary over elements in the domain D.
– Quantifier symbols ∀, ∃ allow one to talk about their quantity. – Universal quantifier: ∀ “for every”, “for all”
– Existential quantifier: ∃ “there exists”, “some”
15/42
Syntax + Semantics: In a nutshell
Example
Here are some formulas and their meaning in the structure H = (H, lovesH, mother_ofH).
∀x loves(x, x)
∀x loves(x, mother_of(x))
∀x loves( mother_of(x), x)
∀x∀y loves(x, y)
∃x∀y loves(x, y)
∀x∃y loves(x, y)
∃x∃y loves(x, y)
Every human loves themself
Everyone loves their mother Everyone’s mother loves them Everyone loves everyone Someone loves everyone Everyone loves someone Someone loves someone
∀x∃y loves(y, mother_of(x))
Everyone’s mother is loved by someone
16/42
Syntax tells us the structure of expressions, or the rules for putting symbols together to form an expression.
17/42
Syntax of Predicate Logic = Symbols + Terms + Formulas
18/42
Syntax: symbols
Suppose structure A has functions fA, gA, hA, . . . , predicates PA,QA,RA,…, and constants aA,bA,cA,….
Then predicate logic formulas for A are built from the following symbols:
1. The vocabulary of A, i.e.,
1.1 Functionsymbolsf,g,h,…
1.2 PredicatesymbolsP,Q,R,… 1.3 Constantssymbolsa,b,c,…
2. Connectives ¬, ∧, ∨ (as in Propositional Logic) 3. Variables u,v,w,x,y,z,…
4. Quantifier symbols ∀, ∃
As we have seen, we may use more suggestive symbols like add (instead of f) and eq (instead of P).
19/42
Syntax: terms
A term refers to an object without naming it
– f(2)
– father(Alan)
– round_up(2.5)
Terms may have variables
– f(x)
– father(x)
– round_up(x)
Terms may be composed
– f(g(x,y))
– father(father(Alan)) – half(round_up(x))
Alan’s father The smallest integer ≥ 2.5
x’s father The smallest integer ≥ x
Alan’s father’s father Half of the smallest integer ≥ x
20/42
Syntax: terms
Here is a precise definition.
Definition
Terms are defined by the following recursive process:
1. Every variable is a term.
2. Every constant symbol is a term.
3. If f is a k-ary function symbol, and if t1,··· ,tk are terms, then f(t1,··· ,tk) is a term.
Examples
– So, if f is unary, g is binary, and c is a constant, then the following are terms: x, c, f(x), g(c,f(y)), f(f(y)),
g(f (x), g(x, y)).
– In the language of Z, the following are terms: add(x,1), add(x, add(x, y)), add(0, add(1, add(1, x)).
21/42
Syntax: formulas
We can finally give the syntax of predicate logic.
Definition
– An atomic formula (of predicate logic) has the form P(t1,…,tk) where P is a k-ary predicate symbol and t1,…,tk are terms.
– A formula (of predicate logic) is defined by the following recursive process:
1. Every atomic formula is a formula.
2. If F is a formula then ¬F is a formula.
3. If F, G are formulas then (F ∧ G) and (F ∨ G) are formulas.
4. If x is a variable and F is a formula then ∃xF and ∀xF are
formulas.
As for propositional logic, we use the same shorthands, i.e., (F →G),(F ↔G),(i Fi),(i Fi),⊤,⊥.
If F is a formula and F occurs as part of the formula G then F is called a subformula of G.
22/42
Syntax: formulas
Example
If f is binary, P is binary, then the following are formulas: – P(f(x,y),f(y,x))
– ∀xP(f(x,y),f(y,x))
– ∀x∀y(P(f(x,y),f(y,x))∨¬P(x,x))
23/42
Syntax: free and bound occurrences of variables
– An occurrence of the variable x in the formula F is bound if x occurs within a subformula of F of the form ∃xG or ∀xG. Otherwise it is a free occurrence.
– Programming analogy: bound/local, free/global
– A variable may have both free and bound occurrences in a formula F.
– Let Free(F) be the set of all variables that occur free in F.
– A formula without free variables (i.e., Free(F ) = ∅) is called a
sentence. Example
∀x(P(x,y)→∃yQ(x,y,z))
24/42
Semantics refers to the meaning of expressions, or how they are evaluated
25/42
Semantics of Predicate Logic = Structures + Assignments + Values of Terms + Truth-values of Formulas
26/42
Semantics: assignments
Definition
Let A be a structure with domain D. An assignment is a function α that maps variables x, y, z, . . . to elements of the domain D.
– So an assignment α gives every variable a value in the domain.
– This means that α can also be seen to give every term a value in the domain.
27/42
Semantics: values of terms
Example
Recall the structure Z = (Z, addZ , eqZ , 0Z , 1Z ).
– Suppose assignment α maps x to 1 and y to 2, i.e.,
α(x) = 1, α(y) = 2.
– Then α gives the term add(x, y) the integer value 3.
– And α gives the term add(x, add(x, y)) the integer value 4.
28/42
Semantics: values of terms
Definition
The value of the term t under assignment α in the structure A is defined by the following recursive process:
1. If t is a variable, say x, then its value is just α(x).
2. If t is a constant symbol, say c, then its value is cA.
3. If t is a term of the form f(t1,··· ,tk) and t1,··· ,tk are terms with values d1,··· ,dk, then its value is fA(d1,··· ,dk).
29/42
Semantics: values of terms
We can write this more concisely:
Definition
The value of the term t under assignment α in the structure A, denoted val(t, α, A), is defined by the following recursive process:
1. val(x,α,A)=α(x).
2. val(c,α,A)=cA.
3. val(f(t1,···,tk),α,A)= fA(val(t1,α,A),··· ,val(tk,α,A)).
Notation
– If the structure A is clear from context, write val(t, α).
– If also the assignment α is clear from context, write val(t).
30/42
Semantics: values of terms
Example
Recall the structure Z = (Z, addZ , eqZ , 0Z , 1Z ).
– Suppose assignment α maps x to 1 and y to 2. – What is the value of the term add(x, add(x, y))?
val(add(x, add(x, y))) = addZ (val(x), val(add(x, y))) 3. = addZ (val(x), addZ (val(x), val(y))) 3. = addZ (α(x), addZ (α(x), α(y))) 1.
= addZ (1, addZ (1, 2)) = 1 + (1 + 2) = 4
31/42
Semantics: truth-values of atomic-formulas
We can now assign truth values to atomic formulas P(t1,··· ,tk). Example
Recall the structure Z = (Z, addZ , eqZ , 0Z , 1Z ). Suppose α(x) = 2, α(y) = 3.
– What is the truth value of the following atomic formula?
eq(add(y, x), add(x, y)) – To answer this, we must ask if
(val(add(y, x)), val(add(x, y))) ∈ eqZ
– Butthisisjustaskingif3+2=2+3,whichistrue,sothe truth value is 1.
32/42
Semantics: truth-values of formulas
Definition
The truth value of a formula F under the assignment α in the structure A, denoted TV(F, α, A) or just TV(F, α), is defined by the following recursive process:
1. For an atomic formula P(t1,…,tk),
1 if (val(t1,α),··· ,val(tk,α)) ∈ PA TV(P(t1,…,tk),α) = 0 otherwise.
33/42
Semantics: truth-values of formulas
Definition
The truth value of a formula F under the assignment α in the structure A, denoted TV(F, α, A) or just TV(F, α), is defined by the following recursive process:
2. TV(¬F,α) = 3. TV((F ∧ G), α) = 4. TV((F ∨ G), α) =
1
0 otherwise
0 1
if TV(F,α) = 1 if TV(F,α) = 0
if TV(F,α) = 1 and TV(G,α) = 1
1 if TV(F,α) = 1 or TV(G,α) = 1 0 otherwise
33/42
Semantics: truth-values of formulas
Definition
The truth value of a formula F under the assignment α in the structure A, denoted TV(F, α, A) or just TV(F, α), is defined by the following recursive process:
5. Define TV(∀xG, α) = 1 if for every element d in the domain of A, TV(G, α[x → d]) = 1, and 0 otherwise.
6. Define TV(∃xG, α) = 1 if there is an element d in the domain of A such that TV(G, α[x → d]) = 1, and 0 otherwise.
α[x → d] is the assignment which is identical to α except that it maps the variable x to d. This can be expressed by the equation:
α(y) if y ̸= x d if y = x
α[x → d](y) =
33/42
Semantics: truth-values of formulas
We can write the definition more succinctly:
Definition
The truth value of a formula F under the assignment α in the structure A, denoted TV(F, α, A) or just TV(F, α), is defined by the following recursive process:
1. TV(P(t1,··· ,tk),α) = 1 if (val(t1,α),··· ,val(tk,α)) ∈ PA, and 0 otherwise.
2. TV(¬F,α)=1−TV(F,α)
3. TV((F ∧ G), α) = min{TV(F, α), TV(G, α)}
4. TV((F ∨ G), α) = max{TV(F, α), TV(G, α)}
5. TV(∀xG, α) = min{TV(G, α[x → d]) : d ∈ D}
6. TV(∃xG, α) = max{TV(G, α[x → d]) : d ∈ D}
34/42
Semantics
Example
Recall the structure Z = (Z,addZ,eqZ,0Z,1Z). Let α be any assignment. Compute TV(∃xG, α) where G is the formula eq(x, add(x, x)).
You can think of this as a loop.
35/42
Semantics
Example
Recall the structure Z = (Z,addZ,eqZ,0Z,1Z). Let α be any assignment. Compute TV(∃xG, α) where G is the formula eq(x, add(x, x)).
– Bytherulefor∃,TV(∃xG,α)=1iffthereissomed∈Z: TV(G, α[x → d]) = 1
– By the rule for predicates, this means that
(val(x, α[x → d]), val(add(x, x), α[x → d])) ∈ eqZ
– By evaluating the terms, this means that (d, d + d) ∈ eqZ . – By evaluating the predicate, this means that d = d + d.
– Is there such an integer d? Yes, d = 0.
– So TV(∃xG,α) = 1.
35/42
Semantics
Example
Recall the structure Z = (Z,addZ,eqZ,0Z,1Z). Let α be any assignment. Compute TV(∀x∀yG, α) where G is the formula eq(add(x, y), add(y, x)).
– By the rule for ∀ (applied twice), TV(∀x∀yG, α) = 1 iff for all d,e ∈ Z: TV(G,α[x,y → d,e]) = 1.
– By the rule for predicates, this means that
(val(add(x, y), α[x, y → d, e]), val(add(y, x), α[x, y → d, e])) ∈ eqZ
– By evaluating the terms, this means that (d + e, e + d) ∈ eqZ .
– By evaluating the predicate, this means that d + e = e + d.
– Is this true for all integers d, e? Yes.
– So TV(∀x∀yG, α) = 1.
36/42
Semantics
– Intuitively, the truth value of a formula F does not depend on α(z) if the variable z does not occur in F.
– More is true:
Fact. The truth value TV(F, α) only depends on α(z) if
z ∈ Free(F).
– In the previous examples the formula F had no free variables. So the truth value of F does not depend at all on the α we start with.
– Of course, as we evaluated the formula, we updated the assignment and the formula, and so some variables became free and the current assignment did matter.
37/42
Semantics: sentences
– A formula without free occurrences of variables (i.e., Free(F ) = ∅) is called a sentence.
– Fact. The truth value of a sentence does not depend on the variable assignment.
– So, for a sentence F and a structure A, if the truth-value is 1 under some assignment, then it is 1 under every assignment.
– InthiscasewesaythatF istrueinA.
38/42
Semantics
So in the previous examples, we have that the following formulas are true in the integer structure Z = (Z, addZ , eqZ , 0Z , 1Z ):
– the formula ∃x eq(x, add(x, x)), which in ordinary notation is written ∃x (x = x + x);
– the formula ∀x∀y eq(add(x, y), add(y, x)) which in ordinary notation is written ∀x∀y (x + y = y + x).
39/42
Semantics: satisfiable sentences
A sentence F is satisfiable if it is true in some structure A. Example
– The formula ∀x∀y eq(add(x, y), add(y, x)) is satisfiable (since it is true in the structure Z).
– The formula ∃x(eq(x, x) ∧ ¬eq(x, x)) is not satisfiable.
40/42
For you to think about
We saw that we can use truth-tables to decide if a given propositional logic formula is satisfiable. Is there an algorithm that decides if a given predicate logic formula is satisfiable?
41/42
Reference
– Chapter 2 of Schöning covers Predicate Logic
– NB. We use the same syntax, but slightly different notation for semantics.
42/42