De Morgan's laws

From TCS Wiki
Jump to navigation Jump to search

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

[math]\displaystyle{ \overline{A \cdot B} = \overline {A} + \overline {B} }[/math]
[math]\displaystyle{ \overline{A + B} = \overline {A} \cdot \overline {B} }[/math]

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:Reflist


Template:Math-stub