Elementary Discrete Math

Sample Exam I

Exam Date: March 28, 2011

1. Show whether each of the following is a tautology, contradiction, or neither using truth tables:

(a) p → ( pq) ... Close neither

(b) q ∧ ( pq) ... Close contradiction

(c) (( pp) → q) ... Close neither

(d) q ∨ (qp) ... Close tautalogy

(e) [( p q ) ∧ ( pr ) ∧ ( qr )] ... 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):

Logical Equivalences Table

(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. pq and ( pq) → ( pq) ... Close = yes

b. ( pq) ∨ p and ( pq) ∧ ( pq) ... Close = no

c. ( pq) and pq ... 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 xy: BLUE( x) → C( y,x)

e. Every red car owner also owns a blue car ... Close xyz: (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

a) P(1, -1) ... Close false

b) P(0, 0) ... Close false

c) ∃y P(3,y) ... Close true

d) ∀xy P( x,y) ... Close true

e) ∃xy P( x,y) ... Close false

f) ∀yx 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 yx R( x,y) or ∃yx
R( x,y)

d) Every student has a dorm room. ... Close xyR( x,y)

e) There is a room with more then one student assigned to it. ... Close xyzR( 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

(a) P(1,-1) ... Close true

(b) P(0,0) ... Close true

(c) ∃yP(3,y) ... Close true

(d) ∀x∃yP( x,y) ... Close true

(e) ∃xyP( x,y) ... Close False

(f) ∀yxP( x,y) ... Close False

(g) ∃yxP( x,y) ... Close False

(h) ∀xy P( x,y) ... Close False


12. Find the size (that is, the cardinal number) of each of the following sets:

(a) {x|x ∈ Z and x2 < 10}. ... Close 7

(b) P({a,b,c,d}), where P denotes the power set. ... Close 16

(c) {1,3,5,7...}. ... Close

(d) A x B where A = {1,2,3,4,5} and B = {1,2,3}. ... Close 15

(e) {x|x ∈ N and 9x2 - 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) {x|x ∈ N and 4x2 - 1 = 0}. ... Close 0


13. Determine the truth value for each of the following.

(a) ∀x ∃y | (x2=y) ... Close True – every number has a square


(b) ∀xy | (x=y2) ... Close False – No y exists if x is negative

(c) ∃xy | ( xy = 0) ... Close True – let x = 0

(d) ∃xy | (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 x2 = 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 x2 < 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}

b. A ∩ B = ... Close { 4 }

c. A ∪ C = ... Close {{ 2,4,6,8, ∅, {4, 7}}

d. A ∩ C = ... Close

e. A - B = ... Close {2, 6, 8}

f. C - ∅ = ... Close {∅, {4, 7}}

g. ∅ - C = ... Close

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:

  1. (A ∪ B)c ∩ (A c ∩ B c) = ... Close (A ∪ B)c ∩ (A ∪ B )c = (A ∪ B)c = Ac ∪ Bc
  2. (A ∪ (B ∩ A)) = ... Close (A ∪ B) ∩ (A ∪ A ) = (A ∪ B) ∩ (A ) = A
  3. (A ∪ (B ∩ A)) c ∩ ((C c ∪ B c) ∩ A c) c

19. Determine which relationship ⊆, =, ⊇ is true between each pair of sets.

a. A ∩ (A ∪ B), A ... Close =

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 ∧ xyw ) } ( N is the set of natural numbers) ... Close Prime numbers, infinite

b. A = {x |x N ∧ x < 100 ∧ (∃y: y Nx = 3y) } ( N is the set of natural numbers) ... Close multiples of 3 {3, 6, 9, ... 99}, 33

c. A = {x |x Z ∧ (∃y: y Zx = y2) } ( Z is the set of Integers) ... Close Squares {0, 1, 2, 4, 9, 16, ...}, ∞

-- JimSkon - 2011-03-14

Topic revision: r6 - 2011-03-15 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback