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`
`#  http://www.coquitlamcollege.com/adawson/DeMorgansLaws.htm`
` `
`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)`