Semantics

1 Overview

The nltk.sem module has two main components:

logic provides a parser for analyzing expressions of First Order Logic (FOL).

evaluate allows users to recursively determine truth in a model for formulas of FOL.

A model consists of a domain of discourse and a valuation function, which assigns values to non-logical constants. We assume that entities in the domain are represented as strings such as 'b1', 'g1', etc. A Valuation is initialized with a list of (symbol, value) pairs, where values are entities, sets of entities or sets of tuples of entities.

>>> import nltk
>>> v = [('adam', 'b1'), ('betty', 'g1'), ('fido', 'd1'),
... ('girl', set(['g1', 'g2'])), ('boy', set(['b1', 'b2'])),
... ('dog', set(['d1'])),
... ('love', set([('b1', 'g1'), ('b2', 'g2'), ('g1', 'b1'), ('g2', 'b1')]))]
>>> val = nltk.sem.Valuation(v)

The domain of discourse can be inferred from the valuation, and model is then created with domain and valuation as parameters.

>>> dom = val.domain
>>> m = nltk.sem.Model(dom, val)

1.1 Assignments

A variable Assignment is a mapping from individual variables to entities in the domain. Individual variables are usually indicated with the letters 'x', 'y', 'w' and 'z', optionally followed by an integer (e.g., 'x0', 'y332'). Assignments are created using the Assignment constructor, which also takes the domain as a parameter.

>>> dom = set(['u1', 'u2', 'u3', 'u4'])
>>> g3 = nltk.sem.Assignment(dom, [('x', 'u1'), ('y', 'u2')])
>>> g3
{'y': 'u2', 'x': 'u1'}

There is also a print format for assignments which uses a notation closer to that in logic textbooks:

>>> print g3
g[u2/y][u1/x]

It is also possible to update an assignment using the add method:

>>> dom = set(['u1', 'u2', 'u3', 'u4'])
>>> g4 = nltk.sem.Assignment(dom)
>>> g4.add('x', 'u1')
{'x': 'u1'}

With no arguments, purge() is equivalent to clear() on a dictionary:

>>> g4.purge()
>>> g4
{}

1.2 Evaluation

The top-level method of a Model instance is evaluate(), which assigns a semantic value to expressions of the logic module, under an assignment g:

>>> dom = val.domain
>>> g = nltk.sem.Assignment(dom)
>>> m.evaluate('all x.(boy(x) -> - girl(x))', g)
True

evaluate() calls a recursive function satisfy(), which in turn calls a function i() to interpret non-logical constants and individual variables. i() delegates the interpretation of these to the the model's Valuation and the variable assignment g respectively. Any atomic expression which cannot be assigned a value by i raises an Undefined exception; this is caught by evaluate, which returns the string 'Undefined'.

>>> m.evaluate('walk(adam)', g, trace=2)

'walk(adam)' is undefined under M, g
'Undefined'

2 Unit Tests

2.1 Unit tests for relations and valuations

>>> from nltk.sem import *

Relations are sets of tuples, all of the same length.

>>> s1 = set([('d1', 'd2'), ('d1', 'd1'), ('d2', 'd1')])
>>> is_rel(s1)
True
>>> s2 = set([('d1', 'd2'), ('d1', 'd2'), ('d1',)])
>>> is_rel(s2)
Traceback (most recent call last):
  . . .
ValueError: Set set([('d1', 'd2'), ('d1',)]) contains sequences of different lengths
>>> s3 = set(['d1', 'd2'])
>>> is_rel(s3)
True
>>> is_rel(set())
True
>>> null_binary_rel = set([(None, None)])
>>> is_rel(null_binary_rel)
True

Sets of entities are converted into sets of singleton tuples.

>>> set2rel(s3)
set([('d1',), ('d2',)])
>>> set2rel(set([1,3,5,]))
set(['1', '3', '5'])
>>> set2rel(set())
set([])
>>> set2rel(set2rel(s3))
set([('d1',), ('d2',)])

Predication is carried out with app().

>>> app(s1, 'd1')
set([('d1',), ('d2',)])
>>> app(s1, 'd2')
set([('d1',)])
>>> app(app(s1, 'd1'), 'd1')
True
>>> app(app(s1, 'd2'), 'd2')
False
>>> app(set(), 'd1')
False
>>> app(s1, 'd3')
set([])
>>> app(app(s1, 'd3'), 'd1')
False
>>> app(s2, 'd1')
Traceback (most recent call last):
  . . .
ValueError: Set set([('d1', 'd2'), ('d1',)]) contains sequences of different lengths
>>> app(null_binary_rel, 'd1')
set([])
>>> app(app(null_binary_rel, 'd1'), 'd1')
False

>>> val = Valuation([('Fido', 'd1'), ('dog', set(['d1', 'd2'])), ('walk', set())])
>>> val['dog']
set([('d1',), ('d2',)])
>>> val.domain == set(['d1', 'd2'])
True
>>> print val.symbols
['Fido', 'dog', 'walk']

Parse a valuation from a string.

>>> v = """
... john => b1
... mary => g1
... suzie => g2
... fido => d1
... tess => d2
... noosa => n
... girl => {g1, g2}
... boy => {b1, b2}
... dog => {d1, d2}
... bark => {d1, d2}
... walk => {b1, g2, d1}
... chase => {(b1, g1), (b2, g1), (g1, d1), (g2, d2)}
... see => {(b1, g1), (b2, d2), (g1, b1),(d2, b1), (g2, n)}
... in => {(b1, n), (b2, n), (d2, n)}
... with => {(b1, g1), (g1, b1), (d1, b1), (b1, d1)}
... """
>>> val = parse_valuation(v)

>>> print val
{'bark': set([('d1',), ('d2',)]),
 'boy': set([('b1',), ('b2',)]),
 'chase': set([('b1', 'g1'), ('g2', 'd2'), ('g1', 'd1'), ('b2', 'g1')]),
 'dog': set([('d1',), ('d2',)]),
 'fido': 'd1',
 'girl': set([('g2',), ('g1',)]),
 'in': set([('d2', 'n'), ('b1', 'n'), ('b2', 'n')]),
 'john': 'b1',
 'mary': 'g1',
 'noosa': 'n',
 'see': set([('b1', 'g1'), ('b2', 'd2'), ('d2', 'b1'), ('g2', 'n'), ('g1', 'b1')]),
 'suzie': 'g2',
 'tess': 'd2',
 'walk': set([('d1',), ('b1',), ('g2',)]),
 'with': set([('b1', 'g1'), ('d1', 'b1'), ('b1', 'd1'), ('g1', 'b1')])}

2.2 Unit tests for function argument application in a Model

>>> v = [('adam', 'b1'), ('betty', 'g1'), ('fido', 'd1'),\
...      ('girl', set(['g1', 'g2'])), ('boy', set(['b1', 'b2'])), ('dog', set(['d1'])),
...      ('love', set([('b1', 'g1'), ('b2', 'g2'), ('g1', 'b1'), ('g2', 'b1')])),
...      ('kiss', null_binary_rel)]
>>> val = Valuation(v)
>>> dom = val.domain
>>> m = Model(dom, val)
>>> g = Assignment(dom)

>>> print app(val['boy'], 'b1')
True
>>> print app(val['boy'], 'g1')
False
>>> print app(val['boy'], 'foo')
False
>>> print app(val['love'], 'b1')
set([('g1',)])
>>> print app(val['kiss'], 'b1')
set([])
>>> print app(app(val['kiss'], 'b1'), 'b1')
False
>>> val.domain
set(['d1', 'g1', 'b1', 'b2', 'g2'])

3 Model Tests

Extension of Lambda expressions

>>> exprs = [
...     r'\x. \y. love(x, y)',
...     r'\x. dog(x) (adam)',
...     r'\x. (dog(x) | boy(x)) (adam)',
...     r'\x. \y. love(x, y)(fido)',
...     r'\x. \y. love(x, y)(adam)',
...     r'\x. \y. love(x, y)(betty)',
...     r'\x. \y. love(x, y)(betty)(adam)',
...     r'\x. \y. love(x, y)(betty, adam)',
...     r'\y. \x. love(x, y)(fido)(adam)',
...     r'\y. \x. love(x, y)(betty, adam)',
...     r'\x. exists y. love(x, y)',
...     r'\z. adam',
...     r'\z. love(x, y)'
...     ]

