De Morgan's laws

In boolean algebra, DeMorgan's laws are the laws of how a NOT gate affects AND and OR statements:

$\overline{A\cdot B}=\bar{A}+\bar{B}$

$\overline{A+B}=\bar{A}\cdot \bar{B}$

They can be remembered by "break the line, change the sign".

Truth tables

The following truth tables prove DeMorgan's laws.

INPUT		OUTPUT 1	OUTPUT 2
A	B	NOT (A AND B)	(NOT A) OR (NOT B)
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

INPUT		OUTPUT 1	OUTPUT 2
A	B	NOT (A OR B)	(NOT A) AND (NOT B)
0	0	1	1
0	1	0	0
1	0	0	0
1	1	0	0

References

Template:Math-stub