Subjects | Gate Vidyalay

Category: Subjects

Latch in Digital Electronics | Latch Construction

Digital Design

Latch-

A latch may be defined as-

A latch is basically an unclocked flip flop.

A latch is the basic building block using which clocked flip flops are constructed.

Latch Construction-

There are following two methods for constructing a latch-

By using 2 NOR gates
By using 2 NAND gates

1. Construction Of Latch By Using 2 NOR Gates-

Logic Circuit-

The logic circuit for a latch constructed using NOR gates is as shown below-

While constructing a latch using NOR gates, it is compulsory to consider-

Reset input R in normal output Q_n.
Set input S in complemented output Q’_n.

Logic Symbol-

The logic symbol for a latch constructed using NOR gates is as shown below-

Truth Table-

The truth table for a latch constructed using NOR gates is as shown below-

INPUTS			OUTPUTS
R	S	Q_n (Present State)	Q_n+1 (Next State)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	Indeterminate
1	1	1	Indeterminate

Truth Table

The above truth table may be reduced as-

INPUTS			OUTPUTS	REMARKS
R	S	Q_n (Present State)	Q_n+1 (Next State)	States and Conditions
0	0	X	Q_n	Hold state condition R = S = 0
0	1	X	1	Set state condition R = 0 , S = 1
1	0	X	0	Reset state condition R = 1 , S = 0
1	1	X	Indeterminate	Indeterminate state condition R = S = 1

Truth Table

2. Construction Of Latch By Using 2 NAND Gates-

Logic Circuit-

The logic circuit for a latch constructed using NAND gates is as shown below-

While constructing a latch using NAND gates, it is compulsory to consider-

Set input S in normal output Q_n.
Reset input R in complemented output Q’_n.

Logic Symbol-

The logic symbol for a latch constructed using NAND gates is as shown below-

Truth Table-

The truth table for a latch constructed using NAND gates is as shown below-

INPUTS			OUTPUTS
S	R	Q_n (Present State)	Q_n+1 (Next State)
0	0	0	Indeterminate
0	0	1	Indeterminate
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

Truth Table

The above truth table may be reduced as-

INPUTS			OUTPUTS	REMARKS
S	R	Q_n (Present State)	Q_n+1 (Next State)	States and Conditions
0	0	X	Indeterminate	Indeterminate state condition S = R = 0
0	1	X	1	Set state condition S = 0 , R = 1
1	0	X	0	Reset state condition S = 1 , R = 0
1	1	X	Q_n	Hold State condition S = R = 1

Truth Table

To gain better understanding about Latch in Digital Electronics,

Watch this Video Lecture

Next Article- Types of Flip-Flops

Get more notes and other study material of Digital Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Participation Constraints | DBMS

Database Management System

Participation Constraints-

Before you go through this article, make sure that you have gone through the previous article on Introduction to ER Diagrams.

Participation constraints define the least number of relationship instances in which an entity must compulsorily participate.

Types of Participation Constraints-

There are two types of participation constraints-

Total participation
Partial participation

1. Total Participation-

It specifies that each entity in the entity set must compulsorily participate in at least one relationship instance in that relationship set.
That is why, it is also called as mandatory participation.
Total participation is represented using a double line between the entity set and relationship set.

Example-

Here,

Double line between the entity set “Student” and relationship set “Enrolled in” signifies total participation.
It specifies that each student must be enrolled in at least one course.

Also read- Relationship Sets in DBMS and Entity Sets in DBMS

2. Partial Participation-

It specifies that each entity in the entity set may or may not participate in the relationship instance in that relationship set.
That is why, it is also called as optional participation.
Partial participation is represented using a single line between the entity set and relationship set.

Example-

Here,

Single line between the entity set “Course” and relationship set “Enrolled in” signifies partial participation.
It specifies that there might exist some courses for which no enrollments are made.

Relationship between Cardinality and Participation Constraints-

Minimum cardinality tells whether the participation is partial or total.

If minimum cardinality = 0, then it signifies partial participation.
If minimum cardinality = 1, then it signifies total participation.

Maximum cardinality tells the maximum number of entities that participates in a relationship set.

Next Article- Types of Attributes in DBMS

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Relationship Sets | DBMS

Database Management System

Relationship in DBMS-

