Introducing Logic

1. Logic is the Study of Truth-Preserving Arguments

Logic is quite simply the study of truth-preserving arguments.

Defining logic's purpose. At its core, logic is concerned with how truth flows from one statement to another. An argument is truth-preserving if the truth of its supporting claims (premises) guarantees the truth of its conclusion. This distinguishes valid arguments from mere assertions or irrelevant statements.

Aristotle's foundational tool. The Greek philosopher Aristotle provided the first systematic approach to logic, viewing it as a tool ("organon") for convincing arguments. He analyzed sentences into subjects and predicates and identified three types:

• Singular (Socrates is a man)
• Universal (Every man is mortal)
• Particular (Some men are mortal)
  He studied the relationships between these sentence types in his "Square of Oppositions."

The syllogism's structure. Aristotle's major contribution was the syllogism, a three-statement argument form where the predicate of the first premise is the subject of the second, and the conclusion combines the remaining terms. He observed that if the premises are true, the conclusion is necessarily true. This formal structure, independent of content, was a crucial step in understanding logical validity.

2. Early Logic Focused on Sentences and Connections

WITH WORDS LIKE “AND”, “OR” AND “IF…THEN…”, DIFFERENT STATEMENTS CAN BE JOINED TOGETHER AND THE TRUTH OF THE WHOLE WILL DEPEND EXCLUSIVELY ON THE TRUTH OF THE PARTS.

Beyond subject-predicate. While Aristotle focused on the internal structure of simple sentences, Chrysippus of Soli, about a century later, shifted attention to how complex statements are formed by joining simpler ones using logical connectives like "and," "or," and "if...then...". This was a major conceptual leap, recognizing that the truth of a complex statement depends solely on the truth values of its components and the specific connective used.

Connectives define truth. Each connective has a unique rule for determining the truth of the combined statement based on the truth of its parts. For example, an "and" statement is true only if both parts are true, while an "or" statement is true if at least one part is true. Chrysippus's work laid the groundwork for understanding these truth-functional relationships, although his ideas were largely lost for centuries.

Aristotle's enduring influence. Despite Chrysippus's innovation, Aristotle's logic dominated for 1,500 years, partly because his writings survived and were adopted by institutions like the Catholic Church. Logicians during this period primarily focused on cataloging and expanding Aristotle's syllogisms, treating logic more like an art of manipulating concepts than a formal system based on truth values and connectives.

3. Leibniz Revolutionized Logic with Algebraic Laws and Reductio

TWO THINGS ARE IDENTICAL IF EVERYTHING THAT CAN BE SAID OF THE ONE CAN BE SAID OF THE OTHER.

Logic as calculation. Gottfried Leibniz envisioned logic as a form of calculation, treating statements like algebraic equations. He introduced the equality sign (=) to denote identity, formulating his famous law: two things are identical if they share all properties. This principle allowed for the substitution of identical terms in statements while preserving truth, providing a powerful tool for logical derivation.

Fundamental laws of thought. Leibniz proposed a set of simple laws from which all valid syllogisms could be derived. These included:

• Law of Identity (a = a)
• Transitivity of Identity (If a=b and b=c, then a=c)
• Law of Double Negation (a = not (not a))
• Law of Contraposition ('a is b' = 'not-b is not-a')
  Crucially, he also emphasized the Law of Non-Contradiction (¬(p&¬p)) and the Law of Excluded Middle (pv¬p), asserting that every statement must be either true or false, but not both.

The power of reductio. Leibniz championed the reductio ad absurdum proof method. This technique assumes a statement is true and then logically derives a contradiction. Since contradictions are always false, the initial assumption must also be false. This method allows proving a statement's truth by showing its negation leads to absurdity, even without a direct constructive proof.

4. Modern Logic Introduced Quantifiers and Formal Systems

IT SHOWS US WHY “I SEE NOBODY ON THE ROAD” IS ACTUALLY QUITE DIFFERENT FROM “I SEE A MESSENGER ON THE ROAD”.

Frege's groundbreaking work. Modern logic is often dated to Gottlob Frege's 1879 Begriffsschrift. Frege combined Leibniz's proof theory with an account of logical connectives, finally incorporating Chrysippus's insights. His most significant innovation was the quantifier, allowing logical analysis of statements about groups ("all," "some") without treating them as simple subjects, thus avoiding linguistic pitfalls like Lewis Carroll's "Nobody."

