Unit II Combinatorics

Department of Mathematics
Sub Code:MA1256 Branch: CSE A,B & C
Course: Discrete Mathematics
UNIT – I MATHEMATICAL LOGIC
Part– A
01 / Get the contra positive of the statement “If it is raining then I get wet”
Solution: Let p: it is raining and q: I get wet
Given p → q. Its contra positive is given by ┐q → ┐p
That is “If I don’t get wet then it is not raining”
02 / Is it true that the negation of a conditional statement is also a conditional statement?
Solution: No because ┐( p → q) = ┐(┐pq) = p┐q
03 / Write the contra positive of the conditional statement: “If you obey traffic rules, then you will not be fined’
Solution: Let p: you obey traffic rules and q: you will be fined
Given p → ┐q. Its contra positive is given by q → ┐p.
That is “you will be fined if you won’t obey traffic rules”
04 / Define the term tautology
Solution: A compound proposition is said to be tautology if its truth value is True
05 / Show that without using truth tables
Solution:
06 / Show that is a tautology.
Solution:
07 / Write the truth table for the formula
Solution: p q
T T F F T F T
T F F T F F F
F T T F F F F
F F T T F T T
08. Prove that

Hence proved
09. Express in symbolic form, everyone who is healthy can do all kinds of work.ution:
Let P(x):x is healthy and Q(x): x do all work
Symbolic form
10. Write the negation of the statement “If there is a will, then there is a way”
Let p: ‘There is a will’ and q: ‘There is a way’
Given.
Its negation is given by
So, the negation of the given statement is “There is a will and there is no way”
11. Obtain the Disjunctive normal form for the formula

12. Prove that

13. Rewrite the following using quantifiers “Every student in the class studied calculus”
Let P(x): x is a student and Q(x): x studied calculus
Symbolic form
14. Check whether is a tautology.

The given statement is not a tautology
15. Write the statement in symbolic form “Some real numbers are rational”
Let R(x): x is a real number and Q(x): x is rational
Symbolic form:
16. Define simple statement function
An expression consisting of a predicate symbol and an individual variable such A(x), B(y)
etc is called as a simple statement function.
17. Define Compound statement formula
An expression consisting of simple statement functions (one or more variables) connected
by logical Connectives are called a compound statement.
18. Write the statement in symbolic form “Some integers are not square of any integers”
Let I(x): x is an integer and S(x): x is a square of any integer
Symbolic form:
19. Define Contradiction.
A propositional formula which is always false irrespective of the truth values of the
individual variables is a contradiction.
20. Define Universal quantification and Existential quantification.
The Universal quantification of a predicate formula P(x) is the proposition, denoted by
that is true if P (a) is true for all subject a.
The Existential quantification of a predicate formula P(x) is the proposition, denoted by
that is true if P(a) is true for some subject a.
Part – B
Prove that (PQ) (QR) (PR)
Show that the premises ES, SH,A~H, EA are inconsistent.
Show that the following argument is valid.
My father praises me only if I can be proud of myself. Either I do well in sports or I cannot be proud of myself. If study hard , then I cannot do well in spots. Therefore if my father praises me, then I do not study well.
Show that the expression
(P Q) (~P Q) ( P ~Q) (~ P ~Q) is a tautology by using truth tables.
Show that J S logically follows from the premises (PQ), (Q~R), R, P( J S).
Show that the expression
[(PQ) (PR) (QR)] R is a tautology by use of truth table.
Test the validity of the following argument. If there was a meeting, catching the bus was difficult. If they arrived on time, then catching the bus was not difficult. They arrived on time. Therefore there was no meeting.
Find the Principal conjunctive and Principal disjunctive normal forms of the formula
S[P (QR)] [ ~P (~Q~R)]
/ Test the validity of the following argument. If there was a meeting, catching the bus was difficult. If they arrived on time, then catching the bus was not difficult. They arrived on time. Therefore there was no meeting.

Unit II Combinatorics

Part - A

Using mathematical induction ,prove that

let p (n) =

Assume p (1): is true.

Assume p(k) : is true

Claim p(k+1) is true.

P(k+1) :

P(k+1) is true.

Hence it is true for all n.

State pigeon hole principle.

If (n+1) pigeon occupies n holes then at least one hole has more than 1 pigeon.

State the generalized pigeon hole principle.

If m pigeon occupies n holes (m>n), then at least one hole has more than pigeon.

Show that, among 100 people, at least 9 of them were born in the same month.

Here no.of pigeon =m= no. of people =100

No. of holes = n= no. of month =12

Then by generalized pigeon hole principle,

Were born in the same month.

In how many ways can 6 persons occupy 3 vacant seats?

Total no of ways ==6.5.4=120 ways.

How many permutations of the letters ABCDEFGH contain the string ABC .