Before you go through this article, make sure that you have gone through the previous article on Introduction to ER Diagrams.

A relationship is defined as an association among several entities.

Example-

‘Enrolled in’ is a relationship that exists between entities Student and Course.

Also read- Entity Sets in DBMS

Relationship Set-

A relationship set is a set of relationships of same type.

Example-

Set representation of above ER diagram is-

Degree of a Relationship Set-

The number of entity sets that participate in a relationship set is termed as the degree of that relationship set. Thus,

Degree of a relationship set = Number of entity sets participating in a relationship set

Types of Relationship Sets-

On the basis of degree of a relationship set, a relationship set can be classified into the following types-

Unary relationship set
Binary relationship set
Ternary relationship set
N-ary relationship set

1. Unary Relationship Set-

Unary relationship set is a relationship set where only one entity set participates in a relationship set.

Example-

One person is married to only one person

2. Binary Relationship Set-

Binary relationship set is a relationship set where two entity sets participate in a relationship set.

Example-

Student is enrolled in a Course

3. Ternary Relationship Set-

Ternary relationship set is a relationship set where three entity sets participate in a relationship set.

Example-

4. N-ary Relationship Set-

N-ary relationship set is a relationship set where ‘n’ entity sets participate in a relationship set.

Next Article- Cardinality in ER Diagram

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Graph Isomorphism | Isomorphic Graphs | Examples | Problems

Graph Theory

Graph Isomorphism-

Graph Isomorphism is a phenomenon of existing the same graph in more than one forms.

Such graphs are called as Isomorphic graphs.

Graph Isomorphism Example-

Here,

The same graph exists in multiple forms.
Therefore, they are Isomorphic graphs.

Graph Isomorphism Conditions-

For any two graphs to be isomorphic, following 4 conditions must be satisfied-

Number of vertices in both the graphs must be same.
Number of edges in both the graphs must be same.
Degree sequence of both the graphs must be same.
If a cycle of length k is formed by the vertices { v₁ , v₂ , ….. , v_k} in one graph, then a cycle of same length k must be formed by the vertices { f(v₁) , f(v₂) , ….. , f(v_k) } in the other graph as well.

Degree Sequence

Degree sequence of a graph is defined as a sequence of the degree of all the vertices in ascending order.

Important Points-

The above 4 conditions are just the necessary conditions for any two graphs to be isomorphic.
They are not at all sufficient to prove that the two graphs are isomorphic.
If all the 4 conditions satisfy, even then it can’t be said that the graphs are surely isomorphic.
However, if any condition violates, then it can be said that the graphs are surely not isomorphic.

Sufficient Conditions-

The following conditions are the sufficient conditions to prove any two graphs isomorphic.

If any one of these conditions satisfy, then it can be said that the graphs are surely isomorphic.

Two graphs are isomorphic if and only if their complement graphs are isomorphic.
Two graphs are isomorphic if their adjacency matrices are same.
Two graphs are isomorphic if their corresponding sub-graphs obtained by deleting some vertices of one graph and their corresponding images in the other graph are isomorphic.

PRACTICE PROBLEMS BASED ON GRAPH ISOMORPHISM-

Problem-01:

Are the following two graphs isomorphic?

Solution-

Checking Necessary Conditions-

Condition-01:

Number of vertices in graph G1 = 4
Number of vertices in graph G2 = 4

Here,

Both the graphs G1 and G2 have same number of vertices.
So, Condition-01 satisfies.

Condition-02:

Number of edges in graph G1 = 5
Number of edges in graph G2 = 6

Here,

Both the graphs G1 and G2 have different number of edges.
So, Condition-02 violates.

Since Condition-02 violates, so given graphs can not be isomorphic.

∴ G1 and G2 are not isomorphic graphs.

Problem-02:

Which of the following graphs are isomorphic?

Solution-

Checking Necessary Conditions-

Condition-01:

Number of vertices in graph G1 = 4
Number of vertices in graph G2 = 4
Number of vertices in graph G3 = 4

Here,

All the graphs G1, G2 and G3 have same number of vertices.
So, Condition-01 satisfies.

Condition-02:

Number of edges in graph G1 = 5
Number of edges in graph G2 = 5
Number of edges in graph G3 = 4

Here,

The graphs G1 and G2 have same number of edges.
So, Condition-02 satisfies for the graphs G1 and G2.
However, the graphs (G1, G2) and G3 have different number of edges.
So, Condition-02 violates for the graphs (G1, G2) and G3.

Since Condition-02 violates for the graphs (G1, G2) and G3, so they can not be isomorphic.

∴ G3 is neither isomorphic to G1 nor G2.

Since Condition-02 satisfies for the graphs G1 and G2, so they may be isomorphic.

∴ G1 may be isomorphic to G2.

Now, let us continue to check for the graphs G1 and G2.

Condition-03:

Degree Sequence of graph G1 = { 2 , 2 , 3 , 3 }
Degree Sequence of graph G2 = { 2 , 2 , 3 , 3 }

Here,

Both the graphs G1 and G2 have same degree sequence.
So, Condition-03 satisfies.

Condition-04:

Both the graphs contain two cycles each of length 3 formed by the vertices having degrees { 2 , 3 , 3 }
It means both the graphs G1 and G2 have same cycles in them.
So, Condition-04 satisfies.

Thus,

All the 4 necessary conditions are satisfied.
So, graphs G1 and G2 may be isomorphic.

Now, let us check the sufficient condition.

Checking Sufficient Condition-

We know that two graphs are surely isomorphic if and only if their complement graphs are isomorphic.

So, let us draw the complement graphs of G1 and G2.

The complement graphs of G1 and G2 are-

Clearly, Complement graphs of G1 and G2 are isomorphic.

∴ Graphs G1 and G2 are isomorphic graphs.

Problem-03:

Are the following two graphs isomorphic?

Solution-

Checking Necessary Conditions-

Condition-01:

Number of vertices in graph G1 = 8
Number of vertices in graph G2 = 8

Here,

Both the graphs G1 and G2 have same number of vertices.
So, Condition-01 satisfies.

Condition-02:

Number of edges in graph G1 = 10
Number of edges in graph G2 = 10

Here,

Both the graphs G1 and G2 have same number of edges.
So, Condition-02 satisfies.

Condition-03:

Degree Sequence of graph G1 = { 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 }
Degree Sequence of graph G2 = { 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 }

Here,

Both the graphs G1 and G2 have same degree sequence.
So, Condition-03 satisfies.

Condition-04:

In graph G1, degree-3 vertices form a cycle of length 4.
In graph G2, degree-3 vertices do not form a 4-cycle as the vertices are not adjacent.

Here,

Both the graphs G1 and G2 do not contain same cycles in them.
So, Condition-04 violates.

Since Condition-04 violates, so given graphs can not be isomorphic.

∴ G1 and G2 are not isomorphic graphs.

To gain better understanding about Graph Isomorphism,

Watch this Video Lecture

Next Article- Complement of Graph

Get more notes and other study material of Graph Theory.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Cardinality in ER Diagram | DBMS

Database Management System

Cardinality Constraint-

Before you go through this article, make sure that you have gone through the previous article on Introduction to ER Diagrams.

Cardinality constraint defines the maximum number of relationship instances in which an entity can participate.

Types of Cardinality Ratios-

There are 4 types of cardinality ratios-

Many-to-Many cardinality (m:n)
Many-to-One cardinality (m:1)
One-to-Many cardinality (1:n)
One-to-One cardinality (1:1 )

Also read- Relationship Sets in DBMS and Entity Sets in DBMS

1. Many-to-Many Cardinality-

By this cardinality constraint,

An entity in set A can be associated with any number (zero or more) of entities in set B.
An entity in set B can be associated with any number (zero or more) of entities in set A.

Symbol Used-

Example-

Consider the following ER diagram-

Here,

One student can enroll in any number (zero or more) of courses.
One course can be enrolled by any number (zero or more) of students.

2. Many-to-One Cardinality-

By this cardinality constraint,

An entity in set A can be associated with at most one entity in set B.
An entity in set B can be associated with any number (zero or more) of entities in set A.

Symbol Used-

Example-

Consider the following ER diagram-

Here,

One student can enroll in at most one course.
One course can be enrolled by any number (zero or more) of students.

3. One-to-Many Cardinality-

By this cardinality constraint,

An entity in set A can be associated with any number (zero or more) of entities in set B.
An entity in set B can be associated with at most one entity in set A.