Subsentential Meaning

LIN 141: Semantics

Masoud Jasbi

Where were we?

Propositional Logic can capture the (truth-conditional) meaning of sentences.

It did relatively well with the meaning of connectives like “not”, “and”, “or”, and “if”.

But as some of you noted there are some discrepancies.

​

Formal Logic vs. Ordinary Language Debate

These discrepancies fueled the logic vs. language debates.

On week 10, we come back to this issue.

We see that these discrepancies truly bothered the philosopher Paul Grice.

So he created a new paradigm of studying meaning.

Natural Language

Language

Syntax

Semantics

Abe is happy, Abe likes cheese, Abe or Bob like cheese, Abe likes Bob, Bob and Abe left, ...

TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, ...

Interpretation

Propositional Logic

Propositional Language

Syntax

Semantics

p, q, r, …

¬p, ¬q,¬r, ... (p⋀q), (p⋀r), (q⋀r), … (p⋁q), (p⋁r), (q⋁r), … (p→q), (p→r), (q→r), … (p⋀q)⋀(q→r)

TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, ...

Interpretation I()

Predicate Logic

First Order (Predicate) Language

Syntax

Semantics

P(a), Q(b), … P(x), Q(y) …

¬P(a), ¬Q(b),...¬P(x), ¬Q(y) … [P(a)⋀Q(b)], … [P(x)⋁Q(y)], …

∀x[P(x)], ∃y[Q(y)], ...

TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, ...

Interpretation

Predicate Logic

(Informal Intro)

Shortcomings of Propositional Logic

Too coarse-grained as a representational system.

No way of representing sub-sentential elements like words and phrases.

Nominals like “Cleo”, “her”, or “the teacher”.

Verbs or Adjectives like “walk” or “happy”.

Quantifiers like “every” and “some”.

Adding Expressivity

We can represent definite and known entities with individual symbols.

“Abe” ⇒ a, “Barbara” ⇒ b, “The Arboretum” ⇒ c, ...

We can represent indefinite entities with variables.

“she” ⇒ x, “this” ⇒ y, …

We can represent properties and relations using predicates.

“Barbara is happy” ⇒ H(b)

“Abe likes the arboretum” ⇒ L(a, c)

Adding Expressivity

We can represent the quantifier “every” using the Universal symbol and a variable.

“Everyone is happy” ⇒ ∀x[ H(x) ]

We can represent the quantifier “some” using the Existential symbol and a variable.

“Someone is happy” ⇒ ∃x[H(x)]

We can keep our propositional symbols for connectives.

“If everyone is happy then someone is happy” ⇒ [∀x[H(x)] → ∃x[H(x)]]

“Abe likes the arboretum or not” ⇒ [L(a, c) ⋁ L(a, c)]

Sentences in Propositional and Predicate Logics

Cleo is happy

p

H(c)

Cleo laughs

q

L(c)

Dasha laughs

r

L(d)

She laughs

?

L(x)

Everyone laughs

e

∀x[L(x)]

Someone laughs

s

∃x[L(x)]

Exercise

How can we represent the following sentences in predicate logic?

1. The UC Davis arboretum is south of the campus.
2. Cleo knows Dasha.
3. Dasha knows Cleo.
4. Cleo and Dasha know each other.
5. If Abe loves Bob, then Bob loves Abe.
6. Barbara and Bob don’t love each other.
7. Someone saw the arboretum.
8. Everyone showed the arboretum to Cleo.

​

First Order (Predicate) Logic

A Short History

Predicate Logic is a streamlined version of a “language of thought” developed by by the German philosopher and mathematician Gottlob Frege (1848 – 1925).

Around the same time, Charles Sanders Peirce, an American philosopher and logician developed essentially the same system.

Gottlob Frege

(1848 – 1925)

Charles Sanders Peirce

(1839 – 1914)

L_pred Syntax

Syntax of Predicate Logic

A set of terms: t₁, t₂, …, t_n

constants like a, b, c, … to represent individuals like Abe & Cleo

variables like: x, y, z, … to represent pronouns like s/he and h(er/im)

A set of predicates: P, Q, R, S, … to represent properties like happy, red, ...

Atomic propositions: P(x), Q(a), R(y,z), S(d), …

to represent properties of individuals and their relations like:

Abe is happy, Cleo runs, ...

Syntax of Predicate Logic (BNF)

We formally define the syntax of L_pred as:

​

c ⩴ a | b | d | …

v ⩴ x | y | z | …

t ⩴ v | c

Pred ⩴ P | Q | R | ...

Atom ⩴ Pred(t₁, …, t_n)

φ ⩴ Atom | ¬ φ | [φ ⋀ φ] | [φ ⋁ φ] | [φ → φ] | [φ ↔ φ] | ∀v[φ] | ∃v[φ]

​

Propositional vs. Predicate Logic

Predicate logic is an extension of propositional logic with structured basic propositions and quantification.

Boolean connectives are similar to propositional logic.

An atomic formula consists of a predicate followed by n terms.

A universally quantified formula consists of ∀ followed by a variable, and a formula.

An existentially quantified formula consists of ∃ followed by a variable, and a formula.

A Context Free Grammar for L_pred

CFG = <𝓢 (starting symbol), 𝓝 (nonterminals), 𝓣 (terminals), ℛ (rules)>

L_Pred= < φ, {φ, Atom, Pred, t}, {a,b, c, …, x,y,z, …, P, Q, R, ... ¬,⋀, ⋁, →, ↔}, ℛ>

​

ℛ:

1. φ ⇒ ¬ φ

2. φ ⇒ [φ ⋀ φ]

3. φ ⇒ [φ ⋁ φ]

4. φ ⇒ [φ → φ]

5. φ ⇒ [φ ↔ φ]

6. φ ⇒ ∀v[φ]

7. φ ⇒ ∃v[φ]

8. φ ⇒ Atom

9. Atom ⇒ Pred (t₁, …, t_n)

10. Pred ⇒ P | Q | R | ...

11. t ⇒ c | v

12. c ⇒ a | b | c | ...

13. v ⇒ x | y | z | ...

ℛ:

1. φ ⇒ ¬ φ

2. φ ⇒ [φ ⋀ φ]

3. φ ⇒ [φ ⋁ φ]

4. φ ⇒ [φ → φ]

5. φ ⇒ [φ ↔ φ]

6. φ ⇒ ∀v [φ]

7. φ ⇒ ∃v [φ]

8. φ ⇒ Atom

9. Atom ⇒ Pred (t₁, …, t_n)

10. Pred ⇒ P | Q | R | ...

11. t ⇒ c | v

12. c ⇒ a | b | c | ...

13. v ⇒ x | y | z | ...

P(x) ⋀ ∀x[Q(x)→R(x,y)]

φ

Exercise: Grow your own trees

Take some time to produce a few well-formed formulas in L_pred(Predicate Logic)

L_Pr= < φ, {φ, Atom, Pred, t, c, v}, {a,b, c, …, x,y,z, …, P, Q, R, ... ¬,⋀, ⋁, →, ↔}, ℛ>

​

ℛ:

1. φ ⇒ ¬ φ

2. φ ⇒ [φ ⋀ φ]

3. φ ⇒ [φ ⋁ φ]

4. φ ⇒ [φ → φ]

5. φ ⇒ [φ ↔ φ]

6. φ ⇒ ∀v[φ]

7. φ ⇒ ∃v[φ]

8. φ ⇒ Atom

9. Atom ⇒ Pred (t₁, …, t_n)

10. Pred ⇒ P | Q | R | ...

11. t ⇒ c | v

12. c ⇒ a | b | c | ...

13. v ⇒ x | y | z | ...

Exercise

Which of the following are well-formed formulas (aka sentences or strings) of predicate logic? (x, y, … are variables; a, b,c ... constants, P, Q, ... predicates)

1. a
2. [x ⋁ y]
3. P(a)
4. ∀x[x]
5. ∃a[P(a) → Q(a)]
6. ∀x∃y[P(x) → Q(x,y)]
7. ∀x¬∃y[P(x) → Q(x,y)]
8. ∀x[¬P(z)⋀Q(a)]

Variable Binding

Variables in predicate logic are either bound or free.

In a formula ∀v[φ] or ∃v[φ], the quantifier binds all occurrences of v in [φ] that are not bound by any other quantifier occurrence inside [φ].

Quantifiers that are not bound, are free!

Example: P(x) ⋀ ∀x[Q(x)→R(x,y)]

The first occurence of x, and y are free.

The second and third occurrences of x are bound by ∀.

​

Exercise: Bound or Free?

For each variable, say whether it is bound or free. If bound say by what operator.

1. P(x) ⋀ Q(y)
2. ∀x[P(y)]
3. ∃x[R(x,y) ⋁ S(x,y,z)] ⋀ P(x)
4. ∀x[P(x)→∃x[R(x,x)]]

​

Predicate Logic (Review)

First Order (Predicate) Language

Syntax

Semantics

P(a), Q(b), … P(x), Q(y) …

¬P(a), ¬Q(b),...¬P(x), ¬Q(y) … [P(a)⋀Q(b)], … [P(x)⋁Q(y)], …

∀x[P(x)], ∃y[Q(y)], ...

TRUE, FALSE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, FALSE, ...

Interpretation

Syntax of Predicate Logic

A set of terms: t₁, t₂, …, t_n

Individual constants like a, b, c, … to represent individuals like Abe & Cleo

Variables like: x, y, z, … to represent pronouns like s/he and h(er/im)

A set of predicates: P, Q, R, S, … to represent properties like happy, red, ...

Atomic propositions: P(x), Q(a), R(y,z), S(d), …

Connectives: ¬, ⋀, →, ⋁ , ↔

Quantifiers: ∀v[φ] | ∃v[φ]

Syntax of Predicate Logic (BNF)

We formally define the syntax of L_pred as:

​

c ⩴ a | b | c | …

v ⩴ x | y | z | …

t ⩴ v | c

Pred ⩴ P | Q | R | ...

Atom ⩴ Pred(t₁, …, t_n)

φ ⩴ Atom | ¬ φ | [φ ⋀ φ] | [φ ⋁ φ] | [φ → φ] | [φ ↔ φ] | ∀v[φ] | ∃v[φ]

L_pred Semantics

Putting Meanings on Forms

We start with the set of terminal symbols and assign them meaning.

Then we come up with a set of rules to derive the meaning of the infinite set of complex expressions.

In propositional logic terminal symbols were all atomic propositions and mapped to True(1) and False(0).

In predicate logic, our terminals are constants (individual + predicate) or variables.

For these we need to build a model of individuals and their relations.

Model-theoretic Interpretation

Instead of a simple mapping to truth values, we map the symbols of predicate logic according to a model.

Then we define truth according to such a model.

This truth definition for predicate logic is due to the Polish logician Alfred Tarski.

Alfred Tarski

Logician, Mathematician

(1901-1983)

Main Components of L_pred Semantics

We interpret L_pred using a model and an assignment function.

A model has two components:

1. The domain D: the set of all entities in the model.
2. The interpretation function I: which maps formulas of L_pred to their meanings.

We formally define a model as M = <D, I>.

The variable assignment function g maps variables to objects in D.

We use the interpretation brackets ⟦⟧^M,g with superscripts M, g to show the interpretation of an expression according to model M and assignment function g.

Example Model: The Simpsons

The Simpsons Model

M_Simpsons = <D_Simpsons, I_Simpsons>

D_Simpsons = { , , , , , }

Assigning Meaning to L_pred Syntax

We will first start with constants:

Individuals (a, b, c, ...)

Predicates: Unary, Binary, Ternary, …

Then we deal with Atoms: P(a), R(a,b), ...

Then we deal with connectives: ¬, ⋀, →, ⋁ , ↔

