Part 1.
Problems 1,2,3,4: translate the following into formal statements of set theory. Assume that the universal set U (containing all objects of interest) consists of all natural numbers smaller or equal than 20.
1. Set A consists of numbers divisible by 10.
Solution: .
2. Let A be the set consisting of all natural numbers, which are divisible by 2 and let B be the set consisting of all natural numbers divisible by 3.
Express the following in terms of equality and set operations performed on A and B.
(i) Set C consists of all natural numbers divisible by 2 and 3.
Solution: .
(ii) Set C consists of all natural numbers divisible by 2 or 3.
Solution: .
(iii) Set C consists of all natural numbers divisible by 2 but not by 3.
Solution: .
(iv) Set C contains at least one number divisible by 3.
Solution: .
Express the following in terms of inclusion relation and set B.
(v) All numbers contained inside set D are divisible by 3.
Solution: .
(vi) None of the numbers inside set D is divisible by 3.
Solution: .
3. Set A consists of prime numbers.
Solution: .
4. Precisely half of the numbers of set A are divisible by 3.
Solution: .
5. Is it true that for all finite sets A, B, C
Solution: Yes, because sets on the right hand side are pair-wise
disjoint (every pair of different sets has empty intersection) and their
union equals .
Part 2.
1. For each of the laws of Set Theory ((i), (ii) (iii)) find the corresponding law of Propositional Calculus.
(i)
(ii)
(iii)
Solution:
(i)
(ii)
(iii)
2. What law of Set Theory corresponds to the following law of
Propositional Calculus ?
Solution: .
Part 3.
Let us assume that the universal set consist of natural numbers, e.g. . Express the following as statements of Propositional Logic.
1. Every number larger than 10 is positive.
Solution: .
2. Every square is non-negative.
Solution: .
3. Every number divisible by 2 and 3 is divisible by 6.
Solution: .
4. At least one of the numbers x,y,z is positive.
Solution: .
5. All the numbers x,y,z are even.
Solution: .
6. None of the numbers x,y,z is positive.
Solution: .
7. None or both x and y are even.
Solution: .
8. Precisely one of the numbers x,y is even.
Solution: .
9. is a prime number, i.e. it is different than 1 and its only divisors are
and .
Solution: .
10. is the smallest number of a subset .
Solution: .
11. is the greatest common divisor of numbers and .
Solution: .
12. is the least common multiple of numbers and .
Solution: .
Part 4.
1. Functions p(x) and q(x) return Boolean values and take arguments, which are Point class objects (in this problem we do not need implementations neither of p(x), q(x) nor of the Point class). Implement function F described below using just one return statement.
bool F(Point x)
{
if(p(x))
return true;
else if (q(x))
return false;
else
return true;
}
bool F(Point x)
{
return ???;
}
Solution: return !q(x)||(p(x)&&q(x)) or .
2. Translate the following into Propositional Logic.
(i) Array a[0..n-1] contains no zeros.
Solution: .
(ii) Array a[0..n-1] consists of ones.
Solution: .
(iii) Array a[0..n-1] consists of prime numbers.
Solution: , where
(iv) Index i corresponds to the largest element of the array
a[0..n-1].
Solution: .
(v) Array a[0..n-1] is ordered increasingly.
Solution: .
Part 5.
1. Let . List all the elements of
Solution: .
2. Express in terms of
(i) and
Solution:
(ii) and
Solution:
3. Express in terms of
(i) and
Solution:
(ii) and