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 (1666), Boole (1847) and De Morgan (1847) that propositional logic was formalised.

This development introduced the core architecture of modern mathematics: formal languages, variables, operators, axioms, logical inference and proof.

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 $\defeq$. For example, writing $x \defeq 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

Mathematics, in its most basic form, is the practice of assigning truth to well-defined statements; it differs from other sciences in that its results are proven rigorously, as opposed to being hypothesized and then “confirmed” via experiements.

For these notes, most of our work amounts to taking a collection of statements which we already know to be true and using them to establish newer, more complex ones, or formulating statements whose truth or falsity we wish to determine. If we were to encounter a falsity, we would have to demonstrate that it is indeed false; so, we begin with the logic that connects what we know to what we wish to know.

The statements mathematicians study are called logical or mathematical statements or propositions, which we define as follows:

By “grammatically correct,” we just mean that the words and symbols follow the rules of English (or any language you speak), and make sense.

The foundation of classical logic rests on the principle of bivalence, which states that every proposition is either true or false, but not both.

Example 4 is something to note: by the principle of bivalence, a sentence need not have a known truth value to qualify as a proposition; all that matters is that it makes logical sense to assign one; in fact, although the truth value of many propositions remains unknown, they are still valid propositions.

By the principle of bivalence, we also see that many mathematical expressions and sentences are not propositions because they lack a definite truth value — imperative sentences (commands) and interrogative sentences (questions), for example, are naturally excluded.

Semantically Void and Self-Contradictory Sentences

Consider the following sentence: “The theory of relativity eats breakfast loudly.” Although it possesses a subject, verb, and adverb, the problem is that a scientific theory is an abstract concept which cannot eat; thus, because it describes a nonsensical scenario, there is no sensible way to assign a truth value to it — assigning $\top$ is absurd, while assigning $\bot$ would require that “The theory of relativity does not eat breakfast loudly” is a true statement, which is equally bizarre.

A more subtle challenge arises from paradoxes: sentences that are semantically meaningful but inherently are 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, denoted by $P$, yields a contradiction:

1. If $P$ is $\top$: Then the sentence asserts that $P$ is false; since it is the only proposition present, $P$ must evaluate to $\bot$, contradicting our initial assumption that $P$ is true.
2. If $P$ is $\bot$: Then the sentence’s assertion that the only proposition on the page is false must itself be false. Since $P$ is the only proposition on the page, $P$ must therefore evaluate to $\top$, contradicting our initial assumption that $P$ is false.

Hence, as the sentence cannot be assigned a truth value, it is not a proposition.

In general, self-referential sentences like the one above, are quite bizarre and can produce some paradoxes that we want to disallow. By narrowing our scope strictly to propositions, we guarantee that our logical framework remains consistent, and most importantly suitable for automated reasoning and algorithmic verification (yes this is about Lean).

Atomic Statements and the Structure of Mathematical Truth

To analyse complex (or compound) statements, we 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 complex statement built from two atomic components.

By combining atomic statements into more complex structures, we can construct rigorous arguments in which certain statements support another, leading to the core mechanism of mathematics: proof.

As we build this mathematical architecture, the results we prove will be categorised by their structural role and intended usage:

• Proposition: In addition to its logical meaning above, “proposition” is also commonly used as a label for a proved result, usually one of lesser or supporting importance than a theorem.
• Theorem: A significant mathematical result.
• Corollary: A result that follows as an immediate logical consequence of a theorem or proposition.

Logical Connectives

Thus far, we have mostly been working with atomic propositions; the next step is to combine statements into new statements using logical operators or connectives, where the truth value of the combined statement is based solely on the truth values of the original statements and on the type of logical operator facilitating the combination. These rules should make sense to you based on your understanding of the English language as a whole, but we also define them using a truth table (a table whose columns correspond to mathematical statements and their respective truth values), which lists the output truth value for every possible combination of truth values assigned to the input propositional variables.

Negation

The simplest logical operator is the negation operator, which produces the “opposite” of the original statement in the logical sense. It is actually a so-called unary operator, i.e., it does not combine statements but is merely applied to one statement. If $p$ is a statement, its negation, written $\neg p$, is the statement with the exact opposite truth value, usually produced by placing a “not” in the grammatically appropriate spot. For example, if $p$ is the statement “Jack is a boy,” then $\neg p$ is the statement “Jack is not a boy,” or for another example if $p$ is the statement “31 is a prime number” ($\top$), then $\neg p$ is the statement “31 is not a prime number” or, equivalently, “31 is composite” ($\bot$).

Compound Sentences

Having seen how a unary operator acts on a single statement, we now proceed to binary logical operators, i.e., logical operators combining precisely two statements. Given two statements $p$ and $q$, we can join them with an “and” or an “or” to build a complex statement whose truth value depends, in the way you would expect, on the truth values of $p$ and $q$.

