Chaining two partial operations gives the same results in either bracketing when the operations agree pointwise.
Docs / Logic / Natural / Relation
The seven relations of natural logic
import Linglib.Logic.Natural.Relation · namespace NaturalLogic
MacCartney and Manning relate denotations by equivalence ≡, forward and reverse entailment ⊑
and ⊒, negation ^, alternation |, cover ⌣ and independence #. Following Icard, each
relation is a conjunction of atomic lattice constraints, x ≤ y, y ≤ x, disjointness and
codisjointness, so that ≡ also satisfies ⊑ and the relations are ordered by implication;
MacCartney and Manning's mutually exclusive relations are their strict versions. The join R ⋈ S,
the strongest relation that R followed by S guarantees, makes the relations a monoid, and it
is sound over distributive lattices.
References
- MacCartney & Manning 2009, An extended model of natural logic formalized
- Icard 2012, Inclusion and Exclusion in Natural Language formalized
Declarations
The seven relations
The seven natural-logic relations between denotations.
- equiv : Relation
Equivalence
≡holds when the denotations coincide (couch / sofa). - forward : Relation
Forward entailment
⊑holds whenA ⊆ B(dog / animal). - reverse : Relation
Reverse entailment
⊒holds whenA ⊇ B(animal / dog). - negation : Relation
Negation
^holds when the denotations are disjoint and exhaustive (happy / unhappy). - alternation : Relation
Alternation
|holds when the denotations are disjoint (cat / dog). - cover : Relation
Cover
⌣holds when the denotations are exhaustive (animal / nondog). - independent : Relation
Independence
#imposes no constraint (hungry / tall).
Derives DecidableEq, Fintype, Repr.
Instances NaturalLogic.ProjectivitySignature.instFaithfulSMulRelation, NaturalLogic.ProjectivitySignature.instMulActionRelation, NaturalLogic.ProjectivitySignature.instSMulRelation
Used by Relation.constraints, Relation.ofAtoms, Relation.instPartialOrder, Relation.le_iff, Relation.instDecidableLE, Relation.instOrderTop, Relation.join, Relation.instMul, Relation.instOne, Relation.mem_constraints_mul, Relation.instMonoid, Relation.top_mul, Relation.mul_top, Relation.converse, Relation.converse_converse, Relation.Holds, Relation.holds_iff, Relation.holds_converse, Relation.decidableHolds, Relation.Holds.of_le, Relation.Holds.apply, Relation.Holds.join
Used in Logic/Natural/Completeness, Logic/Natural/ImplicationSignature, Logic/Natural/Projection, Icard2012, MacCartneyManning2009
The atomic lattice constraints a relation can impose (Icard 2012 Definition 1.2).
Derives DecidableEq, Fintype, Repr.
Used by Relation.constraints, Relation.ofAtoms, Relation.Atom.join, Relation.join, Relation.mem_constraints_mul, Relation.Atom.Holds, Relation.Atom.decidableHolds, Relation.Atom.Holds.join
Used in Logic/Natural/Completeness, Logic/Natural/ImplicationSignature, Logic/Natural/Projection
The atomic constraints a relation asserts, {le, ge} for ≡, {disjoint, codisjoint} for ^
and ∅ for #. A relation holds iff all its constraints do (Relation.holds_iff), and of the
sixteen constraint sets exactly these seven are nondegenerately realizable
(Relation.mem_range_constraints_iff in Logic/Natural/Completeness.lean).
- Relation.equiv.constraints = {Relation.Atom.le, Relation.Atom.ge}
- Relation.forward.constraints = {Relation.Atom.le}
- Relation.reverse.constraints = {Relation.Atom.ge}
- Relation.negation.constraints = {Relation.Atom.disjoint, Relation.Atom.codisjoint}
- Relation.alternation.constraints = {Relation.Atom.disjoint}
- Relation.cover.constraints = {Relation.Atom.codisjoint}
- Relation.independent.constraints = ∅
Built from ,
Used by Relation.constraints_injective, Relation.instPartialOrder, Relation.le_iff, Relation.instDecidableLE, Relation.join, Relation.mem_constraints_mul, Relation.holds_iff
Used in Logic/Natural/Completeness, Logic/Natural/ImplicationSignature, Logic/Natural/Projection, MacCartneyManning2009
Built from
The strongest relation all of whose constraints satisfy P, found by trying the relations
from the strongest down to #, which has none. When the atoms satisfying P are the constraints
of a relation, it is that relation.
The definition is too large to print here; read it in the source.
Built from ,
Used by Relation.join
In the implication order (Icard 2012's ≪), R ≤ R' iff xRy entails xR'y, i.e. iff the
constraints of R' are among those of R (Relation.Holds.of_le). It consists of two diamonds
sharing only the top #, one with ≡ below ⊑ and ⊒, the other with ^ below | and ⌣;
there is no bottom, since x = y makes x and y neither disjoint nor exhaustive. The most
informative relation, which Icard 2012 calls ≪-maximal, is the least one in this order.
- Relation.instPartialOrder = PartialOrder.lift (fun (R : Relation) => OrderDual.toDual R.constraints) Relation.instPartialOrder._proof_1
Built from ,
Built from ,
- x✝¹.instDecidableLE x✝ = decidable_of_iff (x✝.constraints ⊆ x✝¹.constraints) ⋯
Built from ,
- Relation.instOrderTop = { top := Relation.independent, le_top := Relation.instOrderTop._proof_1 }
Built from
The constraint between x and z that a constraint between x and y and one between y
and z guarantee, when there is one (Relation.Atom.Holds.join):
≤ and ≥ are transitive, disjointness is inherited downward and codisjointness upward, and,
in a distributive lattice, x disjoint from y and y codisjoint with z give x ≤ z.
Equations
- Relation.Atom.le.join Relation.Atom.le = some Relation.Atom.le
- Relation.Atom.ge.join Relation.Atom.ge = some Relation.Atom.ge
- Relation.Atom.le.join Relation.Atom.disjoint = some Relation.Atom.disjoint
- Relation.Atom.disjoint.join Relation.Atom.ge = some Relation.Atom.disjoint
- Relation.Atom.ge.join Relation.Atom.codisjoint = some Relation.Atom.codisjoint
- Relation.Atom.codisjoint.join Relation.Atom.le = some Relation.Atom.codisjoint
- Relation.Atom.disjoint.join Relation.Atom.codisjoint = some Relation.Atom.le
- Relation.Atom.codisjoint.join Relation.Atom.disjoint = some Relation.Atom.ge
- x✝¹.join x✝ = none
Built from
Used by Relation.join, Relation.mem_constraints_mul, Relation.Atom.Holds.join
The join R ⋈ R' (Icard 2012, Lemma 1.5) is the strongest relation guaranteed between x
and z given xRy and yR'z, the relation asserting what the atom rule gives for each pair of
constraints of R and R' (Relation.mem_constraints_mul). It approximates relational
composition, which MacCartney & Manning 2009 call join after the database operation; it is not the
lattice join.
Each cell is sound (Relation.Holds.join) and is the least
sound relation (Relation.isLeast_join in Logic/Natural/Completeness.lean), as Icard 2012's
Definition 1.4 requires. Exact composition is a union of the seven relations on 17 of the 49 cells
(MacCartney & Manning 2009 §3), and this gives the best single relation there.
- R.join S = Relation.ofAtoms fun (c : Relation.Atom) => ∃ a ∈ R.constraints, ∃ b ∈ S.constraints, a.join b = some c
Built from , , , ,
Used by Relation.instMul
Used in Logic/Natural/Completeness
- Relation.instMul = { mul := Relation.join }
Built from ,
- Relation.instOne = { one := Relation.equiv }
Built from
Built from , , ,
The relations form a monoid under ⋈ with identity ≡. The identity and absorption laws are
printed in Icard 2012 (p. 710); associativity, printed in neither Icard 2012 nor
MacCartney & Manning 2009, is that of the atom rule. The monoid is not commutative, since ^ ⋈ ⌣ = ⊑ but ⌣ ⋈ ^ = ⊒.
The definition is too large to print here; read it in the source.
Built from
The converse of a relation, holding of x and y when the relation holds of y and x
(Relation.holds_converse): ⊑ and ⊒ exchange, and the other five are symmetric.
- Relation.forward.converse = Relation.reverse
- Relation.reverse.converse = Relation.forward
- x✝.converse = x✝
Built from
Used by Relation.converse_converse, Relation.holds_converse
Used in MacCartneyManning2009
Lattice content of the relations
The lattice content of a natural-logic relation (Icard 2012
Definition 1.2), in mathlib's complementation vocabulary: negation is
IsCompl, alternation is Disjoint, cover is Codisjoint; forward
is non-strict ≤ (MacCartney's exclusive reading takes it proper, which
the projectivity tables do not need).
- Relation.equiv.Holds = fun (x1 x2 : α) => x1 = x2
- Relation.forward.Holds = fun (x1 x2 : α) => x1 ≤ x2
- Relation.reverse.Holds = fun (x1 x2 : α) => x1 ≥ x2
- Relation.negation.Holds = IsCompl
- Relation.alternation.Holds = Disjoint
- Relation.cover.Holds = Codisjoint
- Relation.independent.Holds = fun (x x_1 : α) => True
Built from
Used by Relation.holds_iff, Relation.holds_converse, Relation.decidableHolds, Relation.Holds.of_le, Relation.Holds.apply, Relation.Holds.join
Used in Logic/Natural/Completeness, Logic/Natural/Projection, Icard2012, MacCartneyManning2009
The lattice content of an atomic constraint (Icard 2012 Definition 1.2).
- Relation.Atom.le.Holds = fun (x1 x2 : α) => x1 ≤ x2
- Relation.Atom.ge.Holds = fun (x1 x2 : α) => x1 ≥ x2
- Relation.Atom.disjoint.Holds = Disjoint
- Relation.Atom.codisjoint.Holds = Codisjoint
Built from
Used by Relation.holds_iff, Relation.Atom.decidableHolds, Relation.Atom.Holds.join
Used in Logic/Natural/Completeness, Logic/Natural/ImplicationSignature, Logic/Natural/Projection, MacCartneyManning2009
Built from , , ,
- Relation.Atom.le.decidableHolds x✝¹ x✝ = Relation.Atom.decidableHolds._aux_1 x✝¹ x✝
- Relation.Atom.ge.decidableHolds x✝¹ x✝ = Relation.Atom.decidableHolds._aux_3 x✝¹ x✝
- Relation.Atom.disjoint.decidableHolds x✝¹ x✝ = decidable_of_iff (x✝¹ ⊓ x✝ = ⊥) ⋯
- Relation.Atom.codisjoint.decidableHolds x✝¹ x✝ = decidable_of_iff (x✝¹ ⊔ x✝ = ⊤) ⋯
Built from ,
Equations
- Relation.equiv.decidableHolds x✝¹ x✝ = Relation.decidableHolds._aux_1 x✝¹ x✝
- Relation.forward.decidableHolds x✝¹ x✝ = Relation.decidableHolds._aux_3 x✝¹ x✝
- Relation.reverse.decidableHolds x✝¹ x✝ = Relation.decidableHolds._aux_5 x✝¹ x✝
- Relation.negation.decidableHolds x✝¹ x✝ = decidable_of_iff (x✝¹ ⊓ x✝ = ⊥ ∧ x✝¹ ⊔ x✝ = ⊤) ⋯
- Relation.alternation.decidableHolds x✝¹ x✝ = decidable_of_iff (x✝¹ ⊓ x✝ = ⊥) ⋯
- Relation.cover.decidableHolds x✝¹ x✝ = decidable_of_iff (x✝¹ ⊔ x✝ = ⊤) ⋯
- Relation.independent.decidableHolds x✝¹ x✝ = isTrue trivial
Built from ,
Relation-level order soundness: ≤ is the implication order on
the lattice content (Icard 2012 §1).
Built from ,
Join soundness
The atom rule is sound: chained constraints give the constraint Relation.Atom.join says.
Distributivity is needed for a disjoint pair followed by a codisjoint one, which gives ≤.
Built from , ,
Chained relations compose as the join says, constraint by constraint.
Built from ,