Visit
for more Computer Science Education resources

Last updated: Saturday 28th February 2009, 11:40 PT by AHD

De Morgan's Laws

1)  a Not And is equivalent to an Or with two negated inputs

2) a Not Or is equivalent to an And with two negated inputs

Examples:

In C:

(!(x < 15 && y >= 3) has the same value as (x >= 15 || y < 3)

for any value of x and y

In C++:

(!(x < 15 && y >= 3) has the same value as (x >= 15 || y < 3)

for any value of x and y

In Java:

(!(x < 15 && y >= 3) has the same value as (x >= 15 || y < 3)

for any value of x and y

In Visual Basic:

(Not(x < 15 And y >= 3) has the same value as (x >= 15 Or y < 3)

for any value of x and y

In Python:

(not(x < 15 and y >= 3) has the same value as (x >= 15 or y < 3)

for any value of x and y (see example program below)

De Morgan's Laws are based on the relationship between the And and the Or operators.

Study the outputs of their truth tables. Note that 0 represents false and 1 represents true.

And

Operand A          Operand B          Result

0                     0             0

0                     1             0

1                     0             0

1                     1             1

Or

Operand A          Operand B          Result

0                     0             0

0                     1             1

1                     0             1

1                     1             1

Notice that the results of both operators are complementary:

0001

1110

It is on this relationship that De Morgan's Laws are based.

Python Program demonstrating De Morgan's Laws:

#  File:       04-16.py
#  Purpose:    Demo of DeMorgan's Laws:
#  1.  a Not And is equivalent to an Or with two negated inputs
#  2.  a Not Or is equivalent to an And with two negated inputs
#  Programmer: Anne Dawson
#  Course:     CSCI120A
#  Date:       Monday 21st March 2005, 05:53 PT
#  Test data: 0 0, 0 1, 1 0, 1 1
#  For ***any*** value of x and y, (not(x < 15 and y >= 3)) == (x >= 15 or y < 3)
#  Common uses of De Morgan's rules are in digital circuit design
#  where it is used to manipulate the types of logic gates.
#  Also, computer programmers use them to change a complicated statement
#  like IF ... AND (... OR ...) THEN ... into its opposite (and shorter) equivalent.
#  http://en.wikipedia.org/wiki/De_Morgan%27s_law

x = int(raw_input("Enter a value for x: "))
y = int(raw_input("Enter a value for y: "))
print (not(x < 15 and y >= 3))
print (x >= 15 or y < 3)