Exam Date: March 28, 2011
1. Show whether each of the following is a tautology, contradiction, or neither using truth tables:
(a) p → ¬( p ∨¬q) ... Close neither
(b) q ∧ ¬( p ∨q) ... Close contradiction
(c) (( p ∨ ¬p) → q) ... Close neither
(d) ¬q ∨ (¬q → p) ... Close tautalogy
(e) [( p ∨ q ) ∧ ( p ⊕ r ) ∧ ( q ⊕ r )] ... Close neither
2. Show whether each of the expression in problem 1 is a tautology, contradiction, or neither using the properties of logic. (logical equivalence's):
(a) 
Associative laws 
x(yz) = (xy)z 


x ∨ (y ∨ z) = (x ∨ y) ∨ z 
(b) 
Commutative laws 
x ∧ y = y ∧ x 


x ∨ y = y ∨ x 
(c) 
Distributive laws 
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) 


x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) 
(d) 
Identity laws 
x ∧ T = x 


x ∨ F = x 
(e) 
Dominance laws 
x ∧ F = F 


x ∨ T = T 
(f) 
Idempotent laws 
x ∧ x = x 


x ∨ x = x 
(g) 
Complement laws 
x ∧ ¬x = F 


x ∨ ¬x = T 
(h) 
Double complement law 
¬( ¬x) = x 
(i) 
DeMorgan's laws 
¬(x ∧ y) = ¬x ∨ ¬y 


