KindiakMath

The Massive Impact of Applied Logic

The whole point of examining logic is to develop crucial proof techniques that will aid us for future studies. This is the primary application, and arguably the most crucial one, of examining logic and even tautologies.

Each proof technique is still a compound expression that we can verify to be a tautology, so we can verify that they work just like normal compound expressions.

Each proposition on the left-hand side is either assumed or proven to be a theorem, and the proof techniques ensure that the right-hand side will be a theorem too.

The fundamental proving technique has to be modus ponens, which is essentially a direct proof $p \to q$ .

Theorem 1 (Modus Ponens). Let $p,q$ be propositional variables. Then

$p \wedge (p \to q) \to q = t.$

Proof: Writing implications as disjunctions,

$\begin{aligned} p \wedge (p \to q) \to q &= \neg(p \wedge (p \to q)) \lor q \\ &= \neg p \lor \neg (p \to q) \lor q \\ &= (\neg p \lor q) \lor \neg (p \to q) \\ &= (p \to q) \lor \neg(p \to q) = t.\end{aligned}$

where we used the identity law $\neg p \lor p = t$ , which can be easily verified.

Throughout the rest of the discussion, we will abbreviate each valid proof technique $p = t$ by $p$ . So modus ponens is abbreviated by

$p \wedge (p \to q) \to q .$

This means that if we have established that $p$ is true and $q$ is true, we can logically conclude that $(p \to q)$ must be true. In particular,

$t \wedge (t \to q) \to q.$

This is how we prove theorems. We will also abbreviate the proof technique obtained by chaining implications

$(p \to q) \wedge (q \to r) \to (p \to r)$

by $p \to q \to r$ .

Sometimes, it is easier to prove an equivalent statement of a direct proof. One such equivalence is called the contrapositive.

Theorem 2 (Proof by Contrapositive). Let $p,q$ be propositional variables. Then

$p \wedge (\neg q \to \neg p) \to q.$

Proof. Observe that

$\neg q \to \neg p = \neg (\neg q) \lor \neg p = q \lor \neg p = \neg p \lor q = p \to q.$

By modus ponens, $p \wedge (\neg q \to \neg p) = p \wedge (p \to q) \to q$ . The implication $\neg q \to \neg p$ is known as the contrapositive of the implication $p \to q$ .

A closely related proof technique is known as modus tollens. It is, in a sense, the mirror argument of modus ponens.

Theorem 3 (Modus Tollens). Let $p,q$ be propositional variables. Then

$\neg q \wedge (p \to q) \to \neg p.$

Proof. Using Theorem 2 and double negation,

$\neg q \wedge (p \to q) = \neg q \wedge (\neg(\neg p) \to \neg(\neg q)) \to \neg p$ .

Modus tollens is used to prove $\neg p$ by first establishing $\neg q$ and $p \to q$ via a proof by its contrapositive $\neg q \to \neg p$ .

Throughout our discussion, we have been replacing $p = t$ and $p = c$ . This idea is generalised to a proof by cases.

Theorem 4 (Proof by Cases). Let $p,q,r$ be propositional variables. Then

$(p \to r) \wedge (q \to r) \to ((p \lor q) \to r).$

Proof. Writing implications as disjunctions,

$\begin{aligned} (p \to r) \wedge (q \to r) &= (\neg p \lor r) \wedge (\neg q \lor r) \\ &= (\neg p \wedge \neg q) \lor r \\ &= \neg (p \lor q) \lor r \\ &= (p \lor q) \to r. \end{aligned}$

Other proof techniques include specialisation, which is the rather mundane tautology $p \wedge q \to p$ , generalisation, which is given by $p \to p \lor q$ , and two-directional proof, given by

$(p \leftrightarrow q) = (p \to q) \wedge (q \to p).$

The implication $q \to p$ is the converse of the implication $p \to q$ .

Yet, we have not unveiled two of the most powerful tools. The first is a proof by contradiction, which helps us establish $p$ by showing that $\neg p$ leads to a brick wall.

Theorem 5 (Proof by Contradiction). Let $p$ be a propositional variable. Then

$(\neg p \to c) = p.$

Proof. Writing implications as disjunctions,

$(\neg p \to c) = \neg(\neg p) \lor c = p \lor c = p.$

The last technique is called proof by induction. Intuitively, it follows from chaining $n$ implications together. However, the notion of $n \in \mathbb N$ depends on the definition of $\mathbb N$ , which can get too technical for a first discussion in discrete mathematics. We will state it here without proof for completeness.

Theorem 6 (Proof by Induction). For any natural number $n$ , let $\phi(n)$ be a proposition. Suppose the following hold:

