Sentence Meaning

LIN 141: Semantics

Masoud Jasbi

​

Watching lectures without doing the readings

​

​

Watching lectures having done the readings

Plan

Introduce Propositional Logic

Syntax Propositional Logic

BNF Definition

CFG Definition

Semantics of Propositional Logic

Natural Language vs. Propositional Logic

Defining a Language

Language (informal definition): a system associating symbols with meanings.

Lexicon: the set of symbols.

Syntax: the lexicon and the system that combines them.

Semantics: the meanings associated with the syntax.

Language (formal definition): a syntax mapped onto a semantics.

L= <Syn L, Sem L>

How realistic is this definition for human language?

Propositional Logic

A Short History

Propositional Logic is one of the oldest and most basic logical systems.

Started with Stoic philosophers like Chrysippus of Soli.

Modern version by the British mathematician George Boole.

The atoms (smallest meaningful units) are propositions.

George Boole

Mathematician

1815-1864

Chrysippus

280–207 BC

p = ⟦The cat is on the dog.⟧

Propositions

Informal Definition: the meaning of sentences.

“The dog is on the cat.”

Sometimes we loosely talk about entailment or contradiction between sentences.

What we really mean: entailment or contradiction between the propositions they denote.

Sentence is a syntactic notion.

Proposition, entailment, and contradiction are semantic.

Syntax of Propositional Logic (BNF Definition)

Definition (Syntax of L_prop): Let ℙ be a set of propositional letters like p, q, r, …

φ ⩴ ℙ | ¬ φ | (φ ⋀ φ) | (φ ⋁ φ) | (φ → φ) | (φ ↔ φ)

¬(¬p)

¬(¬q)

¬(¬r)

¬(p⋀q)

¬(p⋀r)

¬(q⋀r)

¬(q⋀p)

¬(r⋀p)

¬(r⋀q)

​

p⋁(p⋀q)

p⋁(p⋀r)

p⋁(q⋀r)

p⋁(q⋀p)

p⋁(r⋀p)

p⋁(r⋀q)

​

Exercise: watch your form!

Which one is a well-formed formula of L_p?

1. (p ¬ q)
2. (((p ⋀ q) ¬ r) → (p ⋁ q))
3. ((((p ↔ p) ⋀ p) ⋀ ¬ p) → ((p → ¬ p) → p))
4. ((p ⋀ q) | (r ⋁ s))
5. ((p → (q → r)) → ((p → q) → (p → r)))
6. (φ ⋁ φ)

Definition (Syntax of L_prop): Let ℙ be a set of propositional letters like p, q, r, …

φ ⩴ ℙ | ¬ φ | (φ ⋀ φ) | (φ ⋁ φ) | (φ → φ) | (φ ↔ φ)

Scope

Let L_prop be the language of propositional logic.

Let ○ ∈ {¬, ⋀, ⋁, →, ↔} be a connective of L_p.

Let W be a well-formed formula of L_p.

The scope of an occurrence of ○ in W is the smallest well-formed part of W containing this occurrence of ○.

Example: (¬(p ⋀ q) → r)

Exercise: scope investigation

Use parentheses to determine possible scopes for each connective.

1. ¬ p ⋀ q
2. p ⋀ q ⋀ r
3. p ⋀ q ⋁ r
4. p ⋁ ¬ q → r ⋀ s

Syntax of Propositional Logic (CFG Definition)

S: starting symbol, N: nonterminal symbols, T: terminal symbols, R: rules

Context Free Grammar G = <S, N, T, R>

L_Prop= < φ, {φ}, {p,q,r, …, ¬,⋀, ⋁, →, ↔}, R >

R: φ ⇒ ¬ φ

φ ⇒ φ ⋀ φ

φ ⇒ φ ⋁ φ

φ ⇒ φ → φ

φ ⇒ φ ↔ φ

φ ⇒ p, q, r, s, t

Noam Chomsky

Linguist

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

Example

Alphabet: p,q,r,s,t, …., ¬,⋀, ⋁, →, ↔