>>> v0 = [('adam', 'b1'), ('betty', 'g1'), ('fido', 'd1'),\
... ('girl', set(['g1', 'g2'])), ('boy', set(['b1', 'b2'])),
... ('dog', set(['d1'])),
... ('love', set([('b1', 'g1'), ('b2', 'g2'), ('g1', 'b1'), ('g2', 'b1')]))]

>>> val0 = Valuation(v0)
>>> dom0 = val0.domain
>>> m0 = Model(dom0, val0)
>>> g0 = Assignment(dom0)

>>> for e in exprs:
...     print e
...     print m0.evaluate(e, g0)
\x. \y. love(x, y)
{'g2': {'g2': False, 'b2': False, 'b1': True, 'g1': False, 'd1': False}, 'b2': {'g2': True, 'b2': False, 'b1': False, 'g1': False, 'd1': False}, 'b1': {'g2': False, 'b2': False, 'b1': False, 'g1': True, 'd1': False}, 'g1': {'g2': False, 'b2': False, 'b1': True, 'g1': False, 'd1': False}, 'd1': {'g2': False, 'b2': False, 'b1': False, 'g1': False, 'd1': False}}
\x. dog(x) (adam)
False
\x. (dog(x) | boy(x)) (adam)
True
\x. \y. love(x, y)(fido)
{'g2': False, 'b2': False, 'b1': False, 'g1': False, 'd1': False}
\x. \y. love(x, y)(adam)
{'g2': False, 'b2': False, 'b1': False, 'g1': True, 'd1': False}
\x. \y. love(x, y)(betty)
{'g2': False, 'b2': False, 'b1': True, 'g1': False, 'd1': False}
\x. \y. love(x, y)(betty)(adam)
True
\x. \y. love(x, y)(betty, adam)
True
\y. \x. love(x, y)(fido)(adam)
False
\y. \x. love(x, y)(betty, adam)
True
\x. exists y. love(x, y)
{'g2': True, 'b2': True, 'b1': True, 'g1': True, 'd1': False}
\z. adam
{'g2': 'b1', 'b2': 'b1', 'b1': 'b1', 'g1': 'b1', 'd1': 'b1'}
\z. love(x, y)
{'g2': False, 'b2': False, 'b1': False, 'g1': False, 'd1': False}

3.1 Propositional Model Test

>>> tests = [
...     ('p & q', True),
...     ('p & r', False),
...     ('- p', False),
...     ('- r', True),
...     ('- - p', True),
...     ('- (p & r)', True),
...     ('p | r', True),
...     ('r | p', True),
...     ('r | r', False),
...     ('- p | r', False),
...     ('p | - p', True),
...     ('p -> q', True),
...     ('p -> r', False),
...     ('r -> p', True),
...     ('p <-> p', True),
...     ('r <-> r', True),
...     ('p <-> r', False),
...     ]
>>> val = Valuation([('p', True), ('q', True), ('r', False)])
>>> dom = set([])
>>> m = Model(dom, val, prop=True)
>>> g = Assignment(dom)
>>> for (sent, testvalue) in tests:
...     semvalue = m.evaluate(sent, g)
...     if semvalue == testvalue:
...         print '*',
* * * * * * * * * * * * * * * * *

3.2 Test of i Function

>>> v = [('adam', 'b1'), ('betty', 'g1'), ('fido', 'd1'),
...      ('girl', set(['g1', 'g2'])), ('boy', set(['b1', 'b2'])), ('dog', set(['d1'])),
...      ('love', set([('b1', 'g1'), ('b2', 'g2'), ('g1', 'b1'), ('g2', 'b1')]))]
>>> val = Valuation(v)
>>> dom = val.domain
>>> m = Model(dom, val)
>>> g = Assignment(dom, [('x', 'b1'), ('y', 'g2')])
>>> exprs = ['adam', 'girl', 'love', 'walks', 'x', 'y', 'z']
>>> lp = LogicParser()
>>> parsed_exprs = [lp.parse(e) for e in exprs]
>>> for parsed in parsed_exprs:
...     try:
...         print "'%s' gets value %s" % (parsed, m.i(parsed, g))
...     except Undefined:
...         print "'%s' is Undefined" % parsed
'adam' gets value b1
'girl' gets value set([('g2',), ('g1',)])
'love' gets value set([('b1', 'g1'), ('b2', 'g2'), ('g1', 'b1'), ('g2', 'b1')])
'walks' is Undefined
'x' gets value b1
'y' gets value g2
'z' is Undefined

