Assignment 2 - final (I think)

The first 4 digits of my student ID number are 2085.
2085 = 5 (mod 8) = 0 (mod 3) = 6 (mod 7).
So I will be answering questions 2f, 3a, and 6g.

Bit Strings and Logic
1. If we consider the four 2-variable inputs (x, y) to be (0,0), (0,1), (1, 0) and (1,1) then there are 16 possible outputs. Each of these combinations can be depicted as a Venn diagram.

Here are some Venn diagrams to illustrate how each of the 16 binary functions can be expressed as a composition of the binary operations AND, OR and NOT. Note that in each function 1 represents TRUE and 0 represents FALSE. These correspond to coloured and white respectively in the diagrams. In the function names, the first element corresponds to the region inside the box, but outside both circles, the second element corresponds to the right circle (y), the third element corresponds to the left circle (x) and the fourth element corresponds to the region where the circles overlap.

(Yes, I coloured by hand and then scanned these in. I was having trouble staying in the lines on Photoshop and didn’t have the patience to go pixel by pixel on this many diagrams.)


2.f) Here are the binary functions which CAN be represented using only combinations of {OR, IMPL}:

Now, OR returns a value of "0" only if BOTH input values are "0" and IMPL returns a value of "0" only if the first input value is a "1" and the second input value is a "0". Since it is impossible to have an input value of "0" across the bottom row of the chart, we conclude that we CANNOT (using OR, IMPL) represent the 8 binary functions ending in "0", ie. 1110, 1100, 1010, 1000, 0110, 0100, 0010, 0000.
It is also impossible to create the representations 1001 (IFF, XAND) and 0001 (AND) since there are no columns in the chart above that have "0" in both middle positions, nor is there a way of composing any of the functions together so that the second input value would be a "0" for both middle positions. The OR function doesn't exclude anything, and both functions OR, IMPL include an OR. In order to create AND, XAND, we would need to be able to exclude. Therefore we are unable to create representations for AND, XAND using OR, IMPL.

3. Out of the 16 binary operators, the following are commutative: 0, AND, XOR, OR, NOR, XAND, NAND, 1. These are represented by the functions: 0000, 0001, 0110, 0111, 1000, 1001, 1110, 1111 respectively in the diagrams above. Note that these correspond to the symmetric diagrams above which makes sense since f(x,y) = f(y,x) if the operators are commutative. Also, this list consists of 4 operators together with their complements.

4. Usually we define a function by a rule, for example, f(x)=x^2. But if we are dealing with a finite function we can define it explicitly in terms of its inputs and outputs. Suppose a finite function has n elements in its domain and m possible choices for its range. Then each function is uniquely determined in the following way: the first input has m possible outputs, the second input has m possible outputs, and so on to the nth input. So the number of such possible functions is m^n; that is, the (number of outputs) to the exponent (number of inputs). For the binary case in question 1 above, there are 2 possible outputs (0, 1) and 4 input combinations (00, 01, 10, 11). Therefore there are 2^4 = 16 possible functions. Extending to the trinary case with 3 possible inputs {0,1,2}, there are 9 possible 2-input arguments (since there are 3 choices for the first input argument and 3 choices for the second input argument). There are 3 possible output values (0, 1, 2). Therefore the total number of possible functions, f(x,y) that can be created = (number of outputs)^(number of inputs) = 3^9 = 19683.

5. Again with trinary inputs as described in question 4, the minimum number of binary operations needed so that compositions of these binary operations can be used to express every possible two argument function on trinary operations is four. They are NOT, OR, AND, IMPL. In the trinary case, IMPL cannot be derived from the other three operations like in the binary case so it needs to be included on the list as a basic operation. Compositions of these four binary operations can be used to express each of the 19683 possible two argument functions. Source: "A Brief Introduction to Ternary Logic" www.fw.uri.br/~arpasi/artigos/ternary.pdf
However, this article doesn't provide any proof or explanation for this claim. While the article appears scholarly and provides examples that are consistent with what we've discussed in class, I don't believe that this is necessarily a unique solution for the minimal number of operations. I was intrigued by what Mike suggested in class, did a bit more Internet research and put together the following "new" operations: (hmmm...trinary logic & a vision test all in one)

I'm not sure how many of these can be derived from the others (it is unlikely that you would need all 10). I do know that MINIMUM acts like AND if both inputs have been SHIFT UP or SHIFT DOWN and that MAXIMUM acts like OR if both inputs have been SHIFT UP or SHIFT DOWN. The two SHIFTS also act to convert the input to a binary system. Finally, from the above list, all except MAGNITUDE and the SHIFTS are commutative, associative and distributive which makes them good candidates for generating a bunch of functions. Most of these ideas came from http://www.trinary.cc/.


6. left image = (pic1 AND pic2), right image = (pic1 OR pic2)

part g) left image = pic1, right image = (pic1 IMPL pic2)

So: pic1 AND (pic1 IMPL pic2)

7. Not the first time I've done uniqueness when all the question asked was existence.

