Question

State and prove De Morgan’s theorems.

Answer 1

Hint: A gate can have multiple inputs but it gives a single output. De Morgan’s laws tell us about the output of complementary addition of binary numbers or the complementary product of binary numbers. We can prove De Morgan’s theorems by creating a truth table for the operations involved.
Complete step-by-step solution:
Gates are circuits which take single or multiple binary inputs and perform logical operations on them to give a single binary output.

The inputs and outputs are binary because it can take only two values-$0$ and $1$.

Let $A$ and $B$ be two binary inputs then the operations that can be performed on them are-
$\begin{align}
  & A+B=A\bigcup B \\
 & A\cdot B=A\bigcap B\, \\
\end{align}$
Also, operations on binary numbers are performed in the following ways-
$\begin{align}
  & 1+0=1 \\
 & 1+1=1 \\
 & 0+1=1 \\
 & 0+0=0 \\
 & 1\times 0=0 \\
 & 0\times 1=0 \\
 & 0\times 0=0 \\
 & 1\times 1=1 \\
\end{align}$

Complementary to a binary number is the inverted value of the number. If $A=1$, then $\overline{A}=0$ and vice versa.

De Morgan’s theorem states that when we take the whole complement of product of some terms then the result is equal to the sum of complement of terms, therefore,
$\overline{A\cdot B}=\overline{A}+\overline{B}$

We can prove the following theorem by using a truth table

Inputs	Truth table outputs for each term
A	B	$\overline{A}$	$\overline{B}$	$A\cdot B$	$\overline{A\cdot B}$	$\overline{A}+\overline{B}$
1	1	0	0	1	0	0
1	0	0	1	0	1	1
0	1	1	0	0	1	1
0	0	1	1	0	1	1

From the above table we can see that the result $\overline{A\cdot B}=\overline{A}+\overline{B}$ holds true.

Similarly, the complement of sum of all the terms is the product of complement of terms. Therefore,
$\overline{A+B}=\overline{A}\cdot \overline{B}$

We can prove the following theorem by using a truth table

Inputs	Truth table outputs for each term
A	B	$\overline{A}$	$\overline{B}$	$A+B$	$\overline{A+B}$	$\overline{A}\cdot \overline{B}$
1	1	0	0	1	0	0
1	0	0	1	1	0	0
0	1	1	0	1	0	0
0	0	1	1	0	1	1

From the above table we can see that the result $\overline{A+B}=\overline{A}\cdot \overline{B}$ holds true.

Therefore, according to De Morgan’s theorems, taking the complement of numbers in an operation, inverts the numbers as well as the operation. De Morgan’s theorems are given by- $\overline{A\cdot B}=\overline{A}+\overline{B}$ and $\overline{A+B}=\overline{A}\cdot \overline{B}$.

Note:
Different gates can perform different operations and their results can be seen in their truth tables. OR gate gives 0 only when both inputs are 0. And gate gives 1 as output only when both inputs are 1. NOT gate inverts the input. XOR gate gives output as 1 when only one of the inputs is 1. These gates can be used to make combinations of gates