Section 1

1- List the members of these sets

a) {x | x is a real number such that 𝑥 2 =1}

c) {x | x is the square of an integer and x<100}

2-Use set builder notation to give a description of each

of these sets.
a) {0,3,6,9,12}

b) {−3,−2,−1,0,1,2,3}

3- How many elements does each of these sets have

where a and b are distinct elements?
a) P({a,b,{a,b}})
b) P(P(∅))

c) P(∅)

4-What is the cardinality of each of these sets?

a) {a}

b) {{a}}

c) {a,{a}}

d) {a,{a},{a,{a}}}

5- Find the power set of each of these sets, where a and b are
distinct elements.

a) {a}
b) {a,b}
c){{∅},∅ }

5-Find the truth set of each of these predicates where

the domain is the set of integers.
a) P(x) : 𝑥 3 ≥1

b) Q(x): 𝑥 2 =2

c) R(x): x<𝑥 2

6-Let A ={ 1,2,3,4,5} and B ={ 0,3,6}. Find

a) A∪B.

b) A∩B.

c) A−B.

.d) B −A

7-Prove the complementation law in Table 1 by showing

that
𝐴= = A

8-Show that if A, B, and C are sets, then

A∩B ∩C = A∪B ∪C
9- Show that if A and B are sets, then

A−B = A∩B
10-Why is f not a function from R to R if

a) f(x)=1/x?

b) f(x)= sqrt (x)?

c) f(x)=±sqrt( 𝑥 2 +1)?
11- Find the domain and range of these functions. Note that in
each case, to find the domain, determine the set of elements
assigned values by the function

a) the function that assigns to each bit string the number of

ones in the string minus the number of zeros in the string

b) the function that assigns to each bit string twice the number
of zeros in that string

12- Find the domain and range of these functions. Note that in
each case, to find the domain, determine the set of elements
assigned values by the function.

a) the function that assigns to each nonnegative integer its last

digit
****************************************************

section 2
1- Give an example of a function from N to N that is

a) one-to-one but not onto.

b) onto but not one-to-one.

c) both onto and one-to-one(but different from the identity

function).

d) neither one-to-one nor onto

2- Let f be the function from R to R defined by f(x)=𝑥 2 . Find

a) 𝑓 −1 ({1}).

b) 𝑓 −1 ({x |0 <x<1}).

c) 𝑓 −1 ({x | x>4})
3-Find these values.
a)⌊1.1⌋
b) ⌊-0.1⌋
c) ⌈1.1⌉
d) ⌈-0.1⌉

G) ⌊1/2+⌈-0.1⌉+1/2⌋
h) ⌈1/2+⌊-0.1⌋+1/2⌉

4-Determine whether each of these functions from Z to

Z is one-to-one.
a) f(n) = n−1
b) f(n) = 𝑛2 +1
c) f(n) = 𝑛3
d) f(n) =⌈n/2⌉
5- Determine whether f:Z×Z→Z is onto if
a) f(m,n) =2m−n.

3 2
.b) f(m,n) = 𝑛 −𝑛
.c) f(m,n) = m
6- Determine whether each of these functions is a bijection
from R to R.

a) f(x)=− 3x +4

b) f(x)=− 3x2 +7
7-Let S ={− 1,0,2,4,7}. Find f(S)if

a) f(x)=1.

b) f(x)=2x +1.
c) f(x)= ⌈x/5⌉

8-Find the inverse function of

f(x)= x3 +1
9-Find these terms of the sequence {an}, where 𝑎𝑛 =
2·𝑛(−3)𝑛 +5𝑛 .
a) 𝑎0

b) 𝑎1
c) 𝑎4
d) 𝑎5

10-Find the first five terms of the sequence defined by

each of these recurrence relations and initial
conditions.
a) 𝑎𝑛 =6𝑎𝑛−1 , 𝑎0 =2

b) 𝑎𝑛 = 𝑎𝑛−1 2 , a1 =2

