ProofTheoryPresentation.md

Syllogistic Logics with ‘More Than’ and ‘Most’

The Natural Logic Program

• Aristotle, Van Benthem, Moss

• Natural language inference

  • No translating into FOL

• Special-purpose logic engineering

  • Complete and decidable logics
  • 5 different systems in this talk alone!

Logics about Size Comparison

• Restricted domain: Reasoning about sizes
• Why not embed into FOL with Arithmetic?
  • Decidable $\to$ More cognitively plausible
  • Light $\to$ More cognitively plausible
  • Counting is not needed:
    • “There is more sand than water in the pond”

$\mathcal{S(card)}$: Syllogistic + ‘More Than’ + ‘At Least as Many’

• $a, b, c, ...$ are nouns

• $all(a, b)$

• $some(a, b)$

• $more(a, b)$

• $atLeast(a, b)$

• No connectives $\and, \or \neg$

• No quantifiers $\forall, \exists$

$\mathcal{S(card)}$: Semantics

• Models: $\mathcal{M}$ consisting of set $M$.

• For all nouns $a$, $[![a]!] \sube M$

• $\mathcal{M} \vDash all(a, b)$             iff $[![a]!] \sube [![b]!]$

• $\mathcal{M} \vDash some(a, b)$        iff $[![a]!] \cap [![b]!] \ne \empty$

• $\mathcal{M} \vDash more(a, b)$        iff $|[![a]!]| \gt |[![b]!]|$

• $\mathcal{M} \vDash atLeast(a, b)$   iff $|[![a]!]| \ge |[![b]!]|$

• $\Gamma \vDash \varphi$ iff every FINITE model $\mathcal{M}$ which satisfies $\Gamma$ satisfies $\varphi$.

$\mathcal{S(card)}$: Natural Deduction Rules

See board

$\mathcal{S(card)}$: Completeness Theorem

Theorem: $\mathcal{S(card)}$ is complete, i.e. $\Gamma \vDash \varphi$ iff $\Gamma \vdash \varphi$.

• From Larry Moss’ “Syllogistic Logic with Cardinality Comparisons”

$\mathcal{S^\dagger(card)}$:  $\mathcal{S(card)}$ + Noun Complement

• For a noun $a$, we allow $a$ to be complemented: $\bar a$
• $\bar{\bar{a}} = a$ at syntax level
• Semantics: $[![\bar a]!] = M \setminus [![a]!]$
• Rules of Inference:
  • See board

$\mathcal{S^\dagger(card)}$: Completeness Theorem

Theorem: $\mathcal{S^{\dagger}(card)}$ is complete, i.e. $\Gamma \vDash \varphi$ iff $\Gamma \vdash \varphi$.

• More complicated than the proof for $\mathcal{S(card)}$!

Bonus Theorem: $\mathcal{S^{\dagger}(card)}$ is decidable in polynomial time!

$\mathcal{S(most)}$: Syllogistic + ‘Most’

• $all(a, b)$

• $some(a, b)$

• $most(a, b)$

• $\mathcal{M} \vDash most(a, b)$ iff $|[![a]!] \cap [![b]!]| \gt \dfrac{1}{2}[![a]!]$

$\mathcal{S(most)}$: Natural Deduction Rules

See board

Theorem: $\mathcal{S(most)}$ is complete. -- and decidable in polynomial time!

The Hierarchy of Syllogistic Logics

$\mathcal{All}$

 $\big \downarrow$

$\mathcal{S}$        $\to$        $\mathcal{S(most)}$

 $\big \downarrow$                    $\big \downarrow$

$\mathcal{S(card)}$         $\big \downarrow$

 $\big \downarrow$                    $\big \downarrow$

$\mathcal{S^{\dagger}(card)}$ $\to$ Holy Grail

• We want a complete logic involving ‘more than’ and ‘most’

• Can’t just combine rules, because of interplay between ‘more than’ and ‘most’

A Solution: Complement and Intersection

• $$most(a, b) \equiv more(a \cap b, a \cap \bar b)$$

• So we need noun complement and noun intersection

• It is easier to make rules for Union $\cup$

  • $a \cap b \equiv \overline{\bar a \cap \bar b}$

$\mathcal{S^{\cup}(card)}$: $\mathcal{S(card)}$ + Noun Union

• For base nouns $a, b$, we allow $a$ and $b$ to be unioned: $$a \cup b$$
• We assume laws of boolean algebra at syntax level (?)
• Semantics: $$[![a \cup b]!] = [![a]!] \cup [![b]!]$$
• Rules of Inference:
  • See board

Conjecture: The set of rules given above for $\mathcal{S^{\cup}(card)}$ is complete.

$\mathcal{S^{\dagger \cup}(card)}$: $\mathcal{S(card)}$ + Noun Union + Noun Complement

• The Holy Grail!
• What is a complete set of rules?
  • Can’t just haphazardly combine $\mathcal{S^{\dagger}(card)}$ and $\mathcal{S^{\cup}(card)}$

$\mathcal{S^{\dagger \cup}(card)}$: Proposed Rules

See board

• We can derive the first 6 ‘most’ rules already!
  • Remember that infinite schema!