Final Exam

Question 1

A countable set

Answer 1

Discrete set

Question 2

A declarative sentence that is true or false, but not both

Answer 2

Proposition

Question 3

A propositional form that is always true, denoted t

Answer 3

Tautology

Question 4

A propositional form that is always false, denoted c

Answer 4

Contradiction

Question 5

An argument where every case the premise (hypothesis) is proven true, the conclusion is also true

Answer 5

Valid argument

Question 6

An integer n is ________ iff ∃k ε Z s.t. n = 2k.

Answer 6

Even integer

Question 7

An integer n is ________ iff ∃k ε Z s.t. n = 2k + 1.

Answer 7

Odd integer

Question 8

An integer n is ________ iff n > 1 and it has no positive divisor other than 1 and itself.
i.e. iff n > 1 and ∀r,s ε Z+ if n = r * s then r = 1 or s = 1.

Answer 8

Prime

Question 9

An integer is __________ iff n > 1 and n is not prime.
i.e. iff n > 1 and ∃r,s ε Z+ s.t. n = r * s but r ≠ 1 and s ≠ 1.

Answer 9

Composite

Question 10

r ε R is called a _____________ iff ∀a,b ε Z s.t. r = a/b and b ≠ 0.

Answer 10

Rational number

Question 11

∀n ε Z ∀d ε Z s.t d ≠ 0 ______________, denoted d | n iff ∃k ε Z s.t. n = dk.

Answer 11

d divides n

Question 12

Any integer n s.t. n > 1 is either a prime or it can be uniquely written as a product of primes in a non-decreasing order.

Answer 12

Fundamental Theorem of Arithmetic (FTA)

Question 13

∀n ε Z ∀d ε Z+ ∃! q, r ε Z s.t. n = dq + r and 0 ≤ r < d

Answer 13

Quotient Remainder Theorem

Question 14

An unordered collection of elements.

Answer 14

A set

Question 15

A set A is a subset iff every element of A is also in B.

Answer 15

A ⊆ B

Question 16

{x ε U| x ε A ∨ x ε B}

Answer 16

A ∪ B

Question 17

{x ε U| x ε A ∧ x ε B}

Answer 17

A ∩ B

Question 18

{x ε U| x ε B ∧ x ∉ A}

Answer 18

B - A

Question 19

{x ε U| x ∉ A}

Answer 19

A^c

Question 20

Let A and B be sets. The Cartesian Product of A and B is the set ___________ of ordered pairs defined {(a, b) | a ε A, b ε B}

Answer 20

A x B

Question 21

A ____________ from a set A to a set B denoted f: A → B is a relation from A to B s.t. each element of A is assigned by f to one and only one element of B.

Answer 21

Function

Question 22

A function f: A → B is ___________ iff ∀a1, a2 ε A if f(a1) = f(a2) then a1 = a2.

Answer 22

1-1

Question 23

A function f: A → B is ___________ iff ∀b ε B ∃a ε A s.t. f(a) = b.

Answer 23

onto

Question 24

Let f: A → B be a function. The ___________________ is the set {(a, b) | a ε A and b = f(a)}

Answer 24

graph of a function

Question 25

Two sets A and B have the same _______________ iff there exists a bijection between them.

Answer 25

Cardinality

Question 26

A set A is ______________ iff it is finite or it has the same cardinality as Z+.

Answer 26

Countable

Question 27

A binary ___________________________ is a subset of A x B s.t. (a, b) ε R iff a is related to b under R, denoted aRb.

Answer 27

relation from a set to a set

Question 28

Let m and n be any integers. Let d ε Z+. m is congruent to n modulo d, denoted ______________________.

Answer 28

m ≡ n mod d iff d | m - n

Question 29

A relation R is called _______________ iff ∀a ε A (a, a) ε R.

Answer 29

Reflexive

Question 30

A relation R on a set A is ______________ iff ∀a, b ε A (a, b) ε R → (b, a) ε R.

Answer 30

Symmetric

Question 31

A relation R on a set A is _______________ iff ∀a, b, c ε A (a, b) ε R if (a, b) ε R and (b, c) ε R then (a, c) ε R.

Answer 31

Transitive

Question 32

A relation on a set A is called an ______________________, iff it is reflexive, symmetric, and transitive.

Answer 32

Equivalence relation