Quantifiers and structure. Frege introduced formal symbols for "all" (∀) and "there is at least one" (∃), treating them as operators separate from subjects and predicates. This allowed for a more precise representation of the logical structure of sentences like "All men are mortal" or "Some men are bald," revealing logical relationships that Aristotle's subject-predicate analysis missed.

Propositional and Predicate Calculus. Frege's system, known as Propositional Calculus (dealing with whole propositions and connectives) and later extended to Predicate Calculus (incorporating subjects, predicates, and quantifiers), became the foundation for modern formal logic. It provided a rigorous framework for analyzing complex logical relationships and became the basis for attempts to formalize mathematics itself.

5. Paradoxes Challenge the Foundations of Logic

A paradox is a statement that entails its negation.

Logic's persistent problem. Throughout history, logic has been plagued by paradoxes – statements that, if assumed true, lead to a contradiction, and if assumed false, also lead to a contradiction. These self-undermining statements threaten the fundamental laws of logic, particularly the law of non-contradiction, and can potentially derail entire logical systems.

The infamous Liar Paradox. One of the oldest and most notorious is the Liar Paradox ("This sentence is false"). If the sentence is true, then what it says is true, meaning it is false. If it is false, then what it says is false, meaning it is true. This circular self-reference creates an unavoidable contradiction, demonstrating a deep problem for systems that allow sentences to speak about their own truth value.

Russell's set-theoretic paradox. Bertrand Russell discovered a similar paradox in Frege's set theory: the set of all sets that are not members of themselves. If this set is a member of itself, it violates its definition and is not a member of itself. If it is not a member of itself, it fits the definition and must be a member of itself. This paradox, a set-theoretic version of the Liar, exposed a fatal flaw in Frege's system and spurred efforts to restrict self-reference, such as Russell's Theory of Types.

6. Gödel Proved Fundamental Limits to Formal Systems

I DISCOVERED THAT ANY SYSTEM COMPLICATED ENOUGH TO BE USED AS A BASIS FOR ARITHMETIC WILL BE INCOMPLETE.

Hilbert's program challenged. David Hilbert sought to ground all of mathematics on a finite set of axioms and prove their consistency using formal methods (Proof Theory). He aimed for a complete and consistent system where every true mathematical statement could be proven. Kurt Gödel, initially working on Hilbert's program, delivered a stunning blow with his Incompleteness Theorems.

Gödel's ingenious encoding. Gödel developed a method to encode logical statements and proofs as numbers (Gödel numbering). This allowed him to translate statements about the formal system (metamathematics) into statements within the system itself. Using this, he constructed a formula within Russell's system that, when translated back, essentially said: "This formula is unprovable in this system."

Incompleteness and inconsistency. Gödel's First Incompleteness Theorem showed that for any formal system strong enough to encompass basic arithmetic, either:

• It is incomplete: There exists a true statement within the system that cannot be proven within the system.
• It is inconsistent: A false statement (a contradiction) can be proven within the system.
  His Second Theorem showed that such a system cannot prove its own consistency. These results demonstrated that Hilbert's dream of a complete and consistent foundation for all of mathematics was impossible in principle, fundamentally altering the landscape of logic and mathematics.

7. Non-Classical Logics Explore Alternatives to True/False

Now we can think of sentences as being “very true”, “fairly true”, “reasonably false”, “completely false” and so on.

Challenging classical assumptions. Classical logic, based on Leibniz's laws, assumes every statement is either strictly true or strictly false (Law of Excluded Middle) and not both (Law of Non-Contradiction). However, problems like the Sorites paradox (the "heap" paradox) highlight the difficulty of applying these strict truth values to vague concepts in natural language.

Intuitionism and constructive proof. L.E.J. Brouwer developed intuitionistic logic, challenging the Law of Excluded Middle, particularly for infinite sets. He argued that a mathematical statement is only true if there is a constructive method to prove it. In this logic, proving that a statement is not false (¬¬p) is not always equivalent to proving that it is true (p), as it is in classical logic.

Many-valued and Fuzzy Logic. Jan Lukasiewicz introduced a logic with a third truth value, "possible" (often represented as ½), in addition to true (1) and false (0). This "many-valued logic" can be extended to any number of truth values, even an infinite continuum between 0 and 1. This approach, known as fuzzy logic, allows statements to have degrees of truth, providing a framework for dealing with vagueness and similarity, which is particularly useful in areas like pattern recognition and AI.

