Chapter 14: Mathematical Logic

This chapter introduces the basic concepts of mathematical logic. These principles form part of the foundation for digital circuits, formal mathematical reasoning, and conditional logic in programming. The focus is the mathematical language of propositions, predicates, connectives, and truth tables.

Propositions and Predicates

Propositions and predicates both express mathematical claims, but they differ in whether a truth value has already been determined. A proposition is a complete statement that is true or false. A predicate contains one or more variables and becomes a proposition after values are assigned to the variables or after a claim is made about the allowed values.

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)

Definition: Predicate and Domain

A statement involving an unspecified variable, such as " $x > 0$ " or " $x$ is even," is called a predicate or open statement. It does not yet have one fixed truth value. The domain is the set of allowed values for the variable, and the truth of the predicate depends on which value is chosen from this set.

Example: Predicate

Let $P (x)$ be the predicate " $x$ is even" with domain $x \in Z$ . Substituting a value for $x$ produces a proposition: $P (4)$ is true, while $P (5)$ is false.

Stating that $P (x)$ holds for every integer, or that it holds for at least one integer, also produces a proposition. The symbols for these statements are introduced near the end of the chapter.

A flow from a predicate and a selected domain value to a proposition with a definite truth value. — Figure 14.1. Here, $D$ is the domain (the set of allowed values for $x$ ), and choosing $a \in D$ turns the predicate $P (x)$ into the proposition $P (a)$ with a definite truth value.

The distinction provides the link to logical operations: predicates describe conditions, substituted values turn those conditions into propositions, and logical connectives combine propositions into more complex statements. This framework supports mathematical proofs and conditional statements in programs.

Logical Operations

Logical operations extend the connection between predicates and propositions. If $P (x)$ and $Q (x)$ are predicates with the same domain, then the combined condition " $P (x)$ and $Q (x)$ " is a new predicate. After a value $a$ is selected, $P (a)$ and $Q (a)$ are propositions, and their combined statement has a definite truth value.

More generally, propositions can be combined using logical connectives such as and, or, not, if...then..., and if and only if. Each connective has a precise meaning and a 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.

Definitions: Logical Connectives

Logical connectives are symbols or words used to build compound propositions from simpler propositions.

Conjunction. The connective $p \land q$ means " $p$ and $q$ " and is true only when both propositions are true.

Disjunction. The connective $p \lor q$ means " $p$ or $q$ " and is true when at least one proposition is true.

Negation. The connective $\neg p$ means "not $p$ " and reverses the truth value of $p$ .

Conditional. The connective $p \to q$ means "if $p$ , then $q$ " and is false only when $p$ is true and $q$ is false.

Biconditional. The connective $p \leftrightarrow q$ means " $p$ if and only if $q$ " and is true when $p$ and $q$ have the same truth value.

An AND gate with inputs p and q and output p and q. — Figure 14.2. The logical connectives AND, OR, and NOT correspond directly to three basic gates used in digital circuits.

An OR gate with inputs p and q and output p or q. — Figure 14.2. The logical connectives AND, OR, and NOT correspond directly to three basic gates used in digital circuits.

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: Reading Truth Tables

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: Conjunction

For $x \in R$ , the conditions $x > 0$ and $x < 5$ require $x$ to satisfy both inequalities simultaneously:

$x > 0 \land x < 5.$

The following values illustrate that the conjunction is true only when both inequalities are true:

Table 14.1. Truth values for a conjunction of two inequalities.

$x$	$x > 0$	$x < 5$	$(x > 0) \land (x < 5)$
$0$	0	1	0
$3$	1	1	1
$5$	1	0	0

Thus, the conjunction is true exactly for $0 < x < 5$ .

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: Disjunction

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

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

For $x \in R$ , the following values illustrate that the disjunction is true when at least one of the equations is true:

Table 14.2. Truth values for a disjunction of two equations.

$x$	$x = 3$	$x = - 3$	$(x = 3) \lor (x = - 3)$
$- 3$	0	1	1
$0$	0	0	0
$3$	1	0	1

Thus, the disjunction is true exactly for $x = 3$ or $x = - 3$ .

Negation (NOT)

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

$p 01 \neg p 10$

Example: Negation

The statement that $x$ is not equal to $5$ is written

$\neg (x = 5) .$

For $x \in R$ , the following values illustrate that negation reverses the truth value of the original equation:

Table 14.3. Truth values for negating an equation.

$x$	$x = 5$	$\neg (x = 5)$
$5$	1	0
$7$	0	1
$0$	0	1

Conditional

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. The symbol $\to$ is a logical connective: it combines $p$ and $q$ to form a new proposition whose truth value is given by the table. It does not by itself state that $p$ is true or that $q$ has been inferred.

Example: Conditional

Let $x \in Z$ and consider the conditional predicate "If $x$ is greater than $10$ , then $x$ is even." This is written

$(x > 10) \to (x is even) .$

The selected values illustrate the four possible combinations and highlight the case where the conditional is false:

Table 14.4. Truth values for a conditional statement.

$x$	$x > 10$	$x$ is even	$(x > 10) \to (x is even)$
$12$	1	1	1
$11$	1	0	0
$8$	0	1	1
$7$	0	0	1

Converse and Contrapositive

Note: Converse and Contrapositive

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

The contrapositive of $p \to q$ is $\neg q \to \neg p$ . The original conditional and its contrapositive always have the same truth value, while the converse need not have the same truth value.

Example: Conditional Forms

Let the domain be the integers, and define the predicates

$P (n)$ : " $n$ is divisible by $4$ ," and
$Q (n)$ : " $n$ is even."

The three associated conditional forms are:

Original: $P (n) \to Q (n)$ .
Converse: $Q (n) \to P (n)$ .
Contrapositive: $\neg Q (n) \to \neg P (n)$ .

The relationship between these forms comes from the truth table:

Table 14.5. Truth values for a conditional, its converse, and its contrapositive.

$p$	$q$	$p \to q$	$q \to p$	$\neg q \to \neg p$
0	0	1	1	1
0	1	1	0	1
1	0	0	1	0
1	1	1	1	1

The original and contrapositive columns agree in every row. For the integer predicates, the original conditional holds for every integer because a number divisible by $4$ can be written as $n = 4 k = 2 (2 k)$ for some $k \in Z$ and is therefore even. The converse is false: $6$ is even but is not divisible by $4$ . The contrapositive states that an integer that is not even cannot be divisible by $4$ , and its truth values match those of the original conditional.

Biconditional

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. Like the conditional, $\leftrightarrow$ is a connective that forms a proposition. A particular biconditional may therefore be true or false. It expresses logical equivalence only when it is true in every possible case.

Example: Biconditional

For a real number $x$ , the number is zero if and only if both $x \geq 0$ and $x \leq 0$ :

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

Both sides have the same truth value for every real number $x$ .

Example: Biconditional Inequality

For a real number $x$ , compare the conditions " $x$ is not less than $5$ " and " $x$ is greater than or equal to $5$ ":

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

The table illustrates the agreement for three values. The two predicates agree for every real $x$ because any real number that is not less than $5$ must be greater than or equal to $5$ :

Table 14.6. Truth values for a biconditional involving inequalities.

$x$	$x < 5$	$\neg (x < 5)$	$x \geq 5$	$\neg (x < 5) \leftrightarrow x \geq 5$
$3$	1	0	0	1
$5$	0	1	1	1
$7$	0	1	1	1

Tautologies and Contradictions

Tautologies and contradictions describe expressions whose truth values do not vary from one possible case to another.

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

A tautology covers every possible truth case. Examples 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: Tautological Predicate

Over the domain $R$ , consider the predicate

$(x = 5) \lor (x \neq = 5)$

For each fixed value of $x$ , this predicate becomes a true proposition. It has the tautological form $P (x) \lor \neg P (x)$ . Equivalently, the statement "for every real number $x$ , either $x = 5$ or $x \neq = 5$ " is a true proposition.

The table illustrates the predicate for a few values. Its universal truth does not follow from testing these examples; it follows because every value of $x$ is either equal to $5$ or not equal to $5$ :

Table 14.7. Truth values showing a tautology.

$x$	$x = 5$	$x \neq = 5$	$(x = 5) \lor (x \neq = 5)$
$5$	1	0	1
$3$	0	1	1
$42$	0	1	1

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

A contradiction combines conditions in a way that can never be satisfied. Examples 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: Contradictory Predicate

Over the domain $R$ , consider the predicate

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

For each fixed value of $x$ , this predicate becomes a false proposition. Equivalently, the statement "for every real number $x$ , it is not the case that both $x > 5$ and $x < 5$ " is a true proposition.

The table illustrates the predicate for a few values. The conclusion for every real $x$ follows because no number can be both greater than and less than $5$ :

Table 14.8. Truth values showing a contradiction.

$x$	$x > 5$	$x < 5$
$3$	0	1
$5$	0	0
$7$	1	0

Logical Equivalence

Two propositional expressions $p$ and $q$ are logically equivalent, written $p \equiv q$ , if they have the same truth value under every assignment of truth values to their component propositions. The symbol $\equiv$ states that this general relationship has been established; it is not another connective with a separate truth table. Equivalently, the biconditional

$p \leftrightarrow q$

is a tautology.

The conditional and its contrapositive give one example:

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

Example: De Morgan's Law

Consider two propositions:

$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."

The two expressions have the same truth value in every possible case. Thus:

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

Table 14.9. Truth values for De Morgan's law.

$p$	$q$	$\neg (p \land q)$	$\neg p \lor \neg q$
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

The final two columns agree in every row, which verifies the equivalence.

Example: Logical Equivalence

Over the domain $R$ , the predicate " $x$ is not less than $5$ " is logically equivalent to " $x$ is greater than or equal to $5$ ":

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

Implication and Bi-implication

The earlier sections distinguished propositions from predicates. If $p$ and $q$ are propositions, then $p \to q$ and $p \leftrightarrow q$ are compound propositions with truth values determined by their truth tables. If $P (x)$ and $Q (x)$ are predicates with the same domain, then

$P (x) \to Q (x) and P (x) \leftrightarrow Q (x)$

are also predicates. Choosing a value $a$ from the domain turns them into the propositions $P (a) \to Q (a)$ and $P (a) \leftrightarrow Q (a)$ . These propositions may be true for some values and false for others.

Implication arises when the corresponding conditional is valid throughout the relevant domain. If $P (x) \to Q (x)$ is true for every allowed value of $x$ , then $P$ implies $Q$ , written

$P (x) \Rightarrow Q (x) .$

Similarly, bi-implication arises when the corresponding biconditional is valid throughout the domain. If $P (x) \leftrightarrow Q (x)$ is true for every allowed value of $x$ , then $P$ and $Q$ bi-imply one another, written

$P (x) \Leftrightarrow Q (x) .$

For propositional expressions, the same distinction is made across all relevant assignments of truth values. Thus,

$p \Rightarrow q means that p \to q is valid in every relevant case,$

and

$p \Leftrightarrow q means that p \leftrightarrow q is valid in every relevant case .$

Equivalently, a bi-implication consists of two implications, one in each direction:

$p \Leftrightarrow q means p \Rightarrow q and q \Rightarrow p .$

The small arrows $\to$ and $\leftrightarrow$ therefore form propositions that can be evaluated in a particular case. The large arrows $\Rightarrow$ and $\Leftrightarrow$ state that the corresponding relationship is valid in every relevant case.

