# De Morgan's Theorem

## De Morgan's Theorem 1:

The complement of the sum of two or more variables is equal to the product of the complement of the variables.

## De Morgan's Theorem 2:

The complement of the product of two or more variables is equal to the sum of the complements of the variables.

For two variables A and B these theorems are written in Boolean notation as follows

The two theorems are proved below.

To prove

Since each variable can have a value either 0 or 1, the following four cases arise:

Since, in every case the left hand side equals the right hand side, the theorem is proved.

To prove

Since each variable can have a value either 0 or 1, the following four cases arise:

As all possible combinations of A and B are exhausted, the theorem is proved.

## Consensus:

Let us prove part (a) algebrically,

Part (b) is the dual of part (a) and can be similarly proved.

If we want to prove that (b) by truth table method, we can do so by enumerating all the eight possible combinations.

A | B | C | A+B | +C | B+C | LHR | RHS |
---|---|---|---|---|---|---|---|

0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |

0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |

0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |

1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |

1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |