Chapter 10: Mathematical Logic

In this chapter, we introduce the basic concepts of mathematical logic. The principles we explore here are not purely theoretical: they form part of the foundation for digital circuits in computers and for the conditional logic used in programming. Both hardware and software rely on the same algebra of propositions that we will study.

Propositions

Definition: Proposition

A proposition is a declarative statement that can be assigned a definite truth value: true or false, but never both.

Examples: Propositions

The following are examples of propositions:

"Four is even." (True)
"1 + 1 is 3." (False)
" $43 > 21$ ." (True)
" $4 \in {1, 3, 5}$ ." (False)

In mathematical logic, propositions mirror the reasoning we use in everyday language, but with strict precision. They can also be compound, formed using logical connectives such as and, or, and not.

This foundation allows us to reason about more complex systems, from proofs in mathematics to conditional statements in computer programs like if and else.

Logical Operations

Simple propositions can be combined to form compound propositions using logical connectives such as and, or, not, if...then..., and if and only if. To avoid ambiguity, we define the meaning of each connective precisely and introduce its standard symbolic representation.

Except for negation (not), which acts on a single proposition, all logical operations act on pairs of propositions. Since each proposition can be either true ( $1$ ) or false ( $0$ ), there are four possible combinations of truth values for two propositions. The effect of a logical operation on these combinations is most clearly shown using a truth table.

Logical Conjunction (AND)

If $p$ and $q$ are propositions, their conjunction, " $p$ and $q$ ," denoted by $p \land q$ , is defined by the truth table:

$p 0011 q 0101 p \land q 0001$

Note

Each row in the table represents one possible case. The conjunction $p \land q$ is true only when both $p$ and $q$ are true, just as in ordinary language.

The symbols $p$ , $q$ , and $r$ are commonly used as placeholders for propositions, similar to how $x$ , $y$ , and $z$ are used for numeric variables.

Example: Logical Conjunction

Suppose we want to solve for $x$ such that $x > 0$ and $x < 5$ . This means $x$ must satisfy both conditions simultaneously:

$x > 0 \land x < 5.$

In Python, we can write this as:

x = 3
if x > 0 and x < 5:
    print("x is between 0 and 5")

Logical Disjunction (OR)

If $p$ and $q$ are propositions, their disjunction, " $p$ or $q$ ," denoted by $p \lor q$ , is defined by:

$p 0011 q 0101 p \lor q 0111$

This operation reflects the inclusive or, meaning the result is true if either or both propositions are true.

Example: Logical Disjunction

A quadratic equation $x^{2} = 9$ has two possible solutions:

$x = 3 \lor x = - 3.$

In Python, we can write this as:

x = -3
if x == 3 or x == -3:
    print("x is a solution to x^2 = 9")

Logical Negation (NOT)

Negation, denoted by $\neg p$ , is the only standard operation that applies to a single proposition.

$p 01 \neg p 10$

Example: Logical Negation

To express that $x$ is not equal to $5$ , we write

$\neg (x = 5) .$

In Python, we can write this as:

x = 7
if not x == 5:
    print("x is not 5")

Conditional Statement (IF...THEN...)

The conditional statement "If $p$ then $q$ ," denoted $p \to q$ , is defined by:

$p 0011 q 0101 p \to q 1101$

The conditional is false only when $p$ is true and $q$ is false.

Example: Conditional Statement

The statement "If $x = 2$ , then $x^{2} = 4$ " can be written as

$x = 2 \to x^{2} = 4.$

In Python, we can write:

x = 2
if x == 2:
    print("Then x squared is", x**2)

Converse and Contrapositive

Note: Converse and Contrapositive

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

For example:

Original: "If you score 95 or better on the exam, then you will receive an A."
Converse: "If you receive an A, then you scored 95 or better."

These statements are not logically equivalent.

The contrapositive of $p \to q$ is $\neg q \to \neg p$ . Unlike the converse, the contrapositive is logically equivalent to the original conditional. This equivalence is often used in proofs because proving the contrapositive can be simpler.

Biconditional (IF AND ONLY IF)

If $p$ and $q$ are propositions, the biconditional, " $p$ if and only if $q$ ," denoted $p \leftrightarrow q$ , is defined by:

$p 0011 q 0101 p \leftrightarrow q 1001$

The biconditional is true when $p$ and $q$ share the same truth value, i.e., both true or both false.

Example: Biconditional Statement

A number $x$ is zero if and only if both $x \geq 0$ and $x \leq 0$ :

$x = 0 \leftrightarrow (x \geq 0 \land x \leq 0) .$

In Python, we can write:

x = 0
if (x == 0) == (x >= 0 and x <= 0):
    print("x is zero")

Logical Implication

A proposition $p$ logically implies a proposition $q$ (written as $p ⟹ q$ or $p \Rightarrow q$ ) if whenever $p$ is true, $q$ is also true.

Equivalently, the conditional statement $p \to q$ is a tautology, meaning it is true in every possible case.

Example: Logical Implication

Let $p$ be "It is raining" and let $q$ be "The ground is wet."

If every time it rains the ground is wet, then we can write:

$p ⟹ q .$

This does not mean it is currently raining or that the ground is wet; it simply states that the truth of $p$ guarantees the truth of $q$ .

Note on `\rightarrow` vs `\Rightarrow`

The symbols $\to$ and $\Rightarrow$ are related but have different roles:

Symbol	Usage	Example	Meaning
$p \to q$	Conditional inside logic	"If it is raining, then the ground is wet."	Defines a logical relationship between $p$ and $q$ .
$p, p \to q \Rightarrow q$	Inference in reasoning	Given "It is raining" and "If it rains, the ground is wet," we can conclude "The ground is wet."	Expresses a reasoning step or consequence.

Think of $\to$ as part of the formula itself and $\Rightarrow$ as indicating a conclusion or reasoning step in a proof.

Logical Equivalence

Two propositions $p$ and $q$ are logically equivalent (written as $p \equiv q$ ) if they always have the same truth value.

Equivalently, the biconditional

$p \leftrightarrow q$

is a tautology.

Example: De Morgan's Law

Consider:

$p$ : "I have been to Toronto."
$q$ : "I have been to Chicago."

Now compare these two propositions:

$\neg (p \land q)$ : "I have not been to both Toronto and Chicago."
$\neg p \lor \neg q$ : "I have not been to Toronto or I have not been to Chicago."

At first glance, they appear different. But if you examine all possible truth values for $p$ and $q$ , you will find they always match. Thus:

$\neg (p \land q) \equiv \neg p \lor \neg q .$

This relationship is an example of De Morgan's Law.

Example: Logical Equivalence

The condition " $x$ is not less than $5$ " is equivalent to " $x$ is greater than or equal to $5$ ":

$\neg (x < 5) \equiv x \geq 5.$

In Python, we can write this as:

x = 7
if not x < 5:
    print("x is greater than or equal to 5")

Tautologies and Contradictions

Understanding tautologies and contradictions is key to working with implication and equivalence.

Tautology

Definition: Tautology

A tautology is a logical expression that is true in every possible case. The symbol $1$ is often used to denote a tautology.

Examples: Tautologies

Examples of tautologies include:

$p \lor \neg p$ ("Either $p$ is true, or it is not.")
$(p \land q) \to p$ ("If both $p$ and $q$ are true, then $p$ is true.")

Example: A Tautology in Python

In any equation, " $x = x$ " is always true.

In Python, we can write this as:

x = 42
if x == x:
    print("This is always true")

Contradiction

Definition: Contradiction

A contradiction is a logical expression that is false in every possible case. The symbol $0$ is often used to denote a contradiction.

Examples: Contradictions

Examples of contradictions include:

$p \land \neg p$ (" $p$ and not $p$ ," which is impossible to be true simultaneously.)
$(p \lor q) \land (\neg p) \land (\neg q)$ ("Either $p$ or $q$ is true, but neither $p$ nor $q$ is true.")

Example: A Contradiction in Python

" $x > 5$ and $x < 5$ " can never be true:

$(x > 5) \land (x < 5) .$

In Python, we can write this as:

x = 5
if x > 5 and x < 5:
    print("This will never run")

Why Tautologies Matter

Implication: A statement $p ⟹ q$ holds if and only if the conditional $p \to q$ is a tautology.
Equivalence: Two statements $p$ and $q$ are equivalent if the biconditional $p \leftrightarrow q$ is a tautology.

This connection between tautologies, implication, and equivalence is fundamental to mathematical logic and proof techniques.

Mathematics Brush-up for Data Science

Chapter 10: Mathematical Logic

Propositions

Logical Operations

Logical Conjunction (AND)

Logical Disjunction (OR)

Logical Negation (NOT)

Conditional Statement (IF...THEN...)

Converse and Contrapositive

Biconditional (IF AND ONLY IF)

Logical Implication

Note on `\rightarrow` vs `\Rightarrow`

Logical Equivalence

Tautologies and Contradictions

Tautology

Contradiction

Why Tautologies Matter

Chapter Exercises

Keyboard shortcuts

Mathematics Brush-up for Data Science