Let P represent the truth value of the phrase “poison caused the victim’s death”.
Let C represent the truth value of the phrase “there was a change in blood chemistry”.
Let R represent the truth value of the phrase “there was a residue of poison in the stomach”.
Let M represent the truth value of the phrase “there were puncture marks on the body”.
Let N represent the truth value of the phrase “poison was injected by a needle”.

Sentence 1: Poison caused the victim’s death if and only if there was a change in his blood chemistry or a residue of poison in the stomach.

P IFF (C OR R) = (P OR NOT(C OR R)) AND (NOT P OR (C OR R))

Sentence 2: There was neither a change in blood chemistry nor a residue of poison in his stomach, but there were puncture marks on the body.

(NOT C AND NOT R) = NOT(C OR R). M.

Since NOT(C OR R) is true, we conclude that NOT P must be true. We also have that M is true .

Sentence 3: Poison was injected by a needle only if there were puncture marks on the body.

N ONLY IF M = N IMPL M = (NOT N) OR M

Sentence 4: Either poison was the cause of the victim’s death, or there are no puncture marks on the body.

P OR (NOT M)

We know from sentences 1 and 2 that NOT P is true. Therefore, for sentence 4 to be true, NOT M must be true. Using the contrapositive with sentence 3, NOT M true implies NOT N is true.

Conclusions:
1) NOT P is true. (sentences 1 and 2)
2) M is true. (sentence 2)
3) NOT M is true. (sentence 4)
4) NOT N is true. (sentences 3 and 4)

We have a contradiction since M is true and NOT M is also true based on these sentences. (There were puncture marks on the body and there were no puncture marks on the body.)


Orders of Magnitude

1. 1GB x (1024 MB/GB) x (1024 K/MB) = 1048576 K

Therefore a computer with 1 GB of memory has: 1048576/64 = 16384 times more memory than a Commodore 64.

2. 4.7 GB x (1024 MB/GB) x (1024 K/MB) = 4928307.2 K

Therefore the number of 800 K floppy disks that are equivalent to a single 4.7GB DVD is 4928307.2/800 which is approximately 6160.

3. Clock rate refers to the speed of a computer's CPU. Here are some historical comparisons:

So, the 2008 computer is approximately 5000 times faster than the Intel 4004. The first mass marketed computers came out around 1975 (eg. the Altair 8800 which was sold as a mail order kit in hobby magazines). Compared to these, today’s computers are approximately 2000 times faster.

integrity

RE: Cheating, technology, integrity
Answering the question (sort of):
The bottom line for me:
a) Did the student learn? (the concepts, skills, etc. that I wanted to get across)
b) Does the grade authentically reflect that student's OWN learning?

With respect to a):
I don't really care how the student accomplishes this learning. I am not egotistical enough to insist that this learning comes only from what I'm doing with them in the classroom. If they can learn from working together (in person or in cyberspace), or from looking at websites, or reading a book, or asking a neighbour, or ... then that is great. In this formative (learning) stage, for me there is no such thing as cheating. Any source is fair game. Get the info. however you can. So for example, if my students want to copy homework solutions off their peers then so be it. They are at least getting some value from handwriting it all out (since we're not yet at the stage where math homework is word processed!). However this stuff counts LITTLE or NOT AT ALL in their marks ... it is simply a chance for them to practice, get feedback, see what they need more work on, etc. If they use this opportunity well, it pays off later on when they ARE being assessed.
Seen technology used for this: eg. 1st year calculus at U of Guelph - Maple tutorials, student/TA/prof chat forum, online quizzes (created using a Maple program so each is unique) that can be attempted repeatedly for practice before counting one for a small part of the grade
(oh ya, and I think this was the intent behind the Fundamentals forum)

and b): Now it's different. The vast majority of the grade MUST come from work that is definitely being done by the student alone. This is their chance to demonstrate the stuff they learned in a). How to do this? Best way is to SUPERVISE THEM. Tests and assignments done in class. Otherwise the grades may be meaningless and may not necessarily reflect what that student can do.
And you avoid the complication of suspecting or even knowing that cheating (eg. plagiarism) has occurred and feeling like there's nothing you can really do ...
There needs to be integrity when grades are being considered. Otherwise what is the value of a course credit, or ultimately a diploma or degree?

widgets and doodles

I would have gone with the surname 'doodle', but I was worried about the jokes such a surname might jenerate.

But, perhaps someday I'll meet Bob Doodle (if the annoying Eve doesn't get to him first) and we'll get together and so, by the addition principle, that would make us Alice + Bob, a pair which is either a widget OR a doodle. Now this may lead some among you to ask, "Alice, what size is your Doodle?", but as we all know the size of the doodle isn't supposed to matter. And wait ... then we could reproduce and that would create, (obviously) the product of a widget AND a doodle which of course, by the multiplication principle, would be a widget-doodle (of some small size).

I guess that I should apologize now to those who were not in the Fundamentals course and so don't understand this. Or perhaps I should be apologizing to those who WERE in the Fundamentals course, and still don't understand this.

A. Widget