The conjunction of $p$ and $q$, read ”$p$ and $q$” and written $p \land q$, is true precisely when both pieces are true, and false otherwise.

The disjunction of $p$ and $q$, read ”$p$ or $q$” and written $p \lor q$, is true if at least one of the component propositions is true, and evaluates to false only when both $p$ and $q$ are false.

Since both may hold at once, our “or” is what computer scientists call an inclusive or. The exclusive or, also known as XOR, on the other hand, denoted $p \oplus q$, evaluates to $\top$ if exactly one of $p$ or $q$ is $\top$.

As you will have noted in the stated examples, logical operators can combine statements even when their meanings do not seem directly connected. While this might seem strange, adding restrictions based on content is neither needed nor helpful, because statements that appear unrelated can later become relevant within the same context. The same point applies to implications and equivalences, where the connection may initially seem even less intuitive.

”If-Then” Statements

Most statements we meet in these notes arrive as “If $p$, then $q$.” These are the conditional statements (or implications), written $p \to q$ (or $q \leftarrow p$) and read ”$p$ implies $q$”; within one, $p$ is called the hypothesis (or premise) and $q$ the conclusion. The logic of the implication is usually a little bit counter-intuitive to beginners so to be extra careful we can think of the statement $p \to q$ to mean the same thing as “whenever $p$ is true, $q$ is also true”; i.e., $p \to q$ evaluates to $\bot$ in only one scenario: when $p$ is $\top$ but $q$ is $\bot$.

Cases 3 and 4 illustrate what is known as a vacuous truth: whenever the hypothesis is $\bot$, the implication places no restriction on the conclusion and therefore evaluates to $\top$ automatically.

Another bit of confusion with these kind of statements comes from the word “implies,” as some use the word to convey some kind of causality. Take, for example the statement ”$1+1=2$ implies $1+2=3$,” which is a true statement; many implications seem to follow this pattern, where the truth of the hypothesis seems to lead us to the truth on the conclusion, but this isnt the case in general!

Another example, “the sky being blue implies $2+2=4$,” is a true statement, despite the color of the sky having nothing to do with $2+2$ equaling 4; thus, the truth of $p\to q$, depends only on the truth values of $p$ and $q$, regardless of if we can deduce the conclusion directly from the hypothesis (or if any meaningful connection between either even exist).

Granted, the implication $p\to q$ is not really useful in situations, where the truth values of both $p$ and $q$ are already known; that is in a typical application, one tries to establish the truth of $p$ to prove the truth of $q$ (a strategy that will fail if $p$ happens to be false); it is important to keep in mind, that this is a consequence of the strategy not an undelying part of how conditional statements are defined.

Finally, like conjuction, there are a plethora of ways to express implication in english; 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$, one may also say:

• If it rains, then the ground is wet.
• The ground being wet is a consequence of it raining.
• From “it is raining,” one may infer “the ground is wet.”
• It raining is sufficient for the ground to be wet.
• The ground being wet is necessary for it to rain.
• It rains only if the ground is wet.

Operator Precedence

Finally, before concluding this section, 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,
2. Conjunction,
3. Disjunction,
4. Implication,

Under these rules, compound propositions are implicitly bracketed. For example, logical equivalence allows us to interpret expressions unambiguously without superfluous parentheses; $\neg p \lor q$ is the same as $(\neg p) \lor q$; likewise, $p \to q \lor \neg r$ means $p \to (q \lor (\neg r))$.

The Structure of Proof Systems

Having established a language of propositions, connectives, and truth tables, the natural question is: what can we actually do with all of this?

Although truth tables answer individual questions, they have several problems, one being that brute-force enumeration of every possible assignment scales poorly: a formula with $n$ atomic variables needs $2^n$ rows (quite obvious to see). Another, more fundamental, problem is that a truth table tells us that something is true without revealing why it is true, or how its truth connects to anything else. To patch this, we build what is called a proof system.

Formally, a proof system — pioneered by Gottlob Frege in 1879 — is a mechanism that uses axioms (assumed truths) and inference rules to mechanically derive new valid statements from existing ones. To achieve this, the system operates on two fundamental objects: statements (finite symbol strings expressing propositions) and proofs (the formal sequences justifying them). The relationship between these objects is governed by two rules:

1. Semantics (Truth): A rule determining whether a given statement is true or false (the previous section used truth tables).
2. Verification (Syntax): A procedure that decides if a specific string constitutes a valid proof for a given statement. This verification must be efficiently computable; a proof whose validity cannot be checked in reasonable time is useless.

The ultimate goal of a proof system is to align these two sides — ensuring that syntactic provability mirrors semantic truth. We measure this alignment through two key properties: Soundness: If a statement has a valid proof, it is true (no false statement possesses a valid proof) and Completeness: If a statement is true, a valid proof for it exists.

