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.