# Difference: EDMExamISampleTest (1 vs. 6)

#### Revision 62011-03-15 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="ElementaryDiscreteMath2011"

# Elementary Discrete Math

###### Sample Exam I
Line: 39 to 39

 (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

Line: 185 to 187
(b) P({a,b,c,d}), where P denotes the power set.
`<--/twistyPlugin twikiMakeVisibleInline-->`
16
`<--/twistyPlugin-->`
Changed:
<
<
(c) {1,3,5,7...}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
Infinity
`<--/twistyPlugin-->`
>
>
(c) {1,3,5,7...}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
`<--/twistyPlugin-->`
(d) A x B where A = {1,2,3,4,5} and B = {1,2,3}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
15
`<--/twistyPlugin-->`
Line: 276 to 278
18. Simplify the following using the properties of set operation:
Changed:
<
<
1. (A ∪ B)c ∩. (A c ∩ B c)
2. (A ∪ (B ∩ A))
>
>
1. (A ∪ B)c ∩ (A c ∩ B c) =
`<--/twistyPlugin twikiMakeVisibleInline-->`
(A ∪ B)c ∩ (A ∪ B )c = (A ∪ B)c = Ac ∪ Bc
`<--/twistyPlugin-->`
2. (A ∪ (B ∩ A)) =
`<--/twistyPlugin twikiMakeVisibleInline-->`
(A ∪ B) ∩ (A ∪ A ) = (A ∪ B) ∩ (A ) = A
`<--/twistyPlugin-->`

1. (A ∪ (B ∩ A)) c ∩ ((C c ∪ B c) ∩ A c) c

Line: 293 to 295
a. A = {x |x N ∧ (∀y,w : y,w N ∧y ≠ 1 ∧ w ≠ 1 ∧ xyw ) } ( N is the set of natural numbers)
`<--/twistyPlugin twikiMakeVisibleInline-->`
Prime numbers, infinite
`<--/twistyPlugin-->`
Changed:
<
<
b. A = {x |x N ∧ x < 100 ∧ (∃y: y N ∧ x = 3y) } ( N is the set of natural numbers)
`<--/twistyPlugin twikiMakeVisibleInline-->`
multiples of 3 {3, 6, 9, ... 99}, 33
`<--/twistyPlugin-->`
>
>
b. A = {x |x N ∧ x < 100 ∧ (∃y: y Nx = 3y) } ( N is the set of natural numbers)
`<--/twistyPlugin twikiMakeVisibleInline-->`
multiples of 3 {3, 6, 9, ... 99}, 33
`<--/twistyPlugin-->`

c. A = {x |x Z ∧ (∃y: y Zx = y2) } ( Z is the set of Integers)

`<--/twistyPlugin twikiMakeVisibleInline-->`
Squares {0, 1, 2, 4, 9, 16, ...}, ∞
`<--/twistyPlugin-->`
-- JimSkon - 2011-03-14

#### Revision 52011-03-15 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="ElementaryDiscreteMath2011"

# Elementary Discrete Math

###### Sample Exam I
Line: 9 to 9
(a) p → ¬( p ∨¬q)
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`
Changed:
<
<
(b) q ∧ ¬( pq)
`<--/twistyPlugin twikiMakeVisibleInline-->`
`<--/twistyPlugin-->`
>
>
(b) q ∧ ¬( pq)
`<--/twistyPlugin twikiMakeVisibleInline-->`
`<--/twistyPlugin-->`
(c) (( p ∨ ¬p) → q)
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`
Line: 193 to 193
(f) P(A), where A is the power set of {a,b,c}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
256
`<--/twistyPlugin-->`
Changed:
<
<
(g) A x B, where A = {a,b,c} and B = Ø.
`<--/twistyPlugin twikiMakeVisibleInline-->`
0
`<--/twistyPlugin-->`
>
>
(g) A x B, where A = {a,b,c} and B = ∅.
`<--/twistyPlugin twikiMakeVisibleInline-->`
0
`<--/twistyPlugin-->`
(h) {x|x ∈ N and 4x2 - 1 = 0}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
0
`<--/twistyPlugin-->`
Line: 215 to 215
(b) {{a}} ⊆ P(A)
Changed:
<
<
(c) Ø ⊆ A
>
>
(c) ∅ ⊆ A

Changed:
<
<
(d) {Ø} ⊆ P(A)
>
>
(d) {∅} ⊆ P(A)

Changed:
<
<
(e) Ø ⊆ A x A
>
>
(e) ∅ ⊆ A x A
(f) {a,c} ∈ A
Line: 242 to 242
(e) {x | x ∈ Z and x2 < 80}.
Changed:
<
<
(a) 1, (b) 2^(2^3)=256, (c) ¥ ,(d) 24, (e) 17

`<--/twistyPlugin twikiMakeVisibleInline-->`
(a) 1, (b) 2^(2^3)=256, (c) infinity ,(d) 24, (e) 17
`<--/twistyPlugin-->`
>
>
`<--/twistyPlugin twikiMakeVisibleInline-->`
(a) 1, (b) 2^(2^3)=256, (c) ∞ ,(d) 24, (e) 17
`<--/twistyPlugin-->`

Changed:
<
<
16. Let A = { 2,4,6,8 } B = {4, 7} C = {Ø, {4, 7}}
>
>
16. Let A = { 2,4,6,8 } B = {4, 7} C = {∅, {4, 7}}
Show the following:
Line: 255 to 253
b. A ∩ B =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{ 4 }
`<--/twistyPlugin-->`
Changed:
<
<
c. A ∪ C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{{ 2,4,6,8, Ø, {4, 7}}
`<--/twistyPlugin-->`
>
>
c. A ∪ C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{{ 2,4,6,8, ∅, {4, 7}}
`<--/twistyPlugin-->`

Changed:
<
<
d. A ∩ C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
Ø
`<--/twistyPlugin-->`
>
>
d. A ∩ C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
`<--/twistyPlugin-->`
e. A - B =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{2, 6, 8}
`<--/twistyPlugin-->`
Changed:
<
<
f. C - Ø =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{Ø, {4, 7}}
`<--/twistyPlugin-->`
>
>
f. C - ∅ =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{∅, {4, 7}}
`<--/twistyPlugin-->`

g. ∅ - C =

`<--/twistyPlugin twikiMakeVisibleInline-->`
`<--/twistyPlugin-->`

Changed:
<
<
g. Ø - C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
Ø
`<--/twistyPlugin-->`
>
>
h. C ∪ (A ∩ B) =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{4, ∅, {4, 7}}
`<--/twistyPlugin-->`

Changed:
<
<
h. C ∪ (A ∩ B) =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{4, Ø, {4, 7}}
`<--/twistyPlugin-->`
>
>
i. P(A) =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{{},{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}}
`<--/twistyPlugin-->`

>
>
j. B x C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{(4, ∅), (4, {4, 7}), (7, ∅), (7, {4, 7}) }
`<--/twistyPlugin-->`

17. Show Venn Diagrams for each of the above.

Line: 280 to 281

1. (A ∪ (B ∩ A)) c ∩ ((C c ∪ B c) ∩ A c) c

Changed:
<
<
19. Prove the following using a. set builder notation and b Membership tables
>
>
19. Determine which relationship ⊆, =, ⊇ is true between each pair of sets.

a. A ∩ (A ∪ B), A

`<--/twistyPlugin twikiMakeVisibleInline-->`
=
`<--/twistyPlugin-->`

b. A ∩ (B ∪ C), (A ∪ B) ∩ (A ∪ C)

`<--/twistyPlugin twikiMakeVisibleInline-->`
`<--/twistyPlugin-->`

c. A ∪ (B ∩ C), (A ∪ B) ∩ (A ∪ C)

`<--/twistyPlugin twikiMakeVisibleInline-->`
=
`<--/twistyPlugin-->`

20. Consider the following sets. Pick the correct description. What is the cardinality of each set?

Changed:
<
<
a. A ∩ (A ∪ B) = A
>
>
a. A = {x |x N ∧ (∀y,w : y,w N ∧y ≠ 1 ∧ w ≠ 1 ∧ xyw ) } ( N is the set of natural numbers)
`<--/twistyPlugin twikiMakeVisibleInline-->`
Prime numbers, infinite
`<--/twistyPlugin-->`

Changed:
<
<
b. A ∩ (B ∪ C) = (A ∪ B) ∩ (A ∪ C)
>
>
b. A = {x |x N ∧ x < 100 ∧ (∃y: y N ∧ x = 3y) } ( N is the set of natural numbers)
`<--/twistyPlugin twikiMakeVisibleInline-->`
multiples of 3 {3, 6, 9, ... 99}, 33
`<--/twistyPlugin-->`
-- JimSkon - 2011-03-14 \ No newline at end of file

#### Revision 42011-03-15 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="ElementaryDiscreteMath2011"

# Elementary Discrete Math

###### Sample Exam I
Line: 9 to 9
(a) p → ¬( p ∨¬q)
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`
Changed:
<
<
(b) ¬p ∧ ¬q
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`
>
>
(b) q ∧ ¬( pq)
`<--/twistyPlugin twikiMakeVisibleInline-->`
`<--/twistyPlugin-->`
(c) (( p ∨ ¬p) → q)
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`

#### Revision 32011-03-14 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="ElementaryDiscreteMath2011"

# Elementary Discrete Math

###### Sample Exam I
Line: 7 to 7
1. Show whether each of the following is a tautology, contradiction, or neither using truth tables:
Changed:
<
<
(a) p → ¬( p ∨¬q)
>
>
(a) p → ¬( p ∨¬q)
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`

Changed:
<
<
(b) ¬p ∧ ¬q
>
>
(b) ¬p ∧ ¬q
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`

Changed:
<
<
(c) (( p ∨ ¬p) → q)
>
>
(c) (( p ∨ ¬p) → q)
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`

Changed:
<
<
(d) ¬q ∨ (¬qp)
>
>
(d) ¬q ∨ (¬qp)
`<--/twistyPlugin twikiMakeVisibleInline-->`
tautalogy
`<--/twistyPlugin-->`

Changed:
<
<
(e) [( p q ) ∧ ( pr ) ∧ ( qr )]
>
>
(e) [( p q ) ∧ ( pr ) ∧ ( qr )]
`<--/twistyPlugin twikiMakeVisibleInline-->`
neither
`<--/twistyPlugin-->`

Line: 44 to 44
3. Evaluate each of the following bitwise logic expressions
Changed:
<
<
a. (011010 ∧ 111100) ∨ 001100 =
>
>
a. (011010 ∧ 111100) ∨ 001100 =
`<--/twistyPlugin twikiMakeVisibleInline-->`
011000 ∨ 001100 = 011100
`<--/twistyPlugin-->`

Changed:
<
<
b. 111000 ∨ 001100 ∨ 000001 =
>
>
b. 111000 ∨ 001100 ∨ 000001 =
`<--/twistyPlugin twikiMakeVisibleInline-->`
111101
`<--/twistyPlugin-->`

Changed:
<
<
c. (101010 ∨ 110011) → 000111 =
>
>
c. (101010 ∨ 110011) ⊕ 000111 =
`<--/twistyPlugin twikiMakeVisibleInline-->`
111011 ⊕000111 = 111100
`<--/twistyPlugin-->`

4. Prove using truth tables whether each of the following pairs of expressions are equivalent:

Changed:
<
<
a. pq and ( pq) → ( pq)
>
>
a. pq and ( pq) → ( pq)
`<--/twistyPlugin twikiMakeVisibleInline-->`
= yes
`<--/twistyPlugin-->`

Changed:
<
<
b. ( pq) ∨ p and ( pq) ∧ ¬( pq)
>
>
b. ( pq) ∨ p and ( pq) ∧ ¬( pq)
`<--/twistyPlugin twikiMakeVisibleInline-->`
= no
`<--/twistyPlugin-->`

Changed:
<
<
c. ¬( p ∧ ¬q) and pq
>
>
c. ¬( p ∧ ¬q) and pq
`<--/twistyPlugin twikiMakeVisibleInline-->`
= yes
`<--/twistyPlugin-->`

Line: 68 to 68
6. State the converse and contrapositive of each of the following implications:
Changed:
<
<
a. If it snows tonight, then I will stay home
>
>
a. If it snows tonight, then I will stay home.
`<--/twistyPlugin twikiMakeVisibleInline-->`

If I stay home then it will snow tonight.
If I don’t stay home then it will not snow tonight.
`<--/twistyPlugin-->`

Changed:
<
<
b. I go to the beach whenever it is a sunny summer day.

c. When I stay up late, it necessary that I sleep until noon
>
>
b. I go to the beach whenever it is a sunny summer day.
`<--/twistyPlugin twikiMakeVisibleInline-->`

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.
`<--/twistyPlugin-->`

c. When I stay up late, it necessary that I sleep until noon
`<--/twistyPlugin twikiMakeVisibleInline-->`

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

`<--/twistyPlugin-->`
Consider the following predicates:
Line: 84 to 88
7. Write the following in symbols:
Changed:
<
<
a. Sandy owns a blue car.
>
>
a. Sandy owns a blue car.
`<--/twistyPlugin twikiMakeVisibleInline-->`
x: C(Sandy,x) ∧ BLUE( x)
`<--/twistyPlugin-->`

Changed:
<
<
b. Every car is either blue or red.
>
>
b. Every car is either blue or red.
`<--/twistyPlugin twikiMakeVisibleInline-->`
∀x: RED( x) ∨ BLUE( x)
`<--/twistyPlugin-->`

Changed:
<
<
c. There is a car that is both blue and red.
>
>
c. There is a car that is both blue and red.
`<--/twistyPlugin twikiMakeVisibleInline-->`
x: BLUE( x) ∧ RED( x)
`<--/twistyPlugin-->`

Changed:
<
<
d. Every blue car has an owner.
>
>
d. Every blue car has an owner.
`<--/twistyPlugin twikiMakeVisibleInline-->`
xy: BLUE( x) → C( y,x)
`<--/twistyPlugin-->`

Changed:
<
<
e. Every red car owner also owns a blue car
>
>
e. Every red car owner also owns a blue car
`<--/twistyPlugin twikiMakeVisibleInline-->`
xyz: (C( x,y) ∧ RED( y)) → (C( x,z) ∧ BLUE( z) )
`<--/twistyPlugin-->`

Line: 111 to 115
8. Tell whether each of the following is true or false, and why.
Changed:
<
<
a. ∃ x : C(Bill, x)
>
>
a. ∃ x : C(Bill, x)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Changed:
<
<
b. ∃ x : C(Sandy, x) ∧ BLUE( x)
>
>
b. ∃ x : C(Sandy, x) ∧ BLUE( x)
`<--/twistyPlugin twikiMakeVisibleInline-->`
false (Sandy only owns a red car)
`<--/twistyPlugin-->`

Changed:
<
<
c. ∀x ∃y: C( x,y)
>
>
c. ∀x ∃y: C( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
false (Jack owns no car)
`<--/twistyPlugin-->`

Changed:
<
<
d. ∀y ∃x: C( x,y)
>
>
d. ∀y ∃x: C( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

9. Suppose P(x,y) is the statement 2x < y, where x and y are integers. What are the truth values of

Changed:
<
<
a) P(1, -1)
>
>
a) P(1, -1)
`<--/twistyPlugin twikiMakeVisibleInline-->`
false
`<--/twistyPlugin-->`

Changed:
<
<
b) P(0, 0)
>
>
b) P(0, 0)
`<--/twistyPlugin twikiMakeVisibleInline-->`
false
`<--/twistyPlugin-->`

Changed:
<
<
c) ∃y P(3,y)
>
>
c) ∃y P(3,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Changed:
<
<
d) ∀xy P( x,y)
>
>
d) ∀xy P( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Changed:
<
<
e) ∃xy P( x,y)
>
>
e) ∃xy P( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
false
`<--/twistyPlugin-->`

Changed:
<
<
f) ∀yx P( x,y)
>
>
f) ∀yx P( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Line: 143 to 147
Write each of the following statements using the above predicate and any needed quantifiers:
Changed:
<
<
a) Fran is in room Elmwood 321
>
>
a) Fran is in room Elmwood 321
`<--/twistyPlugin twikiMakeVisibleInline-->`
R(Fran,Elmwood 321)
`<--/twistyPlugin-->`

Changed:
<
<
b) Bill does not have a dorm room.
>
>
b) Bill does not have a dorm room.
`<--/twistyPlugin twikiMakeVisibleInline-->`
¬∃x R(Bill,x)
`<--/twistyPlugin-->`

Changed:
<
<
c) There is a dorm room which is not in use (no assigned students).
>
>
c) There is a dorm room which is not in use (no assigned students).
`<--/twistyPlugin twikiMakeVisibleInline-->`
¬∀yx R( x,y) or ∃yx¬
R( x,y)
`<--/twistyPlugin-->`

Changed:
<
<
d) Every student has a dorm room.
>
>
d) Every student has a dorm room.
`<--/twistyPlugin twikiMakeVisibleInline-->`
xyR( x,y)
`<--/twistyPlugin-->`

Changed:
<
<
e) There is a room with more then one student assigned to it.
>
>
e) There is a room with more then one student assigned to it.
`<--/twistyPlugin twikiMakeVisibleInline-->`
xyzR( x,y) ∧ R( z,y) ∧ x ≠ z
`<--/twistyPlugin-->`

11. Suppose P(x,y) is the statement x + 2y = xy, where x and y are integers. What are the truth values of

Changed:
<
<
(a) P(1,-1)
>
>
(a) P(1,-1)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Changed:
<
<
(b) P(0,0)
>
>
(b) P(0,0)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Changed:
<
<
(c) ∃yP(3,y)
>
>
(c) ∃yP(3,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Changed:
<
<
(d) ∀x∃yP( x,y)
>
>
(d) ∀x∃yP( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
true
`<--/twistyPlugin-->`

Changed:
<
<
(e) ∃xyP( x,y)
>
>
(e) ∃xyP( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
False
`<--/twistyPlugin-->`

Changed:
<
<
(f) ∀yxP( x,y)
>
>
(f) ∀yxP( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
False
`<--/twistyPlugin-->`

Changed:
<
<
(g) ∃yxP( x,y)
>
>
(g) ∃yxP( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
False
`<--/twistyPlugin-->`

Changed:
<
<
(h) ¬∀xy ¬P( x,y)
>
>
(h) ¬∀xy ¬P( x,y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
False
`<--/twistyPlugin-->`

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

Changed:
<
<
(a) {x|x ∈ Z and x2 < 10}.
>
>
(a) {x|x ∈ Z and x2 < 10}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
7
`<--/twistyPlugin-->`

Changed:
<
<
(b) P({a,b,c,d}), where P denotes the power set.
>
>
(b) P({a,b,c,d}), where P denotes the power set.
`<--/twistyPlugin twikiMakeVisibleInline-->`
16
`<--/twistyPlugin-->`

Changed:
<
<
(c) {1,3,5,7...}.
>
>
(c) {1,3,5,7...}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
Infinity
`<--/twistyPlugin-->`

Changed:
<
<
(d) A x B where A = {1,2,3,4,5} and B = {1,2,3}.
>
>
(d) A x B where A = {1,2,3,4,5} and B = {1,2,3}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
15
`<--/twistyPlugin-->`

Changed:
<
<
(e) {x|x ∈ N and 9x2 - 1 = 0}.
>
>
(e) {x|x ∈ N and 9x2 - 1 = 0}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
0
`<--/twistyPlugin-->`

Changed:
<
<
(f) P(A), where A is the power set of {a,b,c}.
>
>
(f) P(A), where A is the power set of {a,b,c}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
256
`<--/twistyPlugin-->`

Changed:
<
<
(g) A x B, where A = {a,b,c} and B = Ø.
>
>
(g) A x B, where A = {a,b,c} and B = Ø.
`<--/twistyPlugin twikiMakeVisibleInline-->`
0
`<--/twistyPlugin-->`

Changed:
<
<
(h) {x|x ∈ N and 4x2 - 1 = 0}.
>
>
(h) {x|x ∈ N and 4x2 - 1 = 0}.
`<--/twistyPlugin twikiMakeVisibleInline-->`
0
`<--/twistyPlugin-->`

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

Changed:
<
<
(a) ∀x ∃y | (x2=y)

(b) ∀xy | (x=y2)

>
>
(a) ∀x ∃y | (x2=y)
`<--/twistyPlugin twikiMakeVisibleInline-->`
True – every number has a square
`<--/twistyPlugin-->`

(b) ∀xy | (x=y2)
`<--/twistyPlugin twikiMakeVisibleInline-->`
False – No y exists if x is negative

`<--/twistyPlugin-->`

Changed:
<
<
(c) ∃xy | ( xy = 0)
>
>
(c) ∃xy | ( xy = 0)
`<--/twistyPlugin twikiMakeVisibleInline-->`
True – let x = 0

`<--/twistyPlugin-->`

Changed:
<
<
(d) ∃xy | (y ≠ 0 → xy = 1)
>
>
(d) ∃xy | (y ≠ 0 → xy = 1)
`<--/twistyPlugin twikiMakeVisibleInline-->`
False – no number that when multiplied by anything is always 1

`<--/twistyPlugin-->`

Line: 225 to 227
(h) (c,c) ∈ A x A
>
>
`<--/twistyPlugin twikiMakeVisibleInline-->`
(a) F (b) T (c) T (d) T (e) T (f) F (g) F (h) T.
`<--/twistyPlugin-->`

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

Line: 241 to 244
(a) 1, (b) 2^(2^3)=256, (c) ¥ ,(d) 24, (e) 17
>
>
`<--/twistyPlugin twikiMakeVisibleInline-->`
(a) 1, (b) 2^(2^3)=256, (c) infinity ,(d) 24, (e) 17
`<--/twistyPlugin-->`

16. Let A = { 2,4,6,8 } B = {4, 7} C = {Ø, {4, 7}}

Show the following:

Changed:
<
<
a. A ∪ B =
>
>
a. A ∪ B =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{ 2,4,6, 8, 7}
`<--/twistyPlugin-->`

Changed:
<
<
b. A ∩ B =
>
>
b. A ∩ B =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{ 4 }
`<--/twistyPlugin-->`

Changed:
<
<
c. A ∪ C =
>
>
c. A ∪ C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{{ 2,4,6,8, Ø, {4, 7}}
`<--/twistyPlugin-->`

Changed:
<
<
d. A ∩ C =
>
>
d. A ∩ C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
Ø
`<--/twistyPlugin-->`

Changed:
<
<
e. A - B =
>
>
e. A - B =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{2, 6, 8}
`<--/twistyPlugin-->`

Changed:
<
<
f. C - Ø =
>
>
f. C - Ø =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{Ø, {4, 7}}
`<--/twistyPlugin-->`

Changed:
<
<
g. Ø - C =
>
>
g. Ø - C =
`<--/twistyPlugin twikiMakeVisibleInline-->`
Ø
`<--/twistyPlugin-->`

Changed:
<
<
h. C ∪ (A ∩ B) =
>
>
h. C ∪ (A ∩ B) =
`<--/twistyPlugin twikiMakeVisibleInline-->`
{4, Ø, {4, 7}}
`<--/twistyPlugin-->`

#### Revision 22011-03-14 - JimSkon

Line: 1 to 1

 META TOPICPARENT name="ElementaryDiscreteMath2011"

# 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 → ¬( p ∨¬q)

Line: 34 to 36

 x ∨ x = x (g) Complement laws x ∧ ¬x = F x ∨ ¬x = T
Changed:
<
<
 (h) Double complement law ¬(¬x) = x (i) DeMorgan's laws ¬(x ∧ y) = ¬x ∨ ¬y ¬(x ∨ y) = ¬x ∧ ¬y
>
>
 (h) Double complement law ¬(¬x) = x (i) DeMorgan's laws ¬(x ∧ y) = ¬x ∨ ¬y ¬(x ∨ y) = ¬x ∧ ¬y

#### Revision 12011-03-14 - JimSkon

Line: 1 to 1
>
>
 META TOPICPARENT name="ElementaryDiscreteMath2011"

# Elementary Discrete Math

###### Sample Exam I

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

(a) p → ¬( p ∨¬q)

(b) ¬p ∧ ¬q

(c) (( p ∨ ¬p) → q)

(d) ¬q ∨ (¬qp)

(e) [( p q ) ∧ ( pr ) ∧ ( qr )]

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

3. Evaluate each of the following bitwise logic expressions

a. (011010 ∧ 111100) ∨ 001100 =

b. 111000 ∨ 001100 ∨ 000001 =

c. (101010 ∨ 110011) → 000111 =

4. Prove using truth tables whether each of the following pairs of expressions are equivalent:

a. pq and ( pq) → ( pq)

b. ( pq) ∨ p and ( pq) ∧ ¬( pq)

c. ¬( p ∧ ¬q) and pq

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

b. I go to the beach whenever it is a sunny summer day.

c. When I stay up late, it necessary that I sleep until noon

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.

b. Every car is either blue or red.

c. There is a car that is both blue and red.

d. Every blue car has an owner.

e. Every red car owner also owns a blue car

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)

b. ∃ x : C(Sandy, x) ∧ BLUE( x)

c. ∀x ∃y: C( x,y)

d. ∀y ∃x: C( x,y)

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)

b) P(0, 0)

c) ∃y P(3,y)

d) ∀xy P( x,y)

e) ∃xy P( x,y)

f) ∀yx P( x,y)

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

