1

Unit-1
The Foundations-Logic and Proofs: Propositional Logic, Propositional Equivalences,
Predicates and Quantifiers, Nested Quantifiers Rules of Inference, Introduction to Proofs,
Proof Methods and Strategy, Basic Structures-Sets, Functions, Sequences and Sums:
Sets, Set Operations, Functions, Sequences and Summations.

Propositional Logic:
A proposition is a declarative sentence (that is, a sentence that declares a fact)
that is either true or false, but not both.
Example: 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

Propositions 1 and 3 are true, whereas 2 and 4 are false.

The area of logic that deals with propositions is called the propositional calculus or
propositional logic. Many mathematical statements are constructed by com- bining one or
more propositions. New propositions, called compound propositions, are formed from
existing propositions using logical operators.

logical operators:

Operator called
¬ Negation
∧ Conjunction
∨
Disjunction
→ Implication
↔ Bi-implication
Negation: 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. the negation of p, other notations you
might see are ∼p, −p, p′, Np, and !p.
p ¬p
T F
F T
Example: Find the negation of the proposition “Michael’s PC runs Linux” and express
this in simple English.
Solution: Given proposition is, p= Michael’s PC runs Linux
The negation is ~p= “It is not the case that Michael’s PC runs Linux.”
This negation can be more simply expressed as
“Michael’s PC does not run Linux.”
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.
 2

p q p∧
q
T T T
T F F
F T F
F F F

Example: Find the conjunction of the propositions p and q where p is the proposition
“Rebecca’s PC has more than 16 GB free hard disk space” and q is the
proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”

Solution: Let p, q are two prepostions.

p= Rebecca’s PC has more than 16 GB free hard disk space.
q= The processor in Rebecca’s PC runs faster than 1 GHz.
p∧q= Rebecca’s PC has more than 16 GB free hard disk space, and its
processor runs faster than 1 GHz.

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

Example: Find the disjunction of the propositions p and q where p is the proposition
“Rebecca’s PC has more than 16 GB free hard disk space” and q is the
proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”

Solution: Let p, q are two prepostions.

p= Rebecca’s PC has more than 16 GB free hard disk space.
q= The processor in Rebecca’s PC runs faster than 1 GHz.
p v q= Rebecca’s PC has more than 16 GB free hard disk space, or its
processor runs faster than 1 GHz.

Exclusive OR: Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q

(or p XOR 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

Example: Let p and q be the propositions that state “A student can have a salad with dinner”
and “A student can have soup with dinner,” respectively. What is p ⊕ q, the
 3

exclusive or of p and q?

Solution: The exclusive or of p and q is the statement that is true when exactly one of p
and q is true.
p= A student can have a salad with dinner
q= A student can have soup with dinner
p ⊕ q= “A student can have soup or salad, but not both, with dinner.”
Or
“A student can have soup or a salad with dinner,”

Conditional statement: 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). A conditional
statement is also called an implication.
p q p→q
T T T
T F F
F T T
F F T

Example: Let p be the statement “Maria learns discrete mathematics” and q the statement “Maria will find a
good job.” Express the statement p → q as a statement in English.
Solution: p= Maria learns discrete mathematics
q= Maria will find a good job.
p->q= “If Maria learns discrete mathematics, then she will find a good job.”
Bi-Conditional 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

Example: Let p be the statement “You can take the flight,” and let q be the statement “You buy a ticket.”
Then p ↔ q is the statement
Solution: “You can take the flight if and only if you buy a ticket.”
Truth Tables of Compound Propositions:
Example: Construct the truth table of the compound proposition (p ∨ ¬q) → (p ∧ q).
Solution :
p q ¬q p ∨ ¬q p∧ (p ∨ ¬q) → (p ∧ q)
q
T T F T T T
T F T T F F
F T F F F T
 4

F F T T F F

Propositional Equivalences: 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: Show that ¬(p ∨ q) and ¬p ∧ ¬q are logically equivalent

Solution:
p∨ ¬(p ∨ ¬p ¬q ¬p ∧
¬q
p q
q 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

Logical Equivalences:
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
p∧q≡ q∧p laws

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan’s
¬(p ∨ q) ≡ ¬p ∧ ¬q laws

p ∨ (p ∧ q) ≡ p Absorption laws
p ∧ (p ∨ q) ≡ p

p ∨ ¬p ≡ T Negation laws
p ∧ ¬p ≡ F
 5

p → q ≡ ¬p ∨ q p ↔ q ≡ (p → q) ∧ (q →
p) p ↔ q ≡ ¬p ↔ ¬q
p → q ≡ ¬q →
¬p p ∨ q ≡ ¬p p ↔ q ≡ (p ∧ q) ∨ (¬p ∧
→q ¬q)

p ∧ q ≡ ¬(p → ¬q)

¬(p → q) ≡ p ∧ ¬q

(p → q) ∧ (p → r) ≡ p → (q ∧
r)

Constructing New Logical Equivalences:

Example 1: Show that ¬(p → q) and p ∧ ¬q are logically equivalent
Solution : ¬(p → q) ≡ ¬(¬p ∨ q) by the conditional-disjunction equivalence (Example 3)
≡ ¬(¬p) ∧ ¬q by the second De Morgan law
≡ p ∧ ¬q by the double negation law

Example 2: Show that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a series of
logical equivalences.
Solution: ¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q) by the second De Morgan law
≡ ¬p ∧ [¬(¬p) ∨ ¬q] by the first De Morgan law
≡ ¬p ∧ (p ∨ ¬q) by the double negation law
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) by the second distributive law
≡ F ∨ (¬p ∧ ¬q) because ¬p ∧ p ≡ F
≡ (¬p ∧ ¬q) ∨ F by the commutative law for
disjunction
≡ ¬p ∧ ¬q by the identity law for F

Predicates and Quantifiers:

Predicate: A sentence or mathematical assertion that contains variables and can be
true or false depending on the values of those variables .

Statements involving variables, such as “x > 3,” “x = y + 3,” “x + y = z,”

Example: Let P(x) denote the statement “x > 3.” What are the truth values of P(4)
and P(2)?
Solution: Let, P(x)= x>3
P(4)= “4 > 3,” is true.
P(2)= “2 > 3,” is false.
Quantifiers: When the variables in a propositional function are assigned values, the
resulting statement becomes a proposition with a certain truth value. However,
there is another important way, called quantification.

Quantifiers are two types:

1. Universal quantifier
2. Existential quantifier
 6

1. 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).”

2. Existensial 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 true. P(x) is false for every x.

Negating Quantified statements:

Negation Equivalent Statement When Is Negation True? When False?

¬∃xP(x) ∀x¬P(x) For every x, P(x) is false. There is an x for which
P(x) is true.
¬∀xP(x) ∃x¬P(x) There is an x for which P(x) is true for every x.
P(x) is false.

Nested Quantifiers: where one quantifier is within the scope of another.

Like., ∀x∃y(x + y = 0),

Example: Translate into English the statement ∀x∀y((x > 0) ∧ (y < 0) → (xy < 0)),where
the domain for both variables consists of all real numbers

Solution: This statement says that for every real number x and for every real number y,
if x > 0 and y < 0, then xy < 0.
x and y, if x is positive and y is negative, then xy is negative.
“The product of a positive real number and a negative real number is always a
negative real number.”

Rules of Inference:

A valid proposition is,

“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.”

The above can be represented as,

p→q
 7

∴q
p

where ∴ is the symbol that denotes “therefore.”

Rules of Inference.
Rule of Inference Tautology Name
p (p ∧ (p → q)) → q Modus ponens

∴ q
p→q

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

∴ ¬p
p→q

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

∴ p→r
q→r

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

∴ p∧q
q

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

¬p ∨ r
∴ q∨r

Using Rules of Inference to Build Arguments:

Example: Show that the premises “It is not sunny this afternoon and it is colder than
yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then
we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset”
lead to the conclusion “We will be home by sunset.”
Solution: Let p = “It is sunny this afternoon,”
 8

q = “It is colder than yesterday,”

r = “We will go swimming,”
s = “We will take a canoe trip,”
t = “We will be home by sunset.”
Then the premises become
¬p ∧ q,
r → p,
¬r → s,
s → t.
The conclusion is simply t.

Step Reason

1. ¬p ∧ q Premise
2. ¬p Simplification using (1)
3. r→p Premise
4. ¬r Modus tollens using (2) and (3)
5. ¬r → s Premise
6. s Modus ponens using (4) and (5)
7. s→t Premise
8. t Modus ponens using (6) and (7)
Rules of Inference for Quantified Statements:

TABLE 2 Rules of Inference for Quantified Statements.

Rule of Inference Name

∴ P(c)
∀xP(x)
Universal instantiation

∴ ∀xP(x)
P(c) for an arbitrary c
Universal generalization

∴ P(c) for some element c

∃xP(x)
Existential instantiation

∴ ∃xP(x)
P(c) for some element c
Existential generalization

Example: Show that the premises “A student in this class has not read the book,” and
“Everyone in this class passed the first exam” imply the conclusion “Someone
who passed the first exam has not read the book.”

Solution: Let C(x) be “x is in this class,” B(x) be “x has read the book,” and P(x) be “x passed
the first exam.” The premises are ∃x(C(x) ∧ ¬B(x)) and ∀x(C(x) → P(x)). The conclusion is
∃x(P(x) ∧ ¬B(x)). These steps can be used to establish the conclusion from the premises.
Step Reason
1. ∃x(C(x) ∧ ¬B(x)) Premise
2. C(a) ∧ ¬B(a) Existential instantiation from (1)
3. C(a) Simplification from (2)
4. ∀x(C(x) → P(x)) Premise
5. C(a) → P(a) Universal instantiation from (4)
6. P(a) Modus ponens from (3) and (5)
7. ¬B(a) Simplification from (2)
8. P(a) ∧ ¬B(a) Conjunction from (6) and (7)
 9

9. ∃x(P(x) ∧ ¬B(x)) Existential generalization from (8)

Introduction to Proofs :

 Theorem: It is a statement that can be shown to be true.

 Propositions : Less important theorems sometimes are called propositions. (Theorems can
also be referred to as facts or results.)
 Proof: A proof is a valid argument that establishes the truth of a theorem.
 Axioms:The statements used in a proof can include axioms (or postulates), which are
statements we assume to be true (universal truths).
 lemma :A less important theorem that is helpful in the proof of other results is called a
lemma (plural lemmas or lemmata).
 A corollary is a theorem that can be established directly from a theorem that has been
proved.
 A conjecture is a statement that is being proposed to be a true statement, usually on the
basis of some partial evidence, a heuristic argument, or the intuition of an expert. Many
times conjectures are shown to be false, so they are not theorems.

Methods of Proving Theorems

1. Direct method
2. Indirect method
3. Proof by contradiction.
1. Direct proof: A direct proof shows that a conditional statement p → q is true by
showing that if p is true, then q must also be true.

Example: Give a direct proof of the theorem “If n is an odd integer, then n2 is odd.”
Solution: theorem states ∀nP((n) → Q(n)),
P(n) = “n is an odd integer”
Q(n) = “n is odd.”
P(n) implies Q(n),

n = 2k + 1 , where k is some integer and n is odd integer.

n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 2(2k2 + 2k) + 1.

2. Indirect proof (proof by contraposition): contraposition make use of the fact that the
conditional statement p → q to its contrapositive, ¬q → ¬p. This means that the
conditional statement p → q can be proved by showing that its contrapositive, ¬q →
¬p, is true. In a proof by contraposition of p → q, we take ¬q as a premise and ¬p as
conclusion.

Example: Prove that if n is an integer and 3n + 2 is odd, then n is odd.

Solution: We first attempt a direct proof.
Assume that 3n + 2 is an odd integer.
From the definition of an odd integer, we know that
3n + 2 = 2k + 1 for some integer k.
(Can we use this fact to show that n is odd? )
proof by contraposition : p= 3n + 2 is odd,
q=n is odd”
~p=3n+2 is even
~q= n is even
Premise ~q= n is even.
 10

n = 2k for some integer k.

3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). (which is even )
Hence contraposition is true then the theorem “If 3n + 2 is odd, then n is odd.”

3. Proof by contradiction: suppose that we can find a contradiction q such

that ¬p → q is true. Because q is false, but ¬p → q is true, we can conclude that
¬p is false, which means that p is true.
√
Example: Prove that 2 is irrational by giving a proof by contradiction
Solution: To prove by contradiction is
√
P= 2 is irrational.
√
~p= 2is rational
¬p → q is true, then ¬p is false
√
~p= 2is rational [This should be false]

√
 2=a/b [squaring both sides]

2=(a/b)2

2b2=a2 If a2 is multiple of 2( even) then a is even .

If we take a=2c some integer c.

2b2=(2c)2

2b2= 4c2

b2=2c2 if b2 is even the b is even.

Proof Strategies:
1. Forward and backward reasoning Whichever method you choose, you need a starting point for
your proof. To begin a direct proof of a conditional statement, you start with the premises. Using
these premises, together with axioms and known theorems, you can construct a proof using a
sequence of steps that leads to the conclusion. This type of reasoning, called forward reasoning, is
the most common type of reasoning used to prove relatively simple results. Similarly, with indirect
reasoning you can start with the negation of the conclusion and, using a sequence of steps, obtain
the negation of the premises.
2. Adapting existing proofs An excellent way to look for possible approaches that can be used to
prove a statement is to take advantage of existing proofs of similar results. Often an existing
proof can be adapted to prove other facts. Even when this is not the case, some of the ideas used
in existing proofs may be helpful. Because existing proofs provide clues for new proofs, you
should read and understand the proofs you encounter in your studies.
 11

√ √
Example: we proved that 2 is irrational. We now conjecture th√at 3 is irrational. Can we
adapt the proof to show that irrational.

3. Proof Strategy in Action: Mathematics texts (including the bulk of this book) formally present
theorems and their proofs. Such presentations do not convey the discovery process in
mathematics. This process begins with exploring concepts and examples, asking questions,
formulating conjectures, and attempting to settle these conjectures either by proof or by
counterexample. These are the day-to-day activities of mathematicians. Believe it or not, the
material taught in textbooks was originally developed in this way.

Tilings: A checkerboard is a rectangle divided into squares of the same size by horizontal
and vertical lines. The game of checkers is played on a board with 8 rows and 8 columns; this
board is called the standard checkerboard and is shown in Figure 2. In this section we use the
term board to refer to a checkerboard of any rectangular size as well as parts of checkerboards
obtained by removing one or more squares. A domino is a rectangular piece that is one square by
two squares, as shown in Figure 3. We say that a board is tiled by dominoes when all its squares
are covered with no overlapping dominoes and no dominoes overhanging the board. We now
develop some results about tiling boards using dominoes.
 12

SETS

A set is an unordered collection of distinct objects, called elements or members of the

set. A Set is said to contain its elements. We write a ∈ A to denote that a is an element of
the set A. The notation a ∉ A denotes that a is not an element of the set A.
Examples: The set V of all vowels in the English alphabet can be written as V = {a, e, i, o,
u}.
N = {0, 1, 2, 3, …}, the set of all natural numbers
Z = {… , −2, −1, 0, 1, 2, …}, the set of all integers
Z+ = {1, 2, 3, …}, the set of all positive integers
Q = {p/q ∣ p ∈ Z, q ∈ Z, and q ≠ 0}, the set of all rational numbers R, the set of
all real numbers
R+, the set of all positive real numbers
C, the set of all complex numbers.

Properties of sets:
1. Two sets are equal if and only if they have the same elements. Therefore, if A and B
are sets, then A and B are equal if and only if ∀x(x € A ↔ x € B). We write A = B if A
and B are equal sets.
2. There is a special set that has no elements. This set is called the empty set or, null
set, and is denoted by Ф.
3. A set with one element is called a singleton set. A common error is to confuse the
empty Ф with the set { Ф }, which is a singleton set. The single element of the set
{ Ф } is the empty.
4. Venn diagrams the universal set U, which contains all the objects under
consideration, is represented by a rectangle. (Note that the univer- sal set varies
depending on which objects are of interest.) Inside this rectangle, circles or other
geometrical figures are used to represent sets. Sometimes points are used to
represent the par ticular elements of the set.
 13

U
a

u e
V

o i

5. The set A is a subset of B, and B is a superset of A, if and only if every element of

