Mathematical Logic and Proof

P P Savani University

July 24, 2025

(P P Savani University) Mathematical Logic and Proof July 24, 2025 1 / 57

 Propositions

(P P Savani University) Mathematical Logic and Proof July 24, 2025 2 / 57

 Propositions

Propositions

Propositions

A proposition is a declarative sentence (i.e., a sentence that declares a fact)

that is either true or false, but not both.

Example: All the following declarative sentences are propositions.

1 Washington, D.C., is the capital of the United States of America.
2 Toronto is the capital of Canada.
3 1+1=2
4 2+2=3
J
(P P Savani University) Mathematical Logic and Proof July 24, 2025 3 / 57
 Propositions

Example: Consider the following sentences.

1 What time is it?
2 Read this carefully.
3 x + 1 = 2.
4 x + y = z.
Sentences 1 and 2 are not propositions because they are not declarative sentences.
Sentences 3 and 4 are not propositions because they are neither true nor false. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 4 / 57

 Propositions

Negation of proposition

Let p be a proposition. The negation of p, denoted by ¬p (also denoted by p̄),

is the statement “It is not the case that p.” The proposition ¬p is read “not
p.” The truth value of the negation of p, “¬p”, is the opposite of the truth
value of p.

p ¬p
T F
F T
Table: The Truth Table for the Negation of a Proposition

(P P Savani University) Mathematical Logic and Proof July 24, 2025 5 / 57

 Propositions

Conjunction
Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is
the proposition “p and q.” The conjunction p ∧ q is true when both p and q
are true and is false otherwise.

p q p∧q
T T T
T F F
F T F
F F F
Table: The Truth Table for the Conjunction of Two Propositions

(P P Savani University) Mathematical Logic and Proof July 24, 2025 6 / 57

 Propositions

Disjunction
Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is
the proposition “p or q.” The disjunction p ∨ q is false when both p and q are
false and is true otherwise.

p q p∨q
T T T
T F T
F T T
F F F
Table: The Truth Table for the Disjunction of Two Propositions

(P P Savani University) Mathematical Logic and Proof July 24, 2025 7 / 57

 Propositions

Exclusive Or
Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q,
is the proposition that is true when exactly one of p and q is true and is false
otherwise.

p q p⊕q
T T F
T F T
F T T
F F F
Table: The Truth Table for the Exclusive Or of Two Propositions

(P P Savani University) Mathematical Logic and Proof July 24, 2025 8 / 57

 Propositions

Conditional Statements
Let p and q be propositions. The conditional statement p → q is the proposition
“if p, then q.” The conditional statement p → q is false when p is true and
q is false, and true otherwise. In the conditional statement p → q, p is called
the hypothesis (or antecedent or premise) and q is called the conclusion (or
consequence).

p q p→q
T T T
T F F
F T T
F F T
(P P Savani University) Mathematical Logic and Proof July 24, 2025 9 / 57
 Propositions

CONVERSE, CONTRAPOSITIVE, AND INVERSE

Converse of proposition
The proposition q → p is called the converse of p → q.

Contrapositive of proposition
The contrapositive of p → q is the proposition ¬q → ¬p.

Inverse of proposition
The proposition ¬p → ¬q is called the inverse of p → q.

(P P Savani University) Mathematical Logic and Proof July 24, 2025 10 / 57

 Propositions

Conditional Converse Contrapositive Inverse

p q p→q q→p ¬q → ¬p ¬p → ¬q
T T T T T T
T F F T F T
F T T F T F
F F T T T T
Table: The Truth Table for the four Propositions

(P P Savani University) Mathematical Logic and Proof July 24, 2025 11 / 57

 Propositions

Biconditional statement
Let p and q be propositions. The biconditional statement p ↔ q is the
proposition “p if and only if q.” The biconditional statement p ↔ q is true
when p and q have the same truth values, and is false otherwise. Biconditional
statements are also called bi-implications.

p q p↔q
T T T
T F F
F T F
F F T
Table: The Truth Table for the Biconditional p ↔ q
(P P Savani University) Mathematical Logic and Proof July 24, 2025 12 / 57
 Propositions

Truth Tables of Compound Propositions

Example: Construct the truth table of the compound proposition (p∨¬q) → (p∧q).

p q ¬q p ∨ ¬q p∧q (p ∨ ¬q) → (p ∧ q)
T T F T T T
T F T T F F
F T F F F T
F F T T F F
Table: The Truth Table of (p ∨ ¬q) → (p ∧ q)

(P P Savani University) Mathematical Logic and Proof July 24, 2025 13 / 57

 Algebra of Proposition

Algebra of Proposition

(P P Savani University) Mathematical Logic and Proof July 24, 2025 14 / 57

 Algebra of Proposition

Definition
A compound proposition that is always true, no matter what the truth values of the
propositional variables that occur in it, is called a tautology. A compound proposition that is
always false is called a contradiction. A compound proposition that is neither a tautology nor
a contradiction is called a contingency.

Example: We can construct examples of tautologies and contradictions using just one propositional
variable. Consider the truth tables of p ∨ ¬p and p ∧ ¬p, shown in Table. Because p ∨ ¬p is always
true, it is a tautology. Because p ∧ ¬p is always false, it is a contradiction.

p ¬p p ∨ ¬p p ∧ ¬p
T F T F
F T T F
Table: Example of a Tautology and a Contradiction

(P P Savani University) Mathematical Logic and Proof July 24, 2025 15 / 57

 Algebra of Proposition

Logical Equivalences

Definition
The compound propositions p and q are called logically equivalent if p ↔ q is
a tautology. The notation p ≡ q denotes that p and q are logically equivalent.

OR
Compound propositions that have the same truth values in all possible cases
are called logically equivalent.

One way to determine whether two compound propositions are equivalent is to use a
truth table. In particular, the compound propositions p and q are equivalent if and
only if the columns giving their truth values agree.
(P P Savani University) Mathematical Logic and Proof July 24, 2025 16 / 57
 Algebra of Proposition

Example: Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent.

Solution:
p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
Table: Truth Table for ¬(p ∨ q) and ¬p ∧ ¬q

The truth values of the compound propositions ¬(p ∨ q) and ¬p ∧ ¬q agree for all
possible combinations of the truth values of p and q.
It follows that ¬(p ∨ q) ↔ (¬p ∧ ¬q) is a tautology and that these compound
propositions are logically equivalent. J
(P P Savani University) Mathematical Logic and Proof July 24, 2025 17 / 57
 Algebra of Proposition

¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Table: De Morgan’s Laws

This logical equivalence is one of the two De Morgan laws.

(P P Savani University) Mathematical Logic and Proof July 24, 2025 18 / 57

 Algebra of Proposition

Example: Show that p → q and ¬p ∨ q are logically equivalent.

Solution:
p q ¬p ¬p ∨ q p→q
T T F T T
T F F F F
F T T T T
F F T T T
Table: Truth Table for ¬p ∨ q and p → q

Because the truth values of ¬p ∨ q and p → q agree, they are logically equivalent. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 19 / 57

 Algebra of Proposition

Example: Show that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) are logically equivalent. This

is the distributive law of disjunction over conjunction.
Solution:
p q r q ∧ r p ∨ (q ∧ r) p ∨ q p ∨ r (p ∨ q) ∧ (p ∨ r)
T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F
Table: A Demonstration that p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) Are Logically Equivalent
(P P Savani University) Mathematical Logic and Proof July 24, 2025 20 / 57
 Algebra of Proposition

Equivalence Name
p∧T ≡p Identity laws
p∨F ≡p
p∨T ≡T Domination laws
p∧F ≡F
p∨p≡p Idempotent laws
p∧p≡p
¬(¬p) ≡ p Double negation law
p∨q ≡q∨p Commutative laws
p∧q ≡q∧p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(P P Savani University) Mathematical Logic and Proof July 24, 2025 21 / 57
 Algebra of Proposition

Equivalence Name
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan’s laws
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ∨ (p ∧ q) ≡ p Absorption laws
p ∧ (p ∨ q) ≡ p
p ∨ ¬p ≡ T Negation laws
p ∧ ¬p ≡ F

(P P Savani University) Mathematical Logic and Proof July 24, 2025 22 / 57

 Algebra of Proposition

p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p
p ∨ q ≡ ¬p → q
p ∧ q ≡ ¬(p → ¬q)
¬(p → q) ≡ p ∧ ¬q
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
(p → r) ∧ (q → r) ≡ (p ∨ q) → r
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
Table: Logical Equivalences Involving Conditional Statements

(P P Savani University) Mathematical Logic and Proof July 24, 2025 23 / 57

 Algebra of Proposition

p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ ¬p ↔ ¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
¬(p ↔ q) ≡ p ↔ ¬q
Table: Logical Equivalences Involving Bi-conditional Statements

(P P Savani University) Mathematical Logic and Proof July 24, 2025 24 / 57

 Algebra of Proposition

Predicates and Quantifiers

(P P Savani University) Mathematical Logic and Proof July 24, 2025 25 / 57

 Predicates and Quantifiers

Predicates

The statement “x is greater than 3” has two parts. The first part, the variable x,
is the subject of the statement. The second part — the predicate, “is greater
than 3”— refers to a property that the subject of the statement can have. We can
denote the statement “x is greater than 3” by P (x), where P denotes the predicate
“is greater than 3” and x is the variable. The statement P (x) is also said to be the
value of the propositional function P at x. Once a value has been assigned to the
variable x, the statement P (x) becomes a proposition and has a truth value.

(P P Savani University) Mathematical Logic and Proof July 24, 2025 26 / 57

 Predicates and Quantifiers

Example: Let P (x) denote the statement “x > 3”. What are the truth values of
P (4) and P (2)?
Solution: We obtain the statement P (4) by setting x = 4 in the statement “x > 3”.
Hence, P (4), which is the statement “4 > 3”, is true. However, P (2), which is the
statement “2 > 3”, is false. J

Example: Let A(x) denote the statement “Computer x is under attack by an

intruder”. Suppose that of the computers on campus, only C2 and C3 are currently
under attack by intruders. What are truth values of A(C1), A(C2), and A(C3)?
Solution: We obtain the statement A(C1) by setting x = C1 in the statement
“Computer x is under attack by an intruder”. Because C1 is not on the list of
computers currently under attack, we conclude that A(C1) is false. Similarly, because
C2 and C3 are on the list of computers under attack, we know that A(C2) and A(C3)
are true. J
(P P Savani University) Mathematical Logic and Proof July 24, 2025 27 / 57
 Predicates and Quantifiers

We can also have statements that involve more than one variable. For instance,
consider the statement “x = y + 3”. We can denote this statement by Q(x, y),
where x and y are variables and Q is the predicate. When values are assigned to the
variables x and y, the statement Q(x, y) has a truth value.

Example: Let Q(x, y) denote the statement “x = y + 3”. What are the truth values
of the propositions Q(1, 2) and Q(3, 0)?
Solution: To obtain Q(1, 2), set x = 1 and y = 2 in the statement Q(x, y). Hence,
Q(1, 2) is the statement “1 = 2 + 3”, which is false. The statement Q(3, 0) is the
proposition “3 = 0 + 3”, which is true. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 28 / 57

 Predicates and Quantifiers

Quantifiers

Universal Quantifier

The universal quantification of P (x) is the statement

“P (x) for all values of x in the domain.”

