15CS3

DISCRETE MATHEMATICAL STRUCTURES 6

Module 1: Set Theory:

 Sets and Subsets,
 Set Operations and the Laws of Set Theory,
 Counting and Venn Diagrams,
 A First Word on Probability,
 Countable and
 Uncountable Sets

Fundamentals of Logic:

 Basic Connectives and Truth Tables,

 Logic Equivalence –The Laws of Logic,
 Logical Implication – Rules of Inference.

DEPT. OF CSE, ACE Page 4

 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

Set Theory:

Sets and Subsets:

A set is a of objects, called elements the set. set b
collection of A can be y listing
betwee braces: A = {1, 2, 3, 4, 5}. The symbol belongs
its elements n e is (or to) a set.
3 e A. Its negation is represented e.g. finite,
For instance by /e, 7 /e A. If the set Is its
number of elements is represented |A|, e.g. if A = {1, 2, 3, | A| =
4, 5} then 5

1. N = {0, 1, 2, 3, ·· · } = the set of natural numbers.

2. Z = {··· , -3, -2, -1, 0, 1, 2, 3, ··· } = the set of integers.
3. Q = the set of rational numbers.
4. R = the set of real numbers.
5. C = the set of complex numbers.
If S is one of then we also use the following
those sets notations :
1. S = element in S, for
+
set of positive s instance
Z
= {1, 2, 3, the set of positive
+
··· } = integers.
= of negative
-
2. S set elements in S, for instance
= {-1, -2, -3, set of negative
-
Z ··· } = the integers.
∗
3. S =
of in excluding zero, for
∗
set elements S instance R = the set of non zero real
num
bers.

Set-builder An way to define a called set-

notation: alternative set, builder notation, is
by propert (predicat verifie by its
stating a y e) P (x) d exactly elements,for instance
A = {x e | 1 ≤ x ≤ 5} “set of x such that 1 ≤ ≤ 5”—
Z = integers x i.e.: A = {1, 2, 3,
4, general: A = {x e U | p(x)}, U univers of
5}. In where is the e discourse in which
the mus be interpreted, or A = {x | P (x)} if the universe of
predicate P (x) t discourse
for P (x) is understood In set the term universalis often used in
 implicitly . theory set
place of “universe of discourse” for a given
predicate.
Princip of Extension: Two sets are equal only if
le if and they have the same
A = � ∀x (x e A ↔ x e B)
elements, i.e.: B .
Subset: We say A is a of set or A is in B,
that subset B, contained and we represent
if all of A if A = {a, b, c}
it “A ⊆ B”, elements are in B, e.g., and
B = {a, b, c, d, e} then A ⊆
B.
Proper subset: prope subse of represente
A is a r t B, d “A ⊂ B”, if A ⊆ B
i.e., there is some element which is
A = B, in B not in A.

DEPT. OF CSE, Page

ACE 5
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

Empty Set: A set with no elements is called empty set

(or null set, or void set ), and is represented by
∅ or {}.

Note that preven a set from possibly element of se (whic

nothing ts being an another t h
is not the same as being a
subset!). For i n stance
is an elem ent of
if A {1, a, {3, t}, { 1, 2, 3}} { 3, t}, t obvious ly
= and B= hen B A,
i.e., e
B A.

Pow Set: collectio of subse A is the power set of

er The n all ts of a set called A,
is P(A). For instance, if A = {1, 2, 3},
and represented then
P(A) = {∅, {2}, {3}, {1, 2}, {1, 3}, {2, 3},
{1}, A} .
MultCSE ordinar set identical if they have same
ts: Two ys are the elements, so for
instance, {a, a, b} {a, b} the set because exactl
and are same they have y the same
elements namel Howeve in application it might
, y a and b. r, some s be useful to
element a w us multCSEt ar
allow repeated s in set. In that case e e s, which e
mathematical entities similar to possibl repeat elements So
sets, but with y ed . , as
multCSEts, {a, a, b} and {a, b} would be consi dered since in the first one
different, the
element a occurs twice in the second one it occurs only
and once.

S et Oper atio ns:

1. Intersection : The common elements of two sets:

A ∩ B = {x | (x e A) ∧ (x e B)} .
If A ∩ B = ∅, the sets are said to be disjoint.
2. Union : The set of elements that belong to either of two sets:
A ∪ B = {x | (x e A) ∨ (x e B)} .
3.Complement : The set of elements (in the universal set) that do not
belong to a given set:
A = {x e U | x /e A} .

4. Difference or Relative Complement : The set of elements that belong to a

set but not to another:
A - B = {x | (x e A) ∧ (x /e B)} = A ∩ B .

DEPT. OF CSE, ACE Page 6

 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

5. Symmetric Difference : Given two sets, their symmetric differ- ence is the
set of elements that belong to either one or the other set but not both.
A ⊕ B = {x | (x e A) ⊕ (x e B)} .

It can be expressed also in the following way:

A ⊕ B = A ∪ B - A ∩ B = (A - B) ∪ (B - A) .

Counti wit Ven

ng h n Diagra ms:
A Venn with intersecting the most general way divides the
diagram n sets in plane
n
into 2 regions. If we have the of of some
information about number elements portions
of the we find the of in each of the regions
the diagram, n can number elements and
use that for the of othe portions of
information obtaining number elements in r the
plane.

Example : Let M , be the sets of takin matic

P and C students g Mathe- s courses,
Physics courses and Science courses respec-
Computer tively in a university. Assume
|M| = 300, |P | = 350, |C| =
450,
|M � P | = 100, |M � C| = 150, |P � C| = 75, |M � P � C| =
10. How
man student are taking exactly one of those
y s courses?

We see that |(M �P )-(M �P �C )| = 100-10 = 90, |(M

�C )-(M �
P � C )| = 150 - 10 = 140 and |(P � C) - (M � P � C)| = 75 -
10 = 65.
Then the region corresponding to takin Mathematics only
students g courses has
cardinalit 300- = 60. Analogously we numbe
y (90+10+140) compute the r of students
takin courses an takin Computer course
g Physics only (185) d g Science s only (235).
The sum 60 + 185 + 235 = 480 is the taking
number of students exactly one
o f those
courses.
DEPT. OF CSE, ACE Page 7
DISCRETE MATHEMATICAL 15CS3
STRUCTURES 6
Ven Dia
n grams:
Ven diagrams are graphic enclosed areas in
n representa- tions of sets as the plane.
For instance, in figure 2.1, the represents the universal set (the
rectangle set of all
elements con- sidered in a given the region represents se
problem) and shaded a t A.
The other figures represent various set operations.

Counting Ven Diagra

with n ms:
A Venn with set intersecting th most general way divides the
diagram n s in e plane
n
into 2 regions. If we have information th number of
about e elements of some portions
of the the we can find the number of
diagram, n elements in each of the regions and
use that for the of
information obtaining number elements in other portions of the
plane.
Example : Let M , be sets of students
P and C the taking Mathe- matics courses,
Physics courses and
Computer Science courses respec- tively in a university.
Assume
|M| = 300, |P | = 350, |C| = 450,
|M � P | = 100, |M � C| = 150, |P � C| = 75, |M � P � C| =
10. How
many students are taking exactly one of those courses? (fig.
2.7)

Page
DEPT. OF CSE, ACE 8
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

We see that |(M �P )-(M �P �C )| = 100-10 = 90, |(M �C )-(M

� P � C )| = 150 - 10 = 140 and |(P � C) - (M � P � C)| = 75 -
10 = 65.
Then the region corresponding to students taking Mathematics courses only
has cardinality 300-(90+10+140) = 60. Analogously we compute the
number of students taking Physics courses only (185) and taking Computer
Science courses only (235).

Gene ral ized Un ion and Inters ec ti on: Given a

collec- tion of sets A1 , A2, . . . ,
AN , their union is defined as the set of elements that belong to at least one
of the sets (here n represents an integer in the range from 1 to N ):
DEPT. OF CSE, ACE Page 9
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6
Analogously, their intersection is the set of
elements that belong to all
the sets
simultaneously:

These definitions can be applied to infinite collections of sets as

well. For instance assume that Sm = {kn | k = 2, 3, 4, . . . } = set of
multiples of n greater than n. Then

P artitions: A a set X is a collection S of non overlapping non

partition of empty
subsets of X whose the whole X . For instance a partition of X = {1,
union is 2, 3, 4, 5,
6, 7, 8, 9, 10} could be S = {{1, 2, 4, 8}, {3, 6}, {5, 7, 9, 10}} .
Given a partition S of a set X , every element of X belongs to exactly one
member of S.

Example : The division of the integers Z into even and odd numbers is a
partition: S = {E, O}, where E = { 2n | n e Z}, O = { 2n + 1 | n e Z}.

Example : The divisions of Z in negative integers,

positive integers and zero is a
+ -
p art itio n: S = {Z , Z , {0 }}.

Order ed P C ar tes Prod

airs, ian uct:
ordinar pai {a, se tw element
An y r b} is a t with o s. In a set the order of the
el ements is irrelevant, {a, b} {b, elemen
so = a}. If the order of the ts is relevant,
the we use a different called represented (a, b). Now (a, b) =
n object ordered pair, (b,
! ! !
a) (unless a = b). In general (a, b) = (a , b ) iff a = a
!
and b = b .
Given two sets A, B, Cartesian product A × B set of all
their is the ordered pairs (a, b)
such that a e A and b e B :
A × B = {(a, b) | (a e A) ∧ (b e
B)} .
Analogously we can define triples or 3-tuples (a, b, c), 4-tuples
(a, b, c, d),
. . . , n- (a1 , a2, . . . , am ), the 3-fold, 4-fold,. . .
tuples and corresponding ,
DEPT. OF CSE, Page
ACE 10
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

n-fold Cartesian products:

A1 × A2 × ··· × Am =
{(a1 , a2, . . . , am ) | (a1 e A1) ∧ (a2 e A2) ∧ ··· ∧ (am e Am )} .

= A × A × A, etc. In
general:

If all the sets in a Cartesian product are

2
the same, then we can use an exponent: A =
3
A × A, A
(m ti
mes) m

= A × A ×··· × A .

A First Word on Probability:

I ntro Assume we experiment such tossing

duction: that perform an as a
coi
n or
rolling a die. se of possible is called sample
The t outcomes the space of the
experiment.
An event is a of the sample space. instanc if we
subset For e, toss a coin
three
times,
sample space
the is
S — {H H H, H H T , H T H, H T T , T H H, T H T ,
T T H, T T T } .
Th event least two heads in a row” would be
e “at the subset
E — {H H H, H HT, T HH}
.
If all possible outcomes experiment
of an have the same likelihood of
occurrence,
then
the
probability of an event A ⊂ S is give n by Laplace’s rule:

For instance, the probability of getting at least two heads in a

row in the above experiment is 3/8.
DEPT. OF CSE, ACE Page
11
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

Then: Prop er ties of probab ili ty:Let P be a probability func- tion on a sample

space S.

THE CONCEPT OF PROBALITY:

Pr(A)=|A| / |S| where |A| is an event and |S| is sample space
Pr(A)=|A| / |S|=(|S|-|A|)/|S|= 1- (|A|/|S|)= 1-Pr(A).
Pr(A)=0 if and only if Pr(A)=1 and Pr(A)=1 if and only if
Pr(A)=0
ADDITION THEROM:
Suppose A and B are 2 events is a sample space S then A UB is an event in S consisting of
outcomes that are in A or B or both and A ∩ B is an event is S consisting of outcomes thata
recommon to A and B. accordingly by the principle of addition we have |AUB|=|A|+|B|-|A ∩B|
and formula 1 gives
P r(AUB)=|AUB|/|S|=(|A|+|B|-|A ∩B|)/|S|
= |A|/|S| + |B|/|S| - |A ∩ B| / |S|
P r(AUB) =Pr(A)+Pr(B)-Pr(A ∩ B)

DEPT. OF CSE, ACE Page

12
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

MUTUALY EXCLUSIVE EVENTS:

Two events A and B in a sample space are said to be mutual exclusive if A ∩ B =Ø then Pr(A
∩B)=0 and the addition theorem reduces to P r(AUB)= Pr(A)+Pr(B)
If A1, A2…….An are mutualy exclusive events, then Pr(A1UA2U…….UAn)=
Pr(A1)+Pr(A2)+….+Pr(An)

COND ITIONAL PROBABILITY:

If E is an event in a finite sample S with Pr(E)>0 then the probability that an event A in S
occurs when E has already occurred is called the probability of A relative to E or the
conditional p robability of A , given E
This p robability, denoted by Pr(A|E) is defined by Pr(A|
E)=|A∩ E|/ |E| from this |A∩ E|=|E| . Pr(A|E) Pr(A∩ E)= |
A∩ E|/ S=|=|E|/|S| . Pr(A|E)=Pr(E) . Pr(A|E)

Example : Find the probability of obtaining a sum of 10 after rolling two fair dice. Find the
probability of that event if we know that at least one of the dice shows 5 points.
Answer : We call E — “obtaining sum 10” and F — “at least one of the dice shows 5
points”. The number of possible outcomes is 6 × 6 — 36. The event “obtaining a sum 10” is E
— {(4, 6), (5, 5), (6, 4)}, so|E| — 3. Hence the probability is P (E) — |E|/|S|
— 3/36 — 1/12.Now, if we know that at least one of the dice shows 5 points then the sample
space shrinks to
F — {(1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (6, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 6)} ,

so |F | — 11, and the ways to obtain a sum 10 are E n F — {(5, 5)}, |E n F |

— 1, so the probability is P (E | F ) — P (E n F )/P (F ) — 1/11.

MUTUALLY INDEPENDENT EVENTS:

The event A and E in a sample space S are said to be mutually independent if the probability of
the occurrence of A is independent of the probability of the occurrence of E, So that
Pr(A)=Pr(A|E). For such events Pr(A ∩ E)=Pr(A).Pr(E)

This is known as the product rule or the multiplication theorem for mutually independent
events .
A gen eralization of expression is if A1,A2,A3………..An are mutually in dependent events in
a sample space S then
Pr(A1∩ A2∩ ……………∩ An)=Pr(A1).Pr(A2)………..Pr(An)
Example : Assume that the probability that a shooter hits a target is p — 0.7, and that hitting
the target in different shots are independent events. Find:
1. The probability that the shooter does not hit the target in one shot.
2. The probability that the shooter does not hit the target three times in a row.

DEPT. OF CSE, Page

ACE 13
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

3. The probability that the shooter hits the target at least once after shooting three times.

Answer :
1. P (not hitting the target in one shot) — 1 — 0.7 — 0.3.
3
2. P (not hitting the target three times in a row) — 0.3 — 0.027.
3. P (hitting the target at least once in three shots) — 1—0.027 —
0.973.

COUNTABLE AND UNCOUNTABLE SETS

A set A is said to be the c ountable if A is a finite set. A set which is not countable is called an
uncountable set.
THE ADDITION PRINCIPLE:
• |AUB|=|A|+|B|-|A∩ B| is the addition principle rule or the principle of inclusion –
exclusion.
• |A-B|=|A|-|A∩ B|
• |A ∩ B|=|U|-|A|-|B| +|A∩ B|
• |AUBUC|=|A|+|B|+|C|-|A ∩B|-|B ∩ C|-|A ∩ C|+|A ∩ B ∩ C| is extended addition
principle
• NOTE: |A ∩ B ∩ C|=|AUBUC|
=|U|-| AUBUC|
= |U|-|A|-|B| -|C|+|B ∩C|+|A ∩B|+|A ∩C|- |A ∩B ∩C| |
A-B-C|=|A|-|A ∩ B|-|A ∩ C|+|A ∩ B ∩ C|

Fundamentals of Logic:

Intr oduction:
Propositi ons:
A proposition is a declarative sentence that is either true or false (but not both). For
instance, the following are propositions: “Paris is in France” (true), “London is in
Denmark” (false), “2< 4” (true), “4 = 7 (false)”. However the following are not
propositions: “what is your name?” (this is a question), “do your homework” (this
is a command), “this sentence is false” (neither true nor false), “x is an even
number” (it depends on what x represents), “So crates” (it is not even a sentence).
The truth or falsehood of a proposition is called its truth value.
Basic Connectives and Truth Tables:

DEPT. OF CSE, ACE Page

14
DISCRETE MATHEMATICAL 15CS3
STRUCTURES 6

Connectives are used for making compound propositions. The main ones are
the following (p and q represent given propositions):

Name Represent Meaning

Negation ed “not p”
Conjunction ¬p “p and q”
Disjunction p∧q “p or q (or both)”
Exclusive Or “either p or q, but not both”
Implication p ∨q “if p then q”
Biconditional “p if and only if q”
p⊕q

The truth value of a compound proposition depends only on the value of its components.
Writing F for “false” and T for “true”, we can summarize the meaning of the connectives in the
following way:

q ¬p p⊕ p →p ↔ q
p p∧q p∨q q
T T F T T F T T
T F F F T T F F
F T T F T T T F
F F T F F F T T

Note that ∨ represents a non-exclusive or, i.e., p ∨ q is true when any of p, q is true
and also when both are true. On the other hand ⊕ represents an exclusive or, i.e., p
⊕ q is true only when exactly one of p and q is true.

T autol ogy, C ontradi cti on, C onti ngenc y:

1. A proposition is said to be a tautology if its truth value is T for any assignment of
truth values to its compon ents. Example : The proposition p ∨ ¬p is a tautology.

2. A proposition is said to be a contradiction if its truth value is F for any assignment of truth
values to its components. Example : The proposition p ∧ ¬p is a c ontradiction.

3. A proposition that is neither a tautology nor a contradiction is called a contingency

Conditional Propo siti ons: A proposition of the form “if p then q” or “p implies
q”, represented “p → q” is called a conditio nal proposition. For instance: “if John is
from Chicago then John is from Illinois”. The proposition p is called hypothesis or
antecedent, and the proposition q is the conclusion or consequent.

Page
DEPT. OF CSE, ACE 15
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

Note that p → q is true always except when p is true and q is false. So, the following sentences
are true: “if 2 < 4 then Paris is in France” (true → true), “if London is in Denmark t hen 2 < 4”
(false → true),

“if 4 = 7 then London is in Denmark” (false → false). However the following one
is false: “if 2 < 4 then London is in Denmark” (true → false).

In might seem strange that “p → q” is considered true when p is false, regardless

of the truth value of q. This will become clearer when we study predicates such as “if
x is a multiple of 4 then x is a multiple of 2”. That implication is obviously true,
although for the particular
case x = 3 it becomes “if 3 is a multiple of 4 then 3 is a multiple of 2”.

The proposition p ↔ q, read “p if and only if q”, is called bicon- ditional. It is true precCSEly
when p and q have the same truth value, i.e., they are both true or both false.

Logic al Equival ence: Note that the compound proposi- tions p →

q a nd ¬p ∨ q have the same truth values:

p q ¬p ¬p ∨ q p →
T T F T T
T F F F F
F T T T T
F F T T T

When two compound propositions have the same truth values no matter what truth value their
constituent propositions have, they are called logically equivalent. For
inst an ce p → q and ¬p ∨ q are logically equivalent, and we write it:
p → q ≡ ¬p ∨q

Note that that two propositions A and B are logically equivalent precCSEly when A ↔
B is a tautology.
Example : De Morgan’s Laws for Logic. The following propositions are logically

Page
DEPT. OF CSE, ACE 16
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

equivalent:
¬(p ∨ q) ≡ ¬p ∧ ¬q
¬(p ∧ q) ≡ ¬p ∨ ¬q

p q ¬p ¬q p∨ q ¬(p ∨ q) ¬p ∧ ¬q p∧q ¬(p ∧ q) ¬p ∨ ¬q

T T F F T F F T F F
T F F T T F F F T T
F T T F T F F F T T
F F T T F T T F T T

Example : The following propositions are logically e quivalent:

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

Again, this can be checked with the truth tables:

p q p →q → (p →q)∧(qp ↔ q
T T T T T T
T F F T F F
F T T F F F
F F T T T T

ExercCSE : Check the following logical equivalences:

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

Converse, C ontrapo sitive: The converse of a conditional proposition p → q is

the proposition q → p. As we have seen, the bi- conditional proposition is
equivalent to the co njunction of a con ditional propo sition an its converse.

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

So, for instance, saying that “John is married if and only if he has a spouse” is the

DEPT. OF CSE, ACE Page 17

 DISCRETE MATHEMATICAL
STRUCTURES 15CS36

same as saying “if John is married then he has a spouse” and “if he has a spouse then
he is married”.

Note that the converse is not equivalent to the given conditional proposition, for
instance “if John is from Chicago then John is from Illinois” is true, but the converse
“if John is from Illinois then John is from Chicago” may be false.
The contrapositive of a conditional proposition p → q is the propo- sition ¬q →
¬p. They are logically equivalent. For instance the con- trapositive of “if John is
from Chicago then John is from Illinois” is “if
John is not from Illinois then John is not from Chicago”.
LOGICAL CONNECTIVES: New propositions are obtained with the aid of word
or phrases like “not”,”and”,”if….then”,and “if and only if”. Such words or phrases are
called logical connectives. The new propositions obtained by the use of connectives are called
compound propositions. The original propositions from which a compound proposition is
obtained are called the components or the primitives of the compound proposition.
Propositions which do not contain any logical connective are called simple propositions

NE GATION: A Proposition obtained by inserting the word “not” at an appropriate place in a

given proposition is called the negation of the given proposition. The negation of a proposition
p is denoted by ~p(read “not p”)
Ex: p: 3 is a prime number
~p: 3 is not a prime number
Truth Table: p ~p

0 1
10
CONJUNCTION:
A compound proposition obtained by combining two given propositions by inserting the word
“and” in between them is called the conjunction of the given proposition.The conjunction of
two proposition p and q is denoted by p^q(read “p and q”).
• The conjunction p^q is true only when p is true and q is true; in all other cases it is
false.
• Ex: p:√2 is an irational number q: 9 is a prime number
p^q: √2 is an i rational number and 9 is a prime number
• Truth table: p q p^q
0 0 0
0 1 0
1 0 0
1 1 1

DEPT. OF CSE, ACE Page 18

 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

DISJUNCTION:
A compound proposition obtained by combining two given propositions by inserting the word
“or” in between them is called the disjunction of the given proposition.The di sjunction of two
proposition p and q is denoted by p�q(read “p or q”).

• The di sjunction p�q is false only when p is false and q is false ; in all other cases it
is true.
• Ex: p:√2 is an irational number q: 9 is a prime number
p�q : √2 is an irational number or 9 is a prime number Truth table:
• p q p�q
0 0 0
0 1 1
1 0 1
1 1 1
EXCLUSIVE DISJUNCTION:

• The compound proposition “p or q” to be true only when either p is true or q is true but
not both. The exclusive or is denoted by symbol v.

• Ex: p:√2 is an ir rational number q: 2+3=5

Pvq: Either √2 is an i rrational number or 2+3=5 but not both.

• Truth Table:

p q pvq
0 0 0
0 1 1
1 0 1
1 1 0
COND ITIONAL(or IMP LICATION):

• A compound proposition obtained by combining two given propositions by using the

words “if” and “then” at appropriate places is called a conditional or an implication..
Given two propositions p and q, we can form the conditionals “if p, then q” and “if
q, then p:. The conditional “if p, then q”is denoted by p→q and the conditional “if q, then p” is
denoted by q →p.

• The conditional p→q is false only when p is true and q is false ;in all other cases it
DEPT. OF CSE, ACE Page
19
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

is true.

• Ex: p: 2 is a prime number q: 3 is a prime number

p→q: If 2 is a prime number then 3 is a prime number; it is true

• Truth Table:

p q p→q
0 0 1
0 1 1
1 0 0
1 1 1

BICONDITIONAL:

• Let p and q be two propositions,then the conjunction of the conditionals p→q and q→p
is called bi- conditional of p and q. It is denoted by p↔q.

• p↔q is same as (p→q)�( q→p ). As such p↔q is read as “ if p then q and if q then
p”.

• Ex: p: 2 is a prime number q: 3 is a prime number p↔q are true.

Truth Table: p q p→q q→p p↔q

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

COMBINED TRUTH TABLE

P q ~p p^q p�q pvq p→q p↔q

0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0
1 0 0 0 1 1 0 0
DEPT. OF CSE, Page
ACE 20
 DISCRETE MATHEMATICAL
STRUCTURES 15CS36

1 1 0 1 1 0 1 1
TAUTOLOGIES; CONTRADICTIONS:

A compound proposition which is always true regardless of the truth values of its components
is called a tautology.

A compound proposition which is always false regardless of the truth values of its components
is called a cont radiction or an absurdity.

A compound proposition that can be true or false (depending upon the truth values of its
components) is called a contingency I.e contingency is a compound proposition which is
neither a tautology nor a contradiction.

LOGICAL EQUIVALENCE

• Two propositions ‘u’ and ‘v’ are said to be logically equivalent whenever u and v have
the same truth value, or equivalently .

• Then we write u�v. Here the symbol �stands for “logically equivalent to”.

• When the propositions u and v are not logically eq uivalent we write u�v.

LAWS OF LOGIC:

To denote a tautology and To denotes a contradiction.

• Law of Double negation: For any proposition p,(~~p)�p

• Idempotent laws: For any propositions p, 1) (p�p) �p 2) (p�p) �p
• Identity laws: For any proposition p, 1)(p�Fo) �p 2)(p�To) �p
• Inverse laws: For any proposition p, 1) (p � �p) �To 2)(p�~p)�Fo
• Commutative Laws: For any proposition p and q, 1)(p�q)�(q�p) 2)(p�q)�(q�p)
• Domination Laws: For any proposition p, 1) (p�To) �To 2) (p�Fo) �Fo
• Absorption Laws: For any proposition p and q,1) [p� (p�q)] �p 2)[p� (p�q)] �p
• De-Morgan Laws: For any proposition p and q, 1)~ (p�q)��p��q
Associative Laws : For any proposition p ,q and r, 1) p � (q � r) �(p �q) �r 2)
Distributive Laws: For any proposition p ,q and r, 1) p � (q � r) � (p �q) � (p �r )
2) p�(q�r)� (p�q) � (p�r)