.= c) 𝑎𝑛 = 𝑎𝑛−1 +3𝑎𝑛−2 , 𝑎0 =1, 𝑎1 =2

****************************************************
section 3
1-What are the values of these sums , where S ={
1,3,5,7}?
a) ∑𝑠𝑗∈𝐬 𝑗

b) ∑𝑠𝑗∈𝐬 j2
𝑠
c) ∑𝑗∈𝐬(1/j)
d) ∑𝑠𝑗∈𝐬 1
2-Find the value of each of these sums.
8
a) ∑𝑗=𝟎(1 + (−1)2 )

8
b) ∑𝑗=𝟎 3𝑗 + 2𝑗
.3-Compute each of these double sums
3
2
a) ∑ ∑𝑗=𝟎(𝑖 − 𝑗)
𝑖 =𝟎
3
2
b) ∑ ∑𝑗=𝟎(𝑗)
𝑖 =𝟎
3
2
c) ∑ ∑𝑗=𝟎(𝑖 2 𝑗 3 )
𝑖 =𝟎
4- Show that the set of all integers is countable

5- Show that the set of all positive even is countable

6- Show that the set of all positive odd is countable

7- Show that the set of N is countable

8-List the ordered pairs in the relation R from A ={ 0,1,2,3,4}to B

={ 0,1,2,3}, where (a,b) ∈ Rif and only if

a) a=b

. b) a+b =4.

c) a>b

9-For each of these relations on the set{1,2,3,4}, decide

whether it is reflexive, whether it is symmetric, whether it is
antisymmetric, and whether it is transitive.

a) {(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

b) {(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}
c) {(2,4),(4,2)} d) {(1,2),(2,3),(3,4)}

e) {(1,1),(2,2),(3,3),(4,4)}

10-let R1={(1,2),(2,3),(3,4)}and
R2={(1,1),(1,2),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(3,4)}

Find

a) R1 ∪R2.

b) R1 ∩R2.

c) R1 −R2.

d) R2 −R1.
11-Let R1 and R2 be the “divides” and “is a multiple of”
relations on the set of all positive integers, respectively. That is,
R1 ={(a,b) | a divides b}and R2 ={(a,b) | a is a multiple of b}.
Find

a) R1 ∪R2.

b) R1 ∩R2.

c) R1 −R2.

d) R2 −R1.

12-LetR be the relation{(1,2),(1,3),(2,3),(2,4),(3,1)} and S be the

relation {(2,1),(3,1),(3,2),(4,2)}

.Find S ◦R
****************************************************
Section 4
1-List the triples in the relation {(a,b,c)| a,b, and c are integers
with 0 <a<b<c<5}

2-Which 4-tuples are in the relation {(a,b,c,d)| a,b, c, and d are

positive integers with abcd =6}?

3-Represent each of these relations on{1,2,3}with a matrix

(with the elements of this set listed in increasing order).

a) {(1,1),(1,2),(1,3)}

b) {(1,2),(2,1),(2,2),(3,3)}

c) {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}

d) {(1,3),(3,1)}
4-List the ordered pairs in the relations on{1,2,3}corresponding
to these matrices (where the rows and columns correspond to
.the integers listed in increasing order)

a)

1 0 1
0 1 0
1 0 1
b)

0 1 0
0 1 0
0 1 0
c)
1 1 1
1 0 1
1 1 1

5-Let R be the relation represented by the matrix

0 1 1

𝑀𝑅 = 1 1 0

1 0 1

Find the matrix representing

a) 𝑅 −1 .

b) R.

. c) 𝑅 2
5- Let R1 and R2 be relations on a set A represented by the
matrices

0 1 1

𝑀𝑅1 = 1 1 0

1 0 1

0 1 1

𝑀𝑅2 = 1 1 0

1 0 1

Find the matrices that represent

a) R1 ∪R2

b) R1 ∩R2
c) R2◦R1

d) R1◦R1