Symbols of the Grammar: φ, ⇒

Rules of our grammar:

1. φ ⇒ ¬ φ
2. φ ⇒ (φ ⋀ φ)
3. φ ⇒ (φ ⋁ φ)
4. φ ⇒ (φ → φ)
5. φ ⇒ (φ ↔ φ)
6. φ ⇒ p, q, r, s, t, ...

φ

(¬(p ⋀ q) ↔ (¬p ⋁ ¬q))

Exercise

Which ones are valid sentences of propositional logic?

1. p
2. (p⋁q)
3. (¬⋁r)
4. → s
5. ¬ ¬ ¬ ¬ ¬ ¬ ¬ p
6. ((((p⋁q)⋀q)⋁p)→p)
7. (pr→ s)

Alphabet: p,q,r,s,t, …., ¬,⋀, ⋁, →, ↔

Symbols of the Grammar: φ, ⇒

Rules of our grammar:

• φ ⇒ ¬ φ
• φ ⇒ (φ ⋀ φ)
• φ ⇒ (φ ⋁ φ)
• φ ⇒ (φ → φ)
• φ ⇒ (φ ↔ φ)
• φ ⇒ p, q, r, s, t, ...

Semantics for L_prop

Now we need to assignment meaning to all the formulas of L_prop.

φ ⩴ ℙ | ¬ φ | (φ ⋀ φ) | (φ ⋁ φ) | (φ → φ) | (φ ↔ φ)

We can start with the atomic propositions in ℙ like p, q, r, s ...

And then assign meaning to molecular propositions that involve connectives such as (p ⋀ q), (p ⋁ q) → ¬ r, …

Semantics for L_prop

​

Definition (Semantics of propositional logic): An interpretation function I is a function from atomic propositional letters to truth values 0 (F) and 1 (T).

I₁(p) = 1, I₁(q) = 1, ...

I₂(p) = 1, I₂(q) = 0, ...

I₃(p) = 0, I₃(q) = 1, ...

I₄(p) = 0, I₄(q) = 0, ...

Semantics of Propositional Logic

In propositional logic, the meaning of basic propositions (p,q,r, ...) are either true (1) or false (0).

The meaning of complex propositions are computed from the value of basic propositions according to the following truth tables.

​

Interpreting the Symbols

p = 1, q = 0

φ

(¬(p ⋀ q) ↔ (¬p ⋁ ¬q))

=0

=0

=1

=1

=1

=1

What if p=1, q=1?

Or p= 0, q=0?

Or p=0, q=1?

Exercise: moment of truth!

Compute the truth values of the following complex formulas using syntactic trees. Take the interpretation I₅ with I₅(p) = I₅(q)=1, I₅(r)=0.

1. ⟦(¬ p ⋁ q)⟧^I5 =
2. ⟦((¬ p ⋁ q) → r)⟧^I5 =
3. ⟦(¬(p ⋁ q) → r)⟧^I5 =

Truth Table

(¬ (p ⋀ q) ↔ (¬ p ⋁ ¬ q) )

​

Exercise: Table of Truths!

Provide truth tables for the following:

• ⟦¬ (p ⋁ q)⟧
• ⟦¬ (p ⋀ ¬ p)⟧
• ⟦(¬p ⋀ ¬q)⟧
• ⟦(¬ (p ⋁ q) ↔ (¬p ⋀ ¬q))⟧

Tautologies

A formula that gets the value 1 in every valuation is called a tautology.

The notation for tautologies is ⊨ 𝜑.

Some Famous Tautologies:

1. (φ ⋁ ¬φ) The Law of Excluded Middle
2. ¬(φ ⋀ ¬φ) The Law of Non-contradiction
3. ¬¬ φ ↔ φ Double Negation
4. ¬(φ ⋁ ψ) ↔ (¬φ ⋀ ¬ψ) De Morgan’s Law
5. ¬(φ ⋀ ψ) ↔ (¬φ ⋁ ¬ψ) De Morgan’s Law
6. (φ ⋀ (ψ ⋁ χ)) ↔ ((φ ⋀ ψ) ⋁ (ψ ⋀ χ)) Distribution Law
7. (φ ⋁ (ψ ⋀ χ)) ↔ ((φ ⋁ ψ) ⋀ (ψ ⋁ χ)) Distribution Law

