An introduction to logic
Gabriele Puppis
¬ ∀∃
First and foremost: interrupt!
Logic as a formal language
What is “a logic”?
A formal language to express and reason about properties of objects (numbers, graphs, computations, etc)
! a crucial tool for verifying, validating, synthesising safety-critical systems
What is “a logic”?
A formal language to express and reason about properties of objects (numbers, graphs, computations, etc)
! a crucial tool for verifying, validating, synthesising safety-critical systems
Two (in)famous examples where logical formal methods would have saved $$$:
• Pentium I floating point division bug (loss @Intel > $475,000,000)
• Ariane 501 overflow bug: (loss @ESA > $500,000,000)
What is “a logic”?
What is “a logic”?
As a formal language, a logic requires:
• a vocabulary: list of symbols we can use to denote objects and properties
• a syntax: grammar for combining symbols into well-formed terms (formulas)
• a semantics: way of assigning a meaning to symbols and terms
• some algorithms: ways of reasoning automatically about the semantics (e.g. checking whether a given formula is valid)
Syntax and semantics
Q. “Are you two married?”
A. “Depends…”
Syntax and semantics
Q. “Are you two married?”
A. “Depends…”
Two possible relations:
• unary relation R1(x) = “x is married with someone”
• binary relation R2(x,y) = “x and y are married together”
Syntax and semantics
Q. “Are you two married?”
A. “Depends…”
Note: R2(x,y) → R1(x) & R1(y) but not the converse!
Two possible relations:
• unary relation R1(x) = “x is married with someone”
• binary relation R2(x,y) = “x and y are married together”
Syntax and semantics
“All humans are mortal.
Socrates is human.
So Socrates is mortal.”
( (∀x A(x) → B(x)) ∧ A(y) ) → B(y)
Syntax and semantics
“All humans are mortal.
Socrates is human.
So Socrates is mortal.”
The above formula is valid (i.e. true in every model). We call it a tautology ( (∀x A(x) → B(x)) ∧ A(y) ) → B(y)
Syntax and semantics
“All humans are mortal.
Socrates is human.
So Socrates is mortal.”
The above formula is valid (i.e. true in every model). We call it a tautology
“All beatles have 6 legs.
John Lennon is a beatle.
So John Lennon has 6 legs.
( (∀x A(x) → B(x)) ∧ A(y) ) → B(y)
Syntax and semantics
“There is a barber who shaves all and only
those men who do not shave themselves.”
∃x ∀y C(x,y) ¬C(y,y)
Syntax and semantics
The formula is not satisfiable (i.e. false in every model). We call it a contradiction
“There is a barber who shaves all and only
those men who do not shave themselves.”
∃x ∀y C(x,y) ¬C(y,y)
Syntax and semantics
“There exists a set that contains all and only the sets that do not contain themselves.”
The formula is not satisfiable (i.e. false in every model). We call it a contradiction
“There is a barber who shaves all and only
those men who do not shave themselves.”
∃x ∀y C(x,y) ¬C(y,y)
Syntax and semantics
“Every incoming order is eventually processed.”
∀o ∀t A(o,t) → ∃t’ t<t’ ∧ B(o,t’)
Syntax and semantics
“Every incoming order is eventually processed.”
The formula has variables of different sorts (representing objects of different types)
∀o ∀t A(o,t) → ∃t’ t<t’ ∧ B(o,t’)
Syntax and semantics
“If a non-deterministic program
can reach infinitely many configurations, it has an infinite execution.”
Syntax and semantics
“If a finitely branching tree has infinitely many nodes, it contains an infinite path.”
“If a non-deterministic program
can reach infinitely many configurations, it has an infinite execution.”
Syntax and semantics
“If a finitely branching tree has infinitely many nodes, it contains an infinite path.”
“If a non-deterministic program
can reach infinitely many configurations, it has an infinite execution.”
∀x ∀y ∀z A(y,x) ∧ A(z,x) → y=z ∨ A(y,z) ∨ A(z,y) // structure is a tree
∧ ∀x ¬∃∞ y A(x,y) ∧ ∀z A(x,z) → y=z ∨ A(y,z) // is finitely branching
∧ ∃∞ x // is infinite
→ // so
∃S ∃∞ x x∈S // there is an infinite set
∧ ∀x ∀y x∈S ∧ y∈S → x=y ∨ A(x,y) ∨ A(y,x) // which is a path
Syntax and semantics
“If a finitely branching tree has infinitely many nodes, it contains an infinite path.”
The formula uses one relational symbol A (for the “ancestor-of ” relation) and different types of quantifiers (∀x, ∃x, ∃∞x, ∃S)
“If a non-deterministic program
can reach infinitely many configurations, it has an infinite execution.”
∀x ∀y ∀z A(y,x) ∧ A(z,x) → y=z ∨ A(y,z) ∨ A(z,y) // structure is a tree
∧ ∀x ¬∃∞ y A(x,y) ∧ ∀z A(x,z) → y=z ∨ A(y,z) // is finitely branching
∧ ∃∞ x // is infinite
→ // so
∃S ∃∞ x x∈S // there is an infinite set
∧ ∀x ∀y x∈S ∧ y∈S → x=y ∨ A(x,y) ∨ A(y,x) // which is a path
Algorithms
How hard is it to mechanise? ⤳ complexity classes Evaluation of a formula
Validity / satisfiability Logical equivalence Logical consequence
Definability in a logical fragment
…
What can be mechanized? ⤳ decidable/undecidable
Algorithms
How hard is it to mechanise? ⤳ complexity classes
usage of resources: • time
• memory
PCP K H’s 10th
Domino
. . . Evaluation of a formula
Validity / satisfiability Logical equivalence Logical consequence
Definability in a logical fragment
…
What can be mechanized? ⤳ decidable/undecidable
Algorithms
Alg f
time
input size
How hard is it to mechanise? ⤳ complexity classes
What can be mechanized? ⤳ decidable/undecidable
usage of resources: • time
• memory
PCP K H’s 10th
Domino
. . .
Algorithms
Alg f
time
input size
Algorithm Alg is TIME-bounded by a function f : ℕ ⟶ ℕ if
Alg(input) uses less than f (|input|) units of TIME.
How hard is it to mechanise? ⤳ complexity classes
What can be mechanized? ⤳ decidable/undecidable
usage of resources: • time
• memory
PCP K H’s 10th
Domino
. . .
Algorithms
Alg f
time
input size
Algorithm Alg is TIME-bounded by a function f : ℕ ⟶ ℕ if
Alg(input) uses less than f (|input|) units of TIME.SPACE.
SPACE
How hard is it to mechanise? ⤳ complexity classes
What can be mechanized? ⤳ decidable/undecidable
usage of resources: • time
• memory
PCP K H’s 10th
Domino
. . .
Algorithms
P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ · · ·
Alg f
time
input size
Algorithm Alg is TIME-bounded by a function f : ℕ ⟶ ℕ if
Alg(input) uses less than f (|input|) units of TIME.
Deterministic and TIME-bounded by a polynomial
SPACE-bounded by a polynomial
Non-deterministic and TIME-bounded by a polynomial SPACE.
SPACE
How hard is it to mechanise? ⤳ complexity classes
What can be mechanized? ⤳ decidable/undecidable
usage of resources: • time
• memory
PCP K H’s 10th
Domino
. . .
Algorithms
φ
M
yes/no
Model-checking problem
input: formula φ + model M
output: yes iff φ holds on M (M ⊨ φ)
Algorithms
φ
M
yes/no
Variant: sometimes M is fixed (e.g. when M is infinite), and the only input is φ Model-checking problem
input: formula φ + model M
output: yes iff φ holds on M (M ⊨ φ)
Algorithms
φ
yes/no M
Validity problem input: formula φ
output: yes iff φ holds on every model M
Algorithms
φ
yes/no M
Variant: sometimes M is restricted to range over specific class (e.g. finite models) Validity problem
input: formula φ
output: yes iff φ holds on every model M
Algorithms
φ
yes/no
Validity problem
input: formula φ
output: yes iff φ holds on every model M B or not B?
Yes, Dave, that’s valid
Algorithms
φ
yes/no
Variant: sometimes M is restricted to range over specific class (e.g. finite models) Satisfiability problem
input: formula φ
output: yes iff φ holds on some model M B and not B?
No, Dave,
that’s not possible
Algorithms …but not only
expressiveness decidability
succinctness efficiency
When studying logics, algorithms are not the only interesting part:
• Expressive power
Which kinds of properties can be expressed in a given logic?
Is this logic more/less expressive than this other logic?
Does it express undecidable properties?
• Succinctness
How complex it is to express a family of properties?
Which logic is more succinct?
Which logic has more efficient algorithms?
• Normal forms, algebraic representations, …
