Chapter 3 Flashcards
symbol “∃” name and meaning [notation]
“∃” is called the existential quantifier;
means “there exists”
or “there exist”.
symbol “∀” name and meaning [notation]
“∀” is called the universal quantifier;
means “for all”
or “for each”
or “for every”
or “whenever” .
two components of a quantified statement [notation]
(1) quanitfied segments (ex: “(∃0 ∈ Z such that)(∀a ∈ Z)”)
(2) final statement (ex: “a + 0 = a”)
together, make the quantified statement…
(∃0 ∈ Z such that)(∀a ∈ Z) a + 0 = a .
symbol “∄” meaning [notation]
“∄” means “there does not exist”.
symbol “≡” meaning [notation]
“≡” denotes logical equivalence.
symbol “∃!” meaning [notation]
“∃!” means “there exists a unique”.
two statements that are equivalent to a statement of the form
(∃!n ∈ N such that)
[notation]
(1) existence statement (ex: “(∃n ∈ N such that)”)
(2) uniqueness statement (ex: “(if n ∈ N and m ∈ N both have the given property, then n = m)”)
These two statements together mean the same as the uniqueness statement of the form
(∃!n ∈ N such that)
three statements equivalent to “P ⇒ Q” [notation]
“P ⇒ Q” can also be written…
(i) P implies Q .
(ii) If P, then Q .
(iii) (not P) or Q .
If P is a false statement, then the implication P ⇒ Q is … (true/false) [notation]
If P is a false statement, then the implication P ⇒ Q is true.
(follows from the fact that “P ⇒ Q” is equivalent to “(not P) or Q”)
P is true;
Q is true;
then P ⇒ Q is … (true/false) .
[truth table]
P is true;
Q is true;
then P ⇒ Q is true .
P is true;
Q is false;
then P ⇒ Q is … (true/false) .
[truth table]
P is true;
Q is false;
then P ⇒ Q is false .
P is false;
Q is true;
then P ⇒ Q is … (true/false) .
[truth table]
P is false;
Q is true;
then P ⇒ Q is true .
P is false;
Q is false;
then P ⇒ Q is … (true/false) .
[truth table]
P is false;
Q is false;
then P ⇒ Q is true .
symbol “⇔” name and meaning [notation]
“⇔” is called the double implication symbol;
means “if and only if”.
four statements equivalent to “P ⇔ Q” [notation]
“P ⇔ Q” can also be written…
(i) P if and only if Q .
(ii) (P ⇒ Q) and (Q ⇒ P) .
(iii) Either P and Q are both false, or P and Q are both true.
(iv) (P and Q) or ((not P) and (not Q)) .
converse of P ⇒ Q [notation]
The converse of P ⇒ Q
is “Q ⇒ P” .
True or false: an implication and its converse are equivalent.
(If false, correct the statement to make it true.)
[notation application]
False
Correction: An implication and its converse are not generally equivalent.
contrapositive of P ⇒ Q [notation]
The contrapositive of P ⇒ Q
is (not P) ⇒ (not Q) .
True or false: an implication and its contrapositive are equivalent.
(If false, correct the statement to make it true.)
[notation applicaton]
True
negation of the statement “P”
The negation of “P” is “not P”.
” ¬P “ meaning [notation]
” ¬P “ means “not P” (ie negation of statement P).
negation of “and” and “or” [notes]
Negation interchanges “and” and “or” according to De Morgan’s laws.
De Morgan’s laws [notes]
De Morgan’s laws:
¬(P or Q) ≡ (¬P and ¬Q)
¬(P and Q) ≡ (¬P or ¬Q)
“P ⇒ Q” in negation notation [notation]
P ⇒ Q
is equivalent to
¬P or Q .
negation of P ⇒ Q [notation application]
The negation of
¬(P ⇒ Q)
is
(P and ¬Q) .
algorithm for negating a quanifying statement [steps]
To negate a quantifying statement…
(1) Maintain the order of the quantified segments.
(2) Change every (∀…) segment into a (∃… such that) segment.
(3) Change each (∃… such that) segment into a (∀…) segment.
(4) Negate the final statement (ex: change = to ≠ , > to < , etc).
