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 is divisible by 4, it is divisible by 2”.
(a) Write the statement in propositional logic. Prove that it is true or give a counterexample.
(b) Write the inverse of the implication in English and in propositional logic. Prove that it is true
or give a counterexample. (The inverse of an implication P =⇒ Q is ¬P =⇒ ¬Q.)
(c) Write the converse of the implication in English and in propositional logic. Prove that it is true
or give a counterexample.
(d) Write the contrapositive of the implication in English and in propositional logic. Prove that it is true or give a counterexample.
3 Preserving Set Operations
Forafunction f,definetheimageofasetX tobetheset f(X)={y|y= f(x)forsomex∈X}. DefinetheinverseimageorpreimageofasetY tobetheset f−1(Y)={x| f(x)∈Y}. Provethe following statements, in which A and B are sets.
Recall: ForsetsX andY,X =Y ifandonlyifX ⊆Y andY ⊆X. ToprovethatX ⊆Y,itissufficient toshowthat(∀x)((x∈X) =⇒ (x∈Y)).
(a) f−1(A∪B) = f−1(A)∪ f−1(B). (b) f(A∪B)=f(A)∪f(B).
CS 70, Fall 2021, DIS 1A 1
4 Numbers of Friends
Prove that if there are n ≥ 2 people at a party, then at least 2 of them have the same number of friends at the party. Assume that friendships are always reciprocated: that is, if Alice is friends with Bob, then Bob is also friends with Alice.
(Hint: The Pigeonhole Principle states that if n items are placed in m containers, where n > m, at least one container must contain more than one item. You may use this without proof.)
CS 70, Fall 2021, DIS 1A 2