Sets
What set has the least number of subsets?
Empty set, only has 1 subset which is itself
a | a for all a in integers.
False, 0 would not work
Every function is a relation.
True, functions are a specific type of relations.
A ternary predicate is a subset of what set?
U x U x U
The power set of a set with n elements, has how many elements?
n^2
Reflexive, everything divides itself.
Transitive, if a|b and b|c then a|c.
And antisymmetric, if a|b and b|a, they must be equal.
But not symmetric.
Given a set A of n elements, how large can its relations set be?
n x n
How many 4 number credit card password combinations exist?
10 x 10 x 10 x 10 = 10^4
Suppose A is some set, What is the minimum and maximum number of elements that AxA could possibly have?
0 if its empty set, infinity if the set is infinity.
if for all non zero integers x, x does not divide y, then y is a prime number.
True. Antecedent is false, therefore whole statement is true.
What is an equivalence class?
R,S,T
A loop invariant can be false somewhere in the program
True, only in the middle of the program, at the start, end, before and after it must be true
Take set A to be a subset of natural numbers, the summation of the elements of set A will always be larger than the number of elements in A.
False. {1} does not follow this rule
is it true that (m*n) mod m = (m*n) mod n
False, its basically saying n mod m = m mod n, but mod is not symmetric since 2 mod 5 does not equal 5 mod 2.
The equality relation on integers is an equivalence relation and total order
False, it doesnt satisfy totality
Suppose a query on a database specified all variables as free variables, and no quantifiers, what will be returned?
The entire database
If set A is a subset of set B, and set B has an element x that set A does not have, could set A and B be the same size?
Yes
If a ≡ b mod m, then -a ≡ -b mod m.
True
If a relation is symmetric and antisymmetric, it can still be not reflexive.
True
Suppose a function is an equivalence relation and a partial order, is that function bijective?
Yes. it can only be equivalence relation and total order if every number outputs only itself, therefore it is injective(one to one), and surjective(everything has something pointing to it)