Condensed Detachment
Condensed Detachment (Rule D) is a method of finding the most general possible conclusion given two formal logical statements. It was developed by the Irish Logician Carew Meredith in the 1950s and inspired by the work of Łukasiewicz.
Informal description
A rule of detachment says:
Given that <math>p \,\!</math> implies <math>q \,\!</math>, and given <math>p \to\,\!</math> produces <math>q \,\!</math>.
The condensed detachment goes a step further and says:
Given that <math>p \,\!</math> implies <math>q \,\!</math>, and given an <math>r \to\,\!</math> produces the most general possible result of substitutions into <math>q \,\!</math> and <math>r \,\!</math> followed by a standard rule of detachments.
For substitution A that when applied to <math>p \,\!</math> produces <math>t \,\!</math>, and substitution B that when applied to <math>r \,\!</math> produces <math>t \,\!</math>, are called the Unifiers of <math>p \,\!</math> and <math>q \,\!</math>.
Various unifiers may produce expressions with varying numbers of free variables. Some possible unifying expression are substitution instances of others. If one expression is a substitution instance of another (and not just a variable renaming), then that other is called "more general".
If the most general unifier is used in Condensed Detachment, then the logical result is the most general conclusion that can be made in the given inference with the given second expression. (And since any weaker inference you can get is a substitution instance of the most general one, nothing less than the most general unifier is ever used in practice.)
In some logics (such as standard PC) have a set of defining axioms with the "D-completeness" property. Any conclusion that can be arrived at by a sequence of uniform substitution and Modus Ponens steps can either be done as a sequence of Condensed Detachment steps, or is a substitution instance of something that can be.
((((A implies B)implies((not C)implies(not D)))implies C)implies E)implies((E implies A)implies(D implies A))
D-notation
Since a given major premise and a given minor premise uniquely determine the conclusion (up to variable renaming), Meredith observed that it was only necessary to note which two statements were involved and that the condensed detachment can be used without any other notation required. This led to the "D-notation" for proofs. This notation uses the "D" operator to mean condensed detachment, and takes 2 arguments, in a standard prefix notation string. For example:
D D 1 2 D 3 4
shows a condensed detachment step using the result of two prior condensed detachment steps, the first of which used axioms 1 and 2, and the second of which used axioms 3 and 4.
This notation, besides being used in some automated theorem provers, sometimes appears in catalogs of proofs
Condensed detachment's use of Unification predates the resolution techniques of automated theorem proving.
References
- BCK and BCI logics, condensed detachment and the $2$-property by J. Roger Hindley, Notre Dame Journal of Formal Logic 34, no. 2 (1993), 231–250
- Experiments in Automated Deduction with Condensed Detachment, William McCune and Larry Wos, Proceedings of the 11th International Conference on Automated Deduction (1992)
- http://www.mathsci.appstate.edu/~jlh/primer/hirst.pdf A Primer for Logic and Proof (2004)