8. Logic Underpins Digital Electronics and AI

Pretty much all digital electronics is constructed out of “And Gates”, “Or Gates”, and “Not Gates”, which correspond to the logical connectives “&”, “v” and “¬”.

Logic gates as switches. The fundamental operations of digital electronics are direct implementations of logical connectives. Electronic switches, or "logic gates," function like truth tables:

• An "And Gate" outputs a signal (True/1) only if all inputs have a signal (True/1).
• An "Or Gate" outputs a signal if at least one input has a signal.
• A "Not Gate" reverses the input signal.
  These gates, corresponding to the logical connectives "&", "v", and "¬", are the building blocks of complex electronic devices.

Computers as logic machines. Alan Turing's theoretical work on computation showed that a universal machine could perform any calculation by manipulating symbols according to formal rules. This concept, combined with the realization that electronic switches could represent logical states (True/False, 1/0), led to the development of digital computers. In essence, computers are sophisticated machines that execute complex logical proofs or calculations based on the manipulation of binary symbols according to programmed rules derived from logic.

Formal languages and AI. Computer programming languages are formal languages with defined vocabularies and syntactical rules. Artificial Intelligence (AI) research, particularly early approaches, often views intelligence as the ability to manipulate symbols logically. Languages like Prolog are designed around logical inference, allowing machines to process facts and rules to answer questions or perform tasks, embodying Turing's vision of machines capable of learning and communication through formal systems.

9. Logic Shapes Scientific Methodologies

IN SCIENCE, FIRST WE PERFORM EXPERIMENTS, THEN WE GENERALIZE FROM THE EXPERIMENTAL RESULTS TO ARRIVE AT NATURAL LAWS.

Deduction and Induction. Science relies heavily on two main forms of reasoning: deduction and induction. Deduction moves from general laws to specific predictions (e.g., All ravens are black, this is a raven, therefore it is black). Induction moves from specific observations to general laws (e.g., This raven is black, that raven is black... All ravens are black).

The problem of induction. David Hume highlighted a fundamental problem with induction: the truth of the observations does not logically guarantee the truth of the general conclusion. No amount of observing black ravens can logically prove that a white raven doesn't exist. This means scientific laws derived inductively lack the certainty of deductive conclusions, posing a challenge to justifying scientific knowledge.

Falsification and the web of belief. Karl Popper proposed falsification as an alternative methodology, arguing that science progresses by trying to disprove theories rather than confirm them. A single contradictory observation can logically falsify a general law (If all Fs are Gs, and we find an F that is not G, then the law is false). However, W.V.O. Quine argued that experimental results don't falsify single theories in isolation but challenge a whole "web of belief," making it unclear which specific belief to revise. This suggests scientific theories are "underdetermined" by evidence, leading to debates about relativism in science.

10. Logic Provides Models for Language and Mind

THE COMMON ASSUMPTION OF THE COGNITIVE SCIENCES IS THAT THE MIND IS A SIMILAR LOGICAL SYSTEM.

Language as a formal system. Following the success of formal logic, philosophers and linguists have attempted to model natural language using logical structures. Donald Davidson proposed that understanding language involves knowing the truth conditions of its sentences, which can be analyzed using formal semantics, similar to Alfred Tarski's work on truth in formal languages. Noam Chomsky's theory of Universal Grammar suggests an innate, recursive logical structure in the brain that allows children to generate and understand an infinite number of sentences from a finite vocabulary and rules.

The mind as a logical machine. Cognitive science often operates on the assumption that the mind can be understood as a system that performs logical computations or manipulations of symbols, independent of the underlying biology. This "symbolic" approach views mental states as equivalent to specific configurations of symbols in a formal language processed by the brain.

Neural nets and fuzzy logic. A contrasting model in cognitive science views the brain as a "neural net," inspired by biological neurons. These networks process information through weighted connections and can be modeled using fuzzy logic, where states are not strictly binary (on/off) but exist on a continuum. Neural nets excel at pattern recognition (like recognizing faces or speech) but struggle with the systematic manipulation of symbols required for formal logic or complex math, suggesting that different logical models may be needed to capture the full range of cognitive abilities.

Last updated: May 4, 2025