CS 2800 Prelim I study notes verified
to pass 2026
discrete - correct answer ✔things that are neither smooth nor continuous
function - correct answer ✔a mapping from one set to another; an unambiguous rule; every input
should correspond to exactly one unambiguous output
domain - correct answer ✔set of all possible inputs for a function, all of which are mapped to an
output
codomain - correct answer ✔set of all possible outputs for a function that may or may not be mapped
to them
image - correct answer ✔subset of codomain that is set of all actual outputs with an input mapped to
them; a function has only one codomain as assigned by the creator of the function
specifying a function - correct answer ✔give the domain, codomain and a rule
cartesian product AxB - correct answer ✔A and B are sets and AxB is the set of pairs with the first
element in A and the second in B
predicate - correct answer ✔a statement that is true or false depending on the value of a variable
proposition - correct answer ✔a statement that is true or false
quantifiers - correct answer ✔symbols that turn predicates into propositions; for all, there exists
, order of quantifiers - correct answer ✔if different quantifiers are used, their order matters
prove "for all" or disprove "there exists" - correct answer ✔must prove/disprove for all values
(arbitrary x)
disprove "for all" or prove "there exists" - correct answer ✔give an example
"for all" - correct answer ✔all values apply
"there exists" - correct answer ✔at least one value applies
"for all x, there exists a y such that x loves y" - correct answer ✔each x loves its own y
"there exists a y for all x such that x loves y" - correct answer ✔all x love the same y
prove an implication (P implies Q) - correct answer ✔Assume P and prove Q
backwards proof - correct answer ✔proof starts with with what you are trying to prove and reduces it
to something known to be true
proof by contradiction (P implies Q) - correct answer ✔Assume P. For the sake of contradiction,
assume Q is false. Then show that P is no longer true (there is a contradiction between your assumption
and what is true)
surjection (informal) - correct answer ✔onto function where every output has at least one
corresponding input
to pass 2026
discrete - correct answer ✔things that are neither smooth nor continuous
function - correct answer ✔a mapping from one set to another; an unambiguous rule; every input
should correspond to exactly one unambiguous output
domain - correct answer ✔set of all possible inputs for a function, all of which are mapped to an
output
codomain - correct answer ✔set of all possible outputs for a function that may or may not be mapped
to them
image - correct answer ✔subset of codomain that is set of all actual outputs with an input mapped to
them; a function has only one codomain as assigned by the creator of the function
specifying a function - correct answer ✔give the domain, codomain and a rule
cartesian product AxB - correct answer ✔A and B are sets and AxB is the set of pairs with the first
element in A and the second in B
predicate - correct answer ✔a statement that is true or false depending on the value of a variable
proposition - correct answer ✔a statement that is true or false
quantifiers - correct answer ✔symbols that turn predicates into propositions; for all, there exists
, order of quantifiers - correct answer ✔if different quantifiers are used, their order matters
prove "for all" or disprove "there exists" - correct answer ✔must prove/disprove for all values
(arbitrary x)
disprove "for all" or prove "there exists" - correct answer ✔give an example
"for all" - correct answer ✔all values apply
"there exists" - correct answer ✔at least one value applies
"for all x, there exists a y such that x loves y" - correct answer ✔each x loves its own y
"there exists a y for all x such that x loves y" - correct answer ✔all x love the same y
prove an implication (P implies Q) - correct answer ✔Assume P and prove Q
backwards proof - correct answer ✔proof starts with with what you are trying to prove and reduces it
to something known to be true
proof by contradiction (P implies Q) - correct answer ✔Assume P. For the sake of contradiction,
assume Q is false. Then show that P is no longer true (there is a contradiction between your assumption
and what is true)
surjection (informal) - correct answer ✔onto function where every output has at least one
corresponding input
