DEV Community: Dipto Biswas

Important Rules of Boolean Algebra

Dipto Biswas — Sat, 02 Mar 2024 08:56:06 +0000

Definition of Boolean Algebra

Boolean Algebra are a set of rules that are used to simplify a complex logic expression without changing it's functionality.
Boolean Algebra was introduced by the English Mathematician George Boole in 1847.

Rules of Boolean Algebra

Complement Rule: Example - 0' = 1, 1' = 0, (A')' = A,
AND Rule: Example - A.A = A, A.0 = 0, A.1 = A, A.A' = 0,
OR Rule: Example - A + A = A, A + 0 = A, A + 1 = 1, A + A' = 1,
Distributive Law: Example - A(B + C) = A.B + A.C, A + B.C = (A + B)(A + C), A + A'.B = A + B, Similarly, A' + A.B = A' + B,
Commutative Law: Example - A + B = B + A, A.B = B.A,
Associative Law: Example - (A.B)C = A(B.C),
De Morgan's Law: Example - (A + B)' = A'.B', (A.B)' = A' + B',
Redundancy Theorem or Consensus Theorem: Redundancy Theorem is a trick but it will only apply when all the below conditions are satisfied.

Three variables must be present
Each variable must be repeated twice
One variable must be complimented

Then we can keep the complimented variable and remove the extra variable which is the redundant variable.
A.B + A'.C + B.C = A.B + A'.C

Priority of Logic Gates

When we have multiple Logic Gates in a Digital Circuit or Logical Operation it follows the below priority or order of execution:

Conclusion

Above rules help us greatly minimizing Boolean Algebraic expressions, which in real-life translates to less cost, and more hardware efficiency.

Introduction To Digital Electronics

Dipto Biswas — Wed, 28 Feb 2024 21:30:18 +0000

Introduction

Let's learn about the lowest level of computing, and that is Digital Circuits. And let's start by understanding few key concepts.

What is Signal?

Signal is a function that represents the variation of a physical quantity with respect to a parameter.
In Electronics, Signal is a variation of Electrical quantity with respect to time.

What is Analog Signal?

Signals that represent information in a continuous range are called Analog Signals. e.g. Temperature at a given point of time.

What is Digital Signal?

Signals that represent information in a sequence of discrete values are called Digital Signals. e.g. Temperature at a given point of time is hot or cold.

What is Discrete Time Signal?

Signals that represent information in discrete time intervals is called Discrete Time Signal. e.g. Temperature everyday at 9 am in the morning.

What is Noise?

Noise is an unwanted Signal. e.g. what irritates us in phone calls, or video calls.

What is a Digital System?

A Digital System is a system that processes Digital Signals to perform various kinds of Operations. e.g. Computer, Calculator, etc. are Digital Systems. Digital Systems follow below hierarchy.
Digital System -> Sub-systems -> Modules -> Units (Logic Gates) -> Circuits (Transistors)

Advantages of Digital Signals Over Analog Signals

All real-life signals are analog signals. We have to convert them to Digital signals. It costs money, but is worth it! Let's understand how.

Digital Signals can cancel out smaller amounts of noise and give accurate information because it represents data in a sequence of discrete values.
Digital Signals can be processed and used easily by us. Analog Signals are complex and sometimes too difficult to use.
Digital Signals are a sequence of discrete values and hence can be easily reproduced when required. To give a more Philosophical example you can replay a video game, try out as well as copy different strategies, but it's not possible doing the same in the game of life.
There are more advantages also, like the use of less bandwidth, encryption, etc.

What is a Switch?

Switch is a Device that can connect and disconnect an Electrical circuit.
We can create layers of discrete values using switches. For example with only 1 switch we have either on or off, 1 or 0, 2 values. But with 2 switches we have 11, 10, 01, 00, 4 values. With 3 swiches we have 111, 110, 101, 100, 011, 010, 001, 000, 8 values. For n switches we have 2 ** n values.
Hence switch becomes an integral part of Digital Electronics.

Conclusion

These are some of the basic terminologies we should be familiar with and going forward we'll delve deep into Digital Electronics. Cheers!

Theory Of Computation: Some Terminologies

Dipto Biswas — Sun, 18 Feb 2024 16:24:00 +0000

Introduction

Let's discuss about some terminologies related to Theory of Comutation, that'll help us understanding the subject better.

Terminologies

Symbol is a single character. e.g. 0, 1, 2, a, b, x, y, etc.
Alphabet is a collection of symbols. Alphabets are also denoted by Sigma. e.g. {a, b}, {0, 1, 2}, {1, 2, x, y}, etc.
String is a sequence of symbols. e.g. abc, abcd, xy, xyz, a1b2, etc.
Language is a set of Strings.
To give an example of Language consider an Alphabet: {a, b}
We can have a set of Strings that start with a: {a, aa, ab, aab, aba, ...}
This is a language.
Now we can also have a finite set. Consider a set of Strings of length 3: {aaa, aab, abb, aba, bbb, bba, baa, bab}
This is also a language.
Cardinality is the number of elements in a set.
So for the above examples of language, cardinality is infi and 8 respectively.
Sigma Star is the set of all possible Strings of all lengths over an alphabet {0, 1}

Conclusion

Getting to know about these terminologies will surely help you a lot in grasping the more complex concepts in Theory of Computation. So see you there!

Theory Of Computation: Solvable And Unsolvable Problems

Dipto Biswas — Sun, 18 Feb 2024 09:13:53 +0000

Introduction

When we write Programs, we have seen that there are some programs that takes little time to execute, then there are other programs that take a lot of time to execute. So it's fair to conclude that there are easy problems, and there are difficult problems for Computers to solve.
Now we'll go a step ahead, and discuss about problems that Computers can solve, and about problems that Computers cannot solve. So all of our easy and difficult problems, will be falling under the category of problems that Computers can solve. Then there are unsolvable pronlems.
Theory of Computation is the study of problems that can be solved mechanically, also the speed, and the space taken by the solution.

Examples

A good example of solvable problem is given a number as an input, we have to determine whether the number is divisible by 3 or not. This is a solvable problem.
Another example is, given a code we have to find out if it is Python code. This is also a solvable problem. The solution is what we call compilers.
Now one example of an unsolvable problem is, given a program, can we find out if the program will be stuck in an infinite loop. It may sound simple, but we cannot solve this problem, hence it's an unsolvable problem.

What do we do in Theory of Computation?

In the subject of Theory of Computation, we design systems based on some rules, that takes an input, and gives the output as either yes or no. Yes, means the problem can be solved, no means the problem cannot be solved.
Now among these systems, there are different layers:

Finite State Machine (FSM) is the simplest model of Computation.
Context-Free Language (CFL) is a level-above FSM. Langauge in CFL is not a Programming language, it is more like our real languages.
Turing Machine is a powerful Computational Model. We may have heard about it many times in the context of AI.
Undecided is our unsolvable problems.

Conclusion

This is Theory of Computation in brief. In the upcoming Blogs we'll delve deeper into it.