Formal Mathematical Systems
What is Formalism
Formalim is a philosophy which identifies Mathematics as an instrument composed of a set of rules, and aiding in solving real-world problems. The principle of operation of Formal Systems is in contrast to the ideas of Abstract Mathematics. The latter extends far into the spheres of intangibility and ‘unrealness’, like the Mandelbrot’s Set. The former, Formal Systems are by nature, synthetic. Like the rules of a game of Chess. This distinction is with what a mathematician may identify himself as formalist and purist. Purists look at Mathematics as being embedded in Nature, giving itself meaning, existence and beauty. Formalists use Mathematics as a tool, being nothing more than an assemblage of symbols representing a statement.
A starkly contrasting philosophy maybe seen in Intuitionism, which relies on intuition and insight as the fundamental tools of problem solving.
Though the philosophies of Mathematics are multiple, Formalism has much significance in that it constitutes the founding principle in the development of numerous sophisticated systems. Formalism is syntax and semantics to formulate and solve problems. The contours of Formal Theories in Mathematics are vague, as we shall discuss in what are called ‘incompletenesses’. Yet still, formal systems are ‘consistent’ enough to contain quite a lot of feats in engineering.
Truth
We humans have always been mystified at what Truth is. Every religion, philosophy and science on earth has one glimmering beacon to pursue — Truth. Mathematics has always pursued Truth — maybe in ways more than one. Is Truth algorithmic? Can everything in Nature be formulated in Mathematics that would lead us to Truth? Can Mathematics explain a phenomenon like evolution? Maybe someday, yes. But to our discussion, let us concern ourselves with the nature of Mathematics.
We are on a mission to leverage our understanding of the world through Mathematics. In the realm of Artificial Intelligence, we are bothered about how we could emulate human thinking leveraging on Mathematics. We, in our daily lives deal with matters that involve problem-solving, being aware of how we solve, or out of habit. Sleepwalkers meticulously find their way through their houses quite successfully at times. We are led to accept that our thinking, at least to a certain extent is algorithmic — It follows a sequence of steps to come to the result we seek. How far this algorithmic process simulate human thought would be a latter part of our discussion.
Formal Mathematical Systems
The approach of algorithms to solve problems has been the endeavor of formal mathematicians for quite a while. The age of Enlightenment (late 1600-1800) saw the surge of logic fore-fronting the disciplines of reasoning and judgement and ultimately leading to Truth. Mathematicians sought powerful methods that could frame problems and solve them. Many of these methods involved in the consideration of sets, or Set Theory.
Set Theory is where physical objects or mathematical concepts are treated as ‘wholes’ or sets, in which members share a common attribute, or a property. e.g. the set of stars. Georg Cantor was a valued contributor to this. The Set Theory was successful enough to justify itself in view of the proofs it was able to produce on problems of real world existence. However, an argument of Bertrand Russell challenged the completeness of the naive theory of sets:
‘R is the set of all sets which are not members of themselves.’
This property or nature of the elements of the set R makes it a member of itself, and not a member of itself at the same time.
Paradoxes like Russell’s Paradox led to stricter systems based on a well laid out list of axioms and operations of procedure, called formal systems. A formalism describes logical operations in the same way that elementary algebra describes numerical operations. The driving idea being simple :
- To formulate a problem in terms of language of the formal system, in it’s syntax.
- Reason out the truth relying on the axioms and rules of procedure of the system.
Example : Propositional logic is an early system that may be studied under formal systems. A simple reasoning with propositional logic would be like:
- Statement 1: A ⇒ B (A implies B)
- Statement 2: ¬A (Negation of A)
- Inference: ¬B (Negation of B)
The above statements of reasoning could be applied to real-world in a way, to infer upon a truth like:
- Statement 1: If it’s night, it’s dark.
- Statement 2: It’s not night.
- Inference: It’s not dark.
where, A, B represents the variables that can take on values.
⇒ represents implication, i.e. the Left Hand Side implies the Right Hand Side.
¬ represents negation.
Of course, truth in this sense is relative to the system (propositional logic) under study. But the outcome is one that is deduced from, under a system that has been validated as true. More complex logic and deductions are possible, however the concept remains the same. A very elementary real-world example of a formal system (propositional logic) maybe seen in the Wumpus World problem
We shall concern ourselves with Boolean Algebra, which is perhaps the most widely studied formalism in mathematical logic.
Boolean Algebra
Propositional logic shares a very close connection with Boolean Algebra. Boolean Algebra as we know today is an adaptation of what George Boole set forth in his book ‘An Investigation of the Laws of Thought’ in 1854. Boolean Algebra forms the basis of Digital Electronics, which forms the backbone of digital computing.
Claude Shannon, in 1937 while studying switching circuits identified how he could port the analogy of Boolean logic on to the various circuits he had been trying to design. Two-state switching logic, or what we know now as two-element Boolean Algebra originated from his findings. The implementation of combinational logic circuits, like a Half Adder digital circuit, is achieved by the use of gates, the basic ones being defined by fundamental Boolean operations.
S = A ⊕ B (A ‘xor’ B)
C = A & B (A ‘and’ B)
Venn Diagrams for basic Boolean operations: The conjunction, disjunction, and negation.
The modern day digital computer has its foundations on Two-element Boolean Algebra. Let us take a look into the development of digital computing over the years, next week.
Next week: Digital Revolution — The Timeline
Previous week: The Vehicles of AI — Analog and Digital Computers.
First week: Can Machines Think?
P.S: An interesting piece of Information here.
