Re: Richard J. Lipton • Logical Complexity Of Proofs

Another dimension of proof style has to do with how much information is kept or lost as the argument develops.  For the moment let’s focus on classical deductive reasoning at the propositional level.  Then we can distinguish between equational inferences, which keep all the information represented by the input propositions, and implicational inferences, which permit information to be lost as the proof proceeds.

Information-Preserving vs. Information-Reducing Inferences

Implicit in Peirce’s systems of logical graphs is the ability to use equational inferences.  Spencer Brown drew this out and turned it to great advantage in his revival of Peirce’s graphical forms.  As it affects “logical flow” this allows for bi-directional or reversible flows, you might even say a “logical equilibrium” between two states of information.

It is probably obvious when we stop to think about it, but seldom remarked, that all the more familiar inference rules, like modus ponens and resolution or transitivity, entail in general a loss of information as we traverse their arrows or turnstiles.

For example, the usual form of modus ponens takes us from knowing and to knowing but in fact we know more, we actually know   With that in mind we can formulate two variants of modus ponens, one reducing and one preserving the actual state of information, as shown in the following figure.

There’s more discussion of this topic at the following location.

• Propositional Equation Reasoning Systems • Computation and Inference as Semiosis

To be continued …

Resources

• Logic Syllabus
• Logical Graphs
• Cactus Language
• Futures Of Logical Graphs
• Minimal Negation Operators
• Survey of Theme One Program
• Survey of Animated Logical Graphs
• Propositional Equation Reasoning Systems

Applications

• Applications of a Propositional Calculator • Constraint Satisfaction Problems
• Exploratory Qualitative Analysis of Sequential Observation Data

cc: Cybernetics • Ontolog • Peirce (1) (2) (3) (4) (5) (6) • Structural Modeling • Systems