DEPT. OF CSE, ACE Page

21
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

• Law for the negation of a conditional : Given a conditional p→q, its negation is
obtained by using the following law: �(p→q)�[p�(�q)]

TRANSITIVE AND SUBSTITUTION RULES If u,v,w are propositions such that u�v
and v �w, then u �w. (this is transitive rule)

• Suppose that a compound proposition u is a tautology and p is a component of u, we replace

each occurrence of p in u by a proposition q, then the resulting compound proposition v is also
a tautology(This is called a substitution rule).

• Suppose that u is a compound proposition which contains a proposition p. Let q be a

proposition such that q �p , suppose we replace one or more occurrences of p by q and obtain
a compound proposition v. Then u �v (This is also substitution rule)

APPLICATION TO SWITCHING NETWORKS

• If a switch p is open, we assign the symbol o to it and if p is closed we assign the

symbol 1 to it.

• Ex: current flows from the terminal A to the terminal B if the switch is closed i.e if p is
assigned the symbol 1. This network is represented by the s ymbol p

A P B

Ex: parallel network consists of 2 switches p and q in which the current flows from
the terminal A to the terminal B , if p or q or both are closed i.e if p or q (or both) are assigned
the symbol 1. This network is represent by p�q

Ex: Series network consists of 2 switches p and q in which the current flows from the
terminal A to the terminal B if both of p and q are closed; that is if both p and q are assigned
the symbol 1. This network is repr esented by p�q

