Symbols, Logic and Language

Logic is the language of mathematics. It restricts our focus to statements that are definitively true or false, thereby making human language precise. This formalisation resolves inherent ambiguities when interpreting natural expressions such as “if … then”, “or”, and “and”.

Early Greek philosophers, notably Aristotle and Chrysippus, laid the initial formal foundations but frequently struggled with the precise boundaries of semantics. It was not until the work of modern mathematicians such as Leibniz (1750), Boole (1860) and De Morgan (1870) that propositional logic was formalised.

This development introduced the core architecture of modern mathematics: formal languages, variables, operators, axioms, logical inference and proof. Since computational systems are fundamentally discrete, propositional logic is used to specify software properties, and define deterministic states. Furthermore, propositional logic is algorithmically decidable; an algorithm exists to determine whether any given statement evaluates to true or false. This decidability is lost in more complex frameworks.

Syntax and Semantics

Because logic is the formal language of mathematics, it possesses two fundamental aspects. The grammatical rules governing how symbols may be validly composed dictate its syntax, while the meaning behind a particular arrangement of those symbols is its semantics.

In mathematics, we refer to objects by giving them names. A variable is a symbol that stands in for an object that has not yet been specified. We assign a name to a particular object using the assignment operator $:=$. For example, writing $x := 5$ assigns the value $5$ to the variable $x$. We can similarly define the golden ratio as

The objects and variables within an expression are its terms. For instance, $5$, $x + 2$, and $\sqrt{b^2 - 4ac}$ are all distinct terms.

Propositions and Truth Values

Mathematical reasoning is concerned exclusively with declarative sentences that express a complete thought and can be definitively judged as true or false.

The foundation of classical logic rests on a critical assumption regarding the nature of these propositions.

The Principle of Bivalence. A proposition is either true or false, but not both. Every proposition must be assigned exactly one of the truth values $\top$ or $\bot$.

1. $2 + 3 = 5$. (Truth value: $\top$)
2. The integer 7 is even. (Truth value: $\bot$)
3. For any real number $x$, $x^2 \geq 0$. (Truth value: $\top$)
4. There exists a prime number greater than $10^{100}$. (Truth value: $\top$)
5. The Earth is round. (Truth value: $\top$)

Note that all that matters is that it makes logical sense to assign a truth value, regardless of whether that value is actually known to us. The truth value of many mathematical propositions remains currently unknown, yet they are still perfectly valid propositions.

In contrast, many mathematical expressions and sentences are not propositions because they lack a definable truth value. Imperative sentences (commands) and interrogative sentences (questions) are naturally excluded.

1. $x^2 - 9$. (This is a term. Its value depends on $x$, but it is not a complete sentence capable of carrying a truth value.)
2. Solve the equation $x^2 - 9 = 0$. (An imperative command.)
3. Is $\pi$ a rational number? (An interrogative question.)
4. $x > 5$. (This is a sentence, but its truth value depends on the unspecified variable $x$. It is a predicate, which will be addressed in later sections.)

Semantically Void and Self-Contradictory Sentences

The Principle of Bivalence clarifies why certain sentences, despite being grammatically correct, fail to be propositions. For a sentence to qualify, it must be logically possible to assign it a unique truth value. Sentences that prevent this assignment are excluded from our logical system.

Consider a sentence that is syntactically perfect but semantically meaningless, such as “The theory of relativity eats breakfast loudly.” While it possesses a subject, verb, and adverb, a scientific theory is an abstract concept incapable of physical action. Because it describes a nonsensical state of affairs, we cannot assess its truth. Assigning $\top$ is absurd, and assigning $\bot$ implies its negation is true, which is equally nonsensical.

A more subtle challenge arises from paradoxes: sentences that are semantically meaningful but inherently self-contradictory. Consider a page containing only the following sentence:

“The only proposition on this page is false.”

Attempting to assign a truth value to this sentence (let us call it $P$) yields a contradiction:

1. Assume $P$ evaluates to $\top$. The sentence asserts that it is false. Since it is the only proposition present, $P$ must evaluate to $\bot$, contradicting our initial assumption.
2. Assume $P$ evaluates to $\bot$. The assertion that the sentence is false must be incorrect, implying that $P$ evaluates to $\top$. This again contradicts our assumption.

Because the sentence cannot be assigned $\top$ or $\bot$ without violating the Principle of Bivalence, it is not a proposition. By narrowing our scope strictly to propositions, we guarantee that our logical framework remains consistent. This strict decidability is exactly what makes propositional logic suitable for automated reasoning and algorithmic verification.

Atomic Statements and the Structure of Mathematical Truth

To systematically analyse sentences and extract their logical essence, we must decompose them into their foundational components.

For example, “5 is a prime number” is an atomic statement. Conversely, “5 is a prime number and 4 is an even number” is a compound statement built from two atomic components. We traditionally express these base components using propositional variables, denoted by lowercase letters such as $p, q, r, s$.

Constructing rigorous arguments from these atomic statements leads us to the core mechanism of mathematics: the proof.

It is not much good trying to prove results if we do not have anything to prove results about. With this in mind, we will soon introduce numbers and prove results in the context of rational numbers, irrational numbers, and polynomials. As we build this mathematical architecture, the results we prove will be categorised by their structural role and intended usage:

• Proposition: An umbrella term for any proven result, typically referring to a standard or supporting fact.
• Theorem: A key, foundational result of significant importance.
• Lemma: A stepping-stone result whose primary purpose is to assist in the proof of a subsequent theorem, or as a tool for the reader to use in their own proofs.
• Corollary: A result that follows as an immediate logical consequence of a theorem or proposition.

Logical Connectives