3.3 Test for formulas in Model

>>> tests = [
...     ('love(adam, betty)', True),
...     ('love(adam, sue)', 'Undefined'),
...     ('dog(fido)', True),
...     ('- dog(fido)', False),
...     ('- - dog(fido)', True),
...     ('- dog(sue)', 'Undefined'),
...     ('dog(fido) & boy(adam)', True),
...     ('- (dog(fido) & boy(adam))', False),
...     ('- dog(fido) & boy(adam)', False),
...     ('dog(fido) | boy(adam)', True),
...     ('- (dog(fido) | boy(adam))', False),
...     ('- dog(fido) | boy(adam)', True),
...     ('- dog(fido) | - boy(adam)', False),
...     ('dog(fido) -> boy(adam)', True),
...     ('- (dog(fido) -> boy(adam))', False),
...     ('- dog(fido) -> boy(adam)', True),
...     ('exists x . love(adam, x)', True),
...     ('all x . love(adam, x)', False),
...     ('fido = fido', True),
...     ('exists x . all y. love(x, y)', False),
...     ('exists x . (x = fido)', True),
...     ('all x . (dog(x) | - dog(x))', True),
...     ('adam = mia', 'Undefined'),
...     ('\\x. (boy(x) | girl(x))', {'g2': True, 'b2': True, 'b1': True, 'g1': True, 'd1': False}),
...     ('\\x. exists y. (boy(x) & love(x, y))', {'g2': False, 'b2': True, 'b1': True, 'g1': False, 'd1': False}),
...     ('exists z1. boy(z1)', True),
...     ('exists x. (boy(x) & - (x = adam))', True),
...     ('exists x. (boy(x) & all y. love(y, x))', False),
...     ('all x. (boy(x) | girl(x))', False),
...     ('all x. (girl(x) -> exists y. boy(y) & love(x, y))', False),
...     ('exists x. (boy(x) & all y. (girl(y) -> love(y, x)))', True),
...     ('exists x. (boy(x) & all y. (girl(y) -> love(x, y)))', False),
...     ('all x. (dog(x) -> - girl(x))', True),
...     ('exists x. exists y. (love(x, y) & love(x, y))', True),
...     ]
>>> for (sent, testvalue) in tests:
...     semvalue = m.evaluate(sent, g)
...     if semvalue == testvalue:
...         print '*',
...     else:
...         print sent, semvalue
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

3.4 Satisfier Tests

>>> formulas = [
...     'boy(x)',
...     '(x = x)',
...     '(boy(x) | girl(x))',
...     '(boy(x) & girl(x))',
...     'love(adam, x)',
...     'love(x, adam)',
...     '- (x = adam)',
...     'exists z22. love(x, z22)',
...     'exists y. love(y, x)',
...     'all y. (girl(y) -> love(x, y))',
...     'all y. (girl(y) -> love(y, x))',
...     'all y. (girl(y) -> (boy(x) & love(y, x)))',
...     'boy(x) & all y. (girl(y) -> love(x, y))',
...     'boy(x) & all y. (girl(y) -> love(y, x))',
...     'boy(x) & exists y. (girl(y) & love(y, x))',
...     'girl(x) -> dog(x)',
...     'all y. (dog(y) -> (x = y))',
...     '- exists y. love(y, x)',
...     'exists y. (love(adam, y) & love(y, x))'
...     ]
>>> g.purge()
>>> g.add('x', 'b1')
{'x': 'b1'}
>>> for f in formulas:
...     try:
...         print "'%s' gets value: %s" % (f, m.evaluate(f, g))
...     except Undefined:
...         print "'%s' is Undefined" % f
'boy(x)' gets value: True
'(x = x)' gets value: True
'(boy(x) | girl(x))' gets value: True
'(boy(x) & girl(x))' gets value: False
'love(adam, x)' gets value: False
'love(x, adam)' gets value: False
'- (x = adam)' gets value: False
'exists z22. love(x, z22)' gets value: True
'exists y. love(y, x)' gets value: True
'all y. (girl(y) -> love(x, y))' gets value: False
'all y. (girl(y) -> love(y, x))' gets value: True
'all y. (girl(y) -> (boy(x) & love(y, x)))' gets value: True
'boy(x) & all y. (girl(y) -> love(x, y))' gets value: False
'boy(x) & all y. (girl(y) -> love(y, x))' gets value: True
'boy(x) & exists y. (girl(y) & love(y, x))' gets value: True
'girl(x) -> dog(x)' gets value: True
'all y. (dog(y) -> (x = y))' gets value: False
'- exists y. love(y, x)' gets value: False
'exists y. (love(adam, y) & love(y, x))' gets value: True