For propositional expressions, $p \Leftrightarrow q$ and $p \equiv q$ both communicate logical equivalence. This book uses $\equiv$ when comparing logical expressions and also uses $\Leftrightarrow$ for reversible reasoning or algebraic steps with the same solution set. This common convention is used throughout this book, although some texts use these symbols differently.

Example: One-way and Two-way Predicates

Let the domain be $R$ , and define

$P (x)$ : " $x = 2$ ," and
$Q (x)$ : " $x^{2} = 4$ ."

For every real number $x$ , $P (x) \to Q (x)$ is true. Therefore,

$P (x) \Rightarrow Q (x) .$

The reverse conditional fails at $x = - 2$ , because $Q (- 2)$ is true while $P (- 2)$ is false. Consequently, $P$ and $Q$ do not bi-imply one another.

Now define

$R (x)$ : " $2 x + 3 = 7$ ," and
$S (x)$ : " $x = 2$ ."

For every real $x$ , both $R (x) \to S (x)$ and $S (x) \to R (x)$ are true. Hence,

$R (x) \Leftrightarrow S (x),$

or, written directly,

$2 x + 3 = 7 \Leftrightarrow x = 2.$

The two predicates have the same truth value throughout the domain, and the two equations have the same solution set.

Valid Inference

Implication describes a relationship that is valid across the relevant cases. An inference applies propositions in a particular argument: it starts from one or more assumed propositions, called premises, and draws a conclusion. The inference is valid if there is no possible case in which all the premises are true and the conclusion is false.

A predicate does not yet have a fixed truth value, so it must first be turned into a proposition by choosing a value or making a statement about its domain before it can serve as a premise. In this book, $\Rightarrow$ marks a valid conclusion or a one-way reasoning step; it is not a connective used to form a proposition.

Example: Valid Inference

Suppose $p$ and $p \to q$ are both given as premises. Then $q$ follows:

$p, p \to q \Rightarrow q .$

This inference is valid because, when $p$ is true, the conditional $p \to q$ can be true only when $q$ is also true. Thus, there is no case in which both premises are true and the conclusion is false.

Statements that a predicate holds for every value in a domain or for at least one value are propositions. The notation for expressing these domain-wide claims is introduced next.

Additional Notation

A few other foundational logical symbols are commonly used in mathematics. Predicate logic is not developed in detail in this course, but the table below provides a brief overview of notation used in definitions, proofs, and statements about sets or functions.

Quantifiers are especially important because they turn open statements involving variables into propositions by specifying whether a claim holds for every element of a domain or for at least one element. The two central quantifiers, together with closely related notation, are introduced below.

Table 14.10. Common logical notation and its meaning.

Symbol	Operation	Description
$\forall$	Universal quantifier	Means "for all" or "for every"; the statement must hold for every object in the given domain.
$\exists$	Existential quantifier	Means "there exists"; the statement must hold for at least one object in the given domain.
$\exists!$	Unique existence quantifier	Means "there exists exactly one"; the statement must hold for one and only one object in the given domain.

Connection to Set Theory

Logic and set theory describe closely related ideas from different viewpoints. A predicate states a condition that elements of a domain may or may not satisfy, while a set can collect precisely the elements that satisfy that condition. In this way, a logical statement can be viewed as describing membership in a corresponding set.

Logical operations then parallel familiar set operations from Chapter 2: "and" resembles intersection, "or" resembles union, and "not" resembles complement. This connection is also why identities such as De Morgan's laws have the same general structure in logic and set theory.

More precisely, let $p$ mean " $x \in A$ " and let $q$ mean " $x \in B$ ." Then

$p \land q p \lor q \neg p ⟷ x \in A \cap B, ⟷ x \in A \cup B, ⟷ x \in A^{c} .$

In each row, the logical condition and the corresponding set-membership statement are true for exactly the same values of $x$ .

Keyboard shortcuts

Mathematics Brush-up for Data Science