Because the letters ABC must occur as block, we can find the answer by finding no of permutation of six objects, namely the block ABC and individual letters D,E,F,G and H . Therefore, there are 6! =720 permutations of the letters ABCDEFGH in which ABC occurs.

In how many ways can 5 persons be selected from amongst 10 persons?

The selection can be done in ways.

= 252 ways.

How many ways are there to form a committee, if the committee consists of 3 educanalist and 4 socialist ,if there are 9 educanalist and 11 socialist?

The 3 educanalist can be choosen from 9 educanalist in ways .

The 4 socialist can be choosen from 11 socialist in ways.

By product rule ,the no of ways to select, the committee is

= 27720 ways.

There are 5 questions in a question paper in how many ways can a boy solve one or more questions?

The boy can dispose of each question in two ways .He may either solve it or leave it.

Thus the no of ways disposing of all the questions=.

But this includes the case in which he has left all the questions unsolved.

The total no of ways of solving the paper =

= 31.

If the sequence , then find the corresponding recurrence relation.

Ans: for n≥1

, for n≥1, with.

Find the recurrence relation for the sequence.

For n≥1,

= 2n + 9 – 2

Find the recurrence relation whose solution is

Given

is the required recurrence relation.

Find the associated homogeneous solution for .

Its associated homogeneous equation is

Its characteristic equation is

r-3 =0

r =3

Now, the solution of associated homogeneous equation is

solve

The associated homogeneous relation is

Its characteristic equation is

r =2,5

The solution of associated homogeneous equation is

Define Generating function.

The generating function for the sequence‘s’ with terms,of real numbers is the infinite sum .

G(x) = G(s,x ) =

Find the generating function for the sequence ‘s’ with terms 1,2,3,4……..

= .

How many integers between 1 to 100 that are divisible by 3 but not by 7.

Let A and B denote the no between 1 to 100 that are divisible by 3 and 7 respectively.

The number of integers divisible by 3 but not by 7.

== 33-4 = 29.

Find the value of n if.

Given

n-2 = 5

n =7.

19. In how many ways can letters of the word “INDIA” be arranged?

The word contains 5 letters of which 2 are I’s.

The number of words possible

20. What is the value of ‘r’ if

Part-B

Show that
If we select 10 points in the interior of an equilateral triangle of side 1 ,show that there must be at least 2 points whose distance apart is less than 1/3.
Using mathematical induction prove that

Solve the recurrence relation.
Find an explicit formula for the Fibonacci sequence.
Solve.
Using generating function solve the recurrence relation corresponding to the Fibonacci sequence, .
How many positive integers not exceeding 1000 are divisible by 7 or 11?

Unit III Graph Theory

Part - A

Define Graph.

A graph G = (V,E) consists of a finite non empty set V, the element of which are the vertices of G, and a finite set E of unordered pairs of distinct elements of V called the edges of G.

Define complete graph.

A graph of n vertices having each pair of distinct vertices joined by an edge is called a Complete graph and is denoted by Kn. Complete graphs are often called cliques.

Define regular graph

A graph in which each vertex has the same degree is called a regular graph. A regular graph has n – regular if each vertex has degree n.

Define Bipartite Graph.

Let G = (V,E) be a graph. G is bipartite graph if its vertex set V can be partitioned into two nonempty disjoint subsets V1 and V2 , called a bipartition, so that each edge has one end in V1 and in V2 .

Define complete bipartite graph.

A complete bipartite graph is a bipartite graph with bipartition V1 and V2 in which each vertex of V1 is joined by an edge to each vertex of V2 .

Define Subgraph.

A graph H = (V1,E1) is a subgraph of G = (V,E) provided that V1 ,E1 and for each e ε E1 , both ends of e are in V1

Define Isomorphism

Two graphs G1 = (V1,E1) and G2 = (V2,E2) are the same or isomorphic, if there is a bijection F from V1 to V2 such that (u,v) ε E1 if and only if ( F(u), F(v)) ε E2.

Define strongly connected graph

A digraph G is said to be strongly connected if for evry pair of vertices both vertices of the pair are reachable from one another.

State the necessary and sufficient conditions for the existence of an Eulerian path in a connected graph

A connected graph contains an Euler path if and only if it has exactly two vertices of odd degree.

State Handshaking theorem.

Let G be a graph with at least two vertices . at least two vertices of G have the same degree.

Define adjacency matrix

Let G = (V,E) be a graph with n vertices . An nxn matrix A is an adjacency matrix for G if and only if for 1 I,j n,A(I,j) =

Define Connected graph.

A graph for which each pair of vertices is joined by a trail is connected.

Define Tree

A tree is a connected acyclic graph.

What is minimum cost spanning tree.

A spanning tree of minimum weight is called a minimum cost spanning tree.

Define forest.

A graph in which each connected component of a tree is called a forest.

Define spanning subgraph.

