Ana səhifə

De Morgan's laws or De Morgan's theorem


Yüklə 12.63 Kb.
tarix04.05.2016
ölçüsü12.63 Kb.

DeMorgan’s Theorem



Objective:

Students will be able evaluate DeMorgan’s’ Theorem.


Background

In logic, De Morgan's laws (or De Morgan's theorem) are rules in formal logic relating pairs of dual logical operators in a systematic manner expressed in terms of negation. The relationship so induced is called De Morgan duality. To give some intuition, suppose P is true if and only if it is raining and Q is true if and only if you are wearing a raincoat . Consider the following situation- It's not raining, so you don't care whether you're wearing a raincoat or not. In symbols, this would be written (Not P) or Q

Moreover, DeMorgan’s Theorems can help new programmers develop correct expressions for if statements. Thus, we can use DeMorgan’s Law to find the logical negation (NOT), or opposite, of an expression formed with the logical operators && and ||. There are numerous identities that deal with compound Boolean expressions. However, DeMorgan's Laws are use usfful negate compound Boolean expressions.

DeMorgan’s Law


! ( A&& B) = (!A) || (!B)

!(A||B) = (!A) && (!B)


  Notice that it is similar to the distributive postulate in mathematics. The not operator is distributed among both terms inside of the parentheses, except the operator switches from and to or, or vice versa.

  not (A and B) = not A or not B

  not (A or B) = not A and not B
In evaluating DeMorgan’s expressions the following rules need to be followed:
(1) Change all and’s to or’s and all or’s to and’s.

(2) Negate (!) each individual element.

(3) Negate (!) the entire expression.

(4) Eliminate all double Negatations (!!).


Example: !(A||B)=

1. !(A&B )

2. !(!A & !B)

3. !!(!A & !B)

4. (!A & !B)

Exercises

1. !(A&& B)

2. !((X>Y) && (Y <= 3))

3. (X1) && (!X2) + (X1) && (!X2)


4. (2< X) && ( X < 7)



5. (Y<0) || ( Y> 12)

Solutions

1. ! (A && B)

A. !(A||B)

B. !(!A|| !B)

C. !!(!A||!B)

D. (!A||B)
2. !(( X > Y) && (Y <=3))

A. !(( X > Y) || (Y <=3))

B. !(!( X > Y) || !(Y <=3))

C. !!(!( X > Y) || !(Y <=3))

  1. (( X < =Y) || (Y >3))


3. (X1 ) & & (!X2) + ( X1) && (!X3)
A. (X1 )|| (!X2) + ( X1) ||(!X3)

  1. (!X1 )|| (!!X2) + ( !X1) ||(!!X3)

  2. !((!X1 )|| (!!X2) + ( !X1) ||(!!X3))

  3. !((!X1 )|| (X2) + ( !X1) ||(X3))


4. (2 < X) && (X < 7)


  1. (2 < X) || (X < 7)

  2. (!2 < X) || (!X < 7)

  3. (!(!2 < X) || (!X < 7))

  4. (!(2 < = X) || (X >= 7))


5. (Y < 0)|| (Y >12)


  1. (Y < 0)&&(Y >12)

  2. (!Y < 0)&&(!Y >12)

  3. !((!Y < 0)&&(!Y >12))

  4. !((Y >=0)&&(Y < =12))



References
Krane, R. R. (2000) LESSON 17: Boolean Algebra - Retrieved September 25, 2006 from the World Wide Webshttp://dimacs.rutgers.edu/~rkrane/clecs/ict/Lesson17/cppl17.htm
Osborne, L. (2003) Fundamental of Java United States) Thomson Learning
Owen L. Astrachan (2000) Computer Science Tapestry McGraw-Hill



Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©anasahife.org 2016
rəhbərliyinə müraciət