Untitled
1 Statements
1.1 Translations
Suppose p is ”CMSC250 is fun”, q is ”I attend class”, and r is ”I will get an A”. Write the following in
propositional logic.
(i) CMSC250 is fun and I attend class
(ii) CMSC250 is fun but I don’t attend class
(iii) If I attend class, then I will get an an A
(iv) Either I attend class and will get an A, or I will not attend class and not get an A
(v) Exactly one of the following is true: CMSC250 is fun, I attend class, I will get an A
1.2 Implications
Consider the following statement:
If Cliff is a good lecturer and I pay attention, then I will get an A.
Write the:
(i) Contrapositive
(ii) Converse
(iii) Inverse
(iv) ∨-statement equivalent
2 Truth Tables
Construct a truth table for each of the following statements.
(i) p ∨ q ∧ (r ⇒ s)
(ii) ∼(n ⇔ u) ∨ ((∼n ∨ u) ∧ (∼u ∨ n))
(iii) (∼p ∧ r) ⇒ (r ∨ p)
3 Laws of Equivalence
3.1 Checking Equivalence
Check whether the following are equivalent using both truth tables and laws of equivalence:
(i) (p ⇒ (q ∨ r)) ⇒ s ≡ p ∧ s
(ii) (p ∨ q) ∧ (∼p ∨ ∼q) ≡ p ⇔ q
4 Arguments
4.1 Arguments and Validity
Determine if each of the following is valid or invalid using truth tables and rules of inference and laws of
equivalence.
(i)
p ⇒ q
q ⇒ r
∴ q ∨ r
(ii)
∼(p ∨ i) ⇒ z
z ⇒ a
a ⇒ contradiction
∴ p ∨ i
1
5 Circuits
5.1 Circuit to Statements
Write the statements for the following:
(i)
(ii)
5.2 Statements to Circuits
Make circuits for each of the following statements. AND and OR gates may only have two inputs.
(i) (p ∧ q) ∨ (∼p ∨ ∼q)
(ii) ((p ⇒ q) ∧ (s ⇒ q)) ⇒ (s ∨ q)
6 Numbers
6.1 Conversion
Convert the following as specified:
(i) 02134 to base 10
(ii) 1482410 to base 12.
6.2 Addition of number bases
Add the following numbers together:
(i) 010101012 + 215. Answer in Base 4.
(ii) DA916 + 32429 Answer in base 3.
7 Number Theory
7.1 Parity
(i) is 34 even or odd? justify
(ii) is 87 even or odd? justify
7.2 Primes
Are the following composite, prime or neither? Justify your answer:
(i) 143
(ii) 12
(iii) -4
7.3 Divisibility
Are the following true or false? Justify.
(i) 5|34
(ii) 6 ∤ 13
2
7.4 Modular Arithmetic
Are the following statements true or false? Justify your answer
(i) 3 ≡ 5(mod 6)
(ii) 27 ≡ 40(mod 13)
8 Proofs
8.1 Direct Proofs
Prove the following directly:
1. Rational Number + rational = rational
2. ∀x, y ∈ R, ∃z, x < z < y 8.2 Indirect Proofs 8.2.1 Proof via contrapositive Prove the following via contrapositive 1. ∀x ∈ Z, (4|x) ⇒ (2|x) 2. ∀x, y ∈ R≥0, (x2 ≥ y2) ⇒ (x ≥ y) 8.2.2 Proof via Contradiction Prove the following using a proof via contradiction: 1. ∀x ∈ Q, x √ 2 6∈ Q. You may assume that √ 2 6∈ Q 2. There is no smallest real number. 9 Sets 9.1 Building sets Use Set Builder notation to create the following sets 1. odd factors of 100 2. composite numbers > 4
List out all the elements in, and give the cardinality of, each of the following sets:
1. P(∅)× ∅
2. {1, 2, 3} × {2, 3, 4} − {(x, x)|x ∈ Z} Note: Cartesian product comes before subtraction in the order of
operations
9.2 Proofs
(i) ((A ∩B) = ∅) ⇒ (A ∩B) ∩ (A ∪Bc) = ∅
(ii) (A ∩B) ∪ (A ∩Bc) = A
10 Countability
Are each of the following finite, countably infinite, or uncountable?
(i) {x ∈ R|1 < x < 2} (ii) QxQxQ 11 Sequences 11.1 Formula to Sequence Write the starting 5 values for the sequence given 1. an = 6 2−n 2. b(n) = 1 n = 0 −1 n = 1 (−1)n(bn−1 + bn−2) n ≥ 2 3 11.2 Sequence to Formula Write a recursive and non-recursive definition for each of the following sequences. 1. 1, 4, 9, 16, 25, 36, 49, . . . 2. 0, 2,−4, 6,−8, 10, . . . 12 Summations and Prodcuts Calculate the following: 1. 10 ∑ i=0 10 ∑ j=i (i+ j) 2. 5 ∑ i=0 6 ∏ j=3 (ji) 13 Weak Induction Prove the following via Weak Induction 1. Prove that ∀n ∈ Z, n ∑ i=0 i = n(n+1 2 2. Prove that ∀n ∈ Z, n ∑ i=0 i2 = n(n+1)(2n+1) 6 14 Strong Induction Prove the following via Strong Induction 1. a(n) = 3 n = 0 4 n = 1 −n+ a(n− 1) + a(n− 2) n ≥ 2 Prove that ∀n ∈ Z≥0, a(n) = n+ 3 2. b(n) = 0 n = 0 12 n = 1 b(⌊n/3⌋) + b(⌈n/4⌉) + 4n n ≥ 2 Prove that ∀n ∈ Z≥0, b(n) ≤ 12n 15 Structural Induction Prove the following via Structual Induction 1. Let a set S be defined as follows S = 6 ∈ S 4 ∈ S ∀x, y ∈ S, xy ∈ S ∀x, y ∈ S, x+ y ∈ S Prove that ∀x ∈ S, 2|x 16 Combinatorics A standard deck of 52 cards consists of 4 groupings of 13 cards. Each grouping is called a ‘suit’. The four suits are: spades, diamonds, hearts and clubs. Each suit has 9 number cards: {2, 3, 4, 5, 6, 7, 8, 9, 10}, 3 face cards: {jack, queen, king} and an Ace (9 + 3 + 1 = 13). A common family of card games is called ‘poker’. Usually a hand in poker consists of 5 cards. Certain hands have special names. How many ways can you create each of the following hands? 1. 2 pair - A 2-pair hand is one which you have, well, 2 pairs of cards. The suits of the cards does not matter here. Example: (2,2,4,4,9). How many 2-pair hands can you make? 2. Flush - A flush is where all 5 cards have the same suit. For this question’s purpose, the value of the card does not matter. 3. Straight - a straight is where you have 5 cards in adjacent value order. For this hand, Jack is considered a 10, Queen is 11 and King 12. Ace is then considered a 13 or a 1. Hence (Ace,2,3,4,5) and (Ace, King, Queen, Jack, 10) are both straights. (3,4,5,6,7) is also a straight. (2,4,5,6,7) is not considered a straight because ∃x, 2 < x < 4. 4 17 Probability A standard deck of 52 cards consists of 4 groupings of 13 cards. Each grouping is called a ‘suit’. The four suits are: spades, diamonds, hearts and clubs. Each suit has 9 number cards: {2, 3, 4, 5, 6, 7, 8, 9, 10}, 3 face cards: {jack, queen, king} and an Ace (9 + 3 + 1 = 13). A common family of card games is called ‘poker’. Usually a hand in poker consists of 5 cards. Certain hands have special names. What is the probability of each of the hands occurring? 1. Four of a kind - This hand is when you have all four values in the hand. Since there is only 4 of each value, there will only be one other card leftover. Example (2,2,2,2,K). 2. Full House - Where you have 3 of a kind and 2 of another kind. Example (2,4,4,4,2). This is called a house full of 4s. 3. Straight Flush - This is where you have both a straight and a flush. So you have something like (Ace, 2,3,4,5) and all 5 cards are the same suit. 17.1 Conditional Probability and Bayes 1. Suppose you are scambling around the letters of ”Computers”. What is the probability that the ‘p’ is next to both the ‘s’ and the ‘r’ given that the ‘p‘ is in the 1st, 3rd, or 4th position? (or index 0,2, and 3). 2. Some traits are expressed via dominant and recessive genetics, which (if I recall my high school biology correctly) is simplified for general schooling as 2 alleles, one dominant, the other recessive. Each person has 2 alleles for some trait. If at least one of the alleles is dominant, then the trait is expressed, otherwise the recessive trait is expressed. To simplify, everyone has a two character string of either AA,Aa,aA,aa. If a person has AA,Aa,aA, then they have brown eyes. If they have aa, they have blue eyes. When producing offspring, one character is given to the offspring. AA can only give A, Aa can give either A or a, and aa can only give a. Assuming this inheritance is equally likely, (which character is passed down is equally likely) what is the probability that given that someone has brown eyes, that at least one of their parents have blue eyes? (or 1 - probability both parents have brown eyes, given child has brown eyes) 5