University:
Boston University
Course:
CAS LX 110 | Say What? Accents, Dialects, and Society
Academic year:

2022
Views:

64

Pages:

2
Author:

Tiffany Frye

First-order predicate logic and quantifiers 1 Syntax of first-order predicate logic vocabulary: individual constants: j, m, s, … predicate constants (P,Q) with a fixed number of argument places connectives (∧,∨,¬,→,↔) syntax for generating well-formed formulas (wffs): Any atomic expression is a wff. If P is an n-place predicate and t1 , t 2 , … tn are indiv. constants, P(t1 , t 2 , … tn) is a wff. If P and Q are wffs, then ¬P, P∧ Q, P ∨ Q, P→ Q, and P ↔ Q are wffs. Nothing else is a wff. 2 The semantics of first-order predicate logic Assume a model M consisting of a universe of discourse U and an interpretation function I Interpretation function I: specifies what the (individual & predicate) constants refer to. For an individual constant j, I(j) ∈ U. For a 1-place predicate P, I(P) ⊆ U. [[red]]M = I(red) = { x ∈ U | red(x) } For a 2-place predicate Q, I(Q) ⊆ U × U. [[love]] M = I(love) = { ∈ U × U | love(x,y)} n For an n-place predicate R, I(R) ⊆ U . [[R]] M = { ∈ U n | R(x1 , … xn)} Valuation function VM : computes the truth value of an expression in a particular model. Predication interpretation rule: If P(x 1 , …, xn) is an atomic proposition and x1 , …, xn are individual constants, then VM (P(x 1 , …, xn)) = 1 iff ∈ I(P) Logical connectors: VM (¬P) = 1 iff VM (P) = 0 VM (P ∧ Q) = 1 iff VM (P) = 1 and VM (Q) = 1 VM (P ∨ Q) = 1 iff VM (P) = 1 or VM (Q) = 1 VM (P → Q) = 1 iff VM (P) = 0 or VM (Q) = 1 (= not P or Q) VM (P ↔ Q) = 1 iff VM (P) = VM (Q) Semantic properties of relations R and R' are converses iff R(x, y) ↔ R'(y, x). R is symmetric iff R(x, y) ↔ R(y, x). Symmetric predicates are their own converses. R is reflexive iff R(x, x) = 1. R is transitive iff, for any x, y, z, if R(x, y) and R(y, z) are true, R(x, z) is true. 3 Quantifiers (1) Somebody likes Mary. ∃x likes(x, Mary) (2) Everyone likes Mary. ∀x likes(x, Mary) (3) Every student arrived on time. ∀x (student(x) à arrived-on-time(x)) (4) Some/a student arrived on time. ∃x (student(x) ∧ arrived-on-time(x)) Quantifiers and negation ∀xP(x) ⇔ ¬∃x¬P(x) Everyone is here ⇔ it’s not the case that someone is not here. ∃xP(x) ⇔ ¬∀x¬P(x) Someone is here ⇔ it’s not the case that everyone is not here. ¬∀xP(x) ⇔ ∃x¬P(x) Not everyone is here ⇔ Someone is not here. ¬∃xP(x) ⇔ ∀x¬P(x) It is not the case that someone is here ⇔ Everyone is not here. Syntax of quantifiers: If P is a wff and x is an individual variable, then ∀xP and ∃xP are wffs. Semantics of quantifiers: (5) Shei saw itj in the window. see(i, j) g: g(i) = Ann, g(j) = the dog g': g(i) = Sally, g(j) = a ghost For g[x/e] a variable assignment which differs from g at most in that it assigns the individual e to x: [[ ∀xP]] M,g = 1 iff [[P]]M,g[x/e] = 1 for all individuals e in U [[ ∃ xP]] M,g = 1 iff [[P]]M,g[x/e] = 1 for some individual e in U 4 Summary: first-order predicate logic vocabulary: individual constants: j, m, s, … individual variables: x, y , z predicate constants (P,Q) with a fixed number of argument places connectives (∧,∨,¬,→,↔), binary identity predicate =, quantifiers ∀ and ∃ syntax for generating well-formed formulas (wffs): Any atomic expression (no connectives) is a wff. If t1 and t2 are individual constants or variables, then t1 = t2 is a wff. If P is an n-place predicate, t1 , t 2 , … tn are individual constants or variables, P(t1 , t 2 , … tn) is a wff. If P and Q are wffs, then ¬P, P ∧ Q, P ∨ Q, P → Q, and P ↔ Q are wffs. If P is a wff and x is an individual variable, then ∀xP and ∃xP are wffs. Nothing else is a wff. semantics for interpreting well-formed formulas. Assume a model M consisting of a universe of discourse U, an interpretation function I, and an assignment function g. I: function from the (individual and predicate) constants onto U (lexical terminals) g: an assignment function that maps variables into the universe of discourse U. Valuations are conducted with respect to a particular M and g. If t is an individual constant, [[t]]M,g = I(t) If t is an individual variable, [[t]]M,g = g(t) If P(t 1 , …, tn) is an atomic statement with t1 , …, tn individual constants or variables, then: VM,g(P(t 1 , …, tn)) = 1 iff <[[t1 ]] M,g, … [[tn]] M,g> ∈ I(X) VM,g(t 1 = t2 ) = 1 iff [[t1 ]] M,g = [[t2 ]] M,g VM,g(¬P) = 1 iff VM,g(P) = 0 VM,g(P ∧ Q) = 1 iff VM,g(P) = 1 and VM,g(Q) = 1 VM,g(P ∨ Q) = 1 iff VM,g(P]] = 1 or VM,g(Q) = 1 VM,g(P → Q) = 1 iff VM,g(P]] = 0 or VM,g(Q) = 1 VM,g(P ↔ Q) = 1 iff VM,g(P]] = VM,g(Q) VM,g( ∀xP) = 1 iff VM,g[x/e](P) = 1 for all individuals e in U VM,g( ∃ xP) = 1 iff VM,g[x/e](P) = 1 for some individual e in U 5 Quantifier scope (6) Everyone loves someone. a. ∀x ∃y love(x, y) b. ∃y ∀x love(x, y) Laws of quantifier independence ∀x ∀y P(x, y) ⇔ ∀y ∀x P(x, y) ∃x ∃y P(x, y) ⇔ ∃y ∃x P(x, y) ∃x ∀y P(x, y) ⇒ ∀y ∃x P(x, y) (7) Which movie did everyone see? Individual answer: Which movie is such that everyone saw it? Titanic Pair-list answer: John saw Titanic, Sally saw Star Wars, … 6 Anaphora (8) Johni hurt himselfi . hurt(j, j) (9) If Sallyi sees Fredj, shei will invite himj. see(s, f) à invite(s, f) (10) Everyonei hates himselfi . ∀x (hate(x, x)) (11) Everyonei likes hisi parents. ∀x ∃y (mother-of(y, x) ∧ ∀z(mother-of(z, x) à [z=y]) ∧ like (x, y)) ∀x ∃y (mother-of(y, x) ∧ like (x, y)) (12) Everyonei thinks hei is a genius. ∀x (x thinks x is a genius)

First-order Predicate Logic and Quantifiers