Computer Science 161.01

Professor Valente

 

Friday September 8th       

 

READING:  Section 4.1 pages 77-83.

 

 

Logical Operations

 

In addition to arithmetic operations, one can also performed logical operations on bits.

 

The trick to understanding the logic is to think of the logic of AND, OR, and NOT when applied to sentences,

where each sentence may be true or false.

 

For example,

 

“It is the year 2017” is a true sentence. 

 So is the sentence “Hampden-Sydney is in Virginia”.

 

“The Jets won the Super Bowl last year” is a false sentence.

So is the sentence “Hampden-Sydney is a women’s college”.

 

A compound sentence can be made by combining two sentences using AND or OR.

 

It is the year 2017 AND the Jets won the Super Bowl last year.

Combines true AND false.   The resulting compound sentence is false.

 

So, in logic, true AND false   =  false.

With bits, we’ll use 1 to represent true and 0 to represent false.

Thus, 1 AND 0 = 0.

Also, 0 AND 1 = 0

because it doesn’t matter if the false statement precedes AND.

 

What about 0 AND 0?   That’s 0 too.

What about 1 AND 1?  

That’s 1, because “It is 2017 AND Hampden-Sydney is in Virginia” is a true sentence.

Thus, 1 AND 1 = 1.

 

We’ll summarize AND with a truth table. 

Think of A, B as phrases within a sentence and A AND B as the complete sentence.

 

A         B         A AND B

0          0                 0

0          1                 0

1          0                 0

1          1                 1

 

 

When we combine statements with OR, we’ll regard the compound sentence to be true

whenever at least one of the statements is true, and false otherwise.

 

“Hampden-Sydney is in Virginia OR the Jets won the Super Bowl this year”

is a true statement.   So 1 OR 0 = 1.

 

By constructing other examples as well, you’ll convince yourself that the truth table for OR

is as follows:

 

A         B         A OR B

0          0                0

0          1                1

1          0                1

1          1                1

 

The OR is said to be “inclusive” because it allows both A,B to be true.

 

By contrast, “exclusive OR” (abbreviated XOR) does not allow both A,B to be true.

It’s A or B but not both!

 

A         B         A  XOR B

0          0                  0

0          1                  1

1          0                  1

1          1                  0

 

Another way to look at XOR is that it tells us when A,B are different!

So it says 1 when A=0, B=1, and when A=1, B=0.

 

The last binary operation is NOT.  It is simple in that it acts on one phrase.

For example,

The Mets won the World Series last year is false, or 0.

 

 NOT(The Mets won the World Series last year) means

“It is NOT the case that the Mets won the World Series last year”.

Of course, this is true (as it has been every year since 1986).

So NOT 0 = 1 and NOT 1 = 0.  

 

As you can see, there’s not a lot to NOT.

 

Now, if you’re presented these operations with two 8-bit patterns, don’t worry!

You simply treat each column individually as having an A and a B, then apply the operation according to its truth table.

 

For example, xA3 AND x2E is

 

10100011

AND   00101110

            -------------

So,       00100010 ,  which is x22.

 

You can practice all arithmetic and logic operations on 8-bit patterns here!