Chapter 1 and 2
1. On the island of knights and knaves, you meet three natives, A, B, and C, who address
you as follows :A: At least one of us is a knave. B: At most two of us are knaves.
What are A, B, and C?
A: Knight
B: Knight
C:Knave
2. Consider the following circuit.
(a) Find the output of the circuit corresponding to the input P = 1, Q = 0, and R = 1.
To find the output, we need the specific circuit diagram or
description. Without this, we can’t find the output
S = (¬ (P∧Q)) ∧(QvR)
(b) Write the Boolean expression corresponding to the circuit.
3. Write 1101012 in decimal form.
Decimal form: 53
4. Write 75 in binary notation.
Binary Form: 1001011
5. Draw the circuit that corresponds to the following Boolean expression: (P ∧ Q) ∨ (~ P∧ ~
Q).(Note for students who have studied some circuit design: Do not simplify the circuit; just
draw the one that exactly corresponds to the expression.)
P ----|>o-----| |------|
| | | |
| | | AND |
| |----->| | |
| |-----|----> (P ∧ Q)
Q ----|>o-----| |
| |
|------| | AND
| |
| |
|----->| |
|-----|-----|----> (¬P ∧ ¬Q)
P ----|>o-----|
|----->| |
| | OR
Q ----|>o-----| |
|----->|
5. Find a circuit with the following input/output table.
1: NOT gates to handle the negation of (¬P, ¬Q, and ¬S)
2: AND gates to compute each minterm
3. OR gate to combine the outputs of all the AND gates
6. Find 101112 + 10112. Total: 100010
7. Write 1001102 in decimal form. Decimal form: 38
9. (a) Is {5} ∈ {1, 3, 5}?
8. Write the 8-bit two’s complement for 49. Complement for 49: 00110001
(b) Is {5} ⊆ {1, 3, 5}?
(c) Is {5} ∈ {{1}, {3}, {5}}?
(d) Is {5} ⊆ {{1}, {3}, {5}}?
A: No, {5} isn’t an element of {1, 3, 5}
B: No, {5} is not a subset of {1, 3, 5}
C: Yes, {5} is an element of {{1}, {3}, {5}}
D: No, {5} is not a subset of {{1}, {3}, {5}}
10. Let A = {a, b, c} and B = {u, v}. Write a. A × B and b. B × A.
(a) A x B: A x B= {(a,u),(a,v),(b,u), (b,v),(c,u),(c,v)}
(b) B x A: B x A = {(u,a),(u,b)(u,c),(v,a),(v,b),(v,c)}
For all (x, y) ∈ A × B, (x, y) ∈ R ⇔ y/x is an integer.
11. Let A = {3, 5, 7} and B = {15, 16, 17, 18}, and define a relation R from A to B as follows:
(a) Is 3 R 15? Is 3 R 16? Is (7, 17) ∈ R? Is (3, 18) ∈ R? Yes, No, No, Yes
(b) Write R as a set of ordered pairs. R= {(3, 15), (3, 18)}
(c) Write the domain and co-domain of R. Domain = {3}
(d) Draw an arrow diagram for R.
A: 3 5 7
|\
| \
V V
B: 15 18 16 17
(e) Is R a function from A to B? Explain.
A function from A to B must be assigned to one element of B to each element of A. R, 3 is both related
to 15 and 18 so that means 3 is going to have to be assigned to multiple elements in B. R is not a
function from A to B because the 3 in element A is associated with more than one element in B
12. Define a relation R from R to R as follows: For all (x, y) ∈ R × R, (x, y) ∈ R if, and only if,
x = y 2 + 1.
(a) Is (2, 5) ∈ R? Is (5, 2) ∈ R? Is (−3) R 10? Is 10 R (−3)? False, True, False, True
(b) Draw the graph of R in the Cartesian plane.
(c) Is R a function from R to R? Explain.
R is not a function because it does not meet the requirement for each of the inputs of x to
map to another output of y
13. Let A = {1, 2, 3, 4} and B = {a, b, c}. Define a function G: A → B as follows:G = {(1, b),(2,
c),(3, b),(4, c)}.
(a) Find G(2). G(2) = c
(b) Draw an arrow diagram for G.
A: 1 2 3 4
| | | |
V V V V
B: a b c
14. Define functions F and G from R to R by the following formulas:
F(x) = (x + 1)(x − 3) and G(x) = (x − 2)2 − 7.
Does F = G? Explain.
(a) Is {5} ∈ {1, 3, 5}? False
15.
(b) Is {5} ⊆ {1, 3, 5}? True
(c) Is {5} ∈ {{1}, {3}, {5}}? True
(d) Is {5} ⊆ {{1}, {3}, {5}}? False
16. Let A = {a, b, c} and B = {u, v}. Write (a). A × B and (b). B × A.
A×B: {(a,u),(a,v),(b,u),(b,v),(c,u),(c,v)}
B×A: {(u,a),(u,b),(u,c),(v,a),(v,b),(v,c)}
17. Let A = {3, 5, 7} and B = {15, 16, 17, 18}, and define a relation R from A to B as follows: For all (x, y) ∈
(x, y) ∈ R ⇔ y/x is an integer.
A × B,
(a) Is 3 R 15? Is 3 R 16? Is (7, 17) ∈ R? Is (3, 18) ∈ R? True, False, False
(b) Write R as a set of ordered pairs.
R= {(3, 15), (3, 18), (5, 15)}
(c) Write the domain and co-domain of R. Domain = {3, 5} Co-domain = {15, 18}
18. Let A = {1, 2, 3, 4} and B = {a, b, c}. Define a function G: A → B as follows:
G = {(1, b),(2, c),(3, b),(4, c)}.
Find G(2). G(2) = c
19. Define functions F and G from R to R by the following formulas:
F(x) = (x + 1)(x − 3) and G(x) = (x − 2)2 − 7. Does F = G? Explain.
F≠G because F(x) and G(x) produce different results for the same input x.
20. Convert 99 Hex decimal to binary
Binary: 1001 10012v2