Then we assign meaning to variables (x, y, z, ...)

And finally we deal with the meaning of quantifiers: ∀, ∃

Interpretation of Constants

Constants are assigned meaning by the interpretation function I.

The interpretation of an individual or predicate constant c is the value assigned to it by the interpretation function I.

⟦c⟧^M,g = I(c)

⟦Pred⟧^M,g = I(Pred)

Let’s look at the the interpretation function for our example model.

The Simpsons Language

M_Simpsons = <D_Simpsons, I_Simpsons>

D_Simpsons = { , , , , , }

Constants:

Individuals: Homer, Lisa, Bart, Marge, Marvin, Maggie

Unary Predicates: simpsons, therapist, adult, child, walks, crawls, …

Binary Predicates: annoy, hit, …

Ternary Predicates: introduce, ...

Individual Constants

M_Simpsons = <D_Simpsons, I_Simpsons>

D_Simpsons = { , , , , , }

I_Simpsons (Marge) =

I_Simpsons (Homer) =

I_Simpsons (Lisa) =

I_Simpsons (Bart) =

I_Simpsons (Maggie) =

I_Simpsons (Marvin) =

Unary Predicates

I_Simpsons (adult) = { , , }

I_Simpsons (child) = { , , }

I_Simpsons (walk) = { , Z , , , }

I_Simpsons (crawl) = { }

M_Simpsons = <D_Simpsons, I_Simpsons>

D_Simpsons = { , , , , , }

I_Simpsons (simpson) = { , , , , }

I_Simpsons (therapist) = { }

Binary Predicates

I_Simpsons (annoy) ={< , >, < , >, < , >, < , >, < , >}

M_Simpsons = <D_Simpsons, I_Simpsons>

D_Simpsons = { , , , , , }

I_Simpsons (hit) = {< , >, < , >, < , >, < , >, < , >}

Ternary Predicates

I_Simpsons (introduce) ={< , , >, < , , >, < , , >}

M_Simpsons = <D_Simpsons, I_Simpsons>

D_Simpsons = { , , , , , }

N-ary Predicates

The meaning of predicates are created using the elements of the domain.

They are either a set of individuals in the domain or a set of relations among them.

In principle we can have predicates that take more than three terms.

But words in language that denote predicates with more than 3 terms are rare.

Cartesian Product

Consider a set of entities like D = {e₁, e₂, e₃, …, e_n}

We can define the Cartesian product of two sets A and B as:

A × B ={<x, y> | x ∈ A and y ∈ B}

So D × D would be: {<e₁,e₁>, <e₁,e₂>, <e₁,e₃>, … , <e₁,e_n>, … ,<e₂,e₁>, …, <e₂,e_n>, ... }

More generally:

X₁ × … × X_n ={<x₁, …, x_n> | x_i ∈ X_i for every i ∈ {1, … , n}}

Rene Descartes

Philosopher, Mathematician

(1596-1650)

The General Relation between D and I

Let M = <D, I>, and a be an individual constant, P a unary predicate, R a binary predicate, and S a ternary predicate.

D = {e₁, e₂, e₃, …, e_n}

Then:

I(a) is a member of the domain D: I(a) ∈ D

I(P) is a subset of D: I(P) ⊆ D

I(R) is a subset of D × D: I(R) ⊆ D²

I(S) is a subset of D × D × D: I(S) ⊆ D³

...

Meaning of Atoms

An atom with one term Pred(t) is true if and only if the individual denoted by the term is a member of the set denoted by the unary predicate.

⟦Pred(t)⟧^M,g = 1 iff ⟦t⟧^M,g ∈ ⟦Pred⟧^M,g

An atom with n-terms Pred(t₁, …, t_n) is true if and only if the ordered tuple denoted by the terms is a member of the set denoted by the predicate.

⟦Pred(t₁,...,t_n)⟧^M,g = 1 iff <⟦t₁⟧^M,g , …,⟦t₁⟧^M,g > ∈ ⟦Pred⟧^M,g

​

