Description

connected-argument
CS/MATH 113 Discrete Mathematics
1 Inference
1. Prove the following arguments using inference rules. Mention the rule(s) that you use at each step.
(a) 5 points
P2 If the basketball field is occupied, we don’t play basketball.

C We play cricket or volleyball.
Solution: The propositions are as follows:
The arguments as propositional logic are as follows:
P1 p =⇒ (q ∨ r) P2 s =⇒ ¬ r
P3 p ∧ s

C q ∨ t
Starting from P3: p ∧ s
∴ p (by Simplification)
∴ s (by Simplification)
From P1:
p =⇒ (q ∨ r)
∴ q ∨ r (Modus Ponens)
Since p is true, then q or r must be true.
From P3:
s =⇒ ¬ r
∴ ¬ r (Modus Ponens)
Since s is true, then negation of r must be true q or r is true, and negation of r is true, then:
1
q ∨ r
¬ r
∴ q (by Disjunctive Syllogism) q is true, then:
q
∴ q ∨ t (by Addition)
Since q is true, then q or t must be true, so it has been proved that the argument is valid.
(b) 10 points
P1 Ahmed failed the course, but attended every lecture.
P2 Everyone who did the homework every week passed the course.
P3 If a student passed the course, then they did some of the homework.
C Not every student did every homework assignment.
Solution:
Let S(s) be “student ‘s’ has passed the course”
Let LW(s, w) be “ student ‘s’ attended every lecture in week ‘w’ ”
Let HW(s, h) be “ student ‘s’ did every homeowork ‘h’ ”
The Domain for ‘s’ is all students, the domain for ‘w’ is all weeks, the domain for ‘h’ is all homeworks
The arguments as Predicate Logic are as follows:
P1 ¬P(Ahmed) ∧ ∀wLW(Ahmed,w)
P2 ∀s∀hHW(s,h) =⇒ ∀P(s)
P3 ∀sP(s) =⇒ ∃hHW(s,h)

