Animated Logical Graphs • 36

Re: Richard J. LiptonLogical Complexity Of Proofs

Dear Dick,

You asked, “Is this measure, the logical flow of a proof, of any interest?”

I was not sure how you define the measure of flow in a proof — it seemed to have something to do with the number of implication arrows in the argument structure?

But this does bring up interesting issues of “proof style” …

Propositional calculus as a formal language and boolean functions as an object domain form an instructive microcosm for many issues of logic writ large.  The relation between proof theory and model theory is one of those issues, the status of propositional logic as a special case notwithstanding.

Folks who pursue the CSP–GSB line of development in graphical syntax for propositional calculus are especially likely to notice the following dimensions of proof style.

Formal Duality
This goes back to Peirce’s discovery of the “amphecks” as sole sufficient primitives for propositional calculus and the duality between Both Not (nnor) and Not Both (nand).  The same duality is present in Peirce’s graphical systems for propositional calculus.  It is analogous to the duality in projective geometry and it means we are always proving two theorems for the price of one.  That’s a reduction in complexity — it raises the question of how many such group-theoretic reductions we can find.

To be continued …



cc: CyberneticsOntolog • Peirce (1) (2) (3) (4) (5) (6)Structural ModelingSystems

This entry was posted in Amphecks, Animata, Boolean Algebra, Boolean Functions, C.S. Peirce, Cactus Graphs, Constraint Satisfaction Problems, Deduction, Diagrammatic Reasoning, Duality, Equational Inference, Graph Theory, Laws of Form, Logic, Logical Graphs, Mathematics, Minimal Negation Operators, Model Theory, Painted Cacti, Peirce, Proof Theory, Propositional Calculus, Propositional Equation Reasoning Systems, Spencer Brown, Theorem Proving, Visualization and tagged , , , , , , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to Animated Logical Graphs • 36

  1. Pingback: Survey of Animated Logical Graphs • 3 | Inquiry Into Inquiry

  2. Pingback: Animated Logical Graphs • 39 | Inquiry Into Inquiry

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.