Test One - Thursday, October 4th, 2007 1. Floor and Ceiling functions. 2. Convert from a decimal number to a binary number, and vice versa and show your work and process of arriving at the answer. No calculators permitted. 3. Convert from base ten, decimal to base 16, hexadecimal and vice versa. Know that A = 10, B = 11, C = 12, D = 13, E = 14 and F = 15 1010 1011 1100 1101 1110 1111 2 2 2 2 2 2 4. Know truth tables, AND, OR, NOT, Implication. 5. Know converse, inverse, contrapositive of an implication. 6. Know the Josephus problem for eliminating every other person and who will be the winner. 7. Know what the summation notation is and how to read it and figure out a sum you are given in summation notation. 8. Know that the log to the base 2 of 34 would be 5.x and the log to the base 2 of 55 would be 5.y and the log to the base 2 of 63 would be 5.z where .x < .y < .z and that the log to the base 2 of 32 is 5 and the log to the base 2 of 64 is 6. Know how to use the floor or the ceiling function with the log function, i.e. floor(log 33) = floor(log 61) = 5 is an example to 2 2 understand. 9. Know the Existential and Universal Quantifiers. 10. Know DeMorgan's Laws about: the negation of a conjunction being a disjunction of negations, and the negation of a disjunction is a conjunction of negations. 11. Know how to prove something about the even and the odd numbers. Know how to prove anything like involving divisibility of the integers. For example: if a divides b and b divides c then a divides c is true for the integers. Domain Integers: for all a, b, c ( if (a | b and b | c) then a | c ) for all is the UNIVERSAL QUANTIFIER 12. Know modus ponens and modus tollens. Know contrapositive. Know De Morgan's laws. Know disjunctive syllogism. Be able to do a proof using these rules from propositional logic. 13. Know the difference between Direct proof and Indirect proof for implications: P --------------> Q if P then Q Hypothesis GOAL Premises Name ------------ ------- -------------- DIRECT P Q direct proof INDIRECT not P not Q proof by contrapositive not P or Q contradiction proof by contradiction 14. Know how to solve a very simple Knaves and Knights problem. 15. Know how to do a very simple inductive proof. Follow the template approach given by the instructor in class and in all examples. Here is a checklist of the things you will see and do in the inductive proofs you study and write and practice with. BASIS Step: Usually, proving it for n = 1 LHS =? RHS 1 1 Inductive Step: I. Assume as IH that for n = k, where k >= 1 that ... II. Try to show for n = k + 1, that III. Do the proof... Did you start with LHS of II, i.e. Left Hand Side of P(k+1)? Did you arrive eventually at RHS of II, i.e. Right Hand Side of P(k + 1)? Was your use of the IH very clear, where you substituted the RHS of P(k) for the LHS of P(k) and stated what you were doing - "by IH" - as you RECOGNIZED the LHS from step I. above and used your IH (Inductive Hypothesis). Was you algebra clear? 16. Draw a game tree like we did for the tennis match that is the "best of five". Draw a game tree for nickel, dime and quarter toss to illustrate all the different results you could record. 17. Know how to make a CF (Closed Formula) and/or and RF (recursive formula) for a series (sequences) such as 9, 16, 25, 36, 49, ... 18. What is the next number in the following series? 1, 4, 9, 16, 25, 36, 49, 81, __________ ? What is the RF for the above series? What is the CF? What is the 12th number in the sequence of these numbers? 19. Know that if m divides n ( m | n ) then by definition there exists an integer k such that n = kn. Know that if we say n is an even number, then n = r2 for some integer r. 2 divides n is another way of saying that n is even. Know that by definition of odd, that if n is an odd number, there exists j such that n = j2 + 1 2 doesn't divide n is another way of saying n is odd. Be able to prove things like: For all integers x and y, if x is odd and y is odd then x + y is even For all integers x and y, if x is odd and y is odd then the product xy is odd