6-Let R be the relation represented by the matrix

0 1 0

𝑀𝑅 = 0 0 1

1 1 0

Find the matrices that represent

a) R2.

b) R3.

c) R4.
7-Draw the directed graph that represents the relation
{(a,a),(a,b),(b,c),(c,b),(c,d),(d,a), (d,b)}
8-list the ordered pairs in the relations represented by the
directed graphs
9-Let R be the relation on the set {0,1,2,3} containing the
ordered pairs (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0).

Find the

a) reflexive closure of R.

b) symmetric closure of R

10-draw the directed graph of the reflexive closure of the

relations with the directed graph shown

11-Find the smallest relation containing the relation

{(1,2),(1,4),(3,3),(4,1)}that is

a) reflexive and transitive.

b) symmetric and transitive.

c) reflexive, symmetric, and transitive

12-Use Algorithm 1 to find the transitive closures of

these relations on{a,b,c,d,e}.
a) {(a,c),(b,d),(c,a),(d,b),(e,d)}
b) {(b,c),(b,e),(c,e),(d,a),(e,b),(e,c)}

********************************
section5
1-Use Warshall’s algorithm to find the transitive closures of the
relations
a) {(1,2),(2,1),(2,3),(3,4),(4,1)}

b) {(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)}

c) {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

2-Which of these relations on {0,1,2,3} are equivalence

relations? Determine the properties of an equivalence relation
that the others lack.

a) {(0,0),(1,1),(2,2),(3,3)}

b) {(0,0),(0,2),(2,0),(2,2),(2,3),(3,2),(3,3)}

c) {(0,0),(1,1),(1,2),(2,1),(2,2),(3,3)}

d) {(0,0),(1,1),(1,3),(2,2),(2,3),(3,1),(3,2), (3,3)}

e) {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0), (2,2),(3,3)}
3-determine whether the relation with the directed graph
shown is an equivalence relation.
4-Determine whether the relations represented by these zero–
one matrices are equivalence relations.

a) 1 1 1

0 1 1

1 1 1

b) 1 0 1 0

0 1 0 1

1 0 1 0

0 1 0 1
5-Which of these collections of subsets are partitions of
{1,2,3,4,5,6}?

a) {1,2},{2,3,4},{4,5,6}

b) {1},{2,3,6},{4},{5}

c) {2,4,6},{1,3,5}

d) {1,4,5},{2,6}

6- Which of these collections of subsets are partitions of

{−3,−2,−1,0,1,2,3}?

a) {−3,−1,1,3},{−2,0,2}

b) {−3,−2,−1,0},{0,1,2,3}

c) {−3,3},{−2,2},{−1,1},{0}

d) {−3,−2,2,3},{−1,1}

7-Which of these collections of subsets are partitions of the set

of integers?
a) the set of even integers and the set of odd integers

b) the set of positive integers and the set of negative integers

c)the set of integers less than−100, the set of integers with

absolute value not exceeding 100, and the set of integers
greater than 100

8-List the ordered pairs in the equivalence relations produced

by these partitions of{0,1,2,3,4,5}.

a) {0},{1,2},{3,4,5}

b) {0,1},{2,3},{4,5}

c) {0,1,2},{3,4,5}

d) {0},{1},{2},{3},{4},{5}

9-List the ordered pairs in the equivalence relations produced

by these partitions of{a,b,c,d,e,f,g}.

a) {a,b},{c,d},{e,f,g}

b) {a},{b},{c,d},{e,f},{g}

c) {a,b,c,d},{e,f,g}

d) {a,c,e,g},{b,d},{f}

10-Find the smallest equivalence relation on the set {a,b,c,d,e}

containing the relation

{(a,b),(a,c), (d,e)}.
Section 5
1-Determine whether these biconditionals are true or false.

a) 2+2=4 if and only if 1+1=2.

b) 1+1=2 if and only if 2+3=4.

c) 1+1=3 if and only if monkeys can fly.