The verification step is computationally cheap, even when finding the divisor $d$ is extraordinarily difficult.

Satisfiability

Before constructing proofs, we must classify propositions by the range of truth values they can assume. Not all compound propositions behave alike: some are always true, some are always false, and some depend on the assignment.

A proposition is satisfiable if there exists at least one assignment under which it evaluates to $\top$. Every tautology and every contingency is satisfiable. A contradiction is unsatisfiable.

To establish that a proposition is satisfiable, a single witness assignment suffices. To establish that it is unsatisfiable, one must check every assignment, which is precisely the expensive enumeration that motivates the algebraic approach developed below.

Logical Equivalence and Nonequivalence

Next, we need a way to decide when two statements are actually “the same,” at least in terms of their truth values. In particular, we may be able to prove that two statements have the same truth value for every possible assignment of the variables they contain.

From the logical operations and negation we can assemble statements of considerable complexity. Consider the formula $\neg(p \land q) \lor \neg(p \land r) \lor \neg(q \land r).$

This is a disjunction of three terms; by the associativity of $\lor$ (which we will prove shortly), the parentheses around the disjunction are irrelevant, and thus the formula is true exactly when at least one of the negated conjunctions is true. Now compare it with the much simpler expression $\neg(p \land q \land r)$. Even a quick glance suggests they both express “at least one of $p,q,r$ is false.” Their truth tables confirm this equivalence in a single combined table:

The two formulas agree on every row. This phenomenon deserves a name.

We can express this “same truth value” agreement directly in the language with a single connective.

Biconditional

Let $p$ and $q$ be statements, the biconditional, $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. Also note that when dealing with a biconditional $p \leftrightarrow q$, the proposition $p$ is said to be “necessary and sufficient” for $q$.

Equivalently, $p \leftrightarrow q$ asserts both [$(p \to q) \land (q \to p)$]. If $p$ is true, then $p \to q$ forces $q$ to be true; if $p$ is false, then $q \to p$ forces $q$ to be false. Thus, in either case, $p$ and $q$ have the same truth value.

The biconditional gives us a convenient way to characterize logical equivalence. For any particular assignment, $p \leftrightarrow q$ tells us whether $p$ and $q$ agree under that assignment. If they agree under every assignment, then the biconditional is always true.

The opposite situation is equally important.

And thus finally, we now have all the tools to build a proof system.

Equivalence Proofs

We now introduce the axiomatic foundation that allows us to reason about propositional equivalences without enumerating truth tables. The axioms of classical propositional logic specify the algebraic behaviour of the connectives $\land$, $\lor$, and $\neg$. Each axiom is a logical equivalence, asserting that two expressions are interchangeable in all contexts. The first five axiom pairs define a structure known as a Boolean algebra.

The axioms govern only $\neg$, $\land$, and $\lor$. To bring $\to$ and $\leftrightarrow$ within their reach we use the defining equivalences of the two conditional connectives, which rewrite them in terms of the core trio:

From these axioms, we derive theorems. Recall Definition 1.6 : a proof begins from known truths and proceeds via valid logical steps. An equivalence proof is a chain of equivalences, each justified by an axiom, a definition, or a previously established theorem:

The astute might ask: what logically permits us to stitch individual equivalences together into a single chain? Well this method relies on the principle of transitivity; we first show by truth table the closely related transitivity of implication, and then verify the transitivity of equivalence.

Let $p, q,$ and $r$ be any propositions. We show that the transitivity of implication, $\bigl((p \to q) \land (q \to r)\bigr) \to (p \to r)$, is a tautology.

$\begin{array}{ccc|cc|c|c|c} p & q & r & p \to q & q \to r & (p \to q) \land (q \to r) & p \to r & \bigl((p \to q) \land (q \to r)\bigr) \to (p \to r) \\ \hline \top & \top & \top & \top & \top & \top & \top & \top \\ \top & \top & \bot & \top & \bot & \bot & \bot & \top \\ \top & \bot & \top & \bot & \top & \bot & \top & \top \\ \top & \bot & \bot & \bot & \top & \bot & \bot & \top \\ \bot & \top & \top & \top & \top & \top & \top & \top \\ \bot & \top & \bot & \top & \bot & \bot & \top & \top \\ \bot & \bot & \top & \top & \top & \top & \top & \top \\ \bot & \bot & \bot & \top & \top & \top & \top & \top \end{array}$

The final column is $\top$ in every row, so the formula is a tautology. Similarly, for any propositions $p, q,$ and $r$, we show that the transitivity of equivalence, $\bigl((p \leftrightarrow q) \land (q \leftrightarrow r)\bigr) \to (p \leftrightarrow r)$, is also a tautology.

