Difference between revisions of "CSC103: DT's Notes 1"

From dftwiki3
Jump to: navigation, search
Line 69: Line 69:
 
|-
 
|-
 
|
 
|
−
===Counting in Decimal===
+
====Counting in Decimal====
 
|}
 
|}
 
<br />
 
<br />
Line 132: Line 132:
 
</tanbox>
 
</tanbox>
  
−
=====Counting in Binary=====
+
<br />
 +
{| style="width:100%; background:#BF9230"
 +
|-
 +
|
 +
====Counting in Binary====
 +
|}
 +
<br />
  
 
Let's now count in ''base'' 2, in binary.  This time our "internal" table contains only 2 digits: 0, 1.  So, whatever we do, we can only use 0 and 1 to write numbers.  And the list of numbers we use and from which we'll "roll-over" is simply: 0, 1.
 
Let's now count in ''base'' 2, in binary.  This time our "internal" table contains only 2 digits: 0, 1.  So, whatever we do, we can only use 0 and 1 to write numbers.  And the list of numbers we use and from which we'll "roll-over" is simply: 0, 1.
Line 183: Line 189:
 
  ...
 
  ...
  
−
=====Exercise=====
+
<tanbox>
 +
;Exercise
 +
 
  
−
How would we count in base 3?  The answer is that we just need to modify our table of available digits to be 0, 1, 2, and apply the rule we developed above.  Here is a start:
+
:How would we count in base 3?  The answer is that we just need to modify our table of available digits to be 0, 1, 2, and apply the rule we developed above.  Here is a start:
  
 
  0000
 
  0000
Line 194: Line 202:
  
 
Does that make sense?  Continue and write all the numbers until you reach 1000, in base 3.
 
Does that make sense?  Continue and write all the numbers until you reach 1000, in base 3.
 +
</tanbox>
 +
  
 +
<br />
 +
{| style="width:100%; background:#BF9230"
 +
|-
 +
|
 
====Evaluating Binary Numbers====
 
====Evaluating Binary Numbers====
 +
|}
 +
<br />
  
 
What is the decimal equivalent of the binary number 11001 in decimal?  To find out, we return to the decimal system and see how we evaluate, or find the value represented by a decimal number.  For example:
 
What is the decimal equivalent of the binary number 11001 in decimal?  To find out, we return to the decimal system and see how we evaluate, or find the value represented by a decimal number.  For example:
Line 224: Line 240:
  
  
 +
<br />
 +
{| style="width:100%; background:#BF9230"
 +
|-
 +
|
 
====Binary Arithmetic====
 
====Binary Arithmetic====
 +
|}
 +
<br />
  
 
So far, we can count in binary, and we now how to find the decimal value of a binary number.  But could we perform arithmetic with binary numbers?  If we can, then we're that much closer to figure out how to build a computer that can perform computation.  Remember, that's our objective in this chapter: try to understand how something build with electronic circuits that operate with electricity that can be turned on or off can be used to perform the addition of numbers.  If we can add numbers, surely we can also multiply, subtract, divide, and we have an electronic calculator.
 
So far, we can count in binary, and we now how to find the decimal value of a binary number.  But could we perform arithmetic with binary numbers?  If we can, then we're that much closer to figure out how to build a computer that can perform computation.  Remember, that's our objective in this chapter: try to understand how something build with electronic circuits that operate with electricity that can be turned on or off can be used to perform the addition of numbers.  If we can add numbers, surely we can also multiply, subtract, divide, and we have an electronic calculator.
Line 357: Line 379:
 
So, in summary, it doesn't matter if we are limited to having only two digits, we can still count, represent numbers, and do arithmetic.
 
So, in summary, it doesn't matter if we are limited to having only two digits, we can still count, represent numbers, and do arithmetic.
  
−
====Summary of Where we Are====
+
<br />
−
 
+
{| style="width:100%; background:#FFD373"
 +
|-
 +
|
 +
===Summary of Where we Are===
 +
|}
 +
<br />
 
Let's summarize what we now and what we're after.  We know that electricity is cheap, easy to control, a great source of power, and that we can easily build switches that can control voltages over wire.  We know that we can create a code associating 1 to electricity being ON and 0 to electricity being OFF in a wire.  So electricity can be used to represent the numbers 0 and 1.
 
Let's summarize what we now and what we're after.  We know that electricity is cheap, easy to control, a great source of power, and that we can easily build switches that can control voltages over wire.  We know that we can create a code associating 1 to electricity being ON and 0 to electricity being OFF in a wire.  So electricity can be used to represent the numbers 0 and 1.
  
Line 371: Line 398:
 
We'll now look at Boole and Shannon separately.
 
We'll now look at Boole and Shannon separately.
  
−
====Boole and the Boolean Algebra====
+
 
 +
<br />
 +
{| style="width:100%; background:#FFD373"
 +
|-
 +
|
 +
===Boole and the Boolean Algebra===
 +
|}
 +
<br />
  
 
Boole's contribution is a major one  in the history of computers.  In the 1840s, he conceived of a mathematical world where there would be only two symbols, two values, and three operations that could be performed with them, and he proved that such a system could exhibit the same rules exhibited by an algebra.  The two values used by Boole's algebra are ''True'' and ''False'', or ''T'' and ''F'', and the operators are ''and'', ''or'' and ''not''.  Boole was in fact interested in logic, and expressing combinations of statements that can either be true or false, and figuring out whether mathematics could be helpful in formulating a logic system where we could express any logical expression containing multiple simple statements that could be either true or false.
 
