🚀 go-pugleaf

In article <1992Nov11.225953.231@galois.mit.edu> jbaez@riesz.mit.edu (John C. Baez) writes:
>In article <BxGFw2.AJv@cck.coventry.ac.uk> esz001@cck.coventry.ac.uk (Will Overington) writes:
>
>>Can I ask please, is syllogisms and the like what sci.logic is about,
>>or am I missing something fundamental.
>
>Syllogisms are what logicians were up to in the Middle Ages, and there's
>a lot of interesting stuff that has happened since.  (Actually logicians
>were already doing lots of other stuff in the Middle Ages.)  In the late
>1800's a study of the "foundations of mathematics" and logic began which
>led to a lot of spectacular results in this century, such as Goedel's
>theorems.  For a tour of logic you could do worse than to take a peek at
>the entries about logic in the Encyclopedia of Philosophy.  And you can
>read sci.logic to see what sorts of things people argue about.

Must reading on this is Peter Heath's introduction to his anthology of
Augustus De Morgan's "On the Syllogism, and Other Logical Writings",
Routledge and Kegan Paul, London, 1966.  It is one of the best accounts
available of the great battle between De Morgan and Sir William
Hamilton, professor of logic at Edinburgh (not to be confused with
William *Rowan* Hamilton of Ireland, he of the Hamiltonian).  (You can
also read the relevant issues of the Athaenium for 1847 for more
first-hand details by the participants themselves; 19th century prose
but very heated nonetheless.)

De Morgan was the first and last mathematician to take a really serious
look at syllogisms.  The battle with Hamilton prompted Boole to write
up his thoughts on the subject of logic, and within thirty years the
research potential of syllogisms had died, replaced by Boolean logic as
interpreted by Peirce, Jevons, Schroeder, and others.  The 24
syllogisms continued to be taught sporadically for another century,
indeed my first encounter with logic was when my high school swimming
coach lent me his freshman logic text, which confined itself to
syllogisms!

Syllogistic reasoning works with four forms: XaY, XeY, XiY, XoY,
respectively all X are Y, no X are Y, some X are Y, some X are not Y.
Various combinations yield various conclusions; the 24 standard ones
have such mnemonic names as Barbara (from YaZ and XaY infer XaZ) and
Celarent (from YeZ and XaY infer XeZ).  Sound boring?  You got it.

Because of the two existential forms XiY and XoY, syllogistic reasoning
does not reduce to Boolean logic.  Lewis Carroll published a series of
progressively longer syllogisms in his newspaper column, all of which
were universal and so decidable by purely propositional means (and I
imagine in polynomial time, unlike full Boolean logic).  However full
syllogistic logic is also decidable, being a fragment of unary
predicate logic, which is complete in deterministic exponential time.

I do not know of tight bounds for the complexity of syllogistic
reasoning, can someone supply these?  I would expect it to be decidable
in polynomial time, since it should be straightforward to eliminate
premises sequentially and deterministically.  Note that Carroll's forms
although universal tended to step outside the X*Y form by often writing
sentences that had to be rendered as (X&Y)*Y to solve the syllogism;
hence it is conceivable that Carroll's syllogisms are harder than
ordinary syllogisms.  This should not be difficult to resolve.
-- 
Vaughan Pratt				Formal logic and casual fallacy