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
Copyright By PowCoder代写 加微信 powcoder
(b) (P∨Q)∧R ≡ (P∧R)∨(Q∧R) (c) (P∧Q)∨R ≡ (P∨R)∧(Q∨R)
(a) Not equivalent.
P Q P∧(Q∨P) P∧Q TTTT TFTF FTFF FFFF
(b) Equivalent.
P Q R (P∨Q)∧R (P∧R)∨(Q∧R) TTTTT TTFFF TFTTT TFFFF FTTTT FTFFF FFTFF FFFFF
(c) Equivalent.
CS 70, Fall 2021, DIS 1A 1
P Q R (P∧Q)∨R (P∨R)∧(Q∨R) TTTTT TTFTT TFTTT TFFFF FTTTT FTFFF FFTTT FFFFF
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.
(a) (∀x∈N)(4|x =⇒ 2|x). Thisstatementistrue. Weknowthatifxisdivisibleby4,wecan write x as 4k for some integer k. But 4k = (2 · 2)k = 2(2k), where 2k is also an integer. Thus, x must also be divisible by 2, since it can be written as 2 times an integer.
(b) The inverse is that if a natural number is not divisible by 4, it is not divisible by 2: (∀x ∈ N) (4 x =⇒ 2 x). This is false, since 2 is not divisible by 4, but is divisible by 2.
(c) The converse is that any natural number that is divisible by 2 is also divisible by 4: (∀x ∈ N)(2|x =⇒ 4|x). Again,thisisfalse,since2isdivisibleby2butnotby4.
(d) The contrapositive is that any natural number that is not divisible by 2 is not divisible by 4: (∀x∈N)(2x =⇒ 4x). Toshowthatthisistrue,firstconsiderthatsayingthatxisnot divisible by 2 is equivalent to saying that x/2 is not an integer. And if we divide a non-integer by an integer, we get back another non-integer–so (x/2)/2 = x/4 must also not be an integer. But that is exactly the same as saying that x is not divisible by 4.
Note that the inverse and the converse will always be contrapositives of each other, and so will always be logically equivalent.
CS 70, Fall 2021, DIS 1A 2
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).
In order to prove equality A = B, we need to prove that A is a subset of B, A ⊆ B and that B is a subset of A, B ⊆ A. To prove that LHS is a subset of RHS we need to prove that if an element is a member of LHS then it is also an element of the RHS.
(a) Supposex∈ f−1(A∪B)whichmeansthat f(x)∈A∪B. Theneither f(x)∈A,inwhichcasex∈ f−1(A),or f(x)∈B,inwhichcasex∈ f−1(B),soineithercasewehavex∈ f−1(A)∪f−1(B).
This proves that f −1(A ∪ B) ⊆ f −1(A) ∪ f −1(B).
Now, suppose that x ∈ f −1(A) ∪ f −1(B). Suppose, without loss of generality, that x ∈ f −1(A). Then f(x) ∈ A, so f(x) ∈ A∪B, so x ∈ f−1(A∪B). The argument for x ∈ f−1(B) is the same. Hence, f−1(A)∪ f−1(B) ⊆ f−1(A∪B).
(b) Suppose that x ∈ A∪B. Then either x ∈ A, in which case f(x) ∈ f(A), or x ∈ B, in which case f(x) ∈ f(B). In either case, f(x) ∈ f(A)∪ f(B), so f(A∪B) ⊆ f(A)∪ f(B).
Now, suppose that y ∈ f(A)∪ f(B). Then either y ∈ f(A) or y ∈ f(B). In the first case, there isanelementx∈Awith f(x)=y;inthesecondcase,thereisanelementx∈Bwith f(x)=y. In either case, there is an element x ∈ A∪B with f(x) = y, which means that y ∈ f(A∪B). So
f(A)∪ f(B) ⊆ f(A∪B).
The purpose of this problem is to gain familiarity to naming things precisely. In particular, we named an element in the LHS (or the pre-image of the LHS) and then argued about whether that element or its image was in the right hand side. By explicitly naming an element generically where it could be any element in the set, we could argue about its membership in a set and or its image or preimage. With these different concepts floating around it is helpful to be clear in the argument.
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.
CS 70, Fall 2021, DIS 1A 3
(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.)
We will prove this by contradiction. Suppose the contrary that everyone has a different number of friends at the party. Since the number of friends that each person can have ranges from 0 to n − 1, we conclude that for every i ∈ {0, 1, . . . , n − 1}, there is exactly one person who has exactly i friends at the party. In particular, there is one person who has n − 1 friends (i.e., friends with everyone), and there is one person who has 0 friends (i.e., friends with no one), which is a contradiction.
Here, we used the pigeonhole principle because assuming for contradiction that everyone has a different number of friends gives rise to n possible containers. Each container denotes the number of friends that a person has, so the containers can be labelled 0,1,…,n−1. The objects assigned to these containers are the people at the party. However, containers 0, n − 1 or both must be empty since these two containers cannot be occupied at the same time. This means that we are assigning n people to at most n − 1 containers, and by the pigeonhole principle, at least one of the n − 1 containers has to have two or more objects i.e. at least two people have to have the same number of friends.
CS 70, Fall 2021, DIS 1A 4
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com