3.5 Tests based on the Blackburn & Bos testsuite

>>> v1 = [('jules', 'd1'), ('vincent', 'd2'), ('pumpkin', 'd3'),
...       ('honey_bunny', 'd4'), ('yolanda', 'd5'),
...       ('customer', set(['d1', 'd2'])),
...       ('robber', set(['d3', 'd4'])),
...       ('love', set([('d3', 'd4')]))]
>>> val1 = Valuation(v1)
>>> dom1 = val1.domain
>>> m1 = Model(dom1, val1)
>>> g1 = Assignment(dom1)

>>> v2 = [('jules', 'd1'), ('vincent', 'd2'), ('pumpkin', 'd3'),
...       ('honey_bunny', 'd4'), ('yolanda', 'd4'),
...       ('customer', set(['d1', 'd2', 'd5', 'd6'])),
...       ('robber', set(['d3', 'd4'])),
...       ('love', set([(None, None)]))]
>>> val2 = Valuation(v2)
>>> dom2 = set(['d1', 'd2', 'd3', 'd4', 'd5', 'd6'])
>>> m2 = Model(dom2, val2)
>>> g2 = Assignment(dom2)
>>> g21 = Assignment(dom2)
>>> g21.add('y', 'd3')
{'y': 'd3'}

>>> v3 = [('mia', 'd1'), ('jody', 'd2'), ('jules', 'd3'),
...       ('vincent', 'd4'),
...       ('woman', set(['d1', 'd2'])), ('man', set(['d3', 'd4'])),
...       ('joke', set(['d5', 'd6'])), ('episode', set(['d7', 'd8'])),
...       ('in', set([('d5', 'd7'), ('d5', 'd8')])),
...       ('tell', set([('d1', 'd5'), ('d2', 'd6')]))]
>>> val3 = Valuation(v3)
>>> dom3 = set(['d1', 'd2', 'd3', 'd4', 'd5', 'd6', 'd7', 'd8'])
>>> m3 = Model(dom3, val3)
>>> g3 = Assignment(dom3)

>>> tests = [
...     ('exists x. robber(x)', m1, g1, True),
...     ('exists x. exists y. love(y, x)', m1, g1, True),
...     ('exists x0. exists x1. love(x1, x0)', m2, g2, False),
...     ('all x. all y. love(y, x)', m2, g2, False),
...     ('- (all x. all y. love(y, x))', m2, g2, True),
...     ('all x. all y. - love(y, x)', m2, g2, True),
...     ('yolanda = honey_bunny', m2, g2, True),
...     ('mia = honey_bunny', m2, g2, 'Undefined'),
...     ('- (yolanda = honey_bunny)', m2, g2, False),
...     ('- (mia = honey_bunny)', m2, g2, 'Undefined'),
...     ('all x. (robber(x) | customer(x))', m2, g2, True),
...     ('- (all x. (robber(x) | customer(x)))', m2, g2, False),
...     ('(robber(x) | customer(x))', m2, g2, 'Undefined'),
...     ('(robber(y) | customer(y))', m2, g21, True),
...     ('exists x. (man(x) & exists x. woman(x))', m3, g3, True),
...     ('exists x. (man(x) & exists x. woman(x))', m3, g3, True),
...     ('- exists x. woman(x)', m3, g3, False),
...     ('exists x. (tasty(x) & burger(x))', m3, g3, 'Undefined'),
...     ('- exists x. (tasty(x) & burger(x))', m3, g3, 'Undefined'),
...     ('exists x. (man(x) & - exists y. woman(y))', m3, g3, False),
...     ('exists x. (man(x) & - exists x. woman(x))', m3, g3, False),
...     ('exists x. (woman(x) & - exists x. customer(x))', m2, g2, 'Undefined'),
... ]

