discrete mathematics

CS 70 Discrete Mathematics and Probability Theory Fall 2021 1 Party Tricks You are at a party celebrating your completion of the CS 70 midterm. Show off your modular arithmetic skills and impress your friends by quickly figuring out the last digit(s) of each of the following numbers: (a) Find the last digit of 113142.

EECS 70 Discrete Mathematics and Probability Theory Fall 2021 Review of Sets and Mathematical Notation A set is a well defined collection of objects. These objects are called elements or members of the set, and they can be anything, including numbers, letters, people, cities, and even other sets. By convention, sets are usually denoted by

CS 70 Discrete Mathematics and Probability Theory Fall 2021 1 Counting Strings (a) How many bit strings of length 10 contain at least five consecutive 0’s? (b) How many different ways are there to rearrange the letters of DIAGONALIZATION (15 letters with 3 A’s, 3 I’s, 2 N’s, and 2 O’s) without the two N’s

EECS 70 Discrete Mathematics and Probability Theory Fall 2021 1 Mathematical Induction Introduction. In this note, we introduce the proof technique of mathematical induction. Induction is a powerful tool which is used to establish that a statement holds for all natural numbers. Of course, there are infinitely many natural numbers — induction provides a way

CS 70 Discrete Mathematics and Probability Theory Fall 2021 1 Truth Tables Determine whether the following equivalences hold, by writing out truth tables. Clearly state whether or not each pair is equivalent. (a) P∧(Q∨P) ≡ P∧Q (b) (P∨Q)∧R ≡ (P∧R)∨(Q∧R) (c) (P∧Q)∨R ≡ (P∨R)∧(Q∨R) 2 Converse and Contrapositive Consider the statement “if a natural number