A graph H = (V1,E1) is a subgraph of G = (V,E). H is a spanning subgraph of G if H is a subgraph of G and V1= V.

Define Induced subgraph.

A graph H = (V1,E1) is a subgraph of G = (V,E). H is an induced subgraph of G such that E1 consists of all the edges of G with both ends in V1.

Define binary tree.

A binary tree is either a tree with no vertices or a rooted tree for which each vertex has at most two children.

Define Eulerian Circuit.

A circuit in a graph that includes eacg edge exactly once, the circuit is called an Eulerian circuit.

State Konigsberg bridge theorem.

Let G be a connected graph. G has an Eulerian circuit if and only if each vertex is even.

PART - B

Draw a complete graph K5 with vertices A,B,C,D,E . Draw all complete subgraph of K5 with 4 vertices
State and prove Handshaking Theorem.
In any graph, the number of odd vertices is even.
Let T be a graph with n vertices and m edges. The following statements are equivalent.

T is a tree
T is connected and m = n-1
T is cyclic and m = n-1
T is cyclic and the addition of any edge joining two nonadjacent vertices creates a cycle.

If all the vertices of an undirected graph are each of degree k, show that the number of edges of the graph is a multiple of k.
Draw a graph with 5 vertices A,B,C,D,E such that deg(A) = 3, B is an odd vertex, deg(C) =2 and D and E are adjacent.
The adjacency matrices of two pairs of graph as given below.Examine the isomorphism of G and H by finding the permutation matrix

Let T be a graph, T is tree if and only if any two vertices of T joined by a unique path.

Unit – IV Group Theory

Part - A

Define Algebraic system.

A set together with one or more n-ary oprations on it is called an algebraic

system.for example (Z,+) is an algebraic system.

Define Semi Group.

Let S be non empty set * be a binary operation as S. The algebraic system (S, *) is called a semigroup, If the operation is associative.

In other words (S,*) is a semigroup if for any x,y,z ε S, x* (y * z) = (x* y )* z.

DefineMonoid.

A semigroup(M, *) with identity element with respect to * is called a monoid.

Define Group.

An algebraic system (G,*) is called a group if it satisfies the following properties:

◦* is associative.

◦Identitry element exists.(i.e) there exists an element e ε G such that x * e = e * x = x, for every x in G.

State any two properties of a group.

The identity element of a group is unique.

ii. the inverse of each element is unique.

Define a Commutative ring.

If (R,x) is commutative, then the ring (R,+,X) is called a commutative ring.

Show that the inverse of an element in a group (G, *) is unique.

Let (G,*) be a group with identity element e.Let b and c be an inverses of an element.

a * b = b * a = e, a * c = c * a = e.

b = b * e = b * ( c * a) = b * ( a * c) = ( b * a ) * c = e * c = c

therefore b = c . => is unique.

Give an example of semi group but not a monoid.

The set of all positive integers over addition form a semigroup but it is not a monoid.

Define group code.

An (m,n) encoding function e : Bm Bn is called a group code if e(Bm) is a subgroup of Bn

Define cyclic group.

A group (G,*) is aid to be cyclic if there exists an element a ε G such that every element of G can be written as some power of a.

Define group homomorphism.

Let (G,*) and (S,o) be two groups. A mapping f : G  S is said to be a group homomorphism if for any a, b ε G f(a*b) = f(a) o f(b).

Define Coset.

Let (H,*) be a subgroup of (G,*). For any a ε G the set H is defined by aH = {a*h: h ε H} is called the right coset of H determined by a ε G.

State Lagrange’s theorem.

The order of the subgroup of a finite group G divides the order of the group.

Define Ring.

An algebraic system (S,+) is called a ring if the binary operations + and S satisfies the following.

(S,+) is an abelian group.
(s,.) is a semi group.
The operation is distributive over +.

Define field.

Let (S,+,.) be a ring. If for a,b ε S such that a ≠0,b ≠0,a.b ≠0. Then (S,+,.) a ring without divisors of zero.

Define Integral Domain.

A commutative ring R with a unit element is called an integral domain if R has no zero divisors.

Let T be the set of all even integers. Show that the semi groups (Z,+) and (T,+) are isomorphic.

Define a function f: Z  T by f(n) = 2n where n1, n2ε N.

f is a homomorphism since f(n1+ n2 ) =f n1) +f( n2).

f is one-one since f(n1) = f( n2).

f is onto since f(a) = 2a. therefore f is an isomorphism.

Show that the semi group homomorphism preserves the property of idempotency.

Let f : (M,*)  (H,Δ) be a semi group homomorphism. x is idempotent element in M. x*x = x. f(x*x) = f(x) Δ f(x)

Let x = 1001, y = 0100, z = 1000. Find the minimum distance between these code words.

x + y = 1101, y + z = 1100, z + x = 0001.

H(x,y) = 3, H(y,z) = 2, H(z,x) =1. Minimum Distance = 1.

If H is a subgroup of the group G, among the right cosets of H in G , prove that there is only one subgroup H.

Let Ha be a right coset of H in G where a ε G. If Ha is a subgroup of G, then e ε Ha where e is the identity element in G.

Ha is an equivalence class containing a w.r.t an equivalence relation. So e ε Ha => He = Ha. So Ha =H.

Part – B

If (G,*) is anabelian group, show that (a*b)2 = a2 * b2
Show that (Z,+,x) is an integral domain where Z is the set of all integers.
State and prove Lagrange’s theorem.
If (Z,+) and (E , +) where Z is the set of all integers and E is the set of all even numbers. Show that the two semi groups (Z,+) and (E , +) are isomorphic.
Le be a group and a ε of G. Show that the subset {axa-1 : x ε G}of G is a subgroup of G.
Show that every finite group is isomorphic to the permutation group.
Let H be a subgroup of a finite group G. Show that the order of H divides the order of G.
Find the code words generated by the encoding function E : B2 B5 with respect to the parity check matrix

Unit-V Lattices and Boolean Algebra

Part - A

Define lattice?

A partially ordered set (L,≤) in which every pair of elements has a least upper bound

and greatest lower bound is called a lattice.

Briefly explain lattice

If are two lattices, a mapping is called a lattice homomorphism from to , if for any,.

If a homomorphism of two lattices is objective i.e. 1-1, onto, then f is called an isomorphism. If there exists an isomorphism between two lattices, then the lattices are said to be isomorphic.

Define sub lattice with example ?

A non-empty subset M of a lattice is called a sub lattice of L, iff M is closed under both the operations .viz if a,bM,then also in M. is a sub lattice of .

Define partial ordering on S?

A relation on a set S is called a partial ordering on S if it has the following three properties S is reflexive, anti-symmetric, transitive. A set S together with a partial ordering is called a partially ordered set or poset.

Define Hasse diagram?

Hasse diagram of a finite partially ordered set S is the directed graph whose vertices are the elements of S and there is a directed edge from a to b whenever a < b in S.

Simplify the Boolean expression ,using Boolean algebra identities.

Prove that is a complemented lattice by finding the complements of all the elements.

In the poset are the integers 3 and 9 comparable? Are 5 and 7 are comparable?

Since 3/9, the integers 3 and 9 are comparable.

For 5, 7 neither 5/7 nor 7/5

Therefore, the integers 5 and 7 are not comparable.

Write the properties of lattices.

idempotent law
commutative law
associative law
absorption

Define direct product of lattice.

Let and be two lattices. The algebraic system in which the binary operation + and on L x S are such that for any in L x S

Is called the Direct product of the lattice and .

check the given lattice is complemented lattice or not.

Since

Therefore b does not have any complement .the given lattice is not complemented lattice.

prove that

= (a=a+ab)

= (a.1=a)

Reduce the expression.

=0.b

Reduce the expression a(a+c)=aa+ac.

a(a+c)= aa+ac

= a+ac

= a(1+c)

= a

15. Prove the involution law.

It is enough to show that

By dominance laws of Boolean algebra, we get

By commutative laws, we get

Complement of a’ is a

16. Obtain the partial ordering represented by the Hasse diagram.

Show that the ‘greater than or equal to ‘relation (≥) is a partial ordering on the set of integers.

Since a≥ a for every integer a, ≥ is reflexive.

If a≥ b and b≥a,then a=b.hence ‘≥’ is antisymmetric.

Since a≥b and b≥c imply that a≥c,’ ≥’ is transitive.

Therefore ‘≥’ is a partial order relation on the set of integers.

Prove that any lattice homomorphism is order preserving.

Let be a homomorphism.

Let

Then GLB {a,b}==a

LUB {a,b}==b

Now

i.e., GLB {f(a),f(b)}= f(a)

Therefore

If implies

f is order preserving.

which elements of the poset ({2,4,5,10,12,20,25},/ ) are maximal and which are

minimal?

The relation R is

R={(2,4) (2,10) (2,12) (2,20) (4,12) (4,20) (5,10) (5,20) (5,25) (10,20)}

Its Hasse diagram is

The maximal elements are 12, 20, and 25.

The minimal elements are 2 and 5.

Is the poset a lattice.

Let a and b be any 2 positive integer.

Then LUB{a,b} =LCM {a,b}

And GLB{a,b}= GCD{a,b}

Should exists in .

For example ,let a=4,b=20

Then LUB{a,b}=lcm {4,20}=1

GLB{a,b}=gcd{4,20}=4

Hence ,both GLB and LUB exist.

The poset is a lattice.

Part-B

1. State and prove distributive equalities.

2. Every chain is a distributive lattice.

3. Let be a distributive lattice for a,b,c in L