DUALITY:

Suppose u is a compound proposition that contains the connectives � and �. Suppose we

replace each occurrence of � and � in u by � and � re spectively.

Page
DEPT. OF CSE, ACE 22
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

Also if u contains To and Fo as components, suppose we replace each occurrence of To and Fo

by Fo and To respectively, then the resulting compound proposition is called the dual of u and
d
is denoted by u .

Ex: u: p �(q � �r) � (s � To) d

u : p � (q � � r) � (s � Fo)

NOTE:

d d
• (u ) �u. The dual of the dual of u is logically equ ivalent to u.

d d
• For any two propositions u and v if u �v, then u �v . This is known as the pr
inciple of duality.

The connectives NAND and NOR

(p ↑q)= �(p � q) � p �� q
�

(p ↓q)= �(p � q) � p �� q
�

CONVERSE,INVERSE AND CONTRAPOSITIVE

Consider a conditional (p→q) , Then :

1) q→p is called the converse of p→q

2) �p→�q is called the inverse of p→q

3) �q→�p is called the cont rapositive of p→q

RULES OF INFERENCE:

There exist rules of logic which can be employed for establishing the validity of a rguments
. These rules are called the Rules of Inference.

1) Rule of conjunctive simpli fication: This rule states that for any two propositions p
DEPT. OF CSE, ACE Page
23
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

and q if p�q is true, then p is true i.e (p�q )�p.

2) Rule of Disjunctive amplification: This rule states that for any two proposition p and q
if p is true then p�q is true i.e p�(p �q)

3) 3) Rule of Syllogism: This rule states that for any three propositions p,q r if p→q is
true and q→r is true then p→r is true. i.e {(p→q)�(q→)} �(p →r) In tabular form:
p→q q→r � (p →r)

4) 4) Modus pones(Rule of Detachment): This rule states that if p is true and p→q
is true, then q is true, ie {p �(p→q )} �q. Tabular form

p p→q �q

5) Modus Tollens: This rule states that if p→q is true and q is false, then p is false.
{(p→q)��q}�q Tabular form: p→q
�q ��p

6) Rule of Disjunctive Syllogism: This rule states that if p�q is true and p is false,
then q is true i.e. {(p�q)��p}�q Tabular Form p�q

�p �q

QUANTIFIERS:

1. The words “ALL”,”EVERY”,”SOME”,”THERE EXISTS” are called quantifiers in the

proposition

2. The symbol � is used to denote the phrases “FOR ALL”,”FOR EVE RY”,”FOR EACH”
and “FOR ANY”.this is called as universal quantifier.

3. � is used to denote the phrases “FOR SOME”and “THERE EXISTS”and “FOR