$\begin{array}{ccc|cc|c|c|c} p & q & r & p \leftrightarrow q & q \leftrightarrow r & (p \leftrightarrow q) \land (q \leftrightarrow r) & p \leftrightarrow r & \bigl((p \leftrightarrow q) \land (q \leftrightarrow r)\bigr) \to (p \leftrightarrow r) \\ \hline \top & \top & \top & \top & \top & \top & \top & \top \\ \top & \top & \bot & \top & \bot & \bot & \bot & \top \\ \top & \bot & \top & \bot & \bot & \bot & \top & \top \\ \top & \bot & \bot & \bot & \top & \bot & \bot & \top \\ \bot & \top & \top & \bot & \top & \bot & \bot & \top \\ \bot & \top & \bot & \bot & \bot & \bot & \top & \top \\ \bot & \bot & \top & \top & \bot & \bot & \bot & \top \\ \bot & \bot & \bot & \top & \top & \top & \top & \top \end{array}$

By the truth table, the transitivity of equivalence is likewise a tautology, fully justifying the chain-of-equivalences method. This method is vastly more efficient than truth tables for complex formulas (as we see below), though it requires algebraic ingenuity rather than mechanical enumeration.

Fundamental Theorems

This theorem is the engine behind nearly every derivation that follows. It tells us that if something behaves like a complement (annihilates under $\land$, completes under $\lor$), then it is the complement. We now put it to work.

With Theorem 1.18 and its corollaries established, we can now derive the classical theorems of propositional logic.

Of course De Morgan’s Laws are not isolated identities; they are the first manifestation of a much broader symmetry between conjunction and disjunction. This relationship is captured by the notion of logical duality.

Conjunction and disjunction are the fundamental dual pair of classical logic. The two De Morgan’s Laws $\neg(p \land q) \equiv \neg p \lor \neg q, \neg(p \lor q) \equiv \neg p \land \neg q$ show exactly that $\land$ and $\lor$ are dual to each other: negating an AND gives an OR of the negated parts, and negating an OR gives an AND of the negated parts.

Using this we extend the De Morgan’s Laws extend naturally to any finite number of propositions.

Equivalences Involving Conditionals

The defining equivalences of $\to$ and $\leftrightarrow$ allow us to derive every conditional equivalence by reducing implications to $\neg, \land, \lor$ and applying the theorems above:

Notice the pattern in the implication equivalences: when implications share the same premise, the conclusions combine with the same connective ($\land$ or $\lor$). When they share the same conclusion, the premises combine with the opposite connective. This “flip” from $\land$ to $\lor$ (and vice versa) is a direct consequence of the hidden negation in the definition of $\to$: the antecedent of an implication sits behind a $\neg$, so De Morgan’s Laws invert the connective when premises are merged.

Contrapositive, Converse, and Inverse

Let $p$ and $q$ be mathematical statements. From an implication $p \to q$, three related conditionals arise:

• The contrapositive $\neg q \to \neg p$.
• The converse $q \to p$.
• The inverse $\neg p \to \neg q$.

Something hinted at so far is that the direction of an implication matters: in general, reversing an implication does not preserve its truth. That is, even if $p \to q$ is true, its converse $q \to p$ need not be true.

The first equivalence is particularly important. Since $p \to q \equiv \neg q \to \neg p,$ if we wish to prove $p \to q$, we may instead show $\neg q \to \neg p;$ and this technique is one of the most useful methods of proof in mathematics (we see more of it later). However, because the converse is not determined by the truth value of the original implication whenever a mathematician proves a statement of the form $p \to q$, a natural follow-up question is whether the converse also happens to hold. This distinction is also the source of a common logical fallacy: Suppose we have established that $p \to q$; someone might object that $q$ does not necessarily imply $p$, and therefore claim that the original argument is wrong, however, this objection confuses an implication with its converse.

Negating Conditional Statements

For the end of this specific section we ask: what does it mean for an implication itself to be false?

Recall that $p \to q$ fails in exactly one situation: when $p$ is true and $q$ is false; expressing this algebraically using the conditional equivalence:

This has a useful interpretation: to show that an implication $p \to q$ is false, one must exhibit a case in which the hypothesis $p$ holds but the conclusion $q$ fails. In other words, a counterexample to an implication is precisely a witness to $p \land \neg q$. It is worth distinguishing this from several superficially similar statements: neither $\neg p \to q$ nor $p\to \neg q$ is the negation of $p \to q$. Anyway, we can negatate the biconditional similarly.

Thus, a biconditional is false exactly when $p$ and $q$ have different truth values; this is precisely the exclusive-or, relationship.

Equivalence Proofs in Practice

We now work through several examples that demonstrate the method and, simultaneously, show how Python can serve as a rapid sanity check.

The formula reduces to $\top$ with no surviving variables, confirming it is a tautology regardless of assignment.

This result captures a natural proof strategy: to show that a disjunction implies something, it suffices to show that each disjunct separately implies it.