Connection To Intuitionistic Logic
The combinators K and S correspond to two well-known axioms of sentential logic:
AK: A (B A),
AS: (A (B C)) ((A B) (A C)).
Function application corresponds to the rule modus ponens:
MP: from A and A B, infer B.
The axioms AK and AS, and the rule MP are complete for the implicational fragment of intuitionistic logic. In order for combinatory logic to have as a model:
- The implicational fragment of classical logic, would require the combinatory analog to the law of excluded middle, e.g., Peirce's law;
- Complete classical logic, would require the combinatory analog to the sentential axiom F A.
Read more about this topic: SKI Combinator Calculus
Famous quotes containing the words connection and/or logic:
“Children of the same family, the same blood, with the same first associations and habits, have some means of enjoyment in their power, which no subsequent connections can supply; and it must be by a long and unnatural estrangement, by a divorce which no subsequent connection can justify, if such precious remains of the earliest attachments are ever entirely outlived.”
—Jane Austen (1775–1817)
“What avail all your scholarly accomplishments and learning, compared with wisdom and manhood? To omit his other behavior, see what a work this comparatively unread and unlettered man wrote within six weeks. Where is our professor of belles-lettres, or of logic and rhetoric, who can write so well?”
—Henry David Thoreau (1817–1862)