Language of Proof Flashcards
2 synonyms for a STATEMENT
proposition, premise
4 types of statements
(1) simple sentence
(2) mathematical declaration
(3) assertion/definition
(4) deduction/claim to be proven
a statement’s logical value is…
either TRUE or FALSE but not both
a proven statement is…
a statement shown to be true
proof is…
the evidence used to establish a proven statement
a counterexample is…
an example that disproves (falsifies) a statement
what does negation do
changes a statement’s logical value
negation of P is…
“not P”
¬P or ~P or P’ or P̄
the negation of P and Q
not P nor Q
¬(P and Q) = ¬P or ¬Q
the negation of P or Q
not P and not Q
¬(P or Q) = ¬P and ¬Q
the negation of P⟹Q
P and ~Q
there exists a case where P and not Q
(the condition that causes P to imply Q no longer exists)
an implication is…
an IF-THEN statement;
a conditional statement
the notation for “if P then Q”
P⟹Q
“P implies Q”
2 other ways to say “if P then Q”
(1) P is a SUFFICIENT condition to conclude Q
(2) Q is NECESSARY if P
what does a converse statement do
reverses the implication
the converse of P⟹Q
Q⟹P
two statements are EQUIVALENT (aka are an equivalence) when…
the statement and its converse are both true
notation for equivalent statements
P⇔Q
P if and only if Q
P iff Q
(and all vice versa)
what a contrapositive does
(1) negates and (2) swaps both parts of a IF-THEN statement
the contrapositive of P⟹Q (if P then Q)
¬Q⟹¬P
(if not Q then not P)
why original and contrapositive statements are an equivalence
if P⟹Q is true, then ¬Q⟹¬P is also true (kind of like two negatives makes one positive)
e.g. If I’m 80 years old then I’ll die ⇔ if I’m not dead then I’m not 80 years old yet
abbreviation for “if and only if”
iff
what do quantifiers do
quantify (put a number on) how many values a variable can take on from a specified set
e.g. x is rational for all x∈R
universal quantifier:
(1) meaning
(2) notation
(1) “for all” x
(2) ∀x
existential quantifier
(1) meaning
(2) notation
(1) “there exists” x that…
(2) ∃x
abbreviation for “such that”
s.t. or :
RTP means
required to prove
QED means
demonstrated as required (quod erat demonstrandum)
~∀ =
∃
~∃ =
∀
translate into words:
∀n∈Z, ∃m∈Z, s.t. (n+m)/5 ∈Z
for all integers n, there exists integer m, such that (n+m) divided by 5 is an integer—aka n+m is a multiple of 5
translate into words:
∀x∈A, ∃y∈B s.t. P(x,y)
for all x in set A, there exists y in set B such that (statement P)
~[∀x∈A, ∃y∈B s.t. P(x,y)] ⇔
∃x∈A, ∀y∈B s.t. ~P(x,y)
translate into words:
∃x∈A, ∀y∈B s.t. ~P(x,y)
there exists x in set A for all y in set B, such that (statement P) is not the case
