If both the antecedent of the major premise, e. g. one having form C
If the antecedent of the major premise
and the minor premise
Often enough though, we only need to make one substitution in exclusively the major or the minor premise to expand the condensed detachment proof into a substitution and detachment proof. Thus, we require only two steps for an expansion of the condensed detachment proof into the corresponding substitution and detachment proof; a simultaneous substitution and a detachment.
Meta-Theorem 1: If exclusively the antecedent of the major premise or the minor premise have exactly one instance of any propositional variable throughout the antecedent or the major premise respectively, then for any condensed detachment proof, there exists a two line substitution and detachment proof.
Meta-Proof: A most general unifier can get found simply by substituting each variable in the antecedent of the major premise or in the minor premise whichever satisfies the hypothesis. Consequently, the substitution and detachment proof will only need one simultaneous substitution to make a detachment. Since the detachment qualifies as a step also, that makes for a two line proof as was to get metalogically demonstrated.
Meta-Corollary 1: Systems with formulas of any of the following: CpCqp, CCCpqrCqr, CCCpqqCCqpp, CCCpqrCCprr, CCCpqrCCrpp, CCpqCCqrCpr, CCpqCCrpCrq, CCpCqrCqCpr, CpCCpqq, CCpqCCCprqq, CpCCNqNpq and possibly many more do not have a last theorem under condensed detachment.
Discussion: This size of the question space is a bit small to contain much of a meta-proof. But, to see how this works fix the formula selected under condensed detachment and call it a. For formulas which have a in the antecedent, the meta-corollary follows directly from Meta-Theorem 1. For some others, the antecedent of a has bracket type C
Given a condensed detachment proof, let us call the number of steps (lines in a proof) in any of the shortest corresponding substitution and detachment proofs, the condensed detachment expansion number, CoDEN, of a condensed detachment proof of a formula P, CoDEN(
Now, suppose we had a large number of condensed detachment proofs in classical propositional calculi... I don't know maybe a million or a billion or maybe just a hundred, or even just a few proof. What is the value of CoDEN over all of those proofs? If we took the limit of all formal proofs as n gets larger and larger, would CoDEN converge to a rational number or transcendental number? What would make for a suitable upper estimate and a lower estimate for CoDEN if using it to predicate the length of a minimal substitution and detachment proof from a condensed detachment proof? I'll guess between 2.0 and 2.5. Does it matter which set of formal proofs we select? Does selecting theories which have their formal theorems contained in classical propositional logic substantially alter the value of CoDEN? Using a program that I wrote, and perhaps I'll analyze some other proofs, the value of CoDEN for the proof here is 2.25.
Related paper
No comments:
Post a Comment