Final Exam Flashcards
a|b
a divides b
b is a multiple of a
c = a(mod b)
c-a=bm
Direct Proof
Start with the assumption of the premise
Use known facts, definitions, and previously proven theorems to logically deduce the conclusion.
Each step should be justified and should follow logically from the previous steps.
Conclude by stating that the conclusion logically follows from the premise.
Proof by Contradiction
Assume the negation of the statement you want to prove (i.e., assume the statement is false).
Deduce logical consequences from this assumption.
Eventually, reach a contradiction with known facts or axioms.
Since a statement and its negation cannot both be true, the original assumption (that the statement is false) must be false, implying that the original statement is true.
Proof by Contrapositive
Begin by negating the conclusion of the theorem or statement.
Then, rewrite the negated conclusion in an equivalent form, which is the contrapositive of the original statement.
Prove the contrapositive using a direct proof.
Since the contrapositive is logically equivalent to the original statement, proving the contrapositive proves the original statement as well.
Proof by Division into Cases
Identify different cases that cover all possibilities related to the statement.
Prove each case separately using direct or another suitable method of proof.
Make sure that the cases are exhaustive (cover all possibilities) and mutually exclusive (no overlap between cases).
Conclude by showing that each case being true leads to the truth of the overall statement.
Proof of a Biconditional
Prove the implication in one direction (if part) using any suitable proof method (direct, contrapositive, contradiction, etc.).
Prove the implication in the other direction (only if part) using the same or another suitable proof method.
Conclude by stating that both implications have been proven, thus establishing the biconditional statement.
To prove a universal statement, we must…
show that it is true for all elements in the domain under consideration. This typically involves using a direct proof, mathematical induction, or proof by contradiction, depending on the nature of the statement
To prove an existential statement, we must…
provide at least one example or instance where the statement holds true. This demonstrates that there exists at least one element in the domain for which the statement is true. Proof by example, constructive proof, or proof by contradiction are common methods for proving existential statements.
To disprove a universal statement, we must…
find a counterexample, i.e., a specific element in the domain for which the statement is false. This shows that the statement does not hold true for all elements in the domain.
To disprove an existential statement, we must…
we must show that the statement is false for all elements in the domain. This can be accomplished by demonstrating that there is no element in the domain that satisfies the given conditions or by showing a contradiction.
Statement
In mathematics, a statement (also called a proposition)
is a declarative sentence that is either true or false, but not both.
Conditional P → Q
False only when P is true and Q is false
Tautology
A tautology is a compound statement S that is true for
all possible combinations of truth values of the component
statements that are part of S
Contradiction
A contradiction is a compound statement S that is false
for all possible combinations of truth values of the component
statements that are part of S.
negation of the conditional statement
¬(P → Q) ≡ P ∧ ¬Q
the contrapositive of a conditional statement is
¬Q → ¬P
A conditional statement is logically equivalent to its
contrapositive
The converse of a conditional statement
P→Q is Q → P
Set
a well-defined collection of objects that can be thought of
as a single entity itself
Element
one of the objects in a set
Set-roster notation
writing all of a set’s elements between
braces
variable
a symbol representing an
unspecified object that can be chosen from a given set U
constant
a specific member of the universal set.
open sentence (or predicate)
a sentence
P(x1, x2,· · · , xn) that contains a finite number of variables and
becomes a true or false statement when specific values are
substituted for the variables.
Truth set
the truth
set of P(x) is the set of all elements in the universal set that
can be substituted for x to make P(x) true
set builder notation
use a predicate to define a rule that must
be satisfied by all elements in the set
empty set
a set with no elements, usually denoted ∅
The Universal quantifier
∀
(for all, for every, for each, given any, …)
The Existential quantifier
∃
(there exists, there is a, there is at least one, for some, for at
least one, ···)
Negations of
Quantified
Statements
The negation of a statement of the form
(∀x ∈ U) (P(x))
is logically equivalent to a statement of the form
(∃x ∈ U) (¬P(x))
Argument
a sequence of statements called
premises, followed by a final statement called the
conclusion
Proof
a convincing argument that some mathematical
statement is true
Axiom
some mathematical statement that is generally
accepted without proof
Definition
an agreement about the meaning of a term
Conjecture
a statement that we believe might be true, but
that we have not yet proved.
Theorem
a mathematical statement for which we have a
proof
Lemma
a mathematical statement that was proven mainly to
help with proving some theorem.
Corollary
a theorem that follows almost immediately from
the proof of some other theorem.
A ∩ B
The intersection of A and B is the set of
all elements x in U such that x is in A and x is in B.
A ∪ B
The union of A and B is the set of all
elements x in U such that x is in A or x is in B (or both).
A-B
The set difference of A and B is the set
of all elements x in U such that x is in A, but x is not in B.
A^c
The complement of A, is the set of all
elements x in U such that x is not in A.
Injection
a one-to-one function, is a function where every element of the domain maps to a distinct element in the codomain. In other words, no two different elements in the domain map to the same element in the codomain.
Surjection
an onto function, is a function where every element in the codomain is mapped to by at least one element in the domain. In other words, the range of the function coincides with its codomain
Function
A function from a set A to a set B is a rule that associates
each element of the set A with exactly one element of the set
B. A function from A to B is called a mapping from A to B.
If a ∈ �, then the element of � that is associated with a is
denoted by (�(�)) is called the image of � under �.
If � � = � with � ∈ �, then � is the preimage of � for �.
Composite function
(g ∘ f )= g(f(x))
For the inverse of a function to be a function, the original
function must be a bijection
Let n be an integer. If a and b are integer, then we
say that a is congruent to b modulo n provided that n
divides a – b
