$30
COMP9020-Set 1 Numbers, Sets, Words and Logic Solved
1. (Numbers)
How many numbers in the interval [1431,9758] are
a. divisible by 3?
b. divisible by 5?
c. divisible by 3 and 5?
d. divisible by 3 or 5?
2. (Sets)
Prove that (A ∖ B) ∪ (B ∖ A) = (A ∪ B) ∖ (A ∩ B)
a. using Venn diagrams,
b. without Venn diagrams.
[hide answer]
3. (Alphabets and Words)
Let Σ = {a,b,c} and Ψ = {a,c,e}.
a. How many words are in the set Σ2 ?
b. What are the elements of Σ2 ∖ Ψ∗ ?
c. Is it true that Σ∗ ∖ Ψ∗ = (Σ ∖ Ψ)∗ ? Why or why not?
(Propositional Logic)
For each of the following formulae, determine all the truth assignments to A, B and C under which the formula is true.
a. A ∧ (¬C ⇒ (B ∨ ¬A))
b. (A ∧ ¬C) ⇒ (B ∨ ¬A)
c. (¬C ⇒ ¬A) ∧ (B ⇒ (A ∧ ¬C))
d. ¬(C ⇒ A) ∧ (A ∨ (B ∧ ¬C))
4. (Proving properties of algorithms)
Recall the algorithm for computing the greatest common divisor (gcd) of two positive numbers:
⎧⎪ m
gcd(m,n) = ⎨⎩⎪ gcd(m − n,n)
gcd(m,n − m)
if m = n if m n if m < n
Recall the correctness proof given in class. What needs to be changed to adapt it to the faster version below?
m if n = 0 gcd(n,mmodn) if n 0
gcd(m,n) = {
6. Challenge Exercise
A multiplication magic square has the product of the numbers in each row, column and diagonal the same. If the diagram below is filled with positive integers to form a multiplicative magic square, then give the value of y.
1. (Numbers)
How many numbers in the interval [1431,9758] are
a. divisible by 3?
b. divisible by 5?
c. divisible by 3 and 5?
d. divisible by 3 or 5?
2. (Sets)
Prove that (A ∖ B) ∪ (B ∖ A) = (A ∪ B) ∖ (A ∩ B)
a. using Venn diagrams,
b. without Venn diagrams.
[hide answer]
3. (Alphabets and Words)
Let Σ = {a,b,c} and Ψ = {a,c,e}.
a. How many words are in the set Σ2 ?
b. What are the elements of Σ2 ∖ Ψ∗ ?
c. Is it true that Σ∗ ∖ Ψ∗ = (Σ ∖ Ψ)∗ ? Why or why not?
(Propositional Logic)
For each of the following formulae, determine all the truth assignments to A, B and C under which the formula is true.
a. A ∧ (¬C ⇒ (B ∨ ¬A))
b. (A ∧ ¬C) ⇒ (B ∨ ¬A)
c. (¬C ⇒ ¬A) ∧ (B ⇒ (A ∧ ¬C))
d. ¬(C ⇒ A) ∧ (A ∨ (B ∧ ¬C))
4. (Proving properties of algorithms)
Recall the algorithm for computing the greatest common divisor (gcd) of two positive numbers:
⎧⎪ m
gcd(m,n) = ⎨⎩⎪ gcd(m − n,n)
gcd(m,n − m)
if m = n if m n if m < n
Recall the correctness proof given in class. What needs to be changed to adapt it to the faster version below?
m if n = 0 gcd(n,mmodn) if n 0
gcd(m,n) = {
6. Challenge Exercise
A multiplication magic square has the product of the numbers in each row, column and diagonal the same. If the diagram below is filled with positive integers to form a multiplicative magic square, then give the value of y.
1. (Numbers)
How many numbers in the interval [1431,9758] are
a. divisible by 3?
b. divisible by 5?
c. divisible by 3 and 5?
d. divisible by 3 or 5?
2. (Sets)
Prove that (A ∖ B) ∪ (B ∖ A) = (A ∪ B) ∖ (A ∩ B)
a. using Venn diagrams,
b. without Venn diagrams.
[hide answer]
3. (Alphabets and Words)
Let Σ = {a,b,c} and Ψ = {a,c,e}.
a. How many words are in the set Σ2 ?
b. What are the elements of Σ2 ∖ Ψ∗ ?
c. Is it true that Σ∗ ∖ Ψ∗ = (Σ ∖ Ψ)∗ ? Why or why not?
(Propositional Logic)
For each of the following formulae, determine all the truth assignments to A, B and C under which the formula is true.
a. A ∧ (¬C ⇒ (B ∨ ¬A))
b. (A ∧ ¬C) ⇒ (B ∨ ¬A)
c. (¬C ⇒ ¬A) ∧ (B ⇒ (A ∧ ¬C))
d. ¬(C ⇒ A) ∧ (A ∨ (B ∧ ¬C))
4. (Proving properties of algorithms)
Recall the algorithm for computing the greatest common divisor (gcd) of two positive numbers:
⎧⎪ m
gcd(m,n) = ⎨⎩⎪ gcd(m − n,n)
gcd(m,n − m)
if m = n if m n if m < n
Recall the correctness proof given in class. What needs to be changed to adapt it to the faster version below?
m if n = 0 gcd(n,mmodn) if n 0
gcd(m,n) = {
6. Challenge Exercise
A multiplication magic square has the product of the numbers in each row, column and diagonal the same. If the diagram below is filled with positive integers to form a multiplicative magic square, then give the value of y.
