Discrete test 1 study Flashcards
conjunction of p and q
p ^ q p and q
true when both p and q are true
disjunction of p and q
p v q, p or q
true when at least p or q is true
exclusive or of p and q
true when p and q are different signals
if p then q
p -> q,
true in all cases except true implies false.
bi-conditional statement of p and q
pq, p if and only if q.
true when p and q have the same value. true or false
Converse of p -> q
q -> p
contrapositive of p -> q
~q -> ~p
inverse of p -> q
~p -> ~q
the converse is equivalent to
the inverse
the original is equivalent to the
contrapositive
how to tell if something is logically equivalent in 2 ways
use truth tables and match columns or use the table of logical equivalences to get to what you need
tautology
all is true
contradiciton
all is false
contingancy
neither always true nor always false
Axpx
for all x in px
Expx
there exists an x that satisfies px
E!xpx
there exists exactly one x that satisfys p(x)
how to negate A and E
flip them and move it in
even
The integer n is even if there exists an integer k such that n = 2k.
odd
The integer n is odd if there exists an integer k such that n = 2k +1.
rational number
A rational number p has the form 𝑎
𝑏
, where a and b are
integers and b ≠0.
Direct proof
To prove 𝑝 → 𝑞 using a direct proof, you assume
that p is true and show that q must also be true
Indirect proof
(proof by contraposition). To prove 𝑝 → 𝑞 using an
indirect proof, you prove ¬𝑞 → ¬𝑝 (the contrapositive) directly.
Proof by contradiction
To prove that a proposition p is true, we
assume that it is false and attain a logical contradiction, such as
𝑟 ⋀ ¬𝑟. Then it must be the case that p was true
Proof of 𝒑 ↔ 𝒒.contradiction
To prove 𝑝 ↔ 𝑞, we may prove both 𝑝 → 𝑞
and 𝑞 → 𝑝
Vacuous proof.
We know that when p is false, 𝑝 → 𝑞 is true. For
example, if P(n) (n is an integer) is the statement “if n is odd, then
n
2
is odd,” then the proposition P(2) is vacuously true since ‘2 is
odd’ is false.
Trivial proof
We know that when q is true, 𝑝 → 𝑞 is true. For
example, if P(n) (n is an integer) is the statement “if n is even, then
n + 1 > n,” then it P(n) is trivially true since n + 1 > n is true for all
integers, regardless of whether or not n is even.
Proof by cases.
. To prove (𝑝1⋁𝑝2⋁ … ⋁𝑝𝑛) → 𝑞, we show that
𝑝𝑖 → 𝑞 for i = 1, 2, …, n.
Existence Proofs
To prove ∃𝑥𝑃(𝑥) we may either construct an x
for which P(x) is true (constructive existence proof), or we may
demonstrate that P(x) is true for at least one x without actually
finding a specific x (nonconstructive existence proof).
Unique Existence Proof
To prove ∃! 𝑥𝑃(𝑥) we must show:
∃𝑥(𝑃(𝑥) ∧ ∀𝑦(𝑃(𝑦) → 𝑦 = 𝑥)) [Existence and Uniqueness]
Outline: We can use either a constructive or nonconstructive
existence proof to existence To prove uniqueness, suppose P(x)
and P(y) are both true and show that we must have x = y.
