D420 Discrete Math: Logic
proposition
a statement that is either true or false
^
and
K
C
Brainpower
v
or LO Read More
YC
¬
D
negation
→
conditional operation, "if p, then q"
U
ST
Equivalent English expressions that mean "if p, then q"
If p, q
q, if p
p implies q
p only if q
p is sufficient for q
q is necessary for p
, in a conditional proposition "→" p is the _______ and q is the __________
p is the hypothesis and q is the conclusion
The converse is the opposite of the conditional statement
For example, the converse of p → q (if p then q) is q → p (if q then p). If p → q is true, it
does NOT guarantee that q → p is true
The inverse is the negation of the conditional statement
For example, the inverse of p → q (if p then q) is ¬p → ¬q (if not p then not q). If p → q
is true, it does NOT guarantee that ¬p → ¬q is true
The contrapositive is the opposite and negative of the conditional statement
For example, the contrapositive of p → q (if p then q) is ¬q → ¬p (if not q then not p). If
K
p → q is true, it DOES guarantee that ¬q → ¬p is true
biconditional operation
C
is read "p is necessary and sufficient for q" or "if p then q, and conversely" or "p if and
only if q"
LO
Logical equivalence p ≡ q
YC
Two compound propositions are logically equivalent if they have the same truth value.
That is, the truth value in the final column in a truth table is the same for both compound
propositions
tautology
If the compound propositions are always true. For example, p∨¬p.
D
contradiction
if the compound proposition is always false. For example, p∧¬p.
U
De Morgan's Law
logical equivalences that show how to correctly distribute a negation operation inside a
parenthesized expression containing the disjunction or conjunction operator.
ST
¬(p ∨ q) = (¬p ∧ ¬q)
¬(p ∧ q) = (¬p ∨ ¬q)
Absorption laws
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
Associative laws
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
proposition
a statement that is either true or false
^
and
K
C
Brainpower
v
or LO Read More
YC
¬
D
negation
→
conditional operation, "if p, then q"
U
ST
Equivalent English expressions that mean "if p, then q"
If p, q
q, if p
p implies q
p only if q
p is sufficient for q
q is necessary for p
, in a conditional proposition "→" p is the _______ and q is the __________
p is the hypothesis and q is the conclusion
The converse is the opposite of the conditional statement
For example, the converse of p → q (if p then q) is q → p (if q then p). If p → q is true, it
does NOT guarantee that q → p is true
The inverse is the negation of the conditional statement
For example, the inverse of p → q (if p then q) is ¬p → ¬q (if not p then not q). If p → q
is true, it does NOT guarantee that ¬p → ¬q is true
The contrapositive is the opposite and negative of the conditional statement
For example, the contrapositive of p → q (if p then q) is ¬q → ¬p (if not q then not p). If
K
p → q is true, it DOES guarantee that ¬q → ¬p is true
biconditional operation
C
is read "p is necessary and sufficient for q" or "if p then q, and conversely" or "p if and
only if q"
LO
Logical equivalence p ≡ q
YC
Two compound propositions are logically equivalent if they have the same truth value.
That is, the truth value in the final column in a truth table is the same for both compound
propositions
tautology
If the compound propositions are always true. For example, p∨¬p.
D
contradiction
if the compound proposition is always false. For example, p∧¬p.
U
De Morgan's Law
logical equivalences that show how to correctly distribute a negation operation inside a
parenthesized expression containing the disjunction or conjunction operator.
ST
¬(p ∨ q) = (¬p ∧ ¬q)
¬(p ∧ q) = (¬p ∨ ¬q)
Absorption laws
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
Associative laws
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