The notation ∀xP (x) denotes the universal quantification of P (x). Here ∀ is
called the universal quantifier. We read ∀xP (x) as “for all xP (x)” or “for
every xP (x)”. An element for which P (x) is false is called a counterexample
of ∀xP (x).

(P P Savani University) Mathematical Logic and Proof July 24, 2025 29 / 57

 Predicates and Quantifiers

Existential Quantifier

The existential quantification of P (x) is the proposition

“There exists an element x in the domain such that P (x)”.
We use the notation ∃xP (x) for the existential quantification of P (x). Here ∃
is called the existential quantifier.

Statement When True? When False?

∀xP (x) P (x) is true for every x. There is an x for which P (x) is
false.
∃xP (x) There is an x for which P (x) is P (x) is false for every x.
true.
Table: Quantifiers
(P P Savani University) Mathematical Logic and Proof July 24, 2025 30 / 57
 Predicates and Quantifiers

Example: Let P (x) be the statement “x + 1 > x”. What is the truth value of the
quantification ∀xP (x), where the domain consists of all real numbers?
Solution: Because P (x) is true for all real numbers x, the quantification ∀xP (x) is
true. J

Example: Let Q(x) be the statement “x < 2”. What is the truth value of the
quantification ∀xQ(x), where the domain consists of all real numbers?
Solution: Q(x) is not true for every real number x, because, for instance, Q(3) is
false. That is, x = 3 is a counterexample for the statement ∀xQ(x). Thus ∀xQ(x) is
false. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 31 / 57

 Predicates and Quantifiers

Example: What is the truth value of ∀xP (x), where P (x) is the statement “x2 < 10”
and the domain consists of the positive integers not exceeding 4?
Solution: The statement ∀xP (x) is the same as the conjunction

P (1) ∧ P (2) ∧ P (3) ∧ P (4),

because the domain consists of the integers 1, 2, 3, and 4. Because P (4), which is the
statement “42 < 10”, is false, it follows that ∀xP (x) is false. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 32 / 57

 Predicates and Quantifiers

Example: Let P (x) denote the statement “x > 3”. What is the truth value of the
quantification ∃xP (x), where the domain consists of all real numbers?
Solution: Because “x > 3” is sometimes true — for instance, when x = 4 — the
existential quantification of P (x), which is ∃xP (x), is true. J

Example: Let Q(x) denote the statement “x = x + 1”. What is the truth value of
the quantification ∃xQ(x), where the domain consists of all real numbers?
Solution: Because Q(x) is false for every real number x, the existential
quantification of Q(x), which is ∃xQ(x), is false. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 33 / 57

 Predicates and Quantifiers

Example: What is the truth value of ∃xP (x), where P (x) is the statement “x2 > 10”
and the universe of discourse consists of the positive integers not exceeding 4?
Solution: Because the domain is {1, 2, 3, 4}, the proposition ∃xP (x) is the same as
the disjunction
P (1) ∨ P (2) ∨ P (3) ∨ P (4).
Because P (4), which is the statement “42 > 10”, is true, it follows that ∃xP (x) is
true. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 34 / 57

 Predicates and Quantifiers

Precedence of Quantifiers

The quantifiers ∀ and ∃ have higher precedence than all logical operators from
propositional calculus. For example, ∀xP (x) ∨ Q(x) is the disjunction of ∀xP (x)
and Q(x). In other words, it means (∀xP (x)) ∨ Q(x) rather than ∀x(P (x) ∨ Q(x)).

(P P Savani University) Mathematical Logic and Proof July 24, 2025 35 / 57

 Predicates and Quantifiers

Nested Quantifiers
Assume that the domain for the variables x and y consists of all real numbers. The
statement ∀x∀y(x + y = y + x)
says that x + y = y + x for all real numbers x and y. This is the commutative law
for addition of real numbers. Likewise, the statement

∀x∃y(x + y = 0)

says that for every real number x there is a real number y such that x + y = 0. This
states that every real number has an additive inverse. Similarly, the statement

∀x∀y∀z(x + (y + z) = (x + y) + z)

is the associative law for addition of real numbers.

(P P Savani University) Mathematical Logic and Proof July 24, 2025 36 / 57
 Rules of Inference

Rules of Inference

(P P Savani University) Mathematical Logic and Proof July 24, 2025 37 / 57

 Rules of Inference

Definition
An argument in propositional logic is a sequence of propositions. All but the
final proposition in the argument are called premises and the final proposition
is called the conclusion. An argument is valid if the truth of all its premises
implies that the conclusion is true.

(P P Savani University) Mathematical Logic and Proof July 24, 2025 38 / 57

 Rules of Inference

Example: Consider the following argument involving propositions (which, by

definition, is a sequence of propositions):
“If you have a current password, then you can log onto the network”.
“You have a current password”.
Therefore,
“You can log onto the network”.
We would like to determine whether this is a valid argument. That is, we
would like to determine whether the conclusion “You can log onto the network” must
be true when the premises “If you have a current password, then you can log onto
the network” and “You have a current password” are both true.

(P P Savani University) Mathematical Logic and Proof July 24, 2025 39 / 57

 Rules of Inference

Before we discuss the validity of this particular argument, we will look at its form.
Use p to represent “You have a current password” and q to represent “You can log
onto the network.” Then, the argument has the form

p→q
p
∴ q

“If you have access to the network, then you can change your grade”.
“You have access to the network”.
∴ “You can change your grade”.

(P P Savani University) Mathematical Logic and Proof July 24, 2025 40 / 57

 Rules of Inference

TABLE 1 Rules of Inference.

Rule of Inference Tautology Name

p (p ∧ (p → q)) → q Modus ponens

p→q
∴ q

¬q (¬q ∧ (p → q)) → ¬p Modus tollens

p→q
∴ ¬p

p→q ((p → q) ∧ (q → r)) → (p → r) Hypothetical syllogism

q→r
∴ p→r

p∨q ((p ∨ q) ∧ ¬p) → q Disjunctive syllogism

¬p
∴ q

p p → (p ∨ q) Addition
(P P Savani University) Mathematical Logic and Proof July 24, 2025 41 / 57
 Rules of Inference
p∨q ((p ∨ q) ∧ ¬p) → q Disjunctive syllogism
¬p
∴ q

p p → (p ∨ q) Addition
∴ p∨q

p∧q (p ∧ q) → p Simplification
∴ p

p ((p) ∧ (q)) → (p ∧ q) Conjunction

q
∴ p∧q

p∨q ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r) Resolution

¬p ∨ r
∴ q ∨r

AMPLE 3 State which rule of inference is the basis of the following argument: “It is below freezing now.
Therefore, it is either below freezing or raining now.”
(P P Savani University) Mathematical Logic and Proof July 24, 2025 42 / 57
 Rules of Inference

Example: State which rule of inference is used in the argument:

If it rains today, then we will not have a barbecue today. If we do not have a barbecue
today, then we will have a barbecue tomorrow. Therefore, if it rains today, then we
will have a barbecue tomorrow.
Solution: Let p be the proposition “It is raining today”, let q be the proposition
“We will not have a barbecue today”, and let r be the proposition “We will have a
barbecue tomorrow”. Then this argument is of the form

p→q
q→r
∴ p→r

Hence, this argument is a hypothetical syllogism. J

(P P Savani University) Mathematical Logic and Proof July 24, 2025 43 / 57

 Rules of Inference

τ ~αnk Ψφu !!

(P P Savani University) Mathematical Logic and Proof July 24, 2025 44 / 57

 Temporary page!

LATEX was unable to guess the total number of pages correctly. As there
unprocessed data that should have been added to the final page this extra
been added to receive it.
If you rerun the document (without altering it) this surplus page will go away
LATEX now knows how many pages to expect for this document.