Example: Marvin a therapist?

⟦therapist(Marvin)⟧^M,g = 1 iff

⟦Marvin⟧^M,g ∈ ⟦therapist⟧^M,g

⟦Marvin⟧^M,g = I_Simpsons(Marvin) =

⟦therapist⟧^M,g = I_Simpsons(therapist) = { }

∈ { }

Example: Marvin a Simpson?

⟦simpson(Marvin)⟧^M,g = 1 iff

⟦Marvin⟧^M,g ∈ ⟦simpson⟧^M,g

⟦Marvin⟧^M,g = I_Simpsons(Marvin) =

⟦simpson⟧^M,g = I_Simpsons(simpson) = { , , , , }

∉ { , , , , }

Example: Bart hit Homer?

⟦hit(Bart, Homer)⟧^M,g = 1 iff

<⟦Bart⟧^M,g, ⟦Homer⟧^M,g> ∈ ⟦hit⟧^M,g

⟦Bart⟧^M,g = I_Simpsons(Bart) =

⟦Homer⟧^M,g = I_Simpsons(Homer) =

⟦hit⟧^M,g = I_Simpsons(hit) =

< , > ∉

{< , >, < , >, < , >, < , >, < , >}

Example: Marge Introduced Lisa to Marvin?

⟦introduce(Marge, Lisa, Marvin)⟧^M,g = 1 iff

<⟦Marge⟧^M,g, ⟦Lisa⟧^M,g, ⟦Marvin⟧^M,g> ∈ ⟦introduce⟧^M,g

< , , >

⟦introduce⟧^M,g = I_Simpsons (introduce) =

{< , , >, < , , >, < , , >}

Meaning of Connectives

The meaning of connectives are similar to what we had in propositional logic.

⟦¬𝜙 ⟧^M,g = 1 iff ⟦𝜙 ⟧^M,g = 0

⟦𝜙 ⋀ 𝜓 ⟧^M,g = 1 iff ⟦𝜙 ⟧^M,g = ⟦𝜓⟧^M,g = 1

⟦𝜙 ⋁ 𝜓 ⟧^M,g = 0 iff ⟦𝜙 ⟧^M,g = ⟦𝜓⟧^M,g = 0

⟦𝜙 → 𝜓 ⟧^M,g = 0 iff ⟦𝜙 ⟧^M,g =1, ⟦𝜓⟧^M,g = 0

​

​

Example

⟦annoy(Lisa, Bart) ⋁ annoy(Bart, Lisa)⟧^M,g =

0 iff ⟦annoy(Lisa, Bart)⟧^M,g = ⟦annoy(Bart, Lisa)⟧^M,g = 0

⟦annoy(Lisa, Bart)⟧^M,g =

1 iff <⟦Lisa⟧^M,g, ⟦Bart⟧^M,g> ∈ ⟦annoy⟧^M,g

I_Simpsons (annoy) ={< , >, < , >, < , >, < , >, < , >}

Meaning of Variables

The meaning of a variable is assigned using the variable assignment function g.

⟦v⟧^M,g = g(v)

g maps variables of our syntax to individuals in the model.

There can be many different variable assignment functions: g₁, g₂, g₃, ...

​

​

Example g’s

​

​

​

​

g₁ = g₂ = g₃ = ….

D_Simpsons = { , , , , , }

x →

y →

z →

w →

...

x →

y →

z →

w →

...

x →

y →

z →

w →

...

Example 1

⟦hit(x, y)⟧^M,g1 = 1 iff

<⟦x⟧^M,g1, ⟦y⟧^M,g1> ∈ ⟦hit⟧^M,g1

⟦x⟧^M,g1 = g₁(x) =

⟦y⟧^M,g1 = g₁(y) =

x →

y →

z →

w →

...

Example 1

⟦hit(x, y)⟧^M,g1 = 1 iff

<⟦x⟧^M,g1, ⟦y⟧^M,g1> ∈ ⟦hit⟧^M,g1

⟦x⟧^M,g1 = g₁(x) =

⟦y⟧^M,g1 = g₁(y) =

⟦hit⟧^M,g = I_Simpsons(hit) =

{< , >, < , >, < , >, < , >, < , >}

x →

y →

z →

w →

...

Example 2

⟦hit(x, y)⟧^M,g2 = 1 iff

<⟦x⟧^M,g2, ⟦y⟧^M,g2> ∈ ⟦hit⟧^M,g2

⟦x⟧^M,g2 = g₂(x) =

⟦y⟧^M,g2 = g₂(y) =

⟦hit⟧^M,g = I_Simpsons(hit) =

{< , >, < , >, < , >, < , >, < , >}

x →

y →

z →

w →

...

Exercise

​

​

​

​

g₁ = g₂ = g₃ =

⟦annoy(z,y)⟧^M,g1 = ...

I_Simpsons (annoy) ={< , >, < , >, < , >, < , >, < , >}

x →

y →

z →

w →

...

x →

y →

z →

w →

...

x →

y →

z →

w →

...

Notation g[x→ d]

Assignment functions are hard to represent because they map many variables to many entities.

But often we are concerned with only one variable and not all the ones in the logical language.

In such cases, we can write g[x→ d] to pick an assignment exactly like g except that x is mapped to d.

Quantifiers

Let’s assign meaning to our quantifiers:

⟦∃v[φ]⟧^M,g = 1 iff there is at least one entity d ∈ D such that ⟦φ⟧^M,g[v→d] = 1

⟦∀v[φ]⟧^M,g =1 iff for all d ∈ D it holds that ⟦φ⟧^M,g[v→d] = 1

Example 1

⟦∀x[simpson(x)⟧^M,g =

1 iff for all entity d ∈ D it holds that ⟦simpson(x)⟧^{M,g[x→ d]} = 1

⟦simpson(x)⟧^{M,g[x→ d]} =

1 iff ⟦x⟧^{M,g[x→ d]} ∈ ⟦simpson⟧^{M,g[x→ d]} =

1 iff d ∈

{ , , , , }

D_Simpsons = { , , , , , }

Example 2

⟦∃x[simpson(x) ⋀ crawl(x)⟧^M,g =

1 iff there is a d ∈ D such that ⟦simpson(x) ⋀ crawl(x)⟧^{M,g[x→ d]} = 1

⟦simpson(x) ⋀ crawl(x)⟧^{M,g[x→ d]} = 1 iff

⟦simpson(x)⟧^{M,g[x→ d]} = ⟦crawl(x)⟧^{M,g[x→ d]} = 1

⟦x⟧^{M,g[x→ d]} ∈ ⟦simpson⟧^{M,g[x→ d]}

⟦x⟧^{M,g[x→ d]} ∈ ⟦crawl⟧^{M,g[x→ d]}

D_Simpsons = { , , , , , }

I_Simpsons (crawl) = { }

I_Simpsons (simpson) = { , , , , }

Exercise

⟦∀x[simpson(x) → ∃y[hit(y,x)]]⟧^M,g =

1 iff for all d ∈ D ⟦simpson(x) → ∃y[hit(y,x)]⟧^{M,g[x→ d]} = 1

= 0 iff ⟦simpson(x)⟧^{M,g[x→ d]} = 1 but ⟦∃y[hit(y,x)]⟧^{M,g[x→ d]} = 0

⟦x⟧^{M,g[x→ d]} ∈ ⟦simpson⟧^{M,g[x→ d]}

d ∈ I(simpson)

There is an e ∈ D ⟦hit(y,x)⟧^{M,g[x→ d, y→ e]} = 1

<⟦y⟧^{M,g[x→ d, y→ e]}, ⟦x⟧^{M,g[x→ d, y→ e]}> ∈ ⟦hit⟧^{M,g[x→ d, y→ e]}

<e, d> ∈ I_Simpsons(hit)

I_Simpsons (hit) = {< , >, < , >, < , >, < , >, < , >}

I_Simpsons (simpson) = { , , , , }