Difference between revisions of "CSC103: DT's Notes 1"
| Line 38: | Line 38: | ||
The answers to these questions, and the ensuing solutions are provided by two giants of computer science, '''George Boole''', and '''Claude Shannon''' who worked at very different times. | The answers to these questions, and the ensuing solutions are provided by two giants of computer science, '''George Boole''', and '''Claude Shannon''' who worked at very different times. | ||
| − | Boole's contribution was first 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's contribution was first 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. |
| + | |||
| + | While this seems something more interesting to philosophers than mathematicians or engineers, this system is the foundation of modern electronic computers. | ||
| + | |||
| + | Each of the boolean operators can be expressed by a truth table. | ||
| + | |||
| + | {| border="1" cellpadding="10" cellspacing="0" | ||
| + | ! a | ||
| + | ! b | ||
| + | ! a '''and''' b | ||
| + | |- | ||
| + | F | ||
| + | | | ||
| + | F | ||
| + | | | ||
| + | F | ||
| + | |- | ||
| + | F | ||
| + | | | ||
| + | T | ||
| + | | | ||
| + | F | ||
| + | |- | ||
| + | T | ||
| + | | | ||
| + | F | ||
| + | | | ||
| + | F | ||
| + | |- | ||
| + | T | ||
| + | | | ||
| + | T | ||
| + | | | ||
| + | T | ||
| + | |} | ||
| + | |||
| + | The table above is the ''truth table'' for the '''and''' logical operator. It says that if the statement '''a''' is true, and if '''b''' is false, then the '''and''' operator makes the result of ''a'' '''and''' ''b'' false. Only if both statements are true will the result of '''and'''-ing them together be true. This is still pretty abstract. Let's see if we can make this clearer. Assume that ''a'' is the statement ''Today is Monday'', and that ''b'' is the statement ''The time is 9:00 a.m.'', and that you want to be reminded every Monday at 9:00 a.m. to go to Ford Hall to take a particular class. So we can define the alarm signal that reminds you to be ''a'' '''and''' ''b''. The alarm will ring only when the day is Monday, and the time is 9:00 a.m. At 9:00 a.m. on Tuesdays nothing will happen, because at that particular time ''a'' is false, and ''b'' is true, but the '''and''' operator is extremely strick and will not generate true if only one of its operands is true. | ||
An example will illustrate this concept. | An example will illustrate this concept. | ||
| + | |||
| + | ====Example==== | ||
Assume that I'm interested in buying ice cream for three friends: Edna, Liz, and Frida. Before going to the store I probe my friends for their taste in ice cream. Edna likes anything with chocolate, but doesn't like anything with fruit. She also doesn't like | Assume that I'm interested in buying ice cream for three friends: Edna, Liz, and Frida. Before going to the store I probe my friends for their taste in ice cream. Edna likes anything with chocolate, but doesn't like anything with fruit. She also doesn't like | ||
| − | Haagen Dazs icecream. Liz doesn't like chocolate, and doesn't care about the brand. Frida likes everything. | + | Haagen Dazs icecream. Liz doesn't like chocolate, and doesn't care about the brand. Frida likes everything. |
| + | |||
| + | The way Boole would likely recommend we figure out our problem when we are at the store, probing the freezer for potential ice cream containers is as follows. | ||
| + | |||
| + | Let's create three ''boolean variables'', '''Choc''', '''Fruit''', and '''HG''', representing whether an ice cream containers contains chocolate, contains fruits, or is from the Haagen Dazs brand. | ||
| + | |||
| + | We know that Edna likes chocolate but not fruity ice cream, and that she doesn't like Haagen Dazs. So we could create an ''Edna'' function, something that could tell us if Edna would like a particular ice cream or not. This function for Edna would be | ||
| + | |||
| + | Choc '''and''' ( '''not''' Fruit ) and ( '''not''' HG ) | ||
| + | |||
| + | |||
{| border="1" cellpadding="20" cellspacing="0" | {| border="1" cellpadding="20" cellspacing="0" | ||
| Variable ''a'' | | Variable ''a'' | ||