Boole's contribution is a major one  in the history of computers.  In the 1840s, he conceived of a mathematical world where there would be only two symbols, two values, and three operations that could be performed with them, and he proved that such a system could exhibit the same rules exhibited by an algebra.  The two values used by Boole's algebra are ''True'' and ''False'', or ''T'' and ''F'', and the operators are ''and'', ''or'' and ''not''.  Boole was in fact interested in logic, and expressing combinations of statements that can either be true or false, and figuring out whether mathematics could be helpful in formulating a logic system where we could express any logical expression containing multiple simple statements that could be either true or false.
Line 476: Line 510:
 
When ''a'' is true, '''not''' ''a'' is false, and conversely.  
 
When ''a'' is true, '''not''' ''a'' is false, and conversely.  
  
 +
<br />
 
<tanbox>
 
<tanbox>
−
====An Example and Exercise====
+
;An Example and Exercise====
 +
<br />
 +
Assume we want to build a logical machine that can use the logical operators '''and''', '''or''' and '''not''' to help us buy ice cream for a friend.  The friend in question has very specific taste, and likes ice cream with chocolate in it, ice cream with fruit in it, but not Haagen Dazs ice cream.  This example and exercise demonstrate how we can build such a "machine".
 +
 
 
</tanbox>
 
</tanbox>
 +
<br />
 
[[Image:IceCreamContainer.jpg|right|200px]]
 
[[Image:IceCreamContainer.jpg|right|200px]]
−
Assume we want to build a logical machine that can use the logical operators '''and''', '''or''' and '''not''' to help me buy ice cream for a friend.  The friend in question has very specific taste, and likes ice cream with chocolate in it, ice cream with fruit in it, but not Haagen Dazs ice cream.  So we can devise three boolean variables that can be true of false depending on three properties of a container of ice cream: ''choc'', ''fruit'', and ''HG''.  ''choc'' is true if the ice cream contains some chocolate.  ''fruit'' is true if the ice cream contains fruits, and ''HG'' is true if the ice cream is from Haagen Dazs.  A boolean function, or expression, we're going to call it ''isgood'', containing ''choc'', ''fruit'', and ''HG'' that turns true whenever the ice cream is one our friend will like would be this:
+
We can devise three boolean variables that can be true of false depending on three properties of a container of ice cream: ''choc'', ''fruit'', and ''HG''.  ''choc'' is true if the ice cream contains some chocolate.  ''fruit'' is true if the ice cream contains fruits, and ''HG'' is true if the ice cream is from Haagen Dazs.  A boolean function, or expression, we're going to call it ''isgood'', containing ''choc'', ''fruit'', and ''HG'' that turns true whenever the ice cream is one our friend will like would be this:
  
 
''isgood'' = ( ''choc'' '''or''' ''fruit'' ) '''and''' ( '''not''' ''HG'' )
 
''isgood'' = ( ''choc'' '''or''' ''fruit'' ) '''and''' ( '''not''' ''HG'' )
Line 567: Line 606:
 
;Question 4 (challenging)
 
;Question 4 (challenging)
 
: Can you find an ice cream flavor and maker that both our friend and his/her younger brother will like?
 
: Can you find an ice cream flavor and maker that both our friend and his/her younger brother will like?
 +
 +
<br />
 +
{| style="width:100%; background:#FFD373"
 +
|-
 +
|
 +
===Shannon's MIT Master's Thesis: the missing link===
 +
|}
 +
<br />
  
  
−
===Shannon's MIT Master's Thesis: the missing link===
 
  
 
We are now coming to Shannon, who's influence on the field of computer science is quite remarkable, and whose contribution of possibly greatest influence was his Master's thesis at MIT, written in 1948.
 
We are now coming to Shannon, who's influence on the field of computer science is quite remarkable, and whose contribution of possibly greatest influence was his Master's thesis at MIT, written in 1948.
Line 688: Line 734:
 
So, here we are with our premises about our current computers and why they work.  We have answered important questions and made significant discoveries, which we summarize below
 
So, here we are with our premises about our current computers and why they work.  We have answered important questions and made significant discoveries, which we summarize below
  
−
==Discoveries==
+
 +
<br />
 +
{| style="width:100%; background:#FFD373"
 +
|-
 +
|
 +
===Discoveries===
 +
|}
 +
<br />
 
* Computers use electricity as a source of power, and use flows of electrons (electric currents) to convey information.   
 
* Computers use electricity as a source of power, and use flows of electrons (electric currents) to convey information.   
 
* Switches are used to control the flow of electrons, creating a system of two values based on whether the flow is ON or OFF.
 
* Switches are used to control the flow of electrons, creating a system of two values based on whether the flow is ON or OFF.
Line 695: Line 748:
 
* logic operator are easy to generate with electronic switches
 
* logic operator are easy to generate with electronic switches
 
* arithmetic operations in binary can be expressed using the operators of the boolean algebra.
 
* arithmetic operations in binary can be expressed using the operators of the boolean algebra.
−
=References=
+
 
 +
 
 +
 
 +
 
 +
{| style="width:100%; background:#FFC340"
 +
|-
 +
|
 +
==References==
 +
|}
 
<references />
 
<references />
 
</onlysmith>
 
</onlysmith>

Revision as of 11:57, 5 February 2012

--© D. Thiebaut 08:10, 30 January 2012 (EST)


This section is only visible to computers located at Smith College













Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC103:_DT%27s_Notes_1&oldid=13494"