b) Bill does not have a dorm room.

c) There is a dorm room which is not in use (no assigned students).

d) Every student has a dorm room.

e) There is a room with more then one student assigned to it.

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)

(b) P(0,0)

(c) ∃yP(3,y)

(d) ∀x∃yP( x,y)

(e) ∃xyP( x,y)

(f) ∀yxP( x,y)

(g) ∃yxP( x,y)

(h) ¬∀xy ¬P( x,y)

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

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

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

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

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

(e) {x|x ∈ N and 9x2 - 1 = 0}.

(f) P(A), where A is the power set of {a,b,c}.

(g) A x B, where A = {a,b,c} and B = Ø.

(h) {x|x ∈ N and 4x2 - 1 = 0}.

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

(a) ∀x ∃y | (x2=y)

(b) ∀xy | (x=y2)

(c) ∃xy | ( xy = 0)

(d) ∃xy | (y ≠ 0 → xy = 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

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}.

(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 =

b. A ∩ B =

c. A ∪ C =

d. A ∩ C =

e. A - B =

f. C - Ø =

g. Ø - C =

h. C ∪ (A ∩ B) =

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)
2. (A ∪ (B ∩ A))
3. (A ∪ (B ∩ A)) c ∩ ((C c ∪ B c) ∩ A c) c

19. Prove the following using a. set builder notation and b Membership tables

a. A ∩ (A ∪ B) = A

b. A ∩ (B ∪ C) = (A ∪ B) ∩ (A ∪ C)

-- JimSkon - 2011-03-14

Copyright &Â© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback