Propositional Logic

The rules of logic give precise meaning to mathematical statements. These rules are used to
distinguish between valid and invalid mathematical arguments.
Propositions
A proposition is a declarative sentence that is either true or false, but not both.
• Propositional logic the area of logic that deals with propositions.
• Propositional variables that represent propositions: p, q, r, s.
• Truth values T, F

DEFINITION 1
Let p be a proposition. The negation of p, denoted by ¬p (also denoted by p) is thestatement. “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 Truth Table for the Negation of a Proposition

p ¬p
T F
F T

Example: Find the negation of the proposition “Today is Friday.”

Solution: The negation is “It is not the case that today is Friday.” In simple English, “Today is not
Friday.” Or “It is not Friday today.”

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.

The Truth Table for the Disjunction of Two Propositions

p q p∨q

TTF FFT TTT

F T F

1
 The truth table for the
Conjunction ofPropositions two
p q p𝖠q
T F T
T F F
F T F
F T F

DEFINITION 3
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.

The common binary connectives are:

Conjunction p and q
p𝖠q Disjunction p or q
p∨ qp→qp↔q Implication if p then q
p⊕q Bi-conditional p if and only if q
Exclusive or p x-or q
p↓q not or p nor q
p | q or p ↑ q not and p n-and q

In the conditional p → q, p is the antecedent and q is the consequent. Theconditional p → q

is often read informally as “p implies q”.

Converse, Contra-positive and Inverse

• The proposition q → p is called the converse of p →q. The contra-positive of p → q is the
proposition ¬q → ¬p. The proposition ¬p → ¬q is called the inverse of p → q.
• We will see that of these three conditional statements formed from p → q, only the contra-
positive always has the same truth value as p → q.

EXAMPLE: What are the contra-positive, the converse, and the inverse of the conditional-
statement? “The home team wins whenever it is raining?”
Solution:
“If it is raining, then the home team wins.”
The contra-positive of this conditional statement is
“If the home team does not win, then it is not raining.”
The converse is - “If the home team wins, then it is raining.”
The inverse is - “If it is not raining, then the home team does not win.”

Bi-conditionals

DEFINITION 4
Let p and q be propositions. The bi-conditional statement p ↔ q is the proposition “p if and only if
q.” The bi-conditional statement p ↔ q is true when p and q have the same truth values, and is

2
false otherwise. Bi-conditional statements are also called bi-implications.

Truth Table for the Bi-conditional p ↔ q

p q p↔q
T T T
T F F
F T F
F F T

The Truth Table for the Bi-conditional p ↔ q

The statement p ↔ q is true when both the conditional statements are p → q and q → p are true
and is false otherwise.
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
Answer “You can take the flight if and only if you buy a ticket.”

Precedence of Logical Operator

Operator precedence is an ordering of logical operators designed to allow the dropping of
parenthesis in logical expression.

Precedence of Logical Operators

Operator Precedence
¬ 1
𝖠 2
∨ 3
→ 4
↔ 5

Logic and Bit Operations

• A bit is a symbol with two possible values, 0 (zero) and 1 (one).
• A bit can be used to represent a truth value, because there are two truth values, true and
false.
• A variable is called a Boolean variable if its value is either true or false.

Truth
Bit
Value
1
T
F
0

Bit Operators OR, AND, and XOR

x y x∨y x𝖠y x⊕y

0 0 0 0 0

3
 0 1 1 0 1

1 0 1 0 1
1 1 1 1 0

DEFINITION5-A bit string is a sequence of zeroor more bits. The length of this string is the number
of bits in thestring.

EXAMPLE Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 011011 0110 and 11
0001 1101.
Solution: The bitwise OR, bitwise AND, and bitwise XOR are:
01 1011 0110
11 0001 1101
11 1011 1111 Bitwise OR
01 0001 0100 Bitwise AND
10 1010 1011 Bitwise XOR

Propositional Equivalences Tautologies and contradictions

A compound proposition that is always true, regardless of the truth values of the
individual propositions involved, is called a tautology.
Example: 𝑝 ∨ ¬𝑝 is a tautology.

A compound proposition that is always false, regardless of the truth values of the individual
propositions involved, is called a contradiction.
Example: 𝑝 𝖠 ¬𝑝 is a contradiction.

A compound statement that is neither a tautology nor a contradiction is called acontingency.

Logical Equivalences
• Compound propositions that have the same truth values in all possible cases are called
logically equivalent.
• 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.

Examples of Tautology & Contradiction.

p ¬p p ∨ ¬p p 𝖠 ¬p
T F T F

F T T F
Logicalequivalence

4
 De Morgan’s Laws.

¬(p 𝖠 q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p 𝖠 ¬q
• The two algebraic expressions equal if they have the same value for each possible value of the
input variables.
• For example, for all real numbers 𝑥, the left side and the right side have thesame value.
𝑥 2 − 1 = (𝑥 + 1) (𝑥 − 1)
• The two compound statements 𝑝 and 𝑞 “equal” if they always share the same truth value. 𝑝 ≡ 𝑞
means that 𝑝 ↔ 𝑞 is a tautology.
• In these equivalences, T denotes the compound proposition that is always true and F denotes
the compound proposition that is always false.

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 laws
p𝖠q≡q𝖠p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)(p 𝖠 q)
Associative laws
𝖠 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 laws
¬(p ∨ q) ≡ ¬p 𝖠 ¬q
p ∨ (p 𝖠 q) ≡ p
Absorption laws
p 𝖠 (p ∨ q) ≡ p
p ∨ ¬p ≡ T
Negation laws
p 𝖠 ¬p ≡ F

Logical Equivalences Involving Bi-conditional Statements.

5
 p ↔ q ≡ (p → q) 𝖠 (q → p)p ↔ q ≡ ¬p ↔ ¬q
p ↔ q ≡ (p 𝖠 q) ∨ (¬p 𝖠 ¬q)
¬(p ↔ q) ≡ p ↔ ¬q

Logical Equivalences involvingConditional Statements.

p → q ≡ ¬p ∨ q

p → q ≡ ¬q → ¬pp ∨ 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

Using De Morgan’s Laws

The two logical equivalences known as De Morgan’s laws are particularly important. In particular,
the equivalence ¬ (p ∨ q) ≡ ¬p 𝖠 ¬q tells us that the negation of a disjunction is formed by taking
the conjunction of the negations of the component propositions.
Example Show that ¬ (p ∨ (¬p 𝖠 q)) and ¬p 𝖠 ¬q are logically equivalent by developing a series of
logical equivalences.
Sol ¬ (p ∨ (¬p 𝖠 q)) ≡ ¬p 𝖠 ¬ (¬p 𝖠 q) 2nd De Morgan law
≡ ¬p 𝖠 [¬ (¬p) ∨ ¬q] 1st De Morgan law
≡ ¬p 𝖠 (p ∨ ¬q) double negation law
≡ (¬p 𝖠 p) ∨ (¬p 𝖠 ¬q) 2nd distributive law
≡ F ∨ (¬p 𝖠 ¬q) because ¬p 𝖠 p ≡ F
≡ (¬p 𝖠 ¬q) ∨ F commutative law for disjunction
≡ ¬p 𝖠 ¬q identity law for F

Normal Form
• Suppose, A (P1, P2, ... , P n) is a statements formula where P1, P2, ..., P6 are the atomic
variables if we consider all possible assignments of the truth value to P1, P2, ..., P n and
obtain the resulting truth values of the formula A then we get the truth table for A, such a
truth table contains 2^6 rows.
• The formula may have the truth value T for all possible assignments of the truth values to
the variables P1, P2... P n. In this case, A is called identically true or tautology.
• If A has the truth value T for at least one combination of truth values assigned to P1, P2... P
n then A is called Satisfiable.

Product in place of Conjunction

Sum in place of Disjunction

Disjunctive Normal form Conjunctive Normal form

Types of Normal form
6
Disjunctive Normal form
A product of the variable and their negations in a formula is called an elementary product.
Similarly, a sum of the variables and their negations is called as an elementary sum.

Some statements hold for elementary sums and product:

1. For any elementary product, the necessary condition is false is when it contains at least one
pair of a factor in which one is the negation of the other.
2. For any elementary sum, the necessary condition is true when it contains at least one pair of
factors in which one is the negations of the other.

1) Conjunctive Normal Form

The conjunctive normal form of a given formula is the one which contains the product of
elementary sums (that formula is equivalent in the given formula).
2) Principle Disjunctive normal form
Suppose, P and Q is two variables. We construct all possible formulas which consist of a
conjunction of P or in negation and conjunction of Q or its negation. Now of the formulas
should contain both a variable and its negation. For two variables P and Q there is 2^2 such
formula.

These formulas are called min-terms or Boolean conjunction of P and Q from the truth tables of
theses min-terms, it is clear that no two min-terms are equivalent. Each min-term has the truth
value T for exactly one combination of the truth value of the variables P and Q.
For a given formula an equivalent formula consisting of a disjunction of min- terms only is
known as its principle disjunction normal form. Such a normal form is also said to be the sum-
product canonical form.

3) Principle conjunctive normal form

Given a number of variables max-term of these variables is a formula which consists of disjunction
in which each variable or its negations but not both appear only once.
Observe that the max-term are the duals of min-terms. Therefore each of the max-term has the
truth value F for exactly one combination of the truth values of the variables.
The principle of conjunctive normal form or the product-sum canonical form, the equivalent
formula consists of only the conjunction of the max-terms only.

Predicates and QuantifiersPredicates

A predicate is an expression of one or more variables defined on some specific
domain. A predicate with variables can be made a proposition by either assigning a value to the
variable or by quantifying the variable.

For Example: Let P (x) denote the statement “x > 3.” What are the truth values ofP (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.

The following are some examples of predicates −

• Let E(x, y) denote "x = y"
• Let X(a, b, c) denote "a + b + c = 0"
• Let M(x, y) denote "x is married to y"
7
Well Formed Formula
Well Formed Formula is a predicate holding any of the following −
• All propositional constants and propositional variables are WFF.
• If x is a variable and Y is a WFF, ∀X y and ∃x Y are also WFF. Truth value andfalse values are
WFF.

Quantifiers
The variable of predicates is quantified by quantifiers.

There are two types of quantifier in predicate logic − Universal Quantifier and Existential
Quantifier.

Denoted by Quantifiers Denoted by

symbol ∀ symbol ∃

Universal Quantifier Existential Quantifier

Universal Quantifier
Universal quantifier states that the statements within its scope are true for every value of the
specific variable. It is denoted by the symbol ∀.
∀x P(x) is read as for every value of x, P(x) is true.

Statement When True? When False?

P (x) is true for every x

∀x P(x) There is an x for which P (x) isfalse.
There is an x for which P (x)is
∃x P(x) P (x) is false for every x.
true.

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

Existential Quantifier
Existential quantifier states that the statements within its scope are true for some values of
the specific variable. It is denoted by the symbol ∃.
∃x P(x) is read as for some values of x, P(x) is true.

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

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

Negating Quantified Expressions

Consider the negation of the statement
“Every student in your class has taken a course in calculus.”
This statement is a universal quantification, namely,∀x P(x), where P(x) is the statement “x has
taken a course in calculus” and the domain consists of the students in your class.
• The negation of this statement is “It is not the case that every student inyour class has taken
a course in calculus.”
• This is equivalent to “There is a student in your class who has not taken a course in
calculus.”
• And this is simply the existential quantification of the negation of the original propositional
function, namely, ∃x ¬P (x).

De Morgan’s laws for quantifiers

Equivalent
Negation When Is Negation True? When False?
Statement
There is an x forwhich P(x) is
¬∃x P (x) ∀x ¬P (x) For every x, P (x) is false.
true.
¬∀x P (x) ∃x ¬P (x) There is an x for which P(x)is false.
P (x) is true for everyx.

Example What are the negations of the statements “There is an honestpolitician”.

Solution: Let H (x) denote “x is honest.” Then the statement “There is an honest politician” is
represented by ∃x H(x), where the domain consists of all politicians.
The negation of the statement is ¬∃x H(x), which is equivalent to ∀x¬ H(x). “Every politician is
dishonest.”

Nested Quantifiers
Nested quantifiers, where one quantifier is within the scope of another, such as:
∀x ∃y (x + y = 0). Everything within the scope of a quantifier can be thought of as a propositional
function.

For example, ∀x ∃y(x + y = 0) is the same thing as ∀x Q(x), where Q(x) is ∃y P (x,y), where P (x, y) is
x + y = 0.
Understanding Statements Involving Nested Quantifiers
For example, assume that the domain for the variables x and y consists of all realnumbers.
• The statement ∀x ∀y(x + y = y + x) says that x + y = y + x for all real numbers x and y.
(Commutative law)
• 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. (Additive Inverse)
• Similarly, the statement ∀x ∀y ∀z(x+(y+ z) = (x + y) + z) (Associative law)

Example: Let Q(x, y) denote “x + y = 0.” What are the truth values of the quantifications ∃y ∀x Q(x,
y) and ∀x ∃y Q(x, y), where the domain for all variables consists of all real numbers?
Solution: The quantification ∃y ∀x Q(x, y) denotes the proposition. “There is a real number y such
that for every real number x, Q(x, y).”
9
Quantification of two variables
Statement When True? When False?
∀x ∀y P(x,y)
P(x, y) is true for every pairx, y. There is a pair x, y for which P(x, y) isfalse.
∀y ∀x P(x,y)
For every x there is a y forwhich P There is an x such that P(x, y) is falsefor every
∀x ∃y P(x,y)
(x, y) is true. y.
There is an x for which P (x,y) is For every x there is a y for which P(x, y) is
∃x ∀y P(x,y)
true for every y. false.
There is a pair x, y forwhich P (x,
∃x ∃y P(x,y) P (x, y) is false for every pair x, y
y) is true.

Translating Mathematical Statements into StatementsInvolving Nested Quantifiers

Mathematical statements expressed in English can be translated into logicalexpressions.
Example
Translate the statement “The sum of two positive integers is always positive” into a logical
expression.
Solution
“For all positive integers x and y, x + y is positive.” Consequently, we can express this statement as:
∀x ∀y((x > 0) 𝖠 (y > 0) → (x + y > 0)), where the domain for both variables consists of all integers.

Translating from Nested Quantifiers into English

Example Translate the statement ∀x(C(x) ∨ ∃y(C(y) 𝖠 F (x, y))) into English, where C(x) is “x has a
computer,” F (x, y) is “x and y are friends,” and the domain for both x and y consists of all students
in your school.
Solution Every student in your school has a computer or has a friend who has a computer.
Every Theorem in Mathematics, or any subject for that matter, is supported byunderlying proofs.
These proofs are nothing but a set of arguments that are conclusive evidence of the validity of the
theory.
The arguments are chained together using Rules of Inferences to deduce new statements and
ultimately prove that the theorem is valid.

Important Definitions :
1. Argument – A sequence of statements, premises, that end with aconclusion.
2. Validity – A deductive argument is said to be valid if and only if it takes a form that makes it
impossible for the premises to be true and the conclusionnevertheless to be false.
3. Fallacy – An incorrect reasoning or mistake which leads to invalidarguments.

Structure of an Argument :
As defined, an argument is a sequence of statements called premises which end with a
conclusion.

10
Rules of Inference :
Simple arguments can be used as building blocks to construct more complicated valid arguments.
Certain simple arguments that have been established as valid are very important in terms of their
usage. These arguments are called Rules of Inference.

The most commonly used Rules of Inference are tabulated below

Similarly, we have Rules of Inference for quantified statements –

11
how Rules of Inference can be used to deduce conclusions from given arguments or check the
validity of a given argument.

Example : Show that the hypotheses

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

The first step is to identify propositions and use propositional variables torepresent them.

To deduce the conclusion we must use Rules of Inference to construct a proof using the given
hypotheses.

12
Resolution Principle :
To understand the Resolution principle, first we need to know certain definitions.

For example,

We can use the resolution principle to check the validity of arguments or deduce conclusions from
them. Other Rules of Inference have the same purpose, but
Resolution is unique. It is complete by it’s own. You would need no other Rule of Inference to
deduce the conclusion from the given argument.

To do so, we first need to convert all the premises to clausal form. The next step is to apply the
resolution Rule of Inference to them step by step until it cannot be applied any further.

13
For example, consider that we have the following premises –

Note:Implecations can also be visualised on octagon as,

It shows how implecation changes on changing order of there exists and for allsymbols.
Set and Relations
Set
Sets are used to group objects together.

DEFINITION 1 A set is an unordered collection of 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.
It is common for sets to be denoted using uppercase letters. Lowercase letters are usually used to
denote elements of sets.

EXAMPLE 1 The set V of all vowels in the English alphabet can be written as V =
{a, e, i, o, u}.

EXAMPLE 2 The set O of odd positive integers less than 10 can be expressed by O
= {1, 3, 5, 7, 9}.

14
DEFINITION 2 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.

EXAMPLE The sets {1, 3, 5} and {3, 5, 1} are equal, because they have the sameelements.

THE EMPTY SET

There is a special set that has no elements. This set is called the empty set, or null set, and is
denoted by ∅.

Venn diagrams
In Venn diagrams the universal set U, which contains all the objects under consideration, is
represented by a rectangle.

EXAMPLE 7 Draw a Venn diagram set of vowels in the English alphabet.

Venn diagram for the Set of Vowels

Subsets
It is common to encounter situations where the elements of one set are also the elements of a
second set.

DEFINITION 3: The set A is a subset of B 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 theset B.
We see that A ⊆ B if and only if the quantification ∀x(x ∈ A → x ∈ B) is true.
• Showing that A is a Subset of B To show that A ⊆ B, show that if x belongs to A then x also
belongs to B.
• Showing that A is Not a Subset of B To show that A ⊆ B, find a single x ∈ Asuch that x ∈ B.

Venn diagram Showing that A is a Subset of B.

THEOREM 1 For every set S, (i) ∅ ⊆ S and (ii) S ⊆ S.

15
Proof: Let S be a set. To show that ∅ ⊆ S, we must show that ∀x(x ∈∅→ x ∈ S) istrue. Because the
empty set contains no elements, it follows that x ∈ ∅ is always false. It follows that the conditional
statement x ∈∅→ x ∈ S is always true, because its hypothesis is always false and a conditional
statement with a falsehypothesis is true. Therefore, ∀x(x ∈∅→ x ∈ S) is true.

Showing Two Sets are Equal

To show that two sets A and B are equal, show that A ⊆ B and B ⊆ A.

The Size of a Set

DEFINITION 4 Let S be a set. If there are exactly n distinct elements in S where n is a non negative
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|.
EXAMPLE Let A be the set of odd positive integers less than 10. Then |A| = 5.

Power Sets
DEFINITION 6 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 P(S).
EXAMPLE What is the power set of the set {0, 1, 2}?
Solution: The power set P({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence, P({0, 1, 2}) =
{∅,{0},{1},{2},{0, 1},{0, 2},{1, 2},{0, 1, 2}}.

Cartesian Products
The order of elements in a collection is often important. Because sets are unordered, a different
structure is needed to represent ordered collections. Thisis provided by ordered n-tuples.

DEFINITION 7 The ordered n-tuple (a1, a2... a n) is the ordered collection that has a1 as its first
element, a2 as its second element... and a n as its nth element.

DEFINITION 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}.

EXAMPLE What is the Cartesian product of A = {1, 2} and B = {a, b, c}?

Solution: The Cartesian product A × B is A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2,c)}.
Cartesian products A × B and B × A are not equal, unless A = ∅ or B = ∅ or A = B.

