COMP30026 Models of Computation – Predicate Logic: Semantics
COMP30026 Models of Computation
Predicate Logic: Semantics
Bach Le / Anna Kalenkova
Lecture Week 4 Part 1 (Zoom)
Semester 2, 2021
Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 1 / 20
This Lecture is Being Recorded
Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 2 / 20
Reading Materials
Remember, if you need textbook support, check out the resources
that are linked under “Subject Overview” (also accessible from
“Modules” → “Reading Resources”).
O’Donnell, Hall and Page discuss predicate logic in Chapter 7,
including translations from English. In Section 7.3 they make
use of a style of inference also known as “natural deduction”
(not covered by us, and not examinable).
A rather different introduction to predicate logic is in Makinson’s
Chapter 9.
The book by Jenkyns also looks good.
Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 3 / 20
The Meaning of a Predicate Logic Formula
Is this closed formula true or false?
∀x , z (x < z ⇒∃y (x < y ∧ y < z)) Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 4 / 20 The Meaning of a Predicate Logic Formula Is this closed formula true or false? ∀x , z (x < z ⇒∃y (x < y ∧ y < z)) That depends on what ‘<’ stands for, and the domain D of interest, that is, what sort of things x , y , and z denote. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 4 / 20 The Meaning of a Predicate Logic Formula Is this closed formula true or false? ∀x , z (x < z ⇒∃y (x < y ∧ y < z)) That depends on what ‘<’ stands for, and the domain D of interest, that is, what sort of things x , y , and z denote. 1 It is false if D = Z and < is the usual “smaller than”. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 4 / 20 The Meaning of a Predicate Logic Formula Is this closed formula true or false? ∀x , z (x < z ⇒∃y (x < y ∧ y < z)) That depends on what ‘<’ stands for, and the domain D of interest, that is, what sort of things x , y , and z denote. 1 It is false if D = Z and < is the usual “smaller than”. 2 It is true if D = Z and < is “smaller than or equal”. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 4 / 20 The Meaning of a Predicate Logic Formula Is this closed formula true or false? ∀x , z (x < z ⇒∃y (x < y ∧ y < z)) That depends on what ‘<’ stands for, and the domain D of interest, that is, what sort of things x , y , and z denote. 1 It is false if D = Z and < is the usual “smaller than”. 2 It is true if D = Z and < is “smaller than or equal”. 3 It is true if D = R and < is the usual “smaller than”. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 4 / 20 The Meaning of a Predicate Logic Formula Is this closed formula true or false? ∀x , z (x < z ⇒∃y (x < y ∧ y < z)) That depends on what ‘<’ stands for, and the domain D of interest, that is, what sort of things x , y , and z denote. 1 It is false if D = Z and < is the usual “smaller than”. 2 It is true if D = Z and < is “smaller than or equal”. 3 It is true if D = R and < is the usual “smaller than”. 4 It is true if D = {0}. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 4 / 20 The Meaning of a Formula In some cases, the meaning of a formula is independent of what its predicate (and function) names denote, and of what sort of things the variables range over. For example, ∀x P(x) ∨ ∃y (¬P(y )) is inherently true, no matter what (it is valid). Similarly, ∀x P(x) ∧ (¬P(a)) is false no matter what a and P stand for (the formula is unsatisfiable). Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 5 / 20 Interpretations (or Structures) An interpretation (or structure) consists of 1 A non-empty set D (the domain, or universe); 2 An assignment, to each n-ary predicate symbol P, of an n-place function p : Dn → {f, t}; 3 An assignment, to each n-ary function symbol g , of an n-place function g : Dn → D; 4 An assignment to each constant a of some fixed element of D. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 6 / 20 Free Variables and Valuations To give meaning to formulas that may have free variables, such as ∃x P(f (y ), x) we need two things: A valuation σ : var → D for free variables; An interpretation as just discussed. Connectives are always given their usual meaning. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 7 / 20 Terms and Valuations We just said that a valuation is a function σ : var → D. But, given an interpretation I, we get a valuation function from terms automatically, by natural extension: σ(a) = d σ(g(t1, . . . , tn)) = g(σ(t1), . . . , σ(tn)) where d is the element of D that I assigns to a, and g : Dn → D is the function that I assigns to g . Example: Consider term t = f (y , g(x , a)). Let our interpretation (with domain Z) assign to a the value 3, to f the multiplication function, and to g addition. If σ(x) = 9 and σ(y ) = 5 then σ(t) = 60. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 8 / 20 Truth of a Formula The truth of a closed formula should depend only on the given interpretation. The only reason why we are interested in formulas with free variables (and hence in valuations) is that we want to define the truth of a formula compositionally, as done on the next slide. Notation: σx 7→d(y ) = { d if y = x σ(y ) otherwise Read this as “the map σ, updated to map x to d .” Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 9 / 20 Making a Formula True Given an interpretation I (with domain D), and a valuation σ, σ makes P(t1, . . . , tn) true iff p(σ(t1), . . . , σ(tn)) = t, where p is the meaning that I gives P. σ makes ¬F true iff σ does not make F true. σ makes F1 ∧ F2 true iff σ makes both of F1 and F2 true. σ makes ∀x F true iff σx 7→d makes F true for every d ∈ D. If we now define ∃x F ≡ ¬∀x ¬F then the meaning of every other formula follows from this. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 10 / 20 Quantifier Order The order of different quantifiers is important. ∀x∃y is not the same as ∃y∀x . The former says each x has a y that satisfies P(x , y ); the latter says there’s an individual y that satisfies P(x , y ) for every x . But ∀x∀y is the same as ∀y∀x and ∃x∃y is the same as ∃y∃x . Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 11 / 20 Quantified Formulas as a Two-Person Game The truth or falsehood of a quantified formula can be expressed as a question of winning strategies for a two-person game. Say I make a claim (the quantified statement) and you try to disprove it. You get to supply values for the universally quantified variables. If I claim ∀x∃y P(x , y ), then you can challenge me by choosing an x and asking me to find the y that satisfies P(x , y ), but I get to know the x you chose. If I claim ∃y∀x P(x , y ), then you can challenge me by asking me to provide the y , and then you just have to find an x that does not satisfy P(x , y ), knowing the y that I chose. If I claim ∃x∃y P(x , y ), then I have to find both x and y , so it doesn’t matter what order they appear. If I claim ∀y∀x P(x , y ), then you get to pick both x and y , so again their order does not matter. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 12 / 20 Rules of Passage for the Quantifiers We cannot in general “push quantifiers in”. For example, there is no immediate simplification of a formula of the form ∃x (P(x) ∧ Q(x)). However, we do get, for formulas F1 and F2: ∃x (¬F1) ≡ ¬∀x F1 ∀x (¬F1) ≡ ¬∃x F1 ∃x (F1 ∨ F2) ≡ (∃x F1) ∨ (∃x F2) ∀x (F1 ∧ F2) ≡ (∀x F1) ∧ (∀x F2) It follows that ∃x (F1 ⇒ F2) ≡ (∀x F1)⇒ (∃x F2) Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 13 / 20 More Rules of Passage for Quantifiers If G is a formula with no free occurrences of x , then we also get ∃x G ≡ G ∀x G ≡ G ∃x (F ∧ G ) ≡ (∃x F ) ∧ G ∀x (F ∨ G ) ≡ (∀x F ) ∨ G ∀x (F ⇒ G ) ≡ (∃x F )⇒ G ∀x (G ⇒ F ) ≡ G ⇒ (∀x F ) no matter what F is. In particular F may have free occurrences of x . Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 14 / 20 Models and Validity of Formulas A wff F is true in interpretation I iff every valuation makes F true (for I). If not true then it is false in interpretation I. A model for F is an interpretation I such that F is true in I. We write I |= F . A wff F is logically valid iff every interpretation is a model for F . In that case we write |= F . F2 is a logical consequence of F1 iff I |= F2 whenever I |= F1. We write F1 |= F2. F1 and F2 are logically equivalent iff F1 |= F2 and F2 |= F1. We write F1 ≡ F2. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 15 / 20 Summarising: Satisfiability and Validity A closed, well-formed formula F is satisfiable iff I |= F for some interpretation I; valid iff I |= F for every interpretation I; unsatisfiable iff I 6|= F for every interpretation I; non-valid iff I 6|= F for some interpretation I. As in the propositional case, we have F is valid iff ¬F is unsatisfiable; F is non-valid iff ¬F is satisfiable. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 16 / 20 Example of Non-Validity Consider the formula (∀y∃x P(x , y ))⇒ (∃x∀y P(x , y )) It is not valid. For example, consider the interpretation with domain D = Z, and the predicate P meaning “less than”. Or, let D = {0, 1} and let P mean “equals”. The formula is satisfiable, as it is true, for example, in the interpretation where D = {0, 1} and P means “less than or equal”. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 17 / 20 Example of Validity F = (∃y∀x P(x , y ))⇒ (∀x∃y P(x , y )) is valid. If we negate F (and rewrite it) we get (∃y∀x P(x , y )) ∧ (∃x∀y ¬P(x , y )) The right conjunct is made true only if there is some d0 ∈ D for which p(d0, d) is false for all d ∈ D. But the left conjunct requires that p(d0, d) be true for at least some d . Since F ’s negation is unsatisfiable, F is valid. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 18 / 20 Another Example of Validity Consider F = (∀x P(x))⇒ P(t) F is valid no matter what the term t is. To see this, again it is easiest to consider ¬F = (∀x P(x)) ∧ ¬P(t) The term t denotes some element of the domain D, so ¬F cannot be satisfied. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 19 / 20 Puzzle for the Break Deckard is a blade runner—his job is to identify replicants who look exactly like humans but who have actually been created in the laboratories of Tyrell Corp. Deckard interviews suspects. The problem is that some replicants are programmed to always speak the truth, while others are programmed to always lie. Unfortunately the same goes for the humans that Deckard deals with: some are always truthful, and the rest always lie. One day, a suspect makes a simple statement that allows Deckard to conclude the suspect is a lying replicant. What statement would do that? After the break: Clausal form for first-order predicate logic. Models of Computation (Sem 2, 2021) Predicate Logic: Semantics c© University of Melbourne 20 / 20