Visit
www.annedawson.net 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)