d) 0 > 1 if and only if 2 > 1.

2-Determine whether each of these conditional statements is

true or false.

a) If 1+1=2, then 2+2=5.

b) If 1+1=3, then 2+2=4.

c) If 1+1=3, then 2+2=5.

d) If monkeys can fly, then 1+1=3.

3-Construct a truth table for each of these compound

propositions.

a) p∧¬p

b) p∨¬p

c) (p∨¬q)→ q

d) (p∨q)→ (p∧q)

e) (p → q)↔ (¬q →¬p)

f) (p → q)→ (q → p)

4-Construct a truth table for each of these compound

propositions.

a) p →¬p
b) p ↔¬p

c) p⊕(p∨q)

d) (p∧q)→ (p∨q)

e) (q →¬p)↔ (p ↔ q)

f) (p ↔ q)⊕(p ↔¬q)

5-How many rows appear in a truth table for each of these

compound propositions?

a) p →¬p

b) (p∨¬r)∧(q ∨¬s)

c) q ∨p∨¬ s ∨¬ r ∨¬ t ∨ u

d) (p∧r ∧t)↔(q ∧t)

6-Construct a truth table for (p ↔ q)↔ (r ↔ s).

7-Explain, without using a truth table, why (p∨¬q)∧ (q ∨¬r)∧

(r ∨¬p) is true when p, q, and r have the same truth value and it
is false otherwise.

8-Explain, without using a truth table, why (p∨q ∨r) ∧

(¬p∨¬q ∨¬r) is true when at least one of p, q, and r is true and

at least one is false, but is false when all three variables have
the same truth value.

9-What is the value of x after each of these statements is

encountered in a computer program, if x =1 before the
statement is reached?

a) if x +2=3 then x := x +1
b) if (x +1=3) OR (2x +2=3) then x := x +1

c) if (2x +3=5) AND (3x +4=7) then x := x +1

d) if (x +1=2) XOR (x +2=3) then x := x +1

e) if x<2 then x := x +1

10-Find the bitwise OR, bitwise AND, and bitwise XOR of each
of these pairs of bit strings.

a) 101 1110, 010 0001

b) 1111 0000, 1010 1010

c) 00 0111 0001, 10 0100 1000

d) 11 1111 1111, 00 0000 0000

11-Evaluate each of these expressions.

a) 1 1000∧(0 1011∨1 1011)

b) (0 1111∧1 0101)∨0 1000

c) (0 1010⊕1 1011)⊕0 1000

d) (1 1011∨0 1010)∧(1 0001∨1 1011)

12- You can see the movie only if you are over 18 years old or
you have the permission of a parent. Express your answer in
terms of m:“Youcanseethemovie,” e:“Youare over 18 years
old,” and p: “You have the permission of a parent.”

13-You can graduate only if you have completed the

requirements of your major and you do not owe money to the
university and you do not have an overdue library book.
Express your answer in terms of g: “You can graduate,” m:“You
owe money to the university ,”r:“ You have completed the
requirements of your major,” and b:“You have an overdue
library book.”

14- Find the output of each of these combinatorial circuits

15-Find the output of each of these combinatorial circuits.

16-Construct a combinatorial circuit using inverters, OR gates,

and AND gates that produces the output (p∧¬r)∨(¬q ∧r)from
input bits p, q, and r.
17- Construct a combinatorial circuit using inverters, OR gates,
and AND gates that produces the output ((¬p∨¬r)∧¬q)∨(¬p∧(q
∨r)) from input bits p, q, and r.

18- Use truth tables to verify these equivalences.

a) p∧T≡ p

b) p∨F≡ p

c) p∧F≡F

d) p∨T≡T

e) p∨p ≡ p

f) p∧p ≡ p

19- Show that¬(¬p) and p are logically equivalent.

20-Use De Morgan’s laws to find the negation of each of the

following statements.

a) Jan is rich and happy.

b) Carlos will bicycle or run tomorrow