>>> for item in tests:
...     sentence, model, g, testvalue = item
...     semvalue = model.evaluate(sentence, g)
...     if semvalue == testvalue:
...         print '*',
...     g.purge()
* * * * * * * * * * * * * * * * * * * * * *

3.6 Tests for mapping from syntax to semantics

Load a valuation from a file.

>>> from nltk.parse import FeatureEarleyChartParser
>>> import nltk.data
>>> grammar = nltk.data.load('grammars/sem2.fcfg')
>>> val = nltk.data.load('grammars/valuation1.val')
>>> dom = val.domain
>>> m = Model(dom, val)
>>> g = Assignment(dom)

>>> inputs = ['John sees a girl', 'every dog barks']
>>> for s in inputs:
...     print
...     print "Sentence: %s" % s
...     for tree in text_parse(inputs, grammar)[s]:
...         print "Parse:\n %s" %tree
...     print "Semantics: %s" %  root_semrep(tree)

Sentence: John sees a girl
Parse:
 (S[sem=<exists x.(girl(x) & see(john,x))>]
  (NP[-loc, num='sg', sem=<\P.P(john)>]
    (PropN[-loc, num='sg', sem=<\P.P(john)>] John))
  (VP[num='sg', sem=<\y.exists x.(girl(x) & see(y,x))>]
    (TV[num='sg', sem=<\X.\y.X(\x.see(y,x))>, tns='pres'] sees)
    (NP[num='sg', sem=<\Q.exists x.(girl(x) & Q(x))>]
      (Det[num='sg', sem=<\P.\Q.exists x.(P(x) & Q(x))>] a)
      (Nom[num='sg', sem=<girl>] (N[num='sg', sem=<girl>] girl)))))
Semantics: exists x.(girl(x) & see(john,x))

Sentence: every dog barks
Parse:
 (S[sem=<all x.(dog(x) -> bark(x))>]
  (NP[num='sg', sem=<\Q.all x.(dog(x) -> Q(x))>]
    (Det[num='sg', sem=<\P.\Q.all x.(P(x) -> Q(x))>] every)
    (Nom[num='sg', sem=<dog>] (N[num='sg', sem=<dog>] dog)))
  (VP[num='sg', sem=<\x.bark(x)>]
    (IV[num='sg', sem=<\x.bark(x)>, tns='pres'] barks)))
Semantics: all x.(dog(x) -> bark(x))

>>> sent = "every dog barks"
>>> result = nltk.sem.text_interpret([sent], grammar)
>>> for (syntree, semrep) in result[sent]:
...     print syntree
...     print
...     print semrep
(S[sem=<all x.(dog(x) -> bark(x))>]
  (NP[num='sg', sem=<\Q.all x.(dog(x) -> Q(x))>]
    (Det[num='sg', sem=<\P.\Q.all x.(P(x) -> Q(x))>] every)
    (Nom[num='sg', sem=<dog>] (N[num='sg', sem=<dog>] dog)))
  (VP[num='sg', sem=<\x.bark(x)>]
    (IV[num='sg', sem=<\x.bark(x)>, tns='pres'] barks)))

all x.(dog(x) -> bark(x))

>>> result = nltk.sem.text_evaluate([sent], grammar, m, g)
>>> for (syntree, semrel, value) in result[sent]:
...     print syntree
...     print
...     print semrep
...     print
...     print value
(S[sem=<all x.(dog(x) -> bark(x))>]
  (NP[num='sg', sem=<\Q.all x.(dog(x) -> Q(x))>]
    (Det[num='sg', sem=<\P.\Q.all x.(P(x) -> Q(x))>] every)
    (Nom[num='sg', sem=<dog>] (N[num='sg', sem=<dog>] dog)))
  (VP[num='sg', sem=<\x.bark(x)>]
    (IV[num='sg', sem=<\x.bark(x)>, tns='pres'] barks)))

all x.(dog(x) -> bark(x))

True