Section 1 [25 pts (5 each)]:  Number Representations

1.  Convert BB816  to octal.  (Show your work.)

2.  Convert D216  to binary.  Now, treating the number as an 8-bit two’s-complement number, convert to decimal (base-10).

3.  The droid C3PO from Star Wars knows 6 million forms of communication.  We assign each form of communication a unique identifier in the form of a fixed-length unsigned binary number.  (By fixed-length we mean that the number of bits allocated to each identifier is the same.)  How many bits must be allocated for each identifier?  Give your answer in the form of an integer, and explain.

4.  215 = 32, 768. How many numbers between 0 and 215  are the sum of exactly three powers of 8?  Each power must be a natural number.  Natural numbers are the non-negative integers (0, 1, 2, 3, ...). The powers need not be distict. For example, 10 is one such number because 10 = 81 + 80 + 80 = 8 + 1 + 1 and 521 is another such number because 521 = 83 + 81 + 80 = 512 + 8 + 1. Reduce your answer to an integer and explain your answer.

5.  Droids on the planet Tatooine perform calculations in base-6.  What is the largest base-6 number that can be represented with three distinct digits? (Each digit in your base-6 number must be different.) Convert your answer to decimal (base-10).

Section 2 [25 pts]:  Logic

Given the domains m e MOVIES and c e CHARACTERS and the following predicates:

● SW(m): m is a Star Wars movie.

● A(c, m): c is a character who appears in the movie m

● D(c): c is a Droid.

● L(m): I liked m.

● Q(c, q): c says q (c is quoted as saying q.)

● jarjar is the character Jar Jar Binks

●  bad is the quote:  ”I’ve got a bad feeling about this!”

1. Express the following English sentence with predicate logic using Existential and/or Universal quantifiers: I didn’t like any Star  Wars movie if Jar Jar Binks was in it.

2. Express the following English sentence with predicate logic using Existential and/or Universal quantifiers: At least two  droids appear in every Star  Wars movie.  You may use the notation x = y and x  y as needed.

3. Express the following English sentence with predicate logic using Existential and/or Universal quantifiers: In every Star Wars movie, some character in the movie says ”I’ve got a bad feeling about this!”.

4. Negate your expression from sub-problem (3). Now simplify the logical expression using the laws of logical equivalence. To simplify, eliminate implications (if any) and negations in front of quantifiers.  Negations should appear only in front of single predicates.  Show each step. Cite the law of logical equivalence you are applying with each step.

5.  Convert your final simplified expression from the previous problem back into English.

Section 3 [25 pts (15,10)]:  Sets

1. In this problem A = {R2D2, C3PO, BB8} and B = {BB8, R5D4}.  IAI denotes the cardinal- ity (number of members) of the set A. Answer each question with an integer or an expression involving exponents. You do not need to show each step.

i.  IA × BI =?

ii.  IA - BI =?

iii.  I(A - B) n (B - A)I =?

iv.  Ip(A△B)I =?

v.  I{x : x e p(A u B) A IxI = 2}I =?

2.  Some rebel pilots were surveyed to determine what they thought of different star fighters. The three kinds of star fighters are the X-Wing, the Y-Wing, and Tie Fighters.

● Every pilot liked at least one kind of star fighter

●  1 liked all three.  (The force is strong with this pilot!)

●  1 liked X-Wings and Y-Wings

● 2 liked X-Wings and Tie Fighters

● 3 liked Y-Wings and Tie Fighters

● 5 liked X-Wings

● 8 liked Y-Wings

●  13 liked Tie Fighters.

Use the Principle of Inclusion and Exclusion to determine how many pilots answered the survey.  Draw a Venn Diagram depicting the above data.  Note:  when we say, for example, that n pilots liked a particular kind of Star Fighter, it means they might have liked other types as well. For example, some of the 13 pilots that like Tie Fighters liked X-Wings, Y-Wings or maybe both.

Section 4 [25 pts (5 each)]:  Counting

1.  Suppose droids in the Star Wars universe follow the following naming conventions:

● Names must be 3-5 characters including uppercase letters and digits.  (No dashes.)

● All names must start with a letter and contain at least 1 digit.

How many droid names are possible?  You can leave your answer as an expression as long as you clearly explain each term in the expression.  Some valid names include BB8, R2D2, C3PO, and H2SO4.

2.  Seventeen Jedi are fighting for their lives in an arena. Each Jedi uses a light saber with one of 4 colors.

(a) Explain why five or more Jedi must be using the same color light saber. What mathe-

matical principle are you invoking in your explanation?

(b) How many Jedi would there need to be in the arena in order to guarantee that seven or

more Jedi are using the same color light saber?