Other binary connectives

L_prop used the following connectives: {¬,⋀, ⋁, →, ↔}

There are 16 possible binary connectives.

The choice of connective can lead up to different formal languages.

Inclusive vs. Exclusive Disjunction

Inclusive and exclusive disjunction have had an old competition in who is more primary!

Stoics thought exclusive disjunction is primary!

20th century logic considered inclusive disjunction to be more primary.

Natural Language &

Propositional Logic

From Language to Truth

Language

Syntax

Semantics

Abe was 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

From L_prop to Truth

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

Using Propositional Logic

Our goal was to build a model that does what language does.

We built one: propositional logic.

How do we model language with it? How good is this model?

The first step is to see what parts of language fits our model.

So we are going to represent language with propositional logic.

Another way to say it: we are translating language into propositional logic.

Like any translation/representation, there is some information loss.

The Syntax of L_prop & Language

Translating English to Propositional Logic

Examples

Abe was happy.

p

Abe likes cheese.

q

Abe was not happy.

￢p

Abe likes cheese and Abe was happy.

p⋀q

Abe likes cheese or Abe was happy.

p⋁q

If Abe was happy then Abe likes cheese.

p→q

Abe was happy or Abe was not happy.

p⋁￢p

If Abe does not like cheese then Abe was not happy.

￢q→￢p

If Abe likes cheese and Abe was happy then Bob was happy too.

(p⋀q)→r

If Abe was not happy and Abe does not like cheese, then Bob was not happy or Bob does not like cheese.

(￢p⋀￢q)

→

(￢r⋁￢s)

Exercise: Translate to Propositional Logic

If I go home late, my mom is going to kill me.

If I don’t call home and go home late, my mom is going to kill me.

He has an Ace if he does not have a Knight or a Spade.

If it rains and you don’t have a car, then you can carry my umbrella.

He entered the store, did not buy a book or a pen, and if he talked to anyone, it was not me or anyone around me.

The ball is either in my room, or your room, or in the kitchen and since it is not in my room or the kitchen then it is in your room.

p→q

(r⋀￢p)→q

￢(k⋁s)→ a

(s⋀￢c)→ u

((e⋀￢(b⋁n))⋀(y→￢(x⋁o)))

((t⋁w)⋁h)⋀￢(t⋁h)→ w

A conversation in English and L_prop

Abe: ((p⋁q)⋁r)

Bob: ¬p

Abe: ¬q

Bob: r

Abe: It’s either in your room, my room, or in the kitchen.

Bob: It’s not in my room.

Abe: It’s not in my room either.

Bob: So it is in the kitchen!

Notice that we have still not really dealt with meaning.

We have only replaced words with logical symbols.

The Semantics of L_prop and Language

Language

Syntax

Semantics

There is a cat, there is a dog, there isn’t a cat, there isn’t a dog, there is a cat or a dog, there is a cat and a dog, ...

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

Interpretation

Propositional Language

Syntax

Semantics

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

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

Interpretation

Meaning in English and Propositional Logic

We have intuitions about truth of sentences in English.

In propositional logic, we defined meaning this way:

The meaning of basic propositions (p,q, ...) are either true (1) or false (0).

The meaning of complex propositions are computed from the following truth tables:

Do our English intuitions match the predictions of propositional logic?

Sentences and Connectives of English

Propositions and Connectives in L_P

Experimental Results

Response Proportion

Experimental Results (3-5 year-olds)

Response Proportion

Compositionality

The way we compute meaning in propositional logic allows us to model compositionality.

The meaning of complex formulas (sentences) are computed using the meaning of their parts and the way the were put together.