Transcript Composition and Substitution: Learning about Language from

Composition and Substitution:
Learning about Language
from Algebra
Ken Presting
University of North Carolina at
Chapel Hill
Introduction
• Intensional contexts are defined by
substitution failure
– Johnny heard that Venus is the Morning Star
– Johnny heard that Venus is Venus
• Composition accounts for indefinite
application of finite knowledge
– ‘p and q’ is a sentence
– ‘p and q and r’ is a sentence
–…
Role of Recursion
• Syntax
– Atomic symbols
– Combination rules
– Closure principle
• Finiteness
– Limited symbols, rules
– Infinitely many expressions
Compositional Semantics
• The usual:
– Choose assignments to atoms
– Forced valuations for molecules
The Two-Element Boolean Algebra
• The Truth Values
• Just two atomic objects: 2BA = {0, 1}
– Disjunction = max(a, b)
– Conjunction = min(a, b)
– Negation = 1 – a
It’s almost familiar
• Boolean arithmetic
–01=1
–01=0
• Boolean algebra
–AB=C
– (A  B)  ~C = C  ~C
– (A  B)  ~C = 0
A Homomorphism to 2BA
• Take any old function that labels
sentences with 0 or 1.
• For example:
– f(S) = 0
– f(PQ) = 1
– etc.
A Homomorphism to 2BA
• Ask: Does this function have the
‘distributive’
– a(b + c) = ab + ac
– f(S  P) = f(S)  f(P)
• and ‘commutative’ properties?
– ac = ca
– f(~S) = ~f(S)
A Homomorphism to 2BA
…is a compositional semantics for
propositional calculus
Sentence Diagrams
• Tree diagrams
– Binary
– Associativity allows n-ary nodes
• (advanced topic: add leaves for empty
expression)
Repetition
• Identical Subtrees
– In many sentences, certain letters appear
twice or more
• P&QP
– Sometimes whole expressions recur
• (P & R)  (P & R)
Reducing the diagram
•
•
•
•
Identify like-labeled leaves
Identify like-labeled nodes
Form equivalence classes
Redraw tree as lattice
– (advanced topics: empty expression as
zero; quotient)
Set Membership Model
• Mapping sentences to sets
– Set of letters = conjunction
– Singleton set = negation
– Associativity
• And vs. Nand
– Naturalness of negation
– Failure of associativity
Comparing lattices
• Embeddings
• Homomorphism
Substitution for a Letter
• Single-letter expressions
– Every sentence is a substitution-instance
of ‘P’
– Substitution for single letters is easy
• Multiple occurrences of a letter
Substitution for Expressions
• What do these sentences have in
common?
(P & Q) v ~(P & Q)
(T & S) v ~(T & S)
Subalgebras
• A subalgebra is a subset which follows
the same rules as its container
• In our case, that means ‘is also a
sentence’
Quotients
• Ignore specfied details
• In our case, treat a subsentence as a
letter
Sentences as Functions
In Algebra, formulas map numbers to
each other
– F(x) = mx + b
• Sentences map the language to itself
– (P v ~P)(Q) = Q v ~Q
Sentences as Functions
• Mapping the language to itself
– Atomic Sentence letters map L to itself
– No other sentence does
• Complex sentences map the language
to a subset of itself
Image of a Sentence
• Image = all the substitution-instances
Image of ‘P v ~P’ is:
Q v ~Q
R v ~R
(Q & R) v ~(Q & R)
(P & Q) v ~(P & Q)
…
Composition of mappings
• Substitute into a substitution-instance
• Start with
– P v ~P
• Substitute for P
– (Q v R) v ~(Q v R)
• Substitute for R
– (Q v (S & T)) v ~(Q v (S & T))
Sentence Fractions
• Here’s a fraction
R
(P & Q)
• The numerator is R
• The denominator is (P & Q)
Fractions and Substitution
• ‘Multiply’
(P & Q) v ~(P & Q)
• by the fraction
R
(P & Q)
• This will be a substitution!
Sentence Arithmetic
Start with
– (P & Q) v ~(P & Q)
Dividing by (P & Q), gives a lattice with a missing
label:
– ‘x’ v ~ ‘x’
But R replaces ‘x’ (this step is by fiat)
– R v ~R