DEFINITION 9 The Cartesian product of the sets A1, A2,...,A n, denoted by A1 × A2

×···× An, is the set of ordered n-tuples (a1, a2,...,a n), where a i belongs to Ai for i =1, 2,...,n.
In other words, A1 × A2 ×···× A n = {(a1, a2,...,a n) | a i ∈ Ai for i = 1, 2,...,n}.

EXAMPLE What is the Cartesian product A × B × C, where A = {0, 1}, B = {1, 2}, andC = {0, 1, 2} ?
Solution: A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2), (1, 1, 0),
(1, 1, 1),(1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}.

Operations on Sets
The basic set operations are:
1. Union of Sets: Union of Sets A and B is defined to be the set of all those elements which
belong to A or B or both and is denoted by A𝖴B.
1. A𝖴B = {x: x ∈ A or x ∈ B}
16
Example: Let A = {1, 2, 3}, B= {3, 4, 5, 6}
A𝖴B = {1, 2, 3, 4, 5, 6}.

2. Intersection of Sets: Intersection of two sets A and B is the set of all those elements which
belong to both A and B and is denoted by A ∩ B.
1. A ∩ B = {x: x ∈ A and x ∈ B}
Example: Let A = {11, 12, 13}, B = {13, 14, 15}A ∩ B = {13}.

3. Difference of Sets: The difference of two sets A and B is a set of all those elements which
belongs to A but do not belong to B and is denoted by A - B.
1. A - B = {x: x ∈ A and x ∉ B}
Example: Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6} then A - B = {3, 4} and B - A = {5, 6}

2. Complement of a Set: The Complement of a Set A is a set of all those elementsof the universal

17
 set which do not belong to A and is denoted by Ac.
Ac = U - A = {x: x ∈ U and x ∉ A} = {x: x ∉ A}

Example: Let U is the set of all natural numbers.A = {1, 2, 3}

Ac = {all natural numbers except 1, 2, and 3}.

3. Symmetric Difference of Sets: The symmetric difference of two sets A and B is the set
containing all the elements that are in A or B but not in both and is denoted by A ⨁ B i.e.
1. A ⨁ B = (A 𝖴 B) - (A ∩ B)

Example: Let A = {a, b, c, d}B = {a, b, l, m}

A ⨁ B = {c, d, l, m}

Set Identities

Idempotent laws: A𝖴A=A A∩A=A

Associative laws: (A 𝖴 B) 𝖴 C = A 𝖴 (B 𝖴C) (A ∩ B) ∩ C = A ∩ (B ∩ C)
Commutative A𝖴B=B𝖴A A∩B=B∩A
laws:
Distributive laws: A 𝖴 (B ∩ C) = (A 𝖴 B) ∩(A 𝖴 A ∩ (B 𝖴 C) = (A ∩ B) 𝖴
C) (A ∩ C)

Identity laws: A 𝖴∅= A A ∩ U = A A∩U=A

A𝖴U=U

18
 Complement laws: A 𝖴 A`= UU` = ∅ A ∩ A` = ∅
∅` = U

Involution laws: (A`)` = A

De Morgan’s (A 𝖴 B)` = A` ∩ B` (A ∩ B)` = A` 𝖴 B`

laws:

EXAMPLE Use set builder notation and logical equivalences to establish the first De Morgan law A
∩ B =A 𝖴 B.
Solution: A ∩ B = {x | x /∈ A ∩ B} definition of complement
= {x | ¬(x ∈ (A ∩ B))} definition of does not belong symbol
= {x | ¬(x ∈ A 𝖠 x ∈ B)} definition of intersection
= {x | ¬(x ∈ A) ∨ ¬(x ∈ B)} first De Morgan law
= {x | x /∈ A ∨ x /∈ B} by definition of does not belong symbol
= {x | x ∈ A ∨ x ∈ B} definition of complement
= {x | x ∈ A 𝖴 B} definition of union
=A𝖴B

A membership table for the distributive property

A B C B𝖴C A ∩ (B 𝖴 C) A∩B A∩C (A ∩ B) 𝖴 (A ∩C)

1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1
1 0 1 1 1 0 1 1
1 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0

EXAMPLE Let A, B, and C be sets. Show thatA 𝖴 (B ∩ C) = (C 𝖴 B) ∩ A.

Solution: A 𝖴 (B ∩ C) = A ∩ (B ∩ C) First De Morgan law
= A ∩ (B 𝖴 C) Second De Morgan law
= (B 𝖴 C) ∩ A Commutative law
= (C 𝖴 B) ∩ A by the commutative law for unions.

Generalized Unions and Intersections

Unions and intersections of sets satisfy associative laws, the sets A 𝖴 B 𝖴 C and A
∩ B ∩ C are well defined; that is, the meaning of this notation is unambiguouswhen A, B, and C
are sets.

19
FIGURE The Union and Intersection of A, B, and C.

DEFINITION 6 The union of a collection of sets is the set that contains those elements that
are members of at least one set in the collection.

DEFINITION 7 The intersection of a collection of sets is the set that contains those elements that
are members of all the sets in the collection. A1 ∩ A2 ∩···∩ A n to denote the intersection of the sets
A1, A2... A n.

Relations Introduction
An ordered pair of elements a and b, where a is designated as the first element
and b as the second element, is denoted by (a, b). In particular, (a, b) = (c, d) if andonly if a = c and b
= d. Thus (a, b) = (b, a) unless a = b.

Definition 1 Let A and B be sets. A binary relation or, simply, relation from A to Bis a subset of A ×
B.
(i) (a, b) ∈ R; we then say “a is R-related to b”, written a R b.
(ii) (a, b) /∈ R; we then say “a is not R-related to b”, written a R b.

If R is a relation from a set A to itself, that is, if R is a subset of A2 = A × A, then we say that R is a
relation on A.
EXAMPLE Set inclusion ⊆ is a relation on any collection of sets. For, given any pair of set A and B,
either A ⊆ B or A ⊆ B.

Inverse Relation
Let R be any relation from a set A to a set B. The inverse of R, denoted by R−1, is the relation from
B to A which consists of those ordered pairs which, whenreversed, belong to R; that is,
R−1 = {(b, a)|(a, b) ∈ R}
For example, let A = {1, 2, 3} and B = {x, y, z}. Then the inverse ofR = {(1, y), (1, z), (3, y)} is R−1 = {(y,
1), (z, 1), (y, 3)}

Representation of Relations
Mij = 0 if (ai,bj) ∉ R

1 if (ai,bj )∈ R
Relations can be represented in many ways. Some of which are as follows:
1. Relation as a Matrix: Let P = [a1,a2,a3,.......am] and Q = [b1,b2,b3......bn] are finite sets, containing m
20
 and n number of elements respectively. R is a relation from P to Q. The relation R can be
represented by m x n matrix M = [Mij], defined as

Example
1. Let P = {1, 2, 3, 4}, Q = {a, b, c, d}
2. and R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.
The matrix of relation R is shown as fig:

2. Relation as a Directed Graph: There is another way of picturing a relation R when R is a

relation from a finite set to itself.
Example
1. A = {1, 2, 3, 4}
2. R = {(1, 2) (2, 2) (2, 4) (3, 2) (3, 4) (4, 1) (4, 3)}

3. Relation as an Arrow Diagram: If P and Q are finite sets and R is a relation fromP to Q. Relation
R can be represented as an arrow diagram as follows.
Draw two ellipses for the sets P and Q. Write down the elements of P and elements of Q column-
wise in three ellipses. Then draw an arrow from the first ellipse to the second ellipse if a is related
to b and a ∈ P and b ∈ Q.
Example
1. Let P = {1, 2, 3, 4}
2. Q = {a, b, c, d}
3. R = {(1, a), (2, a), (3, a), (1, b), (4, b), (4, c), (4, d)
The arrow diagram of relation R is shown in fig:

21
4. Relation as a Table: If P and Q are finite sets and R is a relation from P to Q.Relation R can
be represented in tabular form.
Make the table which contains rows equivalent to an element of P and columns equivalent to the
element of Q. Then place a cross (X) in the boxes which represent relations of elements on set P
to set Q.
Example
1. Let P = {1, 2, 3, 4}
2. Q = {x, y, z, k}
3. R = {(1, x), (1, y), (2, z), (3, z), (4, k)}.
The tabular form of relation as shown in fig:

Composition of Relations
Let A, B, and C be sets, and let R be a relation from A to B and let S be a relationfrom B to C. That is,
R is a subset of A × B and S is a subset of B × C. Then R and S give rise to a relation from A to C
indicated by R◦S and defined by:
(i) a (R◦S)c if for some b ∈ B we have aRb and bSc.
(ii) is,
(iii) R ◦ S = {(a, c)| there exists b ∈ B for which (a, b) ∈ R and (b, c) ∈ S}

The relation R◦S is known the composition of R and S; it is sometimes denotedsimply by RS.
Let R is a relation on a set A, that is, R is a relation from a set A to itself. Then R◦R, the composition
of R with itself, is always represented. Also, R◦R is sometimes denoted by R2. Similarly, R3 = R2◦R =
R◦R◦R, and so on. Thus Rn is defined for all positive n.

Example1: Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider the relation R1 from X to Y and R2

22
from Y to Z.

R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

Find the composition of relation (i) R1 o R2 (ii) R1o R -1

1
Solution:
1. The composition relation R1 o R2 as shown in fig:

R1 o R2 = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}
2. The composition relation R1o R -1 as shown in fig:
3. 1

R1o R1-1 = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}
Composition of Relations and Matrices
There is another way of finding R◦S. Let MR and MS denote respectively the matrix representations
23
of the relations R and S. Then

Example
1. Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by
2. R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
3. S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.
4. Find the matrices of the above relations.
5. Use matrices to find the following composition of the relation R and S.
6. (i)RoS (ii)RoR (iii)SoR

Solution: The matrices of the relation R and S are a shown in fig:

(i) To obtain the composition of relation R and S. First multiply MR with MS to obtain the matrix MR
x MS as shown in fig:

The non zero entries in the matrix MR x MS tells the elements related in RoS. So,
Hence the composition R o S of the relation R and S is
1. R o S = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.
(ii) First, multiply the matrix MR by itself, as shown in fig
(iii)

Hence the composition R o R of the relation R and S is

24
1. R o R = {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)}
(iv) Multiply the matrix MS with MR to obtain the matrix MS x MR as shown in fig:

The non-zero entries in matrix MS x MR tells the elements related in S o R.

Hence the composition S o R of the relation S and R is

1. S o R = {(2, 4) , (2, 5), (3, 3), (3, 4), (3, 5), (4, 2), (4, 4), (4, 5), (5, 2), (5, 3), (5,
4), (5, 5)}.

Types of Relations
1. Reflexive Relation: A relation R on set A is said to be a reflexive if (a, a) ∈ R forevery a ∈ A.
Example: If A = {1, 2, 3, 4} then R = {(1, 1) (2, 2), (1, 3), (2, 4), (3, 3), (3, 4), (4, 4)}. Is
a relation reflexive?
Solution: The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2), (3, 3), (4, 4) ∈ R.

2. Irreflexive Relation: A relation R on set A is said to be irreflexive if (a, a) ∉ R forevery a ∈ A.

Example: Let A = {1, 2, 3} and R = {(1, 2), (2, 2), (3, 1), (1, 3)}. Is the relation R reflexive or irreflexive?
Solution: The relation R is not reflexive as for every a ∈ A, (a, a) ∉ R, i.e., (1, 1) and (3, 3) ∉ R. The
relation R is not irreflexive as (a, a) ∉ R, for some a ∈ A, i.e., (2, 2) ∈ R.

3. Symmetric Relation: A relation R on set A is said to be symmetric iff (a, b) ∈ R

- (b, a) ∈ R.
Example: Let A = {1, 2, 3} and R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}. Is a
relation R symmetric or not?
Solution: The relation is symmetric as for every (a, b) ∈ R, we have (b, a) ∈ R, i.e.,(1, 2), (2, 1), (2, 3),
(3, 2) ∈ R but not reflexive because (3, 3) ∉ R.

Example of Symmetric Relation:

1. Relation ⊥r is symmetric since a line a is ⊥r to b, then b is ⊥r to a.
2. Also, Parallel is symmetric, since if a line a is ∥ to b then b is also ∥ to a.

Antisymmetric Relation: A relation R on a set A is antisymmetric iff (a, b) ∈ R and(b, a) ∈ R then a

= b.
Example1: Let A = {1, 2, 3} and R = {(1, 1), (2, 2)}. Is the relation R antisymmetric?
Solution: The relation R is antisymmetric as a = b when (a, b) and (b, a) bothbelong to R.

Example2: Let A = {4, 5, 6} and R = {(4, 4), (4, 5), (5, 4), (5, 6), (4, 6)}. Is the relationR antisymmetric?
Solution: The relation R is not antisymmetric as 4 ≠ 5 but (4, 5) and (5, 4) bothbelong to R.

25
5. Asymmetric Relation: A relation R on a set A is called an Asymmetric Relation if for every (a, b)
∈ R implies that (b, a) does not belong to R.
6. Transitive Relations: A Relation R on set A is said to be transitive iff (a, b) ∈ Rand (b, c) ∈ R
⟺ (a, c) ∈ R.
Example1: Let A = {1, 2, 3} and R = {(1, 2), (2, 1), (1, 1), (2, 2)}. Is the relationtransitive?
Solution: The relation R is transitive as for every (a, b) (b, c) belong to R, we have (a, c) ∈ R i.e, (1,
2) (2, 1) ∈ R ⇒ (1, 1) ∈ R.

Note1: The Relation ≤, ⊆ and / are transitive, i.e.,

(i) a ≤ b, b ≤ c then a ≤ c
(ii) Let a ⊆ b, b ⊆ c then a ⊆ c
(iii) Let a/b, b/c then a/c.

Note2: ⊥r is not transitive since a ⊥r b, b ⊥r c then it is not true that a ⊥r c. Since no line
is ∥ to itself, we can have a ∥ b, b ∥ a but a ∦ a. Thus ∥ is not
transitive, but it will be transitive in the plane.

7. Identity Relation: Identity relation I on set A is reflexive, transitive andsymmetric. So identity

relation I is an Equivalence Relation.
Example: A= {1, 2, 3} = {(1, 1), (2, 2), (3, 3)}

8. Void Relation: It is given by R: A →B such that R = ∅ (⊆ A x B) is a null relation. Void Relation R

= ∅ is symmetric and transitive but not reflexive.

9. Universal Relation: A relation R: A →B such that R = A x B (⊆ A x B) is a universal relation.

Universal Relation from A →B is reflexive, symmetric and transitive. So this is an equivalence
relation.

CLOSURE PROPERTIES
A relation with property P will be called a P-relation. The P-closure of an arbitrary relation R on A,
written P (R), is a P-relation such that
R ⊆ P (R) ⊆ S for every P-relation S containing R, For the reflexive, symmetric, and transitive
closures of R.

Reflexive and Symmetric Closures

Suppose P is a property such that there is at least one P-relation containing R and that the
intersection of any P-relations is again a P-relation.
P (R) = ∩(S | S is a P-relation and R ⊆ S) P (R) from the “top-down,” that is, as the intersection of
relations. A = {(a, a)| a ∈ A} is the diagonal or equality relation on A.
Theorem: Let R be a relation on a set A. Then:
(i) R 𝖴 A is the reflexive closure of R.
(ii) R 𝖴 R−1 is the symmetric closure of R.

In other words, reflexive(R) is obtained by simply adding to R those elements (a, a) in the diagonal
which do not already belong to R, and symmetric(R) is obtained by adding to R all pairs (b, a)
whenever (a, b) belongs to R.
26
Transitive Closure Let R be a relation on a set A. R2 = R◦R and R n = R n−1◦R.The following theorem
applies:

Theorem: R∗ is the transitive closure of R.

Theorem: Let R be a relation on a set A with n elements. ThenTransitive(R) = R 𝖴 R^2 𝖴 ... 𝖴 R n

EXAMPLE Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then: R^2
= R◦R = {(1, 3), (2, 3), (3, 3)} and R^3 = R^2◦R = {(1, 3), (2, 3), (3, 3)}
Transitive (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}

EQUIVALENCE RELATIONS
Consider a nonempty set S. A relation R on S is an equivalence relation if R is reflexive, symmetric,
and transitive. That is, R is an equivalence relation on S if it has the following three properties:
1. For every a ∈ S, a R a.
2. If a R b, then b R a.
3. If a R b and b R c, then a R c.

S is an equivalence relation; that is:

1. a = a, for every a ∈ S.
2. If a = b, then b = a.
3. If a = b, b = c, then a = c.

Equivalence Relations and Partitions

This subsection explores the relationship between equivalence relations and partitions on a non-
empty set S.
Partition P of S is a collection {Ai} of nonempty subsets of S with the following twoproperties:
1. Each a ∈ S belongs to some Ai.
2. If Ai = A j then Ai ∩ A j = ∅.

Theorem: Let R be an equivalence relation on a set S. Then S/R is a partition of S.

(i) For each a in S, we have a ∈ [a].
(ii) [a]=[b] if and only if (a, b) ∈ R.
(iii)If [a] = [b], then [a] and [b] are disjoint.

Conversely, given a partition {Ai} of the set S, there is an equivalence relation R on S such that the
sets Ai are the equivalence classes.

EXAMPLE
Consider the relation R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} on S = {1, 2, 3}.
One can show that R is reflexive, symmetric, and transitive, that is, that R is an equivalence
relation. Also: [1]={1, 2}, [2]={1, 2}, [3]={3} Observe that [1] = [2] and that S/R = {[1], [3]} is a partition
of S.

Partial Order Relations

A relation R on a set A is called a partial order relation if it satisfies the followingthree properties:
1. Relation R is Reflexive, i.e. aRa ∀ a∈A.
27
2. Relation R is Antisymmetric, i.e., aRb and bRa ⟹ a = b.
3. Relation R is transitive, i.e., aRb and bRc ⟹ aRc.

Example1: Show whether the relation (x, y) ∈ R, if, x ≥ y defined on the set of +veintegers is a partial
order relation.
Solution: Consider the set A = {1, 2, 3, 4} containing four +ve integers. Find the relation for this set
such as R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3), (1, 1), (2, 2),
(3, 3), (4, 4)}.

Reflexive: The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2), (3,3), (4, 4) ∈ R.

Antisymmetric: The relation is antisymmetric as whenever (a, b) and (b, a) ∈ R,we have a = b.

Transitive: The relation is transitive as whenever (a, b) and (b, c) ∈ R, we have (a,c) ∈ R.

Example: (4, 2) ∈ R and (2, 1) ∈ R, implies (4, 1) ∈ R.

As the relation is reflexive, antisymmetric and transitive. Hence, it is a partialorder relation.
Example2: Show that the relation 'Divides' defined on N is a partial order relation.

Solution:
Reflexive: We have a divides a, ∀ a∈N. Therefore, relation 'Divides' is reflexive.
Antisymmetric: Let a, b, c ∈N, such that a divides b. It implies b divides a iff a = b.So, the relation is
antisymmetric.
Transitive: Let a, b, c ∈N, such that a divides b and b divides c.
Then a divides c. Hence the relation is transitive. Thus, the relation being reflexive, antisymmetric
and transitive, the relation 'divides' is a partial orderrelation.

Example3: (a) The relation ⊆ of a set of inclusion is a partial ordering or anycollection of sets since
set inclusion has three desired properties:
1. A ⊆ A for any set A.
2. If A ⊆ B and B ⊆ A then B = A.
3. If A ⊆ B and B ⊆ C then A ⊆ C
(b) The relation ≤ on the set R of real no that is Reflexive, Antisymmetric andtransitive.
(c) Relation ≤ is a Partial Order Relation.

n-Ary Relations
By an n-ary relation, we mean a set of ordered n-tuples. For any set S, a subset ofthe product set Sn
is called an n-ary relation on S. In particular, a subset of S3 is called a ternary relation on S.
Partial Order Set (POSET):
The set A together with a partial order relation R on the set A and is denoted by (A, R) is called a
partial orders set or POSET.

Total Order Relation

Consider the relation R on the set A. If it is also called the case that for all, a, b ∈ A, we have either
(a, b) ∈ R or (b, a) ∈ R or a = b, then the relation R is known totalorder relation on set A.

Example: Show that the relation '<' (less than) defined on N, the set of +ve integers is neither an
equivalence relation nor partially ordered relation but is atotal order relation.
28
Solution:
Reflexive: Let a ∈ N, then a < a
⟹ '<' is not reflexive.
As, the relation '<' (less than) is not reflexive, it is neither an equivalence relationnor the partial order
relation.
But, as ∀ a, b ∈ N, we have either a < b or b < a or a = b. So, the relation is a totalorder relation.

Equivalence Class
Consider, an equivalence relation R on a set A. The equivalence class of an element a ∈ A, is the
set of elements of A to which element a is related. It isdenoted by [a].

Example: Let R be an equivalence relations on the set A = {4, 5, 6, 7} defined byR = {(4, 4), (5, 5), (6,
6), (7, 7), (4, 6), (6, 4)}.
Determine its equivalence classes.

Solution: The equivalence classes are as follows:

{4} = {6} = {4, 6}
{5} = {5}
{7} = {7}.

Circular Relation
Consider a binary relation R on a set A. Relation R is called circular if (a, b) ∈ R and(b, c) ∈ R implies
(c, a) ∈ R.
Example: Consider R is an equivalence relation. Show that R is reflexive andcircular.
Solution: Reflexive: As, the relation, R is an equivalence relation. So, reflexivity is the property of an
equivalence relation. Hence, R is reflexive.
Circular: Let (a, b) ∈ R and (b, c) ∈ R
⇒ (a, c) ∈ R (∵ R is transitive)
⇒ (c, a) ∈ R (∵ R is symmetric)Thus, R is Circular.

Compatible Relation
A binary relation R on a set A that is Reflexive and symmetric is called CompatibleRelation.
Every Equivalence Relation is compatible, but every compatible relation need notbe an equivalence.
Example: Set of a friend is compatible but may not be an equivalence relation.
Friend Friend
a → b, b → c but possible that a and c are not friends.

Counting
Counting problems arise throughout mathematics and computer science. For example, we must
count the successful outcomes of experiments and all the possible outcomes of these
experiments to determine probabilities of discrete events.

Basic Counting Principles

THE PRODUCT RULE
Product rule
Basic Counting
Principles Sum rule
29
If the events occur one after the other, then all the events can occur in the order indicated in: n1 · n2
· n3 · ...ways.

EXAMPLE
How many different license plates can be made if each plate contains a sequence of three
uppercase English letters followed by three digits?
Solution: By the product rule there are a total of 26·26·26·10·10·10 = 17,576,000 possible license
plates.

THE SUM RULE

Suppose some event E can occur in m ways and a second event F can occur in n ways, and
suppose both events cannot occur simultaneously. Then E or F can occur in m + n ways.

EXAMPLE Suppose a college has 3 different history courses, 4 different literature courses, and 2
different sociology courses.
Solution:
(a) The number m of ways a student can choose one of each kind of courses is: m = 3(4)(2) = 24
(b) The number n of ways a student can choose just one of the courses is: n = 3 +4 + 2 = 9
(1) Sum Rule Principle: Suppose A and B are disjoint sets. Thenn (A 𝖴 B) = n(A) + n(B)
(2) Product Rule Principle: Let A × B be the Cartesian product of sets A and B. Then n (A × B) = n
(A) · n (B)

MATHEMATICAL FUNCTIONS
Two important mathematical functions frequently used are:
Factorial Function
The product of the positive integers from 1 to n inclusive is denoted by n!, read “n factorial.”
Namely:
n! = 1 · 2 · 3 · ... · (n−2)(n−1)n = n(n−1)(n−2) · ... · 3 · 2 · 1
Accordingly, 1! = 1 and n! = n (n − l) !. It is also convenient to define 0! = 1.
EXAMPLE: 3! = 3·2·1 = 6, 4! = 4·3·2·1 = 24, 5 = 5·4! =5(24) = 120.

Binomial Coefficients: The symbol (n r), read “n C r” or “n Choose r,” where r and n are positive
integers with r ≤ n, is defined as follows:
= n(n − 1)···(n − r + 1/ r(r − 1)... 3·2·1 or = n! / r! (n − r)!

Binomial Coefficients and Pascal’s Triangle

The numbers (n r) are called binomial coefficients, since they appear as the coefficients in the
expansion of (a + b) ^n.

The Subtraction Rule (Inclusion–Exclusion for Two Sets)

If a task can be done in either n1 ways or n2 ways, then the number of ways to do the task is n1 +
n2 minus the number of ways to do the task that are common to the two different ways.

The subtraction rule is also known as the principle of inclusion exclusion, especially when it is
used to count the number of elements in the union of two sets.
Formula: |A1 𝖴 A2|=|A1|+|A2|−|A1 ∩ A2|.

30
THE DIVISION RULE
There are n/d ways to do a task if it can be done using a procedure that can be carried out in n
ways, and for every way w, exactly d of the n ways correspond to way w.
Division rule in terms of sets: “If the finite set A is the union of n pair wise disjoint subsets each
with d elements, then n = |A|/d.”

The Pigeonhole Principle

Pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there
must be at least one pigeonhole with at least two pigeons in it.

THEOREM 1 THE PIGEONHOLE PRINCIPLE If k is a positive integer and k + 1 or more objects are
placed into k boxes, then there is at least one box containing two or more of the objects.
(a) Figure there are more Pigeons than Pigeonholes
Proof: We prove the pigeonhole principle using a proof by contraposition. Suppose that none of
the k boxes contains more than one object. Then the total number of objects would be at most k.
This is a contradiction, because there is at least k + 1 objects. The pigeonhole principle is also
called the Dirichlet drawer principle.

COROLLARY 1 A function f from a set with k + 1 or more elements to a set with k elements is not
one-to-one.
EXAMPLE Among any group of 367 people, there must be at least two with the same birthday,
because there are only 366 possible birthdays.

The Generalized Pigeonhole Principle

THEOREM 2 If N objects are placed into k boxes, then there is at least one box containing at least
N/k objects.
Proof: Suppose that none of the boxes contains more than N/k − 1 objects. Then, the total number
of objects is at most
K ( [ N/k ] – 1) < k ( ( N/ k + 1 ) –1) = N , where the inequality N/k < (N/k) + 1 has been used.

EXAMPLE
What is the minimum number of students required in a discrete mathematics class to be sure that
at least six will receive the same grade, if there are five possible grades, A, B, C, D, and F?
Solution: The smallest integer N such that N/5 = 6. The smallest such integer is N =5 · 5 + 1 = 26.

Permutations and CombinationsPermutations

A permutation of a set of distinct objects is an ordered arrangement of these objects. An ordered
arrangement of r elements of a set is called an r- permutation.

31
EXAMPLE Let S = {1, 2, 3}. The ordered arrangement 3, 1, 2 is a permutation of S. The ordered
arrangement 3, 2 is a 2-permutation of S.
The number of r-permutations of a set with n elements is denoted by P (n, r). P (n, r) using the
product rule.

THEOREM 1 If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are P (n, r) = n (n −
1)(n − 2)···(n − r + 1) r-permutations of a set with n distinct elements.
n − (r − 1) = n − r + 1 ways to choose the r th element. By the product rule, there are n (n − 1) (n −
2)···(n − r + 1) r-permutations of the set.

COROLLARY If n and r are integers with 0 ≤ r ≤ n, thenP (n, r) = n! / (n − r)!

Proof: When n and r are integers with 1 ≤ r ≤ n, by Theorem 1 we haveP (n, r) = n (n − 1) (n − 2)···(n −
r + 1) = n!/(n − r)!
n! / (n − 0)! = n!/n! = 1 whenever n is a nonnegative integer

EXAMPLE How many ways are there to select a first-prize winner, a second-prize winner, and a
third-prize winner from 100 different people who have entered a contest?
Solution: Number of 3-permutations of a set of 100 elements.P (100, 3) = 100 · 99 · 98 = 970,200.
Combinations
An r-combination of elements of a set is an unordered selection of r elements from the set.
Thus, an r-combination is simply a subset of the set with r elements.

EXAMPLE Let S be the set {1, 2, 3, 4}. Then {1, 3, 4} is a 3-combination from S.
The number of r-combinations of a set with n distinct elements is denoted by C (n,r).

THEOREM 2 The number of r-combinations of a set with n elements, where n is a nonnegative

integer and r is an integer with 0 ≤ r ≤ n, equals C (n, r) = n! / r! (n − r)!

EXAMPLE How many poker hands of five cards can be dealt from a standard deck of 52 cards?
Also, how many ways are there to select 47 cards from a standard deck of 52 cards?
Solution: C (52, 5) = 52! / (5! 47!)
First divide the numerator and denominator by 47! to obtainC (52, 5) = (52 · 51 · 50 · 49 · 48) / (5 · 4
· 3 · 2 · 1 ) = 2,598,960.

COROLLARY 2: Let n and r be non-negative integers with r ≤ n. Then C (n, r) = C(n,n − r).
DEFINITION 1 A combinatorial proof of an identity is a proof that uses counting arguments to
prove that both sides of the identity count the same objects but in different ways or a proof that is
based on showing that there is a bi-ejection between the sets of objects counted by the two sides
of the identity.
EXAMPLE How many ways are there to select five players from a 10-member tennis team to
make a trip to a match at another school?
Sol: Number of such combinations is C (10, 5) = 10! / 5! 5! = 252.
Combinations and Permutations with and without Repetition.

Type Repetition Allowed? Formula

32
 r-permutations No n! / (n − r)!

r-permutations No n! / r! ( n − r)!

r-permutations Yes nr

r-combinations Yes (n + r − 1)! /r! (n − 1)!

Mathematical Induction
The process to establish the validity of an ordinary result involving natural numbers is the principle
of mathematical induction.

Working Rule
Let n0 be a fixed integer. Suppose P (n) is a statement involving the natural number n and we wish
to prove that P (n) is true for all n ≥n0.
1. Basic of Induction: P (n0) is true i.e. P (n) is true for n = n0.
2. Induction Step: Assume that the P (k) is true for n = k.Then P (K+1) must also be true.
Then P (n) is true for all n ≥n0.
Example 1:
Prove the follo2wing by Mathematical Induction:1 + 3 + 5 +. + 2n - 1 = n2.
Solution: let us assume that.
P (n) = 1 + 3 + 5 +..... + 2n - 1 = n2.For n = 1, P (1) = 1 = 12 = 1
It is true for n = 1 (i)
Induction Step: For n = r,
P (r) = 1 + 3 + 5 +..... +2r-1 = r2 is true.
(ii) Adding 2r + 1 in both sides
P (r + 1) = 1 + 3 + 5 +. +2r-1 + 2r +1
= r2 + (2r + 1) = r2 + 2r +1 = (r+1)2 (iii)
As P(r) is true. Hence P (r+1) is also true.From (i), (ii) and (iii) we conclude that.
1 + 3 + 5 +..... + 2n - 1 =n2 is true for n = 1, 2, 3, 4, 5 Hence Proved.

Example 2:
12 + 22 + 32 +.......+ n2 =

Solution: For n = 1,
P (1) = 12 = = 1
It is true for n = 1.

Induction Step: For n = r, (i)

P (r) = 12 + 22 + 32 +........ + r2 = is true. (ii)
Adding (r+1)2 on both sides, we get
P (r+1) = 12 + 22 + 32 +.......+ r2+ (r+1)2 = + (r+1)2
33
As P (r) is true, hence P (r+1) is true. From (i), (ii) and (iii) we conclude that
12 + 22 + 32 +......+ n2= is true for n = 1, 2, 3, 4, 5 Hence Proved.
Example3: Show that for any integer n
11n+2 + 122n+1 is divisible by 133.
Solution:
Let P (n) = 11n+2+122n+1
For n = 1,
P (1) = 113+123=3059=133 x 23
So, 133 divide P (1) (i)
Induction Step: For n = r,
P (r) = 11r+2+122r+1=133 x s (ii)
Now, for n = r + 1,
P (r+1) = 11r+2+1+122(r)+3=11[133s-122r+1] + 144. 122r+1
= 11 x 133s + 122r+1.133=133[11s+122r+1]=133 x t (iii)
As (i), (ii), and (iii) all are true, hence P (n) is divisible by 133.

PROVING RESULTS ABOUT SETS

Mathematical induction can be used to prove many results about sets.

a•
X

X
54

a•

X𝖴 {a}
T

FIGURE:
34
Generating subsets of a set with k+1elements.Here T = S 𝖴 {a}.

Strong Induction and Well-Ordering

Strong induction, which can often be used when we cannot easily prove a result using
mathematical induction.

To prove that P (n) is true for all positive integers n, where P (n) is a propositional function, we
complete two steps:
BASIS STEP: We verify that the proposition P (1) is true. INDUCTIVE STEP: Conditional statement
[P (1) 𝖠 P (2) 𝖠···𝖠P (k)] → P (k + 1) is true for all positive integers k.

Using Strong Induction in Computational Geometry A polygon is called convex if every line
segment connecting two points in the interior of the polygon lies entirely inside the polygon. (A
polygon that is not convex is said to be non- convex.)

FIGURE Convex and Non-convex Polygons.

THEOREM 1 A simple polygon with n sides, where n is an integer with n ≥ 3, can be triangulated
into n − 2 triangles.
LEMMA 1 Every simple polygon with at least four sides has an interior diagonal.
Proof (of Theorem 1): We will prove this result using strong induction. Let T (n) be the statement
that every simple polygon with n sides can be triangulated into n − 2 triangles.
BASIS STEP: T (3) is true because a simple polygon with three sides is a triangle. Consequently,
every simple polygon with n = 3 has can be triangulated into n − 2 =3 − 2 = 1triangle.

INDUCTIVE STEP: For the inductive hypothesis,T(j ) is true for all integers j with 3 ≤j ≤ k. That is, we
assume that we can triangulate a simple polygon with j sides intoj − 2 triangles whenever 3 ≤ j ≤ k.
To complete the inductive step, we must show that when we assume the inductive hypothesis, P (k
+ 1) is true, that is, that every simple polygon with k + 1 sides can be triangulated into (k + 1) − 2 =
k − 1 triangles.

Proofs Using the Well-Ordering Property

The validity of both the principle of mathematical induction, strong induction follows from a
fundamental axiom of the set of integers, the well-ordering property.

EXAMPLE Use the well-ordering property to prove the division algorithm. Recall that the division
algorithm states that if a is an integer and d is a positive integer, then there are unique integers q
and r with 0 ≤ r<d and a = d q + r.
Solution: Let S be the set of nonnegative integers of the form a – d q, where q is an integer. This
set is nonempty because –d q can be made as large as desired (taking q to be a negative integer
with large absolute value).
By the well-ordering property, S has a least element r = a − dq0. The integer r is nonnegative. It is
also the case that r<d.
35
Recursively Defined Functions
BASIS STEP: Specify the value of the function at zero.
RECURSIVE STEP: Give a rule for finding its value at an integer from its values at smaller
integers.
Such a definition is called a recursive or inductive definition.

EXAMPLE Suppose that f is defined recursively by f (0) = 3,f (n + 1) = 2f (n) + 3.Find f (1), f (2), and f
(4).
Solution: f (1) = 2f (0) + 3 = 2 · 3 + 3 = 9,
f (2) = 2f (1) + 3 = 2 · 9 + 3 = 21,f (4) = 2f (3) + 3 = 2 · 45 + 3 = 93.

Probability
The word 'Probability' means the chance of occurring of a particular event. It is generally possible
to predict the future of an event quantitatively with a certain probability of being correct. The
probability is used in such cases wherethe outcome of the trial is uncertain.

Probability Definition:
The probability of happening of an event A, denoted by P(A), is defined as

Thus, if an event can happen in m ways and fails to occur in n ways and m+n ways is equally
likely to occur then the probability of happening of the event Ais given by

And the probability of non-happening of A is

Note:
1. The probability of an event which is certain to occur is one.
2. The probability of an event which is impossible to zero.
3. If the probability of happening of an event P(A) and that of nothappening is P(A), then
P(A)+ P(A) = 1, 0 ≤ P(A) ≤ 1,0≤ P(A)≤1.

Important Terms related to Probability:

1. Trial and Event: The performance of an experiment is called a trial, and theset of its outcomes
is termed an event.
Example: Tossing a coin and getting head is a trial. Then the event is {HT, TH,HH}
2. Random Experiment: It is an experiment in which all the possible outcomes of the experiment
are known in advance. But the exact outcomes of any specific performance are not known in
advance.
Example:
1. Tossing a Coin
2. Rolling a die
3. Drawing a card from a pack of 52 cards.
4. Drawing a ball from a bag.
36
3. Outcome: The result of a random experiment is called an Outcome.
Example: 1. Tossing a coin is an experiment and getting head is called anoutcome.
2. Rolling a die and getting 6 is an outcome.

4. Sample Space: The set of all possible outcomes of an experiment is called sample space
and is denoted by S.
Example: When a die is thrown, sample space is S = {1, 2, 3, 4, 5, 6}
It consists of six outcomes 1, 2, 3, 4, 5, 6
Note1: If a die is rolled n times the total number of outcomes will be 6 n. Note2: If 1 die rolled n
times then n die rolled 1 time.

5. Complement of Event: The set of all outcomes which are in sample spacebut not an event is
called the complement of an event.

6. Impossible Events: An event which will never be happened.

Example1: Tossing double-headed coins and getting tails in an impossibleevent.
Example2: Rolling a die and getting number > 10 in an impossible outcome.
P (impossible outcome) =0

7. Sure Outcome/Certain Outcome: An Outcome which will definitely behappen

Example1: Tossing double-headed coins and getting heads only.
Example2: Rolling a die and getting number < 6P (sure outcome) = 1
{1, 2, 3, 4, 5 6} is called sure eventP (sure outcome) = 1

8. Possible Outcome: An outcome which is possible to occur is called PossibleOutcome.

Example1: Tossing a fair coin and getting a head on it.

Example2: Rolling a die and getting an odd number.

9. Equally Likely Events: Events are said to be equally likely if one of them cannot be expected
to occur in preference to others. In other words, it means each outcome is as likely to occur
as any other outcome.
Example: When a die is thrown, all the six faces, i.e., 1, 2, 3, 4, 5 and 6 areequally likely to occur.

Mutually Exclusive or Disjoint Events: Events are called mutually exclusive if they cannot occur
simultaneously.
Example: Suppose a card is drawn from a pack of cards, then the events getting a jack and
getting a king are mutually exclusive because they cannotoccur simultaneously.

10.Exhaustive Events: The total number of all possible outcomes of an experiment is called
exhaustive events.
Example: In the tossing of a coin, either head or tail may turn up. Therefore, there are two possible
outcomes. Hence, there are two exhaustive events in tossing a coin.

11.Independent Events: Events A and B are said to be independent if theoccurrence of any one
event does not affect the occurrence of any other event.
37
 P (A ∩ B) = P (A) P (B).
Example: A coin is tossed thrice, and all 8 outcomes are equally likely A: "The first throw results
in heads."
B: "The last throw results in Tails."Prove that event A and B are independent.
Solution:

12.Dependent Event: Events are said to be dependent if occurrence of oneaffect the occurrence
of other events.

Addition Theorem
Theorem1: If A and B are two mutually exclusive events, thenP(A 𝖴B)=P(A)+P(B)
Proof: Let the n=total number of exhaustive cases n1= number of cases favorable to A. n2=
number of cases favorable to B.
Now, we have A and B two mutually exclusive events. Therefore, n1+n2 is the number of cases
favorable to A or B.

Example: Two dice are tossed once. Find the probability of getting an even number on first dice
or a total of 8.
Solution: An even number can be got on a die in 3 ways because any one of 2 , 4,6 , can come. The
other die can have any number. This can happen in 6 ways. ∴ 𝑃( an even number on Ist die ) =
3×6 18 1
= =
36 36 2
A total of 8 can be obtained in the following cases:

{(2,6), (3,5), (4,4), (5,3), (6,2)}

5
∴ 𝑃( a total of 8) =
36
1 5 23
∴ Total Probability = + =
2 36 36
Theorem2: If 𝐴 and 𝐵 are two events that are not mutually exclusive, then

𝑃(𝐴 ∪ 𝐵) = 𝑃(𝐴) + 𝑃(𝐵) − 𝑃(𝐴 ∩ 𝐵).

38
Proof: Let n = total number of exhaustive cases
n1 = number of cases favorable to 𝐴
𝑛2 = number of cases favorable to 𝐵
𝑛3 = number of cases favorable to both 𝐴 and 𝐵
But 𝐴 and 𝐵 are not mutually exclusive. Therefore, 𝐴 and 𝐵 can occur
simultaneously. So, 𝑛1 + 𝑛2 − 𝑛3 is the number of cases favorable to 𝐴 or 𝐵.
𝑛1 +𝑛2 −𝑛3 𝑛1 𝑛2 𝑛3
Therefore, 𝑃(𝐴 ∪ 𝐵) = = + −
𝑛 𝑛 𝑛 𝑛
𝑛 𝑛 𝑛
But we have, 𝑃(𝐴) = 𝑛1 , 𝑃(𝐵) = 𝑛2 and 𝑃(𝐴 ∩ 𝐵) = 𝑛3
Hence, 𝑃(𝐴 ∪ 𝐵) = 𝑃(𝐴) + 𝑃(𝐵) − 𝑃(𝐴 ∩ 𝐵).
Example1: Two dice are tossed once. Find the probability of getting an even number on first dice
or a total of 8 .

Solution: 𝑃( even number on Ist die or a total of 8) = 𝑃 (even number on Ist die ) + 𝑃( total of 8) =
𝑃( even number on Ist die and a total of 8)
18 1
∴ Now, 𝑃( even number on Ist die ) = =
36 2
Ordered Pairs showing a total of 8 = {(6,2), (5,3), (4,4), (3,5), (2,6)} = 5 ∴ Probability;
5
𝑃( total of 8) = 36
3
𝑃( even number on Ist die and total of 8) = 36
18 5 3 20 5
∴ Required Probability = 36 + 36 − 36 = 36 = 9
Example2: Two dice are thrown. The events 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹
𝐴 = getting even number on first die.
𝐵 = getting an odd number on the first die.
𝐶 = getting a sum of the number on dice ≤ 5
𝐷 = getting a sum of the number on dice > 5 but less than 10 .
𝐸 = getting sum of the number on dice ≥ 10.
𝐹 = getting odd number on one of the dice

Show the following:

1. A, B are a mutually exclusive event and Exhaustive Event.
2. A, C are not mutually exclusive.
3. C, D are a mutually exclusive event but not Exhaustive Event.
4. C, D, E are a mutually exclusive and exhaustive event.
5. A'∩B' are a mutually exclusive and exhaustive event.
6. A, B, F are not a mutually exclusive event.

Solution:
A: (2,1),(2,2),(2,3),(2,4),(2,5),(2,6)
(4,1),(4,2),(4,3),(4,4),(4,5),(4,6)
(6,1),(6,2),(6,3),(6,4),(6,5),(6,6)
39
B: (1,1), (1,2),(1,3),(1,4),(1,5),(1,6)
(3,1),(3,2),(3,3),(3,4),(3,5),(3,6)
(5,1),(5,2),(5,3),(5,4),(5,5),(5,6)

C: (1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(3,1),(3,2),(4,1)

D: (1,5),(1,6),(2,4),(2,5),(2,6)
(3,3),(3,4),(3,5),(3,6)
(4,2),(4,3),(4,4),(4,5)
(5,1),(5,2),(5,3),(5,4)
(6,1),(6,2),(6,3)

E: (4,6),(5,5),(5,6),(6,5),(6,6),(6,4)

F: (1,2),(1,4),(1,6)
(2,1),(2,3),(2,5)
(3,2),(3,4),(3,6)
(4,1),(4,3),(4,5)
(5,2),(5,4),(5,6)
(6,1),(6,3),(6,5)

1. (A∩B) =∅ and (A𝖴B)=S

A, B are a mutually exclusive and exhaustive event.
2. (A∩C) are not mutually exclusive(2,1),(2,3),(4,1)≠ ∅
3. C∩D are a mutually exclusive but not exhaustive event.C∩D=∅ C𝖴 D≠S
4. C∩D=∅,D∩E=∅, C∩E=∅ are mutually exclusive and exhaustive event.
5. A'∩B' =(A𝖴B)' are a mutually exclusive and exhaustive event.
6. (A∩B) =∅ are a mutually exclusive
A, B, F are not mutually exclusive events.

Multiplication Theorem
Theorem: If A and B are two independent events, then the probability that both will occur is
equal to the product of their individual probabilities.
P(A∩B)=P(A)xP(B)
Proof: Let event7
A can happen is n1ways of which p are successful
B can happen is n2ways of which q are successful
Now, combine the successful event of A with successful event of B.
Thus, the total number of successful cases = p x q
We have, total number of cases = n1 x n2.
Therefore, from definition of probability

P (A and B) =P(A∩B)=

We have P(A) = ,P(B)=

40
So, P(A∩B)=P(A)xP(B)

If, there are three independent events A, B and C, then

P(A∩B∩C)=P((A∩B)∩C)= P(A∩B)xP(C)
=P(A) x P(B) x P(C).

In general, if there are n independent events, then

Example: A bag contains 5 green and 7 red balls. Two balls are drawn. Find the probability that
one is green and the other is red.

Solution: P(A) =P(a green ball) = P(B) =P(a red ball) =

By Multiplication Theorem

P(A) and P(B) = P(A) x P(B) =

CONDITIONAL PROBABILITY
Suppose E is an event in a sample space S with P (E) > 0. The probability that an event A occurs
once E has occurred or, specifically, the conditional probability ofA given E. written P (A|E), is
defined as follows: P (A|E) = P (A ∩ E) / P (E)

Theorem: Suppose S is an equi-probable space and A and E are events. Then

P (A|E) = number of elements in A ∩ E / number of elements in E = n (A ∩ E) / n(E)
Example: A couple has two children; the sample space is S = {bb, b g, g b, g g} with probability 1/4
for each point. Find the probability p that both children are boys ifit is known that: (i) at least one of
the children is a boy; (ii) the older child is a boy.
Solution: Here the reduced space consists of three elements, {bb, b g, g b}; hencep = 1/3
Here the reduced space consists of only two elements {b b, b g}; hence p = ½

Multiplication Theorem for Conditional ProbabilityTheorem: P (A ∩ B) = P (A) P (B|A)

The multiplication theorem gives us a formula for the probability that events A and B both occur. It
can easily be extended to three or more events A1, A2...A m;that is,
P (A1 ∩ A2 ∩··· Am) = P (A1) · P (A2|A1)··· P (Am|A1 ∩ A2 ∩···∩ Am−1)

INDEPENDENT EVENTS
Definition 7.2: Events A and B are independent if P(A ∩ B) = P(A)P(B); otherwisethey are dependent.
P (A ∩ B) = P (A) P (B) implies both P (B|A) = P (B) and P (A|B) = P (A)

EXAMPLE A fair coin is tossed three times yielding the equi-probable space. S = {HHH, HHT, HTH,
HTT, THH, THT, TTH, TTT}
Solution Consider the events: A = {first toss is heads} = {HHH, HHT, HTH, HTT} B = {second toss is
heads) = {HHH, HHT, THH, THT}
C = {exactly two heads in a row} = {HHT, THH}
P (A) = 4 /8 = 1 / 2, P (B) = 4 / 8 = 1 / 2, P (C) = 2 / 8 = 1/4
P (A ∩B) = P ({HHH, HHT}) = 1 / 4, P (A ∩C) = P ({HHT}) = 1 / 8, P (B ∩ C) = P ({HHT,THH}) = 1 / 4

41
INDEPENDENT REPEATED TRIALS, BINOMIAL DISTRIBUTION
Definition: Let S be a finite probability space. By the space of n independent repeated trials, we
mean the probability space S n consisting of ordered n-tuples of elements of S, with the probability
of an n-tuples defined to be the product ofthe probabilities of its components:
P ((S1, S2,..., S n)) = P (S1)P (S2) . . . P (S n)

RANDOM VARIABLES
Definition: A random variable X is a rule that assigns a numerical value to each outcome in a
sample space S.
EXAMPLE A pair of fair dice is tossed. The sample space S consists of the 36 ordered pairs (a, b)
where a and b can be any of the integers from 1 to 6.
Solution: Let x assign to each point in S the sum of the numbers; then x is a random variable with
range space
Rx = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
Let y assign to each point the maximum of the two numbers; then y is a randomvariable with range
space R y = {1, 2, 3, 4, 5, 6}
Probability Distribution of a Random Variable
Theorem: Let S be an equiv.-probable space, and let f be the distribution of a random variable X on
S with the range space Rx = {x1, x2,...,x t}.
P i = f (x i) = No. of points in S whose image is x i /No. of points in S
EXAMPLE Let X be the random variable in Example 7.13 which assigns the sum tothe toss of a pair
of dice. Note n(S) = 36, and Rx = {2, 3,..., 12}.
Solution: Using Theorem, we obtain the distribution f of X as follows:f (2) = 1/36, since there is one
outcome (1, 1) whose sum is 2.
f (3) = 2/36, since there are two outcomes, (1, 2) and (2,1), whose sum is 3.
f (4) = 3/36, since there are three outcomes, (1, 3), (2, 2) and (3, 1), whose sum is 4.
Similarly, f (5) = 4/36, f (6) = 5/36... f (12) = 1/36. Thus the distribution of Xfollows:
x 2 3 4 5 6 7 8 9 10
F(x) 1/36 2/36 3/36 4/36 5/36 6/36 7/36 8/36 7/36

Binomial Distribution
Theorem: Consider the binomial distribution B (n, p). Then:
(i) Expected value E(X) = μ = n p.
(ii) Variance V a r(X) = σ2 = n p q.
(iii)Standard deviation σ = √n p q.

EXAMPLE
The probability that a man hits a target is p = 1/5. He fires 100 times. Find theexpected number μ of
times
Solution: Man will hit the target and the standard deviation σ.
Here p = 1/5 and so q = 4/5. Hence
μ = n p = 100 *1/5 = 20 and σ = √n p q =√ 100 *1/5 *4/5 = 4

Bayes' theorem in Artificial intelligence

Bayes' theorem:
Bayes' theorem is also known as Bayes' rule, Bayes' law, or Bayesian reasoning, which determines
the probability of an event with uncertain knowledge.
42
In probability theory, it relates the conditional probability and marginal probabilities of two random
events.

Bayes' theorem was named after the British mathematician Thomas Bayes.
The Bayesian inference is an application of Bayes' theorem, which is fundamental to Bayesian
statistics.
It is a way to calculate the value of P(B|A) with the knowledge of P(A|B).
Bayes' theorem allows updating the probability prediction of an event byobserving new information
of the real world.

Example: If cancer corresponds to one's age then by using Bayes' theorem, we can determine the
probability of cancer more accurately with the help of age.
Bayes' theorem can be derived using product rule and conditional probability of event A with known
event B:
As from product rule we can write:
1. P(A ⋀ B)= P(A|B) P(B) or
Similarly, the probability of event B with known event A:
1. P(A ⋀ B)= P(B|A) P(A)
Equating right hand side of both the equations, we will get:

The above equation (a) is called as Bayes' rule or Bayes' theorem. This equation is basic of most
modern AI systems for probabilistic inference.
It shows the simple relationship between joint and conditional probabilities. Here,
P(A|B) is known as posterior, which we need to calculate, and it will be read as Probability of
hypothesis A when we have occurred an evidence B.
P(B|A) is called the likelihood, in which we consider that hypothesis is true, then we calculate the
probability of evidence.
P(A) is called the prior probability, probability of hypothesis before consideringthe evidence
P(B) is called marginal probability, pure probability of an evidence.
In the equation (a), in general, we can write P (B) = P(A)*P(B|Ai), hence the Bayes' rule can be
written as0:

Where A1, A2, A3, , An is a set of mutually exclusive and exhaustive events.
Applying Bayes' rule:

Bayes' rule allows us to compute the single term P(B|A) in terms of P(A|B), P(B), and P(A). This is
very useful in cases where we have a good probability of these three terms and want to determine
the fourth one. Suppose we want to perceive the effect of some unknown cause, and want to
compute that cause, then the Bayes' rule becomes:

43
Example-1:
Question: what is the probability that a patient has diseases meningitis with astiff neck?
Given Data:
A doctor is aware that disease meningitis causes a patient to have a stiff neck, andit occurs 80% of
the time. He is also aware of some more facts, which are given asfollows:
• The Known probability that a patient has meningitis disease is 1/30,000.
• The Known probability that a patient has a stiff neck is 2%.
Let a be the proposition that patient has stiff neck and b be the proposition thatpatient has
meningitis. , so we can calculate the following as:
P(a|b) = 0.8
P(b) = 1/30000
P(a)= .02

Hence, we can assume that 1 patient out of 750 patients has meningitis diseasewith a stiff neck.

Example-2:
Question: From a standard deck of playing cards, a single card is drawn. The probability that the
card is king is 4/52, then calculate posterior probability P(King|Face), which means the drawn
face card is a king card.

Solution:
P(king): probability that the card is King= 4/52= 1/13 P(face): probability that a card is a face card=
3/13

P(Face|King): probability of face card when we assume it is a king = 1Putting all values in equation
(i) we will get:

Application of Bayes' theorem in Artificial intelligence:

Following are some applications of Bayes' theorem:
• It is used to calculate the next step of the robot when the already executedstep is given.
• Bayes' theorem is helpful in weather forecasting.
• It can solve the Monty Hall problem.

Group Theory
Group
Let G be a non-void set with a binary operation * that assigns to each ordered pair
(a, b) of elements of G an element of G denoted by a * b. We say that G is a group under the binary
operation * if the following three properties are satisfied:
1. Associativity: The binary operation * is associative i.e. a*(b*c)=(a*b)*c , ∀ a,b,c
∈G
44
2. Identity: There is an element e, called the identity, in G, such that a*e=e*a=a,
∀a∈G
3. Inverse: For each element a in G, there is an element b in G, called an inverse of a such that
a*b=b*a=e, ∀ a, b ∈ G
Note: If a group has the property that a*b=b*a i.e., commutative law holds then the group is called
an abelian.

Properties of Groups:
The following theorems can understand the elementary features of Groups:
Theorem1:-
1. Statement: - In a Group G, there is only one identity element (uniqueness ofidentity)
Proof: - let e and e' are two identities in G and let a ∈ G
∴ ae = a ⟶(i)
∴ ae' = a ⟶(ii)
R.H.S of (i) and (ii) are equal ⇒ae =ae'
Thus by the left cancellation law, we obtain e= e'
There is only one identity element in G for any a ∈ G. Hence the theorem isproved.

2. Statement: - For each element a in a group G, there is a unique element b in G such that ab=
ba=e (uniqueness if inverses)
Proof: - let b and c are both inverses of a a∈ G
Then ab = e and ac = e
∵ c = ce {existence of identity element}
⟹ c = c (ab) {∵ ab = e}
⟹ c = (c a) b
⟹ c = (ac) b { ∵ ac = ca}
⟹ c = eb
⟹ c = b { ∵ b = eb}
Hence inverse of a G is unique.

Theorem 2:-
1. Statement: - In a Group G,(a-1)-1=a,∀ a∈ G
Proof: We have a a-1=a-1 a=e
Where e is the identity element of GThus a is inverse of a-1∈ G
i.e., (a-1)-1=a,∀ a∈ G

2. Statement: In a Group G,(a b-1)=b-1 a-1,∀ a,b∈ G

Proof: - By associatively we have(b-1 a-1)ab=b-1 (a-1 a)b
⟹(b-1 a-1)ab=b-1 (e)b {∵a-1 a=e}
⟹(b-1 a-1)ab=b-1 b {∵eb=b}
⟹(b-1 a-1)ab=e, {∵b-1 b=e}
Similarly
(ab) (b-1 a-1)=a(b b-1) a-1
⟹(ab) (b-1 a-1)=a (e) a-1
⟹(ab) (b-1 a-1)=a a-1
⟹(ab) (b-1 a-1)=e {∵aa-1=e}
Thus ( b-1 a-1)ab=(ab)(b-1 a-1)=e
∴ b-1 a-1 is the inverse of abi.e., b-1 a-1= a b-1
45
Hence the theorem is proved.

Theorem3:-
In a group G, the left and right cancellation laws hold i.e.
(i) ab = ac implies b=c
(ii) ba=ca implies b=c

Proof
(i) Let ab=ac
Premultiplying a-1 on both sides we geta-1 (ab)=a-1 (ac)
⟹ (a-1a) b=(a-1 a)c
⟹eb=ec
⟹b=c Hence Proved.
(ii) Let ba=ca
Post-multiplying a-1 on both sides
⟹(ba) a-1=(ca) a-1
⟹b(aa-1 )=c(aa-1 )
⟹be=ce
⟹b=c
Hence the theorem is proved.

Finite and Infinite Group:

A group (G, *) is called a finite group if G is a finite set.
A group (G, *) is called a infinite group if G is an infinite set.
Example1: The group (I, +) is an infinite group as the set I of integers is an infiniteset.
Example2: The group G = {1, 2, 3, 4, 5, 6, 7} under multiplication modulo 8 is afinite group as the set
G is a finite set.

Order of Group:
The order of the group G is the number of elements in the group G. It is denoted by |G|. A group of
order 1 has only the identity element, i.e., ({e} *).
A group of order 2 has two elements, i.e., one identity element and one someother element.
Example1: Let ({e, x}, *) be a group of order 2. The table of operation is shown infig:

* e x
e e x
x x e

The group of order 3 has three elements i.e., one identity element and two otherelements.

Symmetric Group S n
A one-to-one mapping σ of the set {1, 2...n} onto itself is called a permutation. σ =
1 2 3_ _ _ n
j1 j2 j3_ _ _ j n
The set of all such permutations is denoted by S n, and there are n! = n (n − 1) · ...
· 2 · 1 of them.

Subgroup
46
If a non-void subset H of a group G is itself a group under the operation of G, wesay H is a subgroup
of G.
Theorem: - A subset H of a group G is a subgroup of G if:
• the identity element a∈ H.
• H is closed under the operation of G i.e. if a, b∈ H, then a, b∈ H and
• H is closed under inverses, that is if a∈ H then a-1∈ H.

Cyclic Subgroup:-
A Subgroup K of a group G is said to be cyclic subgroup if there exists an element x∈ G such that
every element of K can be written in the form xn for some n ∈Z.
The element x is called generator of K and we write K= <x>Cyclic

Group:-
In the case when G=, we say G is cyclic and x is a generator of G. That is, a group G is said to be
cyclic if there is an element x∈ G such that every element of G can be written in the form xn for the
some n∈ Z.

Example: The group G= {1, -1, i,-i} under usual multiplication is a finite cyclic group with i as
generator, since i1=i,i2=-1,i3=-i and i4=1
Abelian Group:

Let us consider an algebraic system (G,*), where * is a binary operation on G. Then the system (G,*)
is said to be an abelian group if it satisfies all the propertiesof the group plus a additional following
property:
1. The operation * is commutative i.e.,a * b = b * a ∀ a,b ∈G
Example: Consider an algebraic system (G, *), where G is the set of all non-zero real numbers and *
is a binary operation defined by

Show that (G, *) is an abelian group.

Solution:

Closure Property: The set G is closed under the operation *, since a * b = is areal number. Hence,
it belongs to G.
Associative Property: The operation * is associative. Let a,b,c∈G, then we have

Identity: To find the identity element, let us assume that e is a +ve real number.
Then e * a = a, where a ∈G.

47
Thus, the identity element in G is 4.

Inverse: let us assume that a ∈G. If a-1∈Q, is an inverse of a, then a * a-1=4

Thus, the inverse of element a in G is

Commutative: The operation * on G is commutative.

Thus, the algebraic system (G, *) is closed, associative, identity element, inverse and commutative.
Hence, the system (G, *) is an abelian group.

Product of Groups:
Theorem: Prove that if (G1,*1)and (G2,*2) are groups, then G = G1 x G2 i.e., (G, *) is a group with
operation defined by (a1,b1)*( a2,b2 )=(a1,*1,a2, b1 *2 b2).
Proof: To prove that G1 x G2 is a group, we have to show that G1 x G2 has the associativity operator,
has an identity and also exists inverse of every element.
Associativity. Let a, b, c ∈ G1 x G2,then
So, a * (b * c) = (a1,a2 )*((b1,b2)*(c1,c2))
= (a1,a2 )*(b1 *1 c1,b2 *2 c2)
= (a1 *1 (b1 *1 c1 ),a2 *2 (b2 *2 c2)
= ((a1 *1 b1) *1 c1,( a2 *2 b2) *2 c2)
= (a1 *1 b1,a2 *2 b2)*( c1,c2)
= ((a1,a2)*( b1,b2))*( c1,c2)
= (a * b) * c.

Identity: Let e1 and e2 are identities for G1 and G2 respectively. Then, the identity for G1 x G2 is
e=(e1,e2 ).Assume same a ∈ G1 x G2
Then, a * e = (a1,a2)*( e1,e2)
= (a1 *1 e1,a2 *2 e2)
= (a1,a2)=a Similarly, we have e * a = a.

Inverse: To determine the inverse of an element in G1 x G2, we will determine itcomponent wise i.e.,
a-1=(a1,a2)-1=(a -1,a -1 )
Now to verify that this is the exact inverse, we will compute a * a-1 and a-1*a.Now, a * a-1=(a1,a2 )*(a
-1,a -1 )

= (a1 *1 a -1,a2 *2 a -1)=( e1,e2)=eSimilarly, we have a-1*a=e.

Thus, (G1 x G2,*) is a group.
In general, if G1,G2,....Gn are groups, then G = G1 x G2 x. x Gn is also a group.

Cosets:

48
Let H be a subgroup of a group G. A left coset of H in G is a subset of G whose elements may be
expressed as xH={ xh | h ∈ H } for any x∈ G. The element x is called a representation of the coset.
Similarly, a right coset of H in G is a subset that may be expressed as Hx= {hx | h ∈H } , for any x∈G.
Thus complexes xH andHx are called respectively a left coset and a right coset.
If the group operation is additive (+) then a left coset is denoted as x + H={x+h | h
∈H} and a right coset is denoted by H + x = {h+x | h ∈ H}

Normal SubGroup
Let G be a group. A subgroup H of G is said to be a normal subgroup of G if for allh∈ H and x∈ G, x
h x-1∈ H
If x H x-1 = {x h x-1| h ∈ H} then H is normal in G if and only if xH x-1⊆H, ∀ x∈ G
Statement: If G is an abelian group, then every subgroup H of G is normal in G.
Proof: Let any h∈ H, x∈ G, thenx h x-1= x (h x-1)
x h x-1= (x x-1) hx h x-1 = e h
x h x-1 = h∈ H
Hence H is normal subgroup of G.

Group Homomorphism:
A homomorphism is a mapping f: G→ G' such that f (xy) =f(x) f(y), ∀ x, y ∈ G. The mapping f
preserves the group operation although the binary operations of the group G and G' are different.
Above condition is called the homomorphism condition.

Kernel of Homomorphism: - The Kernel of a homomorphism f from a group G to a group G' with
identity e' is the set {x∈ G | f(x) =e'}
The kernel of f is denoted by Ker f.
If f: G→G' is a homomorphism of G intoG', then the image set of f is the range, denoted by f (G), of
the map f. Thus
Im (f) = f (G) = {f(x)∈ G'| x ∈G}
If f (G) =G', then G' is called a homomorphic image of G.Note: - A group homomorphism

Isomorphism:
Let (G1,*) and (G2,0) be two algebraic system, where * and 0 both are binary operations. The
systems (G1,*) and (G2,0) are said to be isomorphic if there existsan isomorphic mapping f: G1→G2
When two algebraic systems are isomorphic, the systems are structurally equivalent and one can
be obtained from another by simply remaining theelements and operation.
Example: Let (A1,*) and (A2,⊡) be the two algebraic systems as shown in fig.Determine whether the
two algebraic systems are isomorphic.

49
Solution: The two algebraic system (A1,*) and (A2,⊡) are isomorphic and (A2,⊡) is an isomorphic
image of A1, such that
f( a)=1
f (b)=w f (c)= w2
Automorphism:
Let (G1,*) and (G2,0) be two algebraic system, where * and 0 both are binary operations on G1 and
G2 respectively. Then an isomorphism from (G1,*) to (G2,0) iscalled an automorphism if G1= G2

Rings:
An algebraic system (R, +,) where R is a set with two arbitrary binary operations + and ., is called
aring if it satisfies the following conditions
1. (R, +) is an abelian group.
2. (R,·) is a semigroup.
3. The multiplication operation, is distributive over the addition operation +i.e.,
a (b+c)=ab +ac and (b+c)a = ba + ca for all a, b, c ∈ R.

Example1: Consider M be the set of all matrices of the type over integers under matrix
addition and matrix multiplication. Thus M form a ring.
Example2: The set Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8} under the operation addition and multiplication
modulo 9 forms a ring.

Types of Rings:
1. Commutative Rings: A ring (R, +,) is called a commutative ring if it holds the commutative law
under the operation of multiplication i.e., a. b = b. a, for every a,b∈ R
Example1: Consider a set E of all even integers under the operation of addition and
multiplication. The set E forms a commutative ring.

2. Ring with Unity: A ring (R, +,) is called a ring with unity, if it has a multiplicativeidentity i.e,
Example: Consider a set M of all 2 x 2 matrices over integers under matrix multiplication and

matrix addition. The set M forms a ring with unity .

3. Ring with Zero Divisions: If a.b=0, where a and b are any two non-zero elements of R in the ring
(R, +) then a and b are called divisions of zero and thering (R, +) is called ring with zero division.

4. Rings without Zero Division: An algebraic system (R, +) where R is a set with two arbitrary
binary operation + and is called a ring without divisors of zero if forevery a, b ∈R, we have a.b≠0
⟹a≠0 and b ≠0

SubRings:
A subset A of a ring (R, +) is called a subring of R, if it satisfies following conditions: (A, +) is a
subgroup of the group (R,+)
A is closed under the multiplication operation i.e., a.b ∈A,for every a,b ∈A.
Example: The ring (I, +) of integers is a subring of ring (R, +) of real numbers.
Note:
1. If R is any ring then {0} and R are subrings of R.
50
2. Sum of two subrings may not be a subring.
3. Intersection of subring is a subring.

SemiGroup
Let us consider, an algebraic system (A, *), where * is a binary operation on A. Then, the system (A,
*) is said to be semi-group if it satisfies the following properties:
1. The operation * is a closed operation on set A.
2. The operation * is an associative operation.

Example: Consider an algebraic system (A, *), where A = {1, 3, 5, 7, 9 }, the set
of positive odd integers and * is a binary operation means multiplication. Determine whether (A, *)
is a semi-group.
Solution: Closure Property: The operation * is a closed operation because multiplication of two +ve
odd integers is a +ve odd number.

Associative Property: The operation * is an associative operation on set A. Since every a, b, c ∈ A,

we have
(a * b) * c = a * (b * c)
Hence, the algebraic system (A, *), is a semigroup.

Subsemigroup:
Consider a semigroup (A, *) and let B ⊆ A. Then the system (B, *) is called asubsemigroup if the set
B is closed under the operation *.
Example: Consider a semigroup (N, +), where N is the set of all natural numbersand + is an addition
operation. The algebraic system (E, +) is a subsemigroup of (N, +), where E is a set of +ve even
integers.

Free Semigroup:
Consider a non empty set A = {a1,a2, an}.
Now, A* is the set of all finite sequences of elements of A, i.e., A* consist of all words that can be
formed from the alphabet of A.
If α,β,and,γ are any elements of A*, then α,(β. γ)=( α.β).γ.
Here ° is a concatenation operation, which is an associative operation as shownabove.
Thus (A*,°) is a semigroup. This semigroup (A*,°) is called the free semigroupgenerated by set A.

Product of Semigroup:
Theorem: If (S1,*)and (S2,*) are semigroups, then (S1 x S2*) is a semigroup, where
* defined by (s1',s2')*( s1'',s2'')=(s1'*s1'',s2'*s2'' ).
Proof: The semigroup S1 x S2 is closed under the operation *.Associativity of *.Let a, b, c ∈ S1 x S2
So, a * (b * c) = (a1,a2 )*((b1,b2)*(c1,c2))
= (a1,a2 )*(b1 *1 c1,b2 *2 c2)
= (a1 *1 (b1 *1 c1 ),a2 *2 (b2 *2 c2)
= ((a1 *1 b1) *1*1,( a2 *2 b2) *2 c2)
= (a1 *1 b1,a2 *2 b2)*( c1,c2)
= ((a1,a2)*( b1,b2))*( c1,c2)
= (a * b) * c.
Since * is closed and associative. Hence, S1 x S2 is a semigroup.

51
Monoid:
Let us consider an algebraic system (A, o), where o is a binary operation on A. Then the system (A,
o) is said to be a monoid if it satisfies the following properties:
1. The operation o is a closed operation on set A.
2. The operation o is an associative operation.
3. There exists an identity element, i.e., the operation o.

Bridge (Cut Edges): Consider a graph G=(V, E).A bridge for a graph G, is an edge esuch that G-e has
more connected components than G or disconnected.
Example: Consider the graph shown in fig. Determine the subgraphs

(i) G-e1 (ii) G-e3 (iii) G-e4

Solution:
1. The subgraph G-e1 is shown in fig
2. The subgraph G-e3 is shown in fig
3. The subgraph G-e4 is shown in fig

52
Types of Graphs:
1. Null Graph: A null graph is defined as a graph which consists only the isolatedvertices.
Example: The graph shown in fig is a null graph, and the vertices are isolatedvertices.

2. Undirected Graphs: An Undirected graph G consists of a set of vertices, V and a set of edge E.
The edge set contains the unordered pair of vertices. If (u, v)∈E then we say u and v are
connected by an edge where u and v are vertices in the set V.

Example: Let V = {1, 2, 3, 4} and E = {(1, 2), (1, 4), (3, 4), (2, 3)}.Draw the graph.
Solution: The graph can be drawn in several ways.Two of which are as follows:

3. Multigraph: If in a graph multiple edges between the same set of vertices are allowed, it is
known as Multigraph. In other words, it is a graph having at least oneloop or multiple edges.

53
4. Directed Graphs: A directed graph or digraph G is defined as an unordered pair(V, E), where V is
the set of points called vertices and E is the set of edges. Each edge in the graph G is assigned
a direction and is identified with an ordered pair (u, v), where u is the initial vertex, and v is the
end vertex.

Example: Consider the graph G = (V, E) as shown in fig. Determine the vertex set and edge set of
graph G

.
Solution: The vertex and edge set of graph G =(V, E) is as follow
G={{1,2,3},{(1,2),(2,1),(2,2),(2,3),(1,3)}}.
5. Undirected Complete Graph: An undirected complete graph G=(V,E) of n vertices is a
graph in which each vertex is connected to every other vertex i.e.,and edge exist between every pair
of distinct vertices. It is denoted by Kn.A
complete graph with n vertices will have edges.

Example: Draw Undirected Complete Graphs k4and k6.

Solution: The undirected complete graph of k4 is shown in fig1 and that of k6isshown in fig2.

54
6. Connected and Disconnected Graph:
Connected Graph: A graph is called connected if there is a path from any vertex uto v or vice-versa.
Disconnected Graph: A graph is called disconnected if there is no path between any two of its
vertices.
Example: Consider the graph shown in fig. Determine whether the graphs are
(a) Disconnected Graph
(b) Connected Graph.
Also, write their connected components.

Solution:
(i) The graph is shown in fig is a Disconnected Graph, and its connectedcomponents are
{V1,V2,V3,V4},{V5,V6,V7,V8} and {V9,V10}.
(ii) The graph shown in fig is a Disconnected Graph and its connected componentsare
{V1,V2},{V3,V4},{V5,V6},{V7,V8},{V9,V10}and {V11,V12}.

55
(iii) The graph shown in fig is a connected graph

7. Connected Component: A subgraph of graph G is called the connected component of G, if it is

not contained in any bigger subgraph of G, which isconnected. It is defined by listing its vertices.
Example: Consider the graph shown in fig. Determine its connected components.

Solution: The connected components of this graph is {a, b, c}, {d, e, f}, {g, h ,i} and {j}.
8. Directed Complete Graph: A directed complete graph G = (V, E) on n vertices isa graph in which
each vertex is connected to every other vertex by an arrow. It is denoted by Kn.
Example: Draw directed complete graphs K3 and K5.
Solution: Place the number of vertices at the appropriate place and then draw an arrow from each
56
vertex to every other vertex as shown in fig:

9. Complementary Graph: The complement of a graph G is defined to be a graph which has the
same number of vertices as in graph G and has two vertices connected if and only they are not
related in the graph.
Example: Consider the graph G shown in fig. Find the complement of this graph.

Solution: The complement of the above graph is shown in Fig:

57
10. Labeled Graphs: A graph G=(V, E) is called a labeled graph if its edges are labeled with some
name or data. So, we can write these labels in place of anordered pair in its edges set.
Example: The graph shown in fig is labeled graphs.
G= {{a, b, c, d}, {e1,e2,e3,e4}}

11. Weighted Graphs: A graph G=(V, E) is called a weighted graph if each edge of graph G is
assigned a positive number w called the weight of the edge e.
Example: The graph shown in fig is a Weighted Graph.

58
Degree of a Vertex
The degree of a vertex v in a graph G, written deg (v), is equal to the number ofedges in G which
contain v, that is, which are incident on v.

Bipartite Graphs
DEFINITION: A simple graph G is called bipartite if its vertex set V can be partitioned into two
disjoint sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2.

• C6 is bipartite, as shown in Figure, because its vertex set can be partitioned into the two sets V1
and V2.
• V1 = {v1, v3, v5} and V2 = {v2, v4, v6}, and every edge of C6 connects a vertex in V1 and a vertex in
V2.

Complete Bipartite Graphs: The complete bipartite graphs K2,3, K3, 3, and are displayed in
Figure

K2, 3 K3, 3

New Graphs from Old

DEFINITION: A sub-graph of a graph G = (V, E) is a graph.
H = (W, F), where W ⊆ V and F ⊆ E. A sub-graph H of G is a proper sub-graph of Gif H = G.

DEFINITION: Let G = (V, E) be a simple graph.

The sub-graph induced by a subset W of the vertex set V is the graph (W, F), where the edge set F
contains an edge in E if and only if both endpoints of this edge are in W.
The graph G is a sub-graph of K5. If we add the edge connecting c and e to G, W ={a, b, c, e}.

A Sub-graph of K5

DEFINITION
The union of two simple graphs G1 = (V1, E1) G2 = (V2, E2) is the simple graph with vertex set V1 𝖴 V2
and edge set E1 𝖴 E2. The union of G1 and G2 is denoted by G1 𝖴 G2.

EXAMPLE: Find the union of the graphs G1 and G2.

Solution: The vertex set of the union G1 𝖴 G2 is the union of the two vertex sets
as: {a, b, c, d, e, f}.

59
FIGURE (a) The Simple Graphs G1 and G2; (b) Their Union G1 𝖴 G2.
Isomorphism of Graphs
The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are isomorphic.
• If there exists a one-to-one and onto function f from V1 to V2 with theproperty that a, b
are adjacent in G1.
• If and only if f (a) and f (b) are adjacent in G2, for all a, b in V1. Such a function f is
called an isomorphism.
• Two simple graphs that are not isomorphic are called non-isomorphic.

Example: Show that the graphs G = (V, E) and H = (W, F), displayed in figure, areisomorphic.

Paths
A path is a sequence of edges that begins at a vertex of a graph and travels fromvertex to vertex
along edges of the graph.
• Let n be a nonnegative integer and G an undirected graph.
• A path of length n from u to v in G is a sequence of n edges e1,...,e n of G.
• The path is a circuit if it begins and ends at the same vertex, that is, if u = v, and has length
greater than zero.

Connectedness in Undirected Graphs

• An undirected graph is called connected if there is a path between every pair of distinct
vertices of the graph.
• An undirected graph that is not connected is called disconnected.

60
Connectedness in Directed Graphs
A directed graph is strongly connected if there is a path from a to b and from b to a whenever a
and b are vertices in the graph.
A directed graph is weakly connected if there is a path between every two vertices in the
underlying undirected graph.
FIGURE: The directed graphs G and H.
Figure: The Directed Graphs G and H

Paths and Isomorphism

A path in a multi-graph G consists of an alternating sequence of vertices and edges of the form v0,
e1, v1, e2, v2 ... e n−1, v n−1, e n, v n , where each edge e i contains the vertices v i−1 and vi (which appear
on the sides of e i in the sequence). The number n of edges is called the length of the path. The
path is said to be closed if v 0 = v n. Otherwise, we say the path is from v 0, to v n or between v 0 and v
n, or connects v0 to v n.

Isomorphic Graphs
Graphs G (V, E) and G (V ∗, E∗) are said to be isomorphic if there exists a one-to- one
correspondence f : V → V ∗ such that {u, v} is an edge of G if and only if {f (u), f (v)} is an edge of
G∗.
Figure: A and T are isomorphic graphs

Theorem: There is a path from a vertex u to a vertex v if and only if there exists asimple path from
u to v.
Connectivity, Connected Components

61
 A graph G is connected if there is a path between any two of its vertices.

The graph in Figure (a) is connected, but the graph in Figure (b) is not connected since, for
example, there is no path between vertices D and E.
• The graph G in Fig. 8-8(b) has three connected components, the sub-graphs induced by the
vertex sets {A, C, D}, {E, F}, and {B}.
• The vertex B in Figure (b) is called an isolated vertex since B does not belong to any edge or,
in other words, deg (B) = 0. Therefore, as noted, B itself forms a connected component of
the graph.

Euler and Hamilton Paths

DEFINITION 1 An Euler circuit in a graph G is a simple circuit containing every edge of G. An
Euler path in G is a simple path containing every edge of G.
C

Figure: Multi-graph Model of the Town of Konigsberg

THEOREM 1: A connected multi-graph with at least two vertices has an Euler circuit if and only if
each of its vertices has even degree.
THEOREM 2: A connected multi-graph has an Euler path but not an Euler circuit if and only if it has
exactly two vertices of odd degree.

Figure: Two Undirected Graph

62
Hamilton Paths and Circuits
DEFINITION: A simple path in a graph G that passes through every vertex exactly once is called a
Hamilton path, and a simple circuit in a graph G that passes through every vertex exactly once is
called a Hamilton circuit.

That is, the simple path x0, x1...x n−1, x n in the graph G = (V, E) is a Hamilton path if V = {x0, x1,...,x
n−1, x n} and xi = x j for 0 ≤ i<j ≤ n, and the simple circuit x 0, x1,...,x n−1, x n, x0 (with n > 0) is a Hamilton
circuit if x0, x1,...,x n−1, x n is a Hamilton path.
AB

Labeled and Weighted graphs

A graph G is called a labeled graph if its edges and/or vertices are assigned data of one kind or
another. In particular, G is called a weighted graph if each edge e of G is assigned a non negative
number w (e) called the weight or length of v.

The weight (or length) of a path in such a weighted graph G is defined to be the sum of the weights
of the edges in the path. One important problem in graph theory is to find a shortest path, that
is, a path of minimum weight (length),

between any two given vertices. The length of a shortest path between P and Q in figure is 14; one
such path is (P, A1, A2, A5, A3, A6, Q)

Complete, Regular, and Bipartite graphs

There are many different types of graphs. This section considers three of them: complete, regular,
and bipartite graphs.
63
Complete Graphs
A graph G is said to be complete if every vertex in G is connected to every other vertex in G. Thus a
complete graph G must be connected. The complete graph with n vertices is denoted by Kn. Figure
shows the graphs K1 through K4.

Regular Graphs
A graph G is regular of degree k or k-regular if every vertex has degree k. In other words, a graph is
regular if every vertex has the same degree.

Bipartite Graphs
A graph G is said to be bipartite if its vertices V can be partitioned into two subsets M and N such
that each edge of G connects a vertex of M to a vertex of N.

By a complete bipartite graph, we mean that each vertex of M is connected to each vertex of N; this
graph is denoted by K m, n where m is the number of vertices in M and n is the number of vertices in
N, and, for standardization, we will assume m ≤ n.

Figure shows the graphs K2, 3,

K3, 3, and K2, 4, clearly the graph K m, n has m n edges.

Tree Graphs
• A graph T is called a tree if T is connected and T has no cycles. Examples of trees are
shown in Figure.
• A forest G is a graph with no cycles; hence the connected components of a forest G are
trees.
• A graph without cycles is said to be cycle-free. The tree consisting of a single vertex
64
 with no edges is called the degenerate tree.

Theorem: Let G be a graph with n > 1 vertices. Then the following are equivalent:
(i) G is a tree.
(ii) G is a cycle-free and has n − 1 edges.
(iii) G is connected and has n − 1 edges.

This theorem also tells us that a finite tree T with n vertices must have n − 1 edges. For
example, the tree in
Fig. 8-17(a) has 9 vertices and 8 edges, and the tree in Figure has 13 vertices and12 edges.

Spanning Tree
A subgraph T of a connected graph G is called spanning tree of G if T is a tree and T include all
vertices of G.

Minimum Spanning Tree:

Suppose G is a connected weight graph i.e., each edge of G is assigned a non- negative number
called the weight of edge, then any spanning tree T of G is assigned a total weight obtained by
adding the weight of the edge in T.
A minimum spanning tree of G is a tree whose total weight is as small as possible.

Kruskal's Algorithm to find a minimum spanning tree: This algorithm finds the minimum spanning
tree T of the given connected weighted graph G.
1. Input the given connected weighted graph G with n vertices whoseminimum spanning tree T, we
want to find.
2. Order all the edges of the graph G according to increasing weights.
3. Initialize T with all vertices but do include an edge.
4. Add each of the graphs G in T which does not form a cycle until n-1 edgesare added.

Example1: Determine the minimum spanning tree of the weighted graph shownin fig:

65
Solution: Using kruskal's algorithm arrange all the edges of the weighted graph in increasing order
and initialize spanning tree T with all the six vertices of G. Now start adding the edges of G in T
which do not form a cycle and having minimum weights until five edges are not added as there are
six vertices.
Edges Weights Added or Not
(B, E) 2 Added
(C, D) 3 Added
(A, D) 4 Added
(C, F) 4 Added
(B, C) 5 Added
(E, F) 5 Not added
(A, B) 6 Not added
(D, E) 6 Not added
(A, F) 7 Not added

Step1:

Step2:

66
Step3:

Step4:

Step5:

Step6: Edge (A, B), (D, E) and (E, F) are discarded because they will form the cyclein a graph.
So, the minimum spanning tree form in step 5 is output, and the total cost is 18.

67
Example2: Find all the spanning tree of graph G and find which is the minimal spanning tree of G
shown in fig:

Solution: There are total three spanning trees of the graph G which are shown infig:

68
To find the minimum spanning tree, use the KRUSKAL’S ALGORITHM. The minimalspanning tree is
shown in fig:
Edges Weights Added or Not
(E, F) 1 Added
(A, B) 2 Added
(C, D) 2 Added
(B, C) 3 Added
(D, E) 3 Added
(B, D) 6 Not Added

The first one is the minimum spanning having the minimum weight = 11.

Planner Graphs
A graph or multi-graph which can be drawn in the plane so that its edges do not cross is said to
be planar.

69
A

The complete graph with four vertices K4 is usually pictured with crossing edgesas in Figure A, it
can also be drawn with non-crossing edges as in Figure B; hence K4 is planar. Tree graphs form an
important class of planar graphs.

Maps, Regions
A particular planar representation of a finite planar multi-graph is called a map. The map is
connected if the underlying multi-graph is connected. A given map divides the plane into various
regions.
Non-planar Graphs, Kuratowski’s Theorem
1. Consider first the utility graph; that is, three houses A1, A 2 and A3 are to be connected to outlets
for water, gas and electricity, B1, B2 and B3, as in Figure.
2. Observe that this is the graph K3, 3 and it has p = 6 vertices and q = 9 edges.

• Suppose the graph is planar. By Euler’s formula a planar representation has r = 5 regions.
Observe that no three vertices are connected to each other; hence the degree of each region
must be 4 or more and so the sum of the degrees of the regions must be 20 or more.
• Consider next the star graph in Figure. This is the complete graph K5 on p = 5 vertices and has q
= 10 edges.10 = q ≤ 3p − 6 = 15 − 6 = 9 which is impossible. Thus K5 is non-planar.

Graph Coloring
A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two
adjacent vertices are assigned the same color.

70
FIGURE 2 Dual Graphs of the Maps in Figure 1
DEFINITION: The chromatic number of a graph is the least number of colors needed for a coloring
of this graph. The chromatic number of a graph G is denoted by χ (G).

THEOREM 1 THE FOUR COLOR THEOREM The chromatic number of a planar graph is no greater
than four.

Rooted trees
• A rooted tree T is a tree graph with a designated vertex r called the root of the tree.
• Consider a rooted tree T with root r. The length of the path from the root r to any vertex v is
called the level (or depth) of v, and the maximum vertex level is called the depth of the tree.
• Those vertices with degree 1, other than the root r, are called the leaves of T, and a directed
path from a vertex to a leaf is called a branch.
• The tree has five leaves, d, f, h, i, and j. Observe that: level (a) = 1, level (f) = 2, level (j) =
3. Furthermore, the depth of the tree is 3.

• The fact that a rooted tree T gives a direction to the edges means that we can give a
precedence relationship between the vertices.
• Specifically, we will say that a vertex u precedes a vertex v or that v follows u if there is a
(directed) path from v to u.
• In particular, we say that v immediately follows u if (u, v) is an edge, that is,if v follows u and
v is adjacent to u.

EXAMPLE
Suppose Marc and Erik are playing a tennis tournament such that the first person to win two
games in a row or who wins a total of three games wins the tournament. Find the number of ways

71
the tournament can proceed.

Solution: The rooted tree in Figure (b) shows the various ways that the tournament could proceed.
There are 10 leaves which correspond to the 10 ways that the tournament can occur:
MM, MEMM, MEMEM, MEMEE, MEE, EMM, EMEMM, EMEME, EMEE, EE
Specifically, the path from the root to the leaf describes who won which games in the particular
tournament.

Ordered Rooted Trees

Consider a rooted tree T in which the edges leaving each vertex are ordered. Then we have the
concept of an ordered rooted tree.
Boolean algebra Boolean Functions
Boolean algebra provides the operations and the rules for working with the set {0,
1}.The complement of an element, denoted with a bar, is defined by bar 0 = 1andbar 1 = 0.
The Boolean sum, denoted by + or by OR, has the following values:1+ 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 +
0=0
The Boolean product, denoted by · or by AND, has the following values:1· 1 = 1, 1 · 0 = 0, 0 · 1 = 0, 0 ·
0=0

EXAMPLE 1 Find the value of 1 · 0 + (0 + 1).

Solution: 1 · 0 + (0 + 1) = 0 + 1 = 0 + 0 = 0.
EXAMPLE 2 Translate 1 · 0 + (0 + 1) = 0, the equality into a logical equivalence.

Solution:
• Translate each 1 into a T, 0 into an F,
• Boolean sum into a disjunction, each Boolean product into a conjunction, and each
complementation into a negation.
(T 𝖠 F) ∨ ¬ (T ∨ F) ≡ F

Boolean Expressions and Boolean Functions

• Let B = {0, 1}. Then B n = {(x1, x2... x n) | xi ∈ B for 1 ≤ i ≤ n} is the set of all possible n-
tuples of 0s and 1s.
• The variable x is called a Boolean variable if it assumes values only from B, that is, if its
only possible values are 0 and 1.
• A function from B n to B is called a Boolean function of degree n.
EXAMPLE: The function F (x, y) = x y from the set of ordered pairs of Booleanvariables to the
set {0, 1} is a Boolean function of degree 2 with F (1, 1) = 0, F (1,
0) = 1, F (0, 1) = 0, and F (0, 0) = 0.

We display these values of F in Table.

x y F(x, y)
1 1 0
1 0 1
0 1 0
0 0 0

72
The Boolean expressions in the variables x1, x2...x n are defined recursively as 0, 1, x1, x 2...x n are
Boolean expressions;

If E1 and E2 are Boolean expressions, then E1, (E1E2), and (E1 + E2) are Booleanexpressions.

Identities of Boolean algebra

Law of the double complement: x`` = x
Idempotent laws: x + x = x, x · x = x Identity laws: x + 0 = x, x · 1 = x Domination laws: x + 1 = 1, x · 0
= 0 Commutative laws: x + y = y + x, x y = y x
Associative laws: x + (y + z) = (x + y) + z, x (y z) = (x y)z Distributive laws: x + y z = (x + y)(x + z), x(y
+ z) = x y + x zDe Morgan’s laws: (x y) = x + y, (x + y) = x y
Absorption laws: x + x y = x, x (x + y) = xUnit property: x + x = 1
Zero property x x = 0

EXAMPLE: Prove the absorption law x(x + y) = x using the other identities ofBoolean algebra.
Solution: x(x + y) = (x + 0) (x + y) Identity law for the Boolean sum
= x + 0 · y Distributive law
= x + y · 0 Commutative law
= x + 0 Domination law
= x Identity law

Duality
The dual of a Boolean expression is obtained by interchanging Boolean sums and Boolean
products and interchanging 0s and 1s.
EXAMPLE: Find the duals of x(y + 0) and x · 1 + (y + z).
Solution: Interchanging · signs and + signs and interchanging 0s and 1s. The duals are x + (y · 1)
and (x + 0) (y z), respectively.

The Abstract Definition of a Boolean Algebra

DEFINITION: A Boolean Algebra is a set B with two binary operations ∨ and 𝖠, elements 0 and 1,
and a unary operation such that these properties hold for all x, y, and z in B:
Identity laws: x ∨ 0 = x, x 𝖠 1 = x Complement laws: x ∨ x = 1, x 𝖠 x = 0
Associative laws: (x ∨ y) ∨ z = x ∨ (y ∨ z), (x 𝖠 y) 𝖠 z = x 𝖠 (y 𝖠 z)Commutative laws: x ∨ y = y ∨ x, x 𝖠
y=y𝖠x
Distributive laws: x ∨ (y 𝖠 z) = (x ∨ y) 𝖠 (x ∨ z), x 𝖠 (y ∨ z) = (x 𝖠 y) ∨ (x 𝖠 z)

Sum-of-Products Expansions
EXAMPLE: Find Boolean expressions that represent the functions F (x, y, z ) and G(x, y, z).
x y z F G

73
 1 1 1 0 0
1 1 0 0 1
1 0 1 1 0
1 0 0 0 0
0 1 1 0 0
0 1 0 0 1
0 0 1 0 0
0 0 0 0 0

Solution: An expression that has the value 1 when x = z = 1 and y = 0, and the value 0 otherwise, is
needed to represent F.
To represent G, we need an expression that equals 1 when x = y = 1 and z = 0, or x
= z = 0 and y = 1.

DEFINITION: A literal is a Boolean variable or its complement.

A Min-term of the Boolean variables x1, x2,..., x n is a Boolean product y1y2 ··· y n, where y i = xi or y i =
x i. Hence, a min-term is a product of n literals, with one literal for each variable.
EXAMPLE: Find a min-term that equals 1 if x1 = x3 = 0 and x2 = x4 = x5 = 1, and equals 0 otherwise.
Solution: The midterm x1x2x3x4x5 has the correct set of values.

Functional Completeness
• Each min-term is the Boolean product of Boolean variables or their complements.
• Shows that every Boolean function can be represented using the Boolean operators ·, +, and
−. Because every Boolean function can be represented using these operators we say that
the set {·, +, −} is functionally complete.
We can eliminate all Boolean sums using the identity x + y = x y.

Optimization
Linear Programming
• Problems which seek to maximize (or, minimize) profit (or, cost) form ageneral class of
problems called optimization problems.
• A special but a very important class of optimization is linear programmingproblem.
A linear programming (LP) problem is an optimization problem that can bewritten

Maximize: c x
Subject to: Ax ≤ b
Where A is a given q × n matrix, c is a given row vector of length n, and b is a givencolumn vector of
length q.

Linear programming problem

A linear programming problem is one that is concerned with finding the optimal value (maximum
or minimum) of a linear function of several variables (called objective function) subject to the
conditions that:
1. The variables are non-negative and satisfy a set of linear inequalities (called linear constraints).
2. Variables are sometimes called decision variables and are non-negative.

74
Objective function: Linear function Z = ax+ by, where a, b are constants, which has to be
maximized or minimized is called a linear objective function.
Constraints: The linear inequalities or equations or restrictions on the variables of a linear
programming problem are called constraints.

Optimization problem: A problem which seeks to maximize or minimize a linear function subject to
certain constraints as determined by a set of linear inequalitiesis called an Optimization problem.
The common region determined by all the constraints including the non-negative constraints x ≥ 0,
y ≥ 0 of a linear programming problem is called feasible region (or solution region) for the
problem.
1. Points within and on the boundary of the feasible region represent feasible solutions of the
constraints.
2. Any point outside the feasible region is an infeasible solution.Optimal Solution
Any point in the feasible region that gives the optimal value (maximum or minimum) of the
objective function is called an optimal solution.

Theorem 1 Let R be the feasible region (Convex Polygon) for a linear programming problem and
let Z = ax+ by be the Objective function. When Z has an optimal value (maximum or minimum),
where the variables x and y are subject to constraints described by linear inequalities, this optimal
value must occur at a corner point (vertex) of the feasible region.

Theorem 2 Let R be the feasible region for a linear programming problem and letZ = ax+ by be the
Objective function. If R is bounded, then the objective function Z has both a maximum and a
minimum value on R and each of these occurs at a corner point (vertex) of R. A corner point of a
feasible region is a point in the region which is the intersection of two boundary lines.

X ≥ 0 ConstraintsY ≥ 0

Bounded and Unbounded

A feasible region of a system of linear inequalities is said to be bounded.
• If it can be enclosed within a circle. Otherwise, it is called unbounded.
• Unbounded means that the feasible region does not extend indefinitely inany direction.

Corner Point Method (Steps)

1. Find the feasible region of the linear programming problem and determine its corner point
either by inspection or by solving the two equations of the lines intersecting at that point.
2. Evaluate the objective function Z = ax+ by at each corner point. Let M and m, respectively
denote the largest and smallest values of these points.
3. When the feasible region is bounded, M and m are the maximum and minimum value of Z.
4. In case feasible region is unbounded, we have:
(a) M is the maximum value of Z, if the open half plane determined by ax + by > M has no point in
common with the feasible region. Otherwise, Z has no maximum value.
(b) Similarly, m is the minimum value of Z, if the open half plane determined by ax + by > M has no
75
 point in common with the feasible region. Otherwise, Z has no minimum value.

Corner Point Solution

The optimal solution to LPP, if it exists, occurs at the corners of the feasibleregion.
The method includes the following steps:
• Step 1: Find the feasible region of the LPP.
• Step 2: Find the co-ordinates of each vertex of the feasible region. These co-ordinates can be
obtained from the graph or by solving the equation of the line s.
• Step 3: At each vertex (corner point) compute the value of the objective function.
• Step 4: Identify the corner point at which the value of the objective function maximum (or
minimum depending on the LP).
• The co-ordinates of this vertex are the optimal solution and the value of Z isthe optimal value.

Different types of linear programmingExample: Maximize y

-x + y ≤ 1 3x +2y ≤ 12
2x +3y ≤ 12x, y ≥ 0
• The feasible integer points are shown in red, and the red dashed lines indicate their convex hull,
which is the smallest convex polyhedron that contains all of these points.
• The blue lines together with the coordinate axes define the polyhedron of the LP relaxation,
which is given by the inequalities without theintegrality constraint.
• The goal of the optimization is to move the black dotted line as far upward while still touching
the polyhedron. The optimal solutions of the integer problem are the points and which both
have an objective value of 2.
• The unique optimum of the relaxation is with objective value of 2.8. If the solution of the
relaxation is rounded to the nearest integers, it is notfeasible for the ILP.

LINEAR PROGRAMMING – SIMPLEX METHOD

• If the linear programming problem has larger number of variables, the suitable method for
solving is Simplex Method.
The Simplex method also helps the decision maker/manager to identify thefollowing:
➢ Redundant Constraints
➢ Multiple Solutions
76
➢ Unbounded Solution
➢ Infeasible Problem

Basics of Simplex Method

The basic of simplex method is explained with the following linear programmingproblem.
Example:
Maximize
60x1 + 70x2
Subject to:
2x1 + x2 ≤ 300
3x1 + 4x2 ≤ 509
4x1 + 7x2 ≤ 812
x1, x2 ≥ 0
Solution: First we introduce the variables s3, s4, s5 ≥ 0 So that the constraints becomes equations,
thus
2x1 + x2 + s3 = 300
3x1 + 4x2 + s4 = 509
4x1 + 7x2 +s5 = 812
Corresponding to the three constraints, the variables s3, s4, s5 are called as slack variables.
There are two types of solutions they are basic and basic feasible, which are discussed as
follows:

Basic Solution
• We may equate any two variables to zero in the above system of equations, and then the
system will have three variables.
• Thus, if this system of three equations with three variables is solvable such a solution is
called as basic solution.
• The variables s3, s4, and s5 are known as basic variables where as the variables x1,
x2 are known as non-basic variables.

Basic Feasible Solution

• A basic solution of a linear programming problem is called as basic feasiblesolutions if it is
feasible it means all the variables are non-negative.
• The solution s3=300, s4=509 and s5=812 is a basic feasible solution.

Simplex Method Computation

Consider the following linear programming problemMaximize
60x1 + 70x2
Subject to:
2x1 + x2 + s3 = 300
3x1 + 9x2 + s4 = 509
4x1 + 7x2 +s5 = 812
x1, x2, s3, s4, s5 ≥ 0
The profit Z = 60x1 + 70x2 i.e. Maximize 60x1 + 70x2
The standard form can be summarized in a compact table form as

CB Basic CJ 60 70 0 0 0

77
 Variables XB x1 x2 s3 s4 s5
0 s3 300 2 1 1 0 0
0 s4 509 3 4 0 1 0
0 s5 812 4 7 0 0 1

Z -60 -70 0 0 0 0

Consider the first equation 2x1 + x2 + s3 = 3002x1 + s3 = 300 – x2 (x1 = 0, s3 ≥ 0)

300 - x2 ≥ 0 i.e. x2 ≤ 300
Second equation: 3x1 + 9x2 + s4 = 5093x1 + s4 = 509 - 4x2 (x1 = 0, s4 ≥ 0)
509 – 9x2 ≥ 0
So, x 2 ≥ 509/9
Third equation: 4x1 + 7x2 +s5 = 8124x1 + s5 = 812 - 7x2 (x1 = 0, s5 ≥ 0)
812 - 7x2 ≥ 0
So, x2 ≥ 812/7
Therefore the three equations: x2 ≤ 300, x 2 ≥ 509/9, x2 ≥ 812/7Thus x2=Min (x2 ≤ 300, x 2 ≥ 509/9, x2 ≥
812/7)
So, x2=Min (x2 ≤ 300/1, x 2 ≥ 509/9, x2 ≥ 812/7) = 116
Therefore x2 = 116, if x2=116, you may be note from the third equation7x2 +s5 = 812 i.e. s5=0 So, x2 =
812/7 = 116
Thus, the variable s5 becomes non-basic in the next iteration.The other two basic variables are
S3=300 - x2 = 184 S4=509 - 4*116 = 45

Using the following rules the Table 2 is computed from the Table 1.
(i) The revised basic variables are s3, s4 and x2. Accordingly, we make CB1=0, CB2=0 and CB3=70.
(ii) As x2 is the incoming basic variable we make the coefficient of x2 one by dividing each element
of row-3 by 7. Thus the numerical value of the element corresponding to x1 is 4/7,
corresponding to s5 is 1/7 in Table 2.
(iii) The incoming basic variable should appear only in the third row. So we multiply the third-row of
Table 2 by 1 and subtract it from the first-row of Table 1 element by element. Thus the element
corresponding to x2 in the first-row of Table 2 is 0.
Therefore the element corresponding to x1 is 2-1*4/7=10/7 and the element corresponding to s5
is 0-1*1/7=-1/7
In this way we obtain the elements of the first and the second row in Table 2. In Table 2 the
numerical values can also be calculated in a similar way.

CB Basic CJ 60 70 0 0 0
Variables XB x1 x2 s3 s4 s5
0 s3 184 10/7 1 1 0 -1/7
0 s4 45 5/7 4 0 1 -4/7
0 s5 116 4/7 7 0 0 1/7

Zj–Cj -140/7 0 0 0 70/7

z1 - c1 = 10/7*0 + 5/7*0 + 70*4/7 - 60 = -140/7z5 – c5 = -1/7*0 - 4/7*0 + 1/7*70 - 0 = 70/7

78
(i) Now we apply rule (1) to Table 2. Here the only negative zj-c j is z1-c1 = -140/7
Hence x1 should become a basic variable at the next iteration.
(ii) This minimum occurs corresponding to s4, it becomes a non basic variablein next iteration.

CB Basic Cj 60 70 0 0 0
Variables XB x1 x2 s3 s4 s5
0 s3 94 10/7 1 1 -2 1
0 s4 63 5/7 4 0 7/5 -4/5
0 s5 80 4/7 7 0 -4/5 3/5

Zj–Cj 0 0 0 28 -6

1. Now we apply rule (1) to Table 2. Here the only negative Z j-C j is z1-c1 = -140/7
2. We compute the minimum of the ratio
Min (180/10/7, 45/5/7, 116/4/7) = Min (644/5, 63, 203) = 63
This minimum occurs corresponding to s4; it becomes a non basic variablein next iteration.
1. z 5 – c5 < 0 should be made a basic variable in the next iteration.
2. Now compute the minimum ratiosMin (94/1, 80/3/5) = 94
Since y25 = -4/5 < 0, the corresponding ratio is not taken for comparison. The variable s3 becomes
non basic in the next iteration.

CB Basic CJ 60 70 0 0 0
Variables XB x1 x2 s3 s4 s5
0 s3 94 10/7 1 1 2 1
0 s4 691/5 5/7 4 4/5 -1/5 0
0 s5 118/5 4/7 7 -3/5 2/5 0

Zj–Cj 0 0 6 16 0

Thus, the objective function is maximized for x1 = 691/5 and x2=118/5 and themaximum value
of the objective function is 9944.

Key Terms
Basic Variable: Variable of a basic feasible solution has n non-negative value.
Non Basic Variable: Variable of a feasible solution has a value equal to zero.
Artificial Variable: A non-negative variable introduced to provide basic feasible solution and
initiate the simplex procedures.
Slack Variable: A variable corresponding to a ≤ type constraint is a non-negative variable
introduced to convert the inequalities into equations.
Surplus Variable: A variable corresponding to a ≥ type constraint is a non- negative variable
introduced to convert the constraint into equations.
Basic Solution: System of m-equation and n-variables i.e. m<n is a solution where at least n-m
variables are zero.
Basic Feasible Solution: System of m-equation and n-variables i.e. m<n is a solution where m
variables are non-negative and n-m variables are zero.
79
Optimum Solution: A solution where the objective function is minimized ormaximized.

DUAL LINEAR PROGRAMMING PROBLEMS

For every linear programming problem there is a corresponding linear programming problem called
the dual.
Dual Problem Formulation
If the original problem is in the standard form then the dual problem can beformulated using
the following rules:
• The number of constraints in the original problem is equal to the number of dual variables. The
number of constraints in the dual problem is equal to the number of variables in the original
problem.
• The original problem profit coefficients appear on the right hand side of the dual problem
constraints.
• If the original problem is a maximization problem then the dual problem is a minimization
problem. Similarly, if the original problem is a minimization problem then the dual problem is a
maximization problem.
• The original problem has less than or equal to (≤) type of constraints while the dual problem
has greater than or equal to (≥) type constraints.
• The coefficients of the constraints of the original problem which appear from left to right are
placed from top to bottom in the constraints of the dual problem and vice versa.

Simple Way of Solving Dual Problem

Minimize: P = x1 + 2x2Subject to: x1 + x2 ≥ 8
2x1 + x2 ≥12X1 ≥1
Solution: Step 1: Set up the P-matrix and its transpose

Step 2: Form the objective function and constraints for the dual w1 + 2w 2 + w 1 ≤ 1
w1 + w 2 + w 1 ≤ 2 Z = 8w1 = 12w 2 +2
Step 3: Construct the initial simplex tableau for the dual
w1 W2 W3 S1 S2 g z
1 2 1 1 0 0 1
1 1 0 0 1 0 2
-8 -12 -1 0 0 1 0

The most negative number in the bottom row to the left of the last column is -12. This establishes
the pivot column. The smallest non- negative ratio is ½.

80
Step 4: Pivoting
Pivoting about the 2 we get:
w1 W2 W3 S1 S2 g z
1 2 1 1 0 0 1
1/2 0 -1/25 -1/26 1 0 3/2
-2 0 0 1 6

w1 W2 W3 S1 S2 g z
1/2 1 1/2 1/2 0 0 1/2
1 1 0 0 1 0 2
-8 -12 -1 0 0 1 0

The most negative entry in the bottom row to the left of the last column is -2Pivoting about the 1/ 2

w1 W2 W3 S1 S2 g z
1/2 1 1/2 1/2 0 0 1/2
1/2 0 -1/25 -1/26 1 0 3/2
-2 0 0 1 6

Therefore, the optimum solution providing by x1 = 8 and x2 = 0

w1 W2 W3 S1 S2 g z
1 2 1 1 0 0 1
0 -1 -1 -1 1 0 1
0 4 7 8 0 1 8

Therefore, the optimum solution providing by x1 = 8 and x2 = 0.The minimum valueis 8.

81