¬(x ∨ y) = ¬x ∧ ¬y 
(j)  Absorbtion  (x ∨ y) ∧ x = x 
(x ∧ y) ∨ x = x 
3. Evaluate each of the following bitwise logic expressions
a. (011010 ∧ 111100) ∨ 001100 = ... Close 011000 ∨ 001100 = 011100
b. 111000 ∨ 001100 ∨ 000001 = ... Close 111101
c. (101010 ∨ 110011) ⊕ 000111 = ... Close 111011 ⊕000111 = 111100
4. Prove using truth tables whether each of the following pairs of expressions are equivalent:
a. p ↔ q and ( p ∨ q) → ( p ∧ q) ... Close = yes
b. ( p ↔ q) ∨ p and ( p ∨ q) ∧ ¬( p ∧ q) ... Close = no
c. ¬( p ∧ ¬q) and p ⊕ q ... Close = yes
5. Show whether each of the expression in problem 4 are equivalent using the properties of logic. (logical equivalence's):
6. State the converse and contrapositive of each of the following implications:
a. If it snows tonight, then I will stay home. ... Close
If I stay home then it will snow tonight.
If I don’t stay home then it will not snow tonight.
b. I go to the beach whenever it is a sunny summer day. ... Close
It is a sunny summer day whenever I go to the beach.
It is not a sunny summer day whenever I don’t go to the beach.
c. When I stay up late, it necessary that I sleep until noon ... Close
When I sleep until noon, it necessary that I stay up late.
When I don’t sleep until noon, it necessary that I don’t stay up late
Consider the following predicates:
C( x,y)  true if person x owns car y.
RED( x)  true if x is a red car.
BLUE( x)  true if x is a blue car.
7. Write the following in symbols:
a. Sandy owns a blue car. ... Close ∃x: C(Sandy,x) ∧ BLUE( x)
b. Every car is either blue or red. ... Close ∀x: RED( x) ∨ BLUE( x)
c. There is a car that is both blue and red. ... Close ∃x: BLUE( x) ∧ RED( x)
d. Every blue car has an owner. ... Close ∀x∃y: BLUE( x) → C( y,x)
e. Every red car owner also owns a blue car ... Close ∀x ∀y ∃z: (C( x,y) ∧ RED( y)) → (C( x,z) ∧ BLUE( z) )
Now consider a world for the above predicates with only 4 people and four cars:
a. Bill owns a blue car and a red car.
b. Sandy owns a red car.
c. Robin owns a blue car.
d. Jack does not own a car.
For the following, consider ONLY the data above:
8. Tell whether each of the following is true or false, and why.
a. ∃ x : C(Bill, x) ... Close true
b. ∃ x : C(Sandy, x) ∧ BLUE( x) ... Close false (Sandy only owns a red car)
c. ∀x ∃y: C( x,y) ... Close false (Jack owns no car)
d. ∀y ∃x: C( x,y) ... Close true
9. Suppose P(x,y) is the statement 2x < y, where x and y are integers. What are the truth values of
d) ∀x∃y P( x,y) ... Close true
e) ∃x∀ y P( x,y) ... Close false
f) ∀y∃x P( x,y) ... Close true
10. Suppose the variable x represents students and y represents dorm rooms:
R( x,y): student x is in dorm room y.
Write each of the following statements using the above predicate and any needed quantifiers:
a) Fran is in room Elmwood 321 ... Close R(Fran,Elmwood 321)
b) Bill does not have a dorm room. ... Close ¬∃x R(Bill,x)
c) There is a dorm room which is not in use (no assigned students). ... Close ¬∀y∃x R( x,y) or ∃y∀x ¬
R( x,y)
d) Every student has a dorm room. ... Close ∀x∃yR( x,y)
e) There is a room with more then one student assigned to it. ... Close ∃x∃y∃zR( x,y) ∧ R( z,y) ∧ x ≠ z
11. Suppose P(x,y) is the statement x + 2y = xy, where x and y are integers. What are the truth values of
(d) ∀x∃yP( x,y) ... Close true
(e) ∃x∀yP( x,y) ... Close False
(f) ∀y∃xP( x,y) ... Close False
(g) ∃y∀xP( x,y) ... Close False
(h) ¬∀x∃y ¬P( x,y) ... Close False
12. Find the size (that is, the cardinal number) of each of the following sets:
(a) {xx ∈ Z and x^{2} < 10}. ... Close 7
(b) P({a,b,c,d}), where P denotes the power set. ... Close 16
(d) A x B where A = {1,2,3,4,5} and B = {1,2,3}. ... Close 15
(e) {xx ∈ N and 9x^{2}  1 = 0}. ... Close 0
(f) P(A), where A is the power set of {a,b,c}. ... Close 256
(g) A x B, where A = {a,b,c} and B = ∅. ... Close 0
(h) {xx ∈ N and 4x^{2}  1 = 0}. ... Close 0
13. Determine the truth value for each of the following.
(a) ∀x ∃y  (x^{2}=y) ... Close True – every number has a square
(b) ∀x ∃y  (x=y^{2}) ... Close False – No y exists if x is negative
(c) ∃x ∀y  ( xy = 0) ... Close True – let x = 0
(d) ∃x ∀y  (y ≠ 0 → xy = 1) ... Close False – no number that when multiplied by anything is always 1
14. Suppose A = {a,b,c}. Mark each of the following TRUE or FALSE:
(a) {b,c} ⊆ P(A)
(b) {{a}} ⊆ P(A)
(c) ∅ ⊆ A
(d) {∅} ⊆ P(A)
(e) ∅ ⊆ A x A
(f) {a,c} ∈ A
(g) {a,b} ∈ A x A
(h) (c,c) ∈ A x A
... Close (a) F (b) T (c) T (d) T (e) T (f) F (g) F (h) T.
15.Find the size (that is, the cardinal number) of each of the following sets:
(a) {x x ∈ Z and x^{2} = 2x}
(b) P(A), where A = P(P({1,2,3})
(c) {1, 3, 5, 7...}
(d) S x T, where S = {a,b,c,d} and T = {1,2,3,4,5,6}
(e) {x  x ∈ Z and x^{2} < 80}.
... Close (a) 1, (b) 2^(2^3)=256, (c) ∞ ,(d) 24, (e) 17
16. Let A = { 2,4,6,8 } B = {4, 7} C = {∅, {4, 7}}
Show the following:
a. A ∪ B = ... Close { 2,4,6, 8, 7}
c. A ∪ C = ... Close {{ 2,4,6,8, ∅, {4, 7}}
e. A  B = ... Close {2, 6, 8}
f. C  ∅ = ... Close {∅, {4, 7}}
h. C ∪ (A ∩ B) = ... Close {4, ∅, {4, 7}}
i. P(A) = ... Close {{},{2},{2,4},{2,4,6},{2,4,6,8},{2,4,8},{2,6},{2,6,8},{2,8},{4},{4,6},{4,6,8},{4,8},{6},{6,8},{8}}
j. B x C = ... Close {(4, ∅), (4, {4, 7}), (7, ∅), (7, {4, 7}) }
17. Show Venn Diagrams for each of the above.
18. Simplify the following using the properties of set operation:
19. Determine which relationship ⊆, =, ⊇ is true between each pair of sets.
b. A ∩ (B ∪ C), (A ∪ B) ∩ (A ∪ C) ... Close ⊇
c. A ∪ (B ∩ C), (A ∪ B) ∩ (A ∪ C) ... Close =
20. Consider the following sets. Pick the correct description. What is the cardinality of each set?
a. A = {x x ∈ N ∧ (∀y,w : y,w ∈ N ∧y ≠ 1 ∧ w ≠ 1 ∧ x ≠ yw ) } ( N is the set of natural numbers) ... Close Prime numbers, infinite
b. A = {x x ∈ N ∧ x < 100 ∧ (∃y: y ∈ N ∧ x = 3y) } ( N is the set of natural numbers) ... Close multiples of 3 {3, 6, 9, ... 99}, 33
c. A = {x x ∈ Z ∧ (∃y: y ∈ Z ∧ x = y^{2}) } ( Z is the set of Integers) ... Close Squares {0, 1, 2, 4, 9, 16, ...}, ∞
 JimSkon  20110314