The propositions established thus far have been atomic, representing single, indivisible concepts. However, the power of formal logic derives from our ability to form complex arguments by combining these atomic statements. These new structures are called compound propositions, constructed using logical connectives.

Each connective represents a precise mathematical rule that determines the truth value of a compound statement based solely on the truth values of its constituent parts. We define these rules exhaustively using a truth table, which lists the output truth value for every possible combination of input variables.

Unary and Binary Connectives

Negation ($\neg$). The simplest operation modifies a single proposition by denying it. Negation is a unary connective that inverts the truth value of its input. For example, if $p$ is the statement “The integer 7 is an even number” ($\bot$), its negation $\neg p$ (read “not $p$”) is “The integer 7 is not an even number” ($\top$).

Conjunction ($\land$). Two propositions $p$ and $q$ may be combined to form the conjunction $p \land q$ (read ”$p$ and $q$”). This compound statement is $\top$ if and only if both $p$ and $q$ are $\top$.

Disjunction ($\lor$) and Exclusive Or ($\oplus$). The disjunction $p \lor q$ (read ”$p$ or $q$”) evaluates to $\top$ if at least one of the component propositions is $\top$, and evaluates to $\bot$ only when both $p$ and $q$ are $\bot$. Conversely, the exclusive or, denoted $p \oplus q$, evaluates to $\top$ if exactly one of $p$ or $q$ is $\top$.

Conjunction and disjunction form a foundational dual pair within propositional logic. Negating a conjunction is logically equivalent to the disjunction of the negations, a property that forms a cornerstone of Boolean algebra.

Implications and Biconditionals

Mathematical theorems fundamentally rely on establishing dependencies between propositions, achieved through conditional statements.

Implication ($\to$). The conditional statement $p \to q$ (read “if $p$, then $q$”) establishes $p$ as the antecedent (or premise) and $q$ as the consequent (or conclusion).

The logic of the implication is occasionally counter-intuitive to beginners because $p \to q$ evaluates to $\bot$ in exactly one scenario: when $p$ is $\top$ but $q$ is $\bot$. To understand this, it is helpful to view an implication as a contract. Consider the statement: “If the employee finishes the project by Friday ($p$), then they will receive a bonus ($q$).”

1. $p$ is $\top$, $q$ is $\top$: The employee finishes on time and gets the bonus. The contract is upheld ($\top$).
2. $p$ is $\top$, $q$ is $\bot$: The employee finishes on time, but does not receive the bonus. The contract is violated ($\bot$).
3. $p$ is $\bot$, $q$ is $\top$: The employee misses the deadline but receives a bonus anyway (perhaps for previous good work). The original statement only specified what happens if the project is finished on time; it did not prohibit a bonus otherwise. The statement remains true ($\top$).
4. $p$ is $\bot$, $q$ is $\bot$: The employee misses the deadline and receives no bonus. The statement remains true ($\top$).

Cases 3 and 4 illustrate a vital mathematical concept known as vacuous truth: if the antecedent is $\bot$, the implication makes no assertions about the consequent and is automatically evaluated as $\top$.

Biconditional ($\leftrightarrow$). The material equivalence $p \leftrightarrow q$ (read ”$p$ if and only if $q$”, frequently abbreviated as “iff”) describes a relationship where two propositions strictly share the same truth value. For example, “A polygon is a triangle ($p$) if and only if it has exactly three sides ($q$).” If one is true, the other must be true; if one is false, the other must be false.

The Language of Necessary and Sufficient Conditions

In mathematical prose, standard logical notation is frequently replaced by variations of English phrasing. Understanding these translations is vital for interpreting theorems. Consider the implication $p \to q$, where $p$ is “It is raining” and $q$ is “The ground is wet”. Assuming the implication evaluates to $\top$, we may express this dependency in several logically equivalent ways:

• Standard form: If it rains, the ground is wet.
• Sufficiency: It raining is sufficient for the ground to be wet. (Knowing $p$ is $\top$ guarantees $q$ is $\top$).
• Necessity: The ground being wet is necessary for it to rain. (If $q$ is $\bot$, then $p$ cannot possibly be $\top$).
• Only if: It rains only if the ground is wet.

When dealing with a biconditional $p \leftrightarrow q$, the proposition $p$ is said to be “necessary and sufficient” for $q$.

Logical Equivalence and Nonequivalence

To establish that two compound propositions are logically equivalent (denoted $\equiv$), one must demonstrate that they yield identical truth values under every possible assignment of their constituent variables. Conversely, proving nonequivalence is a much simpler task.

This concept formally justifies a critical structural rule of mathematics: implication is strictly directional. A pervasive logical fallacy is to assume that an implication $p \to q$ is equivalent to its converse $q \to p$. We may rigorously disprove this by identifying a single counterexample via a truth table.

Consider the assignment where $p$ is $\top$ and $q$ is $\bot$. Under this assignment, the implication $p \to q$ evaluates to $\bot$, whereas its converse $q \to p$ evaluates to $\top$. Since we have isolated a case where their truth values diverge, this single counterexample is sufficient proof that $p \to q \not\equiv q \to p$. The truth of an implication provides absolutely no guarantees regarding its converse.

Operator Precedence

To preserve clarity and avoid an unreadable accumulation of parentheses in complex expressions, logical connectives adhere to a strict order of precedence. Operations are evaluated in the following hierarchy:

1. Negation ($\neg$)
2. Conjunction ($\land$)
3. Disjunction ($\lor$)
4. Implication ($\to$)
5. Biconditional ($\leftrightarrow$)

Under these rules, compound propositions are implicitly bracketed. For example, logical equivalence allows us to interpret expressions unambiguously without superfluous parentheses:

The exclusive or ($\oplus$) lacks a universally standardised precedence level within this hierarchy; consequently, parentheses must always be explicitly written when incorporating it into compound statements.