C ∃s∃h¬HW(s,h)
Then:
1) ¬P(Ahmed) ∧ ∀wLW(Ahmed,w) (P1)
2) ¬P(Ahmed) (By Simplification of 1)
3) ∀s∀hHW(s,h) =⇒ ∀P(s) (P2)
4) ∀hHW(Ahmed,h) =⇒ P(Ahmed) (Universal Instantiation of 3)
5) ¬∀hHW(Ahmed,h) (Modus Tollens on 2 and 4)
6) ∃s¬∀hHW(s,h) (Existential Generalization of 5)
7) ∃s∃h¬HW(s,h) (Negating Quantifier of 6)
As shown, we reach the conclusion from the argument, thus the argument is proved to be valid.
Solution:
If k ∈ Z and R(x) is the remainder of the square of x when divided by 4, the given statement can be expressed as:
∀k((2k + 1) /4 → R(2k + 1) = 1) ∵ all odd numbers can be expressed as 2k+1 where k ∈ Z
Direct Proof:
Taking antecedent or premise to be true ((2k + 1)2/4), we have to prove that conclusion/consequence (remainder=1) can be expressed in the form of (quotient/dividend + 1).
Here, ((2k + 1)2)/4
(4k2 + 4k + 1)/4
(4k2/4 + 4k/4 + 1/4 + 1 − 1)
(4k2/4 + 4k/4 − 3/4 + 1 (4k2 + 4k − 3)/4 + 1 where (4k2 + 4k − 3) is the quotient, 4 is the dividend and 1 is the remainder, as given in the statement. Hence, it is proven that the remainder of the square of any odd number when divided by 4 is 1.
(b) 5 points Write the statement from above using a bi-conditional instead of a conditional. Prove whether the new statement holds.
Solution:
Now considering ((2k + 1)2/4 ⇔ R(2k + 1) = 1) or
((2k + 1)2/4 → R(2k + 1) = 1) ∧ (R(2k + 1) = 1 → (2k + 1)2/4)
As we have already proven ((2k + 1)2/4 → R(2k + 1) = 1) in part, let’s consider (R(2k + 1) = 1 → (2k + 1)2/4)
This does not hold as given by a counter example where the remainder is 1, but an odd number is not divided by 4,
Counter example: the remainder of 4/3 is 1, but neither the numerator is odd or divided 4. Hence, the bioconditional does not hold. odd number
3. 5 points Show that these statements about the real number x are equivalent: (i) x is irrational, (ii) is irrational. Which proof method did you use?
Solution: (Proof by Contradiction)
Suppose that x is irrational, however, is rational. Then can be represented as where p and q are integers in their simplest form and q ̸= 0. So . Then . Since 2p is also an integer, let 2p = r. Then . But x is irrational and cannot be represented in the form of thus we have a contradiction. So must be irrational. Moreover, the same can be argued when is supposed to be irrational and x is supposed to be rational. As x is rational, it can be represented aswhere p and q are integers in their simplest form and q ̸= 0. Then . Dividing both sides by 2 results in
. However, since is irratinoal, it cannot be represented as . Thus we have a contradiction.
Hence proved that the two statements are equivalent.
4. This question refers to the tiling or tessellation operation.
Given a standard checkerboard and dominoes, answer the following questions. Explain your answer for each question.
(a) 5 points Can we tile the standard checkerboard using dominoes?
Solution:
Yes, we can tile a standard 8×8 checkerboard dominoes. Since a domino has the size of two checkerboard boxes and a checkerboard is contains 64 total boxes. Then it can be tiled by 32 dominoes, placing the dominoes parallel to eachother.
(b) 5 points Can we tile a checkerboard obtained by removing one of the four corner squares of a standard checkerboard?
Solution:
No, a checkerboard cannot be tiled by removing one of the corners. If a corner is removed. The number of boxes are not even anymore and cannot be tiled with 1×2 size dominoes.
Proof by contradiction:
Suppose one of the four corners is removed from the checkerboard and we are left with 63 boxes instead of 64. In this case if we want to tile the checkerboard using dominoes, one tile will always be extra and left in the checkerboard. This results in contradiction and we must not remove any corners of the checkerboardin order to tile it dominoes.
(c) 5 points Can we tile a board obtained by removing both the upper left and the lower right squares of a standard checkerboard?
Solution:
Proof by contradiction:
Let’s suppose the board has upper left and lower right squares removed. Now in order to tile this board we need 31 dominoes. Since a domino has one black and one white tile. So we will have equal numbers of black and white tiles on the board. However, the oriantaion of the checkerboardis such that opposite ends have same colored tiles. So if we removed opposite white squares, the dominoes should be able to account for 30 white tiles and 32 black tiles. Since each domino only has two tiles, this cannot be achieved and contradiction arises. Hence, our assumption was wrong and the checkerboard cannot be tiled if the upper left and the lower right squares are removed.
5. 10 points The following is a murder case solved by Sherlock Holmes, in “A Study in Scarlet” :
“And now we come to the great question as to the reason why. Robbery has not been the object of the murder, for nothing was taken. Was it politics, then, or was it a woman? That is the question which confronted me. I was inclined from the first to the latter supposition. Political assassins are only too glad to do their work and fly. This murder had, on the contrary, been done most deliberately, and the perpetrator has left his tracks all over the room, showing he had been there all the time.”
From these, Sherlock Holmes concluded: “It was a woman”. Translate the above argument to statements in predicate logic and prove its validity.
Solution: The simple propositions are as follows:
p : it’s a robbery q : something was taken r : the object of murder involved politics s : a woman was involved t : assassin left as soon as the work was finished
u : assassin left tracks
The arguments can be written as follows:
P1 : if it’s a robbery, then something was taken
P2 : nothing was taken
P3 : if it’s not a robbery, then it was either politics or a woman
P4 : if it’s politics, then the assassin would have left as soon as the work was finished
P5 : if the assassin left tracks, then he did not leave as soon as the work was finished P6 : the assassin left tracks
The situation can then be represented as follows:
1 : p =⇒ q
2 : ¬ q
3 : ¬p =⇒ (r ∨ s)
4 : r =⇒ t
5 : u =⇒ ¬t
6 : u
From P2:
¬ q
From P1 and P2: ¬ q p =⇒ q
∴ ¬p (by Modus Tollens)
Thus it was not a robbery. From P3: ¬p

r ∨ s (By Addition)
From P6:
u
From P5 and P6: u
u =⇒ ¬t
∴ ¬t (by Modus Ponens)
Since the assassin left tracks, the assassin did not leave as soon as the work was finished. Then:
∴ ¬r (by Modus Tonens)
Then the object of murder did not involve politics. Therefore: r ∨ s
¬r
∴ s (by Disjunctive Syllogism)
Hence we prove that the argument is valid and a woman was involved.
2 Equivalence Relation
6. Prove or disprove whether each of the relations represented below is an equivalence relation.
(a) 5 points R on R = {(x,y) | xy ≥ 0}
(b) 5 points R on R = {(x,y) | x = 1}
(c) 5 points 1
0 1

0 0
1
0
1 1
0
1
0 0
1
0
1
1 1 1 0
(d) 5 points
0 0 0 1
(e) 5 points R1 ∩ R2 where R1 and R2 are equivalence relations on a set, S.
Solution:
(a) Three properties for equivalence: 1. Reflexivity 2. Symmetry 3. Transitivity
R = {(x,y) | xy ≥ 0}
1. Reflexivity: ∀a ∈ R → (a,a) ∈ R
As squares of numbers are always positive, i.e. x2, y2 hence if (x,y) ∈ R then (x,x) ∈ R and (y,y) ∈ R
2. Symmetry: Since multiplicaion is a commutative operatione i.e. the order of operation doesnot matter, this relation is symmetric, expressed as:
(x,y) ∈ R → (y,x) ∈ R
3. Transitivity: By definition xy ≥ 0 R contains every positive elements of first set to the positive elements of second set and negative elements of first set and negative elements of second set.
Hence, lets suppose xRy and yRc. Either x, y , and z will be positive or negative. So if all are postive,
xRc ∵ xy ≥ 0 and if all are negative, xRy ∧ yRc → xRc ∵ (−x) ∗ (−c) = xc ≥ 0xc ≥ 0
(b) R on R = {(x,y) | x = 1} 1. Reflexivity: ∀a ∈ R → (a,a) ∈ R
Here, x is a constant that is not changing and at every value of y, x remains the same. Hence, this relation is not relfexive. Counterexample: (1,0), given the definition of reflexivity, both (1,1) and (0,0) ∈ R. However, the value of x is always 1 and nothing else. Hence, the relation is not reflexive. 2. Symmetry: (x,y) ∈ R → (y,x) ∈ R
Since x is constant, no matter how much y changes, x will remain 1.
Counterexample: (1,0) ∈ R but not (0,1) ∈ R
3. Transitivity: unsure
(c) 1. Reflexivity: ∀a ∈ R → (a,a) ∈ R
Here, the diagonal suggests that the relation is indeed reflexive. Let the rows of be i and columns be j. We see that for all i’s and j’s positions where i=j there exists 1 in the graph which indicates that the aRa for all values in the relation. Hence, it proved that the relation is reflexive. 2. Symmetry: (x,y) ∈ R → (y,x) ∈ R
Symmetry of a relation through graphical representation is expressed as same elements on the non diagonals, i.e. if position ij = 0 then ji = 0 or if ij = 1 then ji = 1, this proves that the relation is indeed symmetric. 3. Transitivity: if (x,y) ∈ R ∧ (y,z) ∈ R → (x,z) ∈ R To observe the matrix, let’s call the rows and columns 1,2,3,4. Now for transitivity, (0,3) ∧ (3,0) → (0,0)
(2,1) ∧ (1,4) → (2,4)
…(4,2) ∧ (2,4) → (4,4)
There are no counterexamples, hence, transitivity is proven
(d) 1. Reflexivity: ∀a ∈ R → (a,a) ∈ R
Here, the diagonal suggests that the relation is indeed reflexive. Let the rows of be i and columns be j. We see that for all i’s and j’s positions where i=j there exists 1 in the graph which indicates that the aRa for all values in the relation. Hence, it proved that the relation is reflexive. 2. Symmetry: (x,y) ∈ R → (y,x) ∈ R
Symmetry of a relation through graphical representation is expressed as same elements on the non diagonals, i.e. if position ij = 0 then ji = 0 or if ij = 1 then ji = 1, this proves that the relation is indeed symmetric. 3. Transitivity: if (x,y) ∈ R ∧ (y,z) ∈ R → (x,z) ∈ R
To observe the matrix, let’s again call the rows and columns 1,2,3,4. Now for transitivity,
(1,2) ∧ (2,3) → (1,3)
(2,3) ∧ (3,1) → (2,1)
…(4,4) ∧ (4,4) → (4,4)
There are no counterexamples, hence, transitivity is proven
(e) tbd
Let R be a relation from a set A to a set B. The inverse relation from B to A, denoted by R−1, is

the set of ordered pairs {(b,a) | (a,b) ∈ R}. The complementary relation R is the set of ordered pairs {(a,b) | (a,b) ̸∈ R}. A relation R on the set A is irreflexive if ∀a ∈ A: (a,a) ̸∈ R. That is, R is irreflexive if no element in A is related to itself.
7. (a) 5 points Show that the relation R on a set A is symmetric if and only if R = R−1.
Solution: If R = R−1, then R ⊆ R−1 and R−1 ⊆ R.
If R = R−1: If R is symmetric, then ∀a,b ∈ A, (a,b) ∈ R and (b,a) ∈ R, so (a,b) ∈ R−1 (by definition of inverse of relation). Thus, R ⊆ R−1. Moreover, R−1 ⊆ R. Therefore, R = R−1 Only If R = R−1: Conversely, if R = R−1 and (a,b) ∈ R, then (b,a) ∈ R−1, so (b,a) ∈ R.

Thus R is symmetric.

(b) 5 points Show that the relation R on a set A is reflexive if and only if R is irreflexive.

Solution: By the definition of the complementary relation R, if (a,b) ∈/ R,(a,b) ∈ R. R is reflexive if and only if R contains all the pairs (a,a). Then by definition of complementary

relation, none of those pairs can exist in R. Thus the pairs (a,a) ∈/ R, then by definition

of irreflexive, R is irreflexive. So R can only be reflexive if its complementary relation R is irreflexive. Hence proved.
(c) 5 points Let R be a relation that is reflexive and transitive. Prove that Rn = R for all positive integers n.
Solution: (Proof by Induction)
Rn = R, by definition of composite relations, Rn = Rn−1 ◦ R. Thus Rn−1 ◦ R ⊆ R, and R ⊆ Rn−1 ◦ R
For Reflexive:
Base Step (n = 1): R1 = R (Trivial Proof). R is reflexive
Assumption (n = k): Assume that Rk is reflexive. Then for all pairs, (a,a) ∈ R and (a,a) ∈ Rk.
Inductive Step (n = k+1): By definitin, Rk+1 = Rk ◦ R. Since for all pairs (a,a) ∈ R, and (a,a) ∈ Rk, so (a,a) ∈ Rk+1.
For Transitive:
Base Step, (n = 1): R1 = R (Trivial Proof). R is transitive.
Assumption, (n = k): Assume that Rk is transitive. So our inductive hypothesis becomes that Rk = R
Inductive Step, (n = k + 1): By definition, Rk+1 = Rk ◦ R. For a pair (a,c) ∈ Rn ◦ R, there must exist an element b such that (a,b) ∈ R, and (b,c) ∈ Rk. Then by the inductive hypothesis, (b,c) ∈ R. Since R is transitive, (a,c) ∈ R, and also since Rk = R, (a,b) ∈ Rk so (a,c) ∈ Rk.
So it can be concluded from above that Rn ⊆ R and R ⊆ Rn. Thus proved that Rn = R where R is a relation that is reflexive and transitive.
(d) 5 points Show that the relation R on a set A is transitive if and only if Rn ⊆ R for all positive integers n.
Solution: If: Suppose that Rn ⊆ R for n = 2 (trivial for n = 1). Then R2 ⊆ R. If (a,b) ∈ R, and (b,c) ∈ R then by definition of composite relation, (a,c) ∈ R2. Since R2 ⊆ R, then (a,c) ∈ R as well. Hence R is transitive.
Only if: (Proof by induction)
Statement is trivially true for n = 1. R1 ⊆ R
Assume that Rn ⊆ R. Then Rn+1 must also be a subset of R. By definition, Rn+1 = Rn ◦ R. Assume that (a,c) ∈ Rn+1, then there is an element b such that (a,b) ∈ R and (b,c) ∈ Rn. Then Rn ⊆ R implies that (b,c) ∈ R. Also since R is transitive, (a,c) ∈ R since (a,b) ∈ R and (b,c) ∈ R. Since (a,c) ∈ R and (a,c) ∈ Rn+1, this shows that Rn+1 ⊆ R. Hence proved.
8. Given the matrix, MR, for a relation, R, on a finite set, A, explain how to obtain the following matrices?
(a) 5 points MR−1 (b) 5 points MR
Solution:
(a) We know that MR−1 is defined as MR−1 = {(b,a) | (a,b) ∈ R}
In other words, the order of the ordered pairs in the relation is reversed. In terms of matrix representation, it can be expressed as a transpose of the original matrix M.
The transpose of a matrix is obtained by swapping the rows and and columns of the matrix. So, the values that were represented by the columns would now be represented by rows and vice versa. This obtains the desired matrix representation for MR−1.
(b) MR is defined as the complementary relation over M: MR = {(a,b) | (a,b) ∈/ R}
Here the matrix representation swaps 1’s and 0’s. To represent that (a,b) exists in the relation M, Mij = 1 for the respective row (i) and column (j). However to represent MR, instead of 1 the MR ij = 0 indicating the absence of (a,b) ∈ R in MR.
9. The following questions refer to the relations, R and S, involving the set X = {a,b,c}. Specifically, R and S are relations on 2X, the power set of X. For the definitions of R and S given below, prove whether each is an equivalence relation.
(a) 5 points R = {(A,B) | |A| = |B|}. (b) 5 points S = {(A,B) | |A| < |B|}.
Solution:
(a) R will be reflexive as for any element A ∈ 2X, the cardinality of A is equal to itself. Therefore, (A,A) ∈ R. R will also be symmetric as for A,B ∈ 2X, if |A| is equal to |B|, then |B| is also equal to |A|. Therefore, (A,B) ∈ R, and (B,A) ∈ R as well. R will be transitive as for A,B,C ∈ 2X. If |A| is equal to |B|, and |B| is equal to |C|, then |A| is also equal to |C|. Thus R will be transitive.
Since R is reflexive, symmetric and transitive, R is an equivalence relation.
(b) S will not be reflexive as for any element A ∈ 2X, the cardinality of that element cannot be less than itself. Thus S will not be reflexive. Moreover, S is also not symmetric as for A,B ∈ 2X, if |A| < |B|, then |B| ≮ |A|, therefore S is also not symmetric. So it can be concluded that S is not an equivalence relation.
10. 5 points A partition P1 is called a refinement of the partition P2 if every set in P1 is a subset of one of the sets in P2. Given equivalence relations, R1 and R2, on a set, A, and the corresponding partitions, P1 and P2, show that R1 ⊆ R2 if and only if P1 is a refinement of P2.
Solution:
P1 is a refinement of P2 can be expressed as:
∀a∃b(a ⊆ b)|(a ∈ P1)(b ∈ P2) since partitions P1 and P2 correspond to relations R1 and R2 on set A respectively, above statement can also be written as,
∀a∃b(a ⊆ b)|(a ∈ xR1y)(b ∈ xR2y)
To show that R1 ⊆ R2 ⇐⇒ ∀a∃b(a ⊆ b)|(a ∈ xR1y)(b ∈ xR2y)
First R1 ⊆ R2 ⇒ ∀a∃b(a ⊆ b)|(a ∈ xR1y)(b ∈ xR2y)
Let |a| be a representative of a random equivalence class in R1 on set A then as per the definition of a class, every element of this class exists in xR1y or |a|R1 ⊆ xR1y for a random class |a|R1 in R1. We know that R1 ⊆ R2, through transivity we can say that |a|R1 ⊆ R2
Since |a|R1 was a random equivalence class, this can be generalized for all the equivalence classes of
R1:
∀a : |a|R1(|a|R1 ⊆ R2)
Like we did for R1 we can deduce that every equivalence class in R2 is a subset of R2:
∀b : |b|R2(|b|R2 ⊆ R2)
R2 can also be written as the union of all partitions of R2
∀b : |b|R2(|b|R2 ⊆ UPiR2) where UPiR2 represents the union of all the equivalent classes of R2. By the definition of a union then we can conclude that |a|R1 is the subset of at least one partition of R2 and hence:
∀a : |a|R1∃P2 : P2 ∈ R2(|a|R1 ⊆ P2) By using the transitivity property of subsets, let b ⊆ P2
∀a∃b(|a|R1 ⊆ P2)|(|a|R1)(b ∈ P2)
It is the same definition as P1 is a refinement of P2. Hence proven that
R1 ⊆ R2 ⇒ ∀a∃b(a ⊆ b)|(a ∈ xR1y)(b ∈ xR2y)
Following the same method ∀a∃b(a ⊆ b)|(a ∈ xR1y)(b ∈ xR2y) ⇒ R1 ⊆ R2 can also be proved.
3 Ordering
11. Prove or disprove whether each of the relations represented below is a partial order.
1 1 1 0
(a) 5 points(b) 5 points 10 10 11 01
1 1 0 1
Solution:
(a) The matrix representing the relation is not antisymmetric since (1, 2) and (2, 1) both exist within the relation, however, 1 ̸= 2. Thus it is not partial order relation.
(b) The matrix representing the relation is not antisymmetric since (1, 2) and (2, 1) both exist within the relation, however, 1 ̸= 2. Moreover, (2, 3) exist, and (3, 4) exists, however, (2, 4) does not exist so it is also not transitive. Thus this relation is not partial order.
12. 5 points Given a poset (S,R), its dual is (S,R−1). Show that the dual is also a poset.
Solution:
The inserve relation R−1 is defined as R−1 = {(b,a) | (a,b) ∈ R}
Since (S,R) is a poset then it satisifies, reflextiviy, antisymmetry, and transitivity. Considering (S,R−1):
For reflexivity:
Let a be a random such that (a,a) ∈ (S,R), since (a,a) is commutative, (a,a) ∈ (S,R−1) Since a is random, it can generalized to all a in (S,R−1), hence (S,R−1) is reflexive.
For antisymmetry:
Let a random (x,y) ∈ (S,R), then (x,y) ∈ (S,R−1). Because of the antisymmetry of (S,R), (y,x) does not exist in (S,R) which means (x,y) cannot exist in (S,R−1).
This is true for all x,y such that (x,y) and x ̸= y. Hence, (S,R−1) is antisymmetric.
For transitivity:
Let (x,y) ∈ (S,R) and (y,z) ∈ (S,R), then as per transitivity (x,c) ∈ (S,R). Considering the same elements. (x,y) ∈ (S,R) ⇒ (y,x) ∈ (S,R−1) ∧ (y,z) ∈ (S,R) ⇒ (z,y) ∈ (S,R−1).
Here, (z,y) and (y,x) indicates that (z,x) ∈ (S,R−1). This is true for all x,y,z such that (x,y) ∈ (R,S) ∧ (y,z) ∈ (R,S) .
13. Answer the following questions for the partial order represented by the given Hasse diagram.
(a) 2 points Find the maximal elements.
(b) 2 points Find the minimal elements.
(c) 1 point Is there a greatest element? If so, what is it?
(d) 1 point Is there a least element? If so, what is it?
(e) 2 points Find all upper bounds of {a,b,c}.
(f) 1 point Find the least upper bound of {a,b,c}, if it exists.
(g) 2 points Find all lower bounds of {f,g,h}.
(h) 1 point Find the greatest lower bound of {f,g,h}, if it exists.

Solution:
(a) Maximal elements do not have any element above them, so they are l and m.
(b) Minimal elements do not have any element below them, so they are a, b and c.
(c) A greatest element is a unique element greater than all other elements. l and m are both at the same level, neither is greater, so there is no greatest element.
(d) A least element is a unique element lesser than all other elements. a, b and c are both at the same level with none below any other, so there is no least element.
(e) Upper bounds of elements {a,b,c} will be common elements from which a downward path can be created to all three elements. Thus the upper bounds will be l, m and k.
(f) Least upper bound will be the element lesser than all the other upper bounds of {a,b,c}. k is the least upper bound.
(g) Lower bounds of elements {f,g,h} will be common elements from which an upward path can be created to all three elements. However, there is no such common element between f and h thus there are no lower bounds.
(h) There is no greatest lower bound since there are no lower bounds.