$\phi(0) = \mathrm T$ ,
for any natural number $k$ , $\phi(k) \to \phi(k+1) = \mathrm T$ .

Then $\phi(n) = \mathrm T$ for any natural number $n$ .

Proof. Roughly speaking, chaining implications yields

$\begin{aligned} &(\phi(0) \to \phi(1)) \wedge \dots \wedge (\phi(n-1) \to \phi(n)) \\ &= (\phi(0) \to \phi(1) \to \dots \to \phi(n)) \to (\phi(0) \to \phi(n)). \end{aligned}$

Hence, by modus ponens,

$\phi(0) \wedge (\phi(0) \to \phi(n)) \to \phi(n).$

We will provide a more complete proof when discussing $\mathbb N$ in a future post.

These proof techniques, coupled with some set-theoretic starting points (for introductory discrete mathematics, we will use naïve set theory as our launchpad), will help us prove most of mathematics. But before doing so, we need two more notions in order to make headway into mathematics—universal and existential quantifiers.

—Joel Kindiak, 16 Nov 24, 2236H

Discrete Math, Theory

Published by

joelkindiak

Responses

The Truth of God – KindiakMath

November 3, 2025 at 11:53 am

[…] written in the main page, the goal of these posts is to establish the logical truth of Christianity. As with any mathematical model, we will nevertheless, require some basic […]

LikeLike

Reply
The Logic of Predicates – KindiakMath

December 28, 2025 at 12:25 am

[…] like modus ponens, universal modus ponens is one of the most crucial proof techniques in mathematics. Using our […]

LikeLike

Reply
Atomic Numbers – KindiakMath

December 28, 2025 at 12:41 am

[…] Suppose, for a contradiction, that there are only finitely many primes . Consider the number . Since for any , is not […]

LikeLike

Reply
Cheryl’s Birthday Problem – KindiakMath

January 5, 2026 at 6:08 pm

[…] Albert says “I know that Bernard doesn’t know”. By Lemma 2, Bernard’s date number can be matched by more than one month. If, however, his numbers are 18 or 19, then each of these numbers can only match one month, a contradiction: […]

LikeLike

Reply
A Fascinating Multiples Problem – KindiakMath

January 5, 2026 at 6:18 pm

[…] claim that by way of contradiction. Suppose otherwise that . Then by the third and second properties respectively, […]

LikeLike

Reply
Prime Factorisation – KindiakMath

January 5, 2026 at 6:20 pm

[…] there exists such that , then , a blatant contradiction. Therefore, for any . Similarly, . Therefore, , so that . Therefore, […]

LikeLike

Reply
Polynomial Long Division – KindiakMath

January 5, 2026 at 6:23 pm

[…] contradiction. Hence, , yielding […]

LikeLike

Reply
Theoretical Partial Fractions – KindiakMath

January 5, 2026 at 6:25 pm

[…] , then . Since as well, we have is a nonzero constant, a contradiction. Therefore, and . Therefore, is non-empty, so that is non-empty. By the well-ordering principle, […]

LikeLike

Reply
Doing Logic the Lazy Way – KindiakMath

January 5, 2026 at 6:38 pm

[…] Why did we care about logic? We have completed what amounts to verification of various truth values, given certain combinations of propositional variables. We even derived several useful tautologies. These tautologies form the bedrock of proof techniques, which are the ligaments of mathematics. We discuss this next time. […]

LikeLike

Reply
Proving that Pi is Irrational – KindiakMath

January 5, 2026 at 8:34 pm

[…] of Theorem 1. Suppose for a contradiction that for some positive integers . Defining in Lemma 1, we […]

LikeLike

Reply
Curious Continuity – KindiakMath

January 5, 2026 at 8:45 pm

[…] for a contradiction, there exists such that . Assume without loss of generality. By the intermediate value theorem, […]

LikeLike

Reply
Classical Optimisation – KindiakMath

January 5, 2026 at 8:59 pm

[…] Fix . If , then being strictly decreasing implies , a contradiction. Therefore, . Since as , there exists such that . Use the intermediate value theorem to obtain […]

LikeLike

Reply
Some Calculus of Variations – KindiakMath

January 5, 2026 at 9:18 pm

[…] By way of contradiction, suppose . By Problem 1, there exists such that without loss of generality, whenever . Define […]

LikeLike

Reply
Defining Dimension – KindiakMath

January 6, 2026 at 3:23 pm

[…] This process must end before , otherwise will have a basis of elements, which by Lemma 1 is not linearly independent, which is a contradiction. […]

LikeLike

Reply

The Massive Impact of Applied Logic

Share this:

Responses

Leave a comment Cancel reply