A is also an element of B. We use the notation A ⊆ B to indicate that A is a subset of
the set B. If, instead we want to stress that B is a superset of A, we use the
equivalent notation B ⊇ A. (So, A ⊆ Band B ⊇ A are equivalent statements.)
A ⊆ B = ∀x(x ∈ A → x ∈ B)
6. Let S be a set. If there are exactly n distinct elements in S where n is a
nonnegative integer, we say that S is a finite set and that n is the cardinality of S.
The cardinality of S is denoted by |S|.
Let A be the set of odd positive integers less than 10. Then | A| = 5.
7. Given a set S, the power set of S is the set of all subsets of the set S. The power
set of S is denoted by (S).
The power set ({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence
({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.
8. Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the
set of all ordered pairs (a, b), where a ∈ A and b ∈ B. Hence,

A × B = {(a, b) ∣ a ∈ A ∧ b ∈ B}.

A = {1, 2} and B = {a, b, c}. The Cartesian product A × B = {(1, a), (1, b), (1, c),
(2, a), (2, b), (2, c)}.

Set Operations:

There are three major types of operations performed on sets, such as:
1. Union of sets
2. Intersection of sets
3. Disjoint
4. Set Difference

1. Union: Union of sets A and B, denoted by A ∪ B, is the set of distinct elements that belong to
5. Complement

set A or set B, or both.

Venn diagram of A ∪ B

Solution: A ∪ B = {2, 3, 4, 5}.

Example: Find the union of A = {2, 3, 4} and B = {3, 4, 5};
 14

2. Intersection : The intersection of the sets A and B, denoted by A ∩ B, is the set of elements that
belong to both A and B i.e. set of the common elements in A and B.

Venn diagram of A ∩ B
Example: Find the intersection of A = {2, 3, 4} and B = {3, 4, 5}
Solution: A ∩ B = {3, 4}.
3. Disjoint: Two sets are said to be disjoint if their intersection is the empty set. i.e, sets have no
common elements.

Above is the Venn Diagram of A disjoint B.

For Example: Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8}
A and B are disjoint sets since both of them have no common elements.
4. Set Difference: The difference between sets is denoted by ‘A – B’, which is the set containing
elements that are in A but not in B. i.e., all elements of A except the element of B.

Above is the Venn Diagram of A – B.

Example: If A = {1, 2, 3, 4, 5} and B = {2, 4, 6, 8}, find A – B
Solution: A – B = {1, 3, 5}

TABLE 1 Set Identities.

Identity Name
A∩U=A Identity laws
A∪∅=A
A∪U=U Domination laws
A∩∅=∅
A∪A=A Idempotent laws
A∩A=A

(A) = A Complementation law

A∪B=B∪ Commutative laws

AA∩B=B
∩A
 15

A ∪ (B ∪ C) = (A ∪ B) ∪ Associative laws
C A ∩ (B ∩ C) = (A ∩ B)
∩C
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Distributive laws
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

A∩B=A∪ De Morgan’s laws

BA∪B=A
∩B

A ∪ (A ∩ B) = Absorption laws
A A ∩ (A ∪ B)
=A

A∪A=U Complement laws

A∩A=∅

Example: Use set builder notation and logical equivalences to establish the first De Morgan law
(A ∩ B)’ = A’ ∪ B’.
Solution: We can prove this identity with the following steps.
(A ∩ B)’ = {x ∣ x ∉ A∩ B} by definition of complement
= {x ∣ ¬(x ∈ (A ∩ B))} by definition of does not belong symbol
= {x ∣ ¬(x ∈ A ∧ x ∈ B)} by definition of intersection
= {x ∣ ¬(x ∈ A) ∨ ¬(x ∈ B)} by the first De Morgan law for logical equivalences
= {x ∣ x ∉ A ∨ x ∉ B} by definition of does not belong symbol

= {x ∣ x ∈ A’ ∨ x ∈ B’} by definition of complement

= {x ∣ x ∈ (A’ ∪ B’)’} by definition of union

= A’ ∪ B’ by meaning of set builder notation

Functions:
A function is a relation between two sets set A and set B. Such that every element of set A has an image
in set B and no element in set A has more than one image in set B.

by which each element a ∈ A is associated with a unique element b ∈ B.

Let A and B be two nonempty sets. A function or mapping f from A to B is written as f: A → B is a rule

Domain, Codomain, and Range of a Function

The elements of set X are called the domain of f and the elements of set Y are called the codomain of f.
The images of the elements of set X are called the range of function, which is always a subset of Y. The
image given below demonstrates the domain, codomain, and range of the function.
 16

The image demonstrates the domain, co-domain, and range of the function. Remember the element
which is mapped only will be counted in the range as shown in the image. The domain, codomain, and
range of the above function are:
Domain = {a, b, c}
Codomain = {1, 2, 3, 4, 5}
Range = {1, 2, 3}

Types of Functions: Types of functions based on set elements depend on the number of
relationships amongst the elements in the domain and the codomain. The different types of functions
depending on the set elements are as discussed below.

1. One–One Function or Injective Function: The one-to-one function is also termed an injective
function. Here each element of the domain possesses a different image or co-domain element for the
assigned function.

A function f: A → B is declared to be a one-one function if different components in A have different

images or are associated with different elements in B.

2. Onto Function or Surjective Function: A function f: A → B is declared to be an onto function if each

component in B has at least one pre-image in A. i.e., If-Range of function f = Co-domain of function f,
then f is onto. The onto function is also termed a subjective function.

3. Bijective Function or One One and Onto Function :A function f: A → B is declared to be a bijective
function if it is both one-one and onto function. In other words, we can say that every element of set A is
related to a different element in set B, and there is not a single element in set B that has been left out to be
connected to set A.
 17

Sequences and Summations:

A sequence is a function from a subset of the set of integers (usually either the set {0, 1, 2, …}
or the set {1, 2, 3, …}) toa set S. We use the notation an to denote the image of the integer n.
We call an a term of the sequence.

Examle: Consider the sequence {an}, where

1
an =
n
The list of the terms of this sequence, beginning with a1, namely,

a 1, a 2, a 3, a 4, … ,

starts with1,1/2,1/3,1/4,……

Summation: This notation is the symbol ∑ (called "sigma"). This new symbol is a shorthand notation
used to represent the sum of a number of terms having a common form. This shorthand notation is referred
to as "summation notation" or "sigma notation"

Example: ∑n i=1i = 1 + 2 + 3 + ... + n = n(n+1)2