ATLEAST ONE”.this s ymbol is called existential quantifier.

A proposition involving the universal or the existential quantifier is called a quantified

statement

LOGICAL EQUIVALENCE:
DEPT. OF CSE, ACE Page
24
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

1. � x,[p(x)�q(x)]�(�x p(x))�(�x,q(x))

2. � x, [p(x)�q(x)]�(�x p(x)) �(�x,q(x))

3. � x, [p(x)→q(x)] ��x ,[�p(x)�q(x)]

RULE FOR NEGATION OF A QUANTIFIED STATEMENT:

�{�x,p(x)}≡�x{�p(x)} �{�x,p(x)}≡�x{�p(x)}

RULES OF INTERFERENCE:

1. RULE OF UNIVERSAL SPECIFICATION

2. RULE OF UNIVERSAL GENERALIZATION

If an open statement p(x) is proved to be true for any (arbitrary)x chosen from a set S,
then the quantified statement �x€S, p(x) is true.

ME THODS OF PROOF AND DIS PROOF:

1.DIRECT PROOF:

The direct method of proving a conditional p→q has the following lines of argument:

a) hypothesis : First assume that p is true

b) Analysis: starting with the hypothesis and employing the rules /laws of
logic and other known facts , infer that q is true

c) Conclusion:p→q is true.

2. INDIRECT PROOF:

Condition p→q and its contrapositive �q→�p are logically equivalent. On basis of this
proof, we infer that the conditional p→q is true. This method of proving a conditional is

DEPT. OF CSE, ACE Page

25
 15CS3
DISCRETE MATHEMATICAL STRUCTURES 6

called an indirect method of proof.

3 .PROOF BY CONTRADICTION

The indirect method of proof is equivalent to what is known as the proof by contradiction.
The lines of argument in this method of proof of the statement p→q are as follows:
1) Hypothesis: Assume that p→q is false i.e assume that p is true and q is
false.
2)Analysis: starting with the hypothesis that q is false and employing the rules of logic
and other known facts , infer that p is false. This contradicts the assumption that p is true

3)Conculsion: because of the contradiction arrived in the analysis , we infer that p→q
is true

4 .PROOF BY E XHAUSTION:

“�x €S,p(x)” is true if p(x)is true for every (each) x in S.If S consists of only a limited number
of elements , we can prove that the statement “�x €S,p(x)” is true by considering p(a) for each
a in S and verifying that p(a) is true .such a method of prove is called method of exhaustion.

5 .PROOF OF EXISTENCE:

“�x €S,p(x)” is true if any one element a € S such that p(a) is true is exhibited. Hence , the
best way of proving a proposition of the form “�x €S,p(x)” is to exhibit the existence of one
a€S such that p(a) is true. This method of proof is called proof of existence.

6.DI SPROOF BY CONTRADICTION :

Suppose we wish to disprove a conditional p→q. for this propose we start with the hypothesis
that p is true and q is true, and end up with a contradiction. In view of the contradiction , we
conclude that the conditional p→q is false.this method of disproving p→q is called
DISPROOF BY CONTRADICTION

DEPT. OF CSE, ACE Page

26