8/31/24, 5:46 PM
D420 Discrete Math: Logic
Jeremiah
Terms in this set (111)
proposition a statement that is either true or false
and
^
or
v
¬ negation
conditional operation, "if p, then q"
→
If p, q
q, if p
Equivalent English expressions that mean "if p implies q
p, then q" p only if q
p is sufficient for q
q is necessary for p
in a conditional proposition "→" p is the _______ p is the hypothesis and q is the conclusion
and q is the __________
The converse is the opposite of the For example, the converse of p → q (if p then q) is q → p (if q then p). If p → q is true, it
conditional statement does NOT guarantee that q → p is true
The inverse is the negation of the conditional For example, the inverse of p → q (if p then q) is ¬p → ¬q (if not p then not q). If p → q
statement is true, it does NOT guarantee that ¬p → ¬q is true
The contrapositive is the opposite and For example, the contrapositive of p → q (if p then q) is ¬q → ¬p (if not q then not p). If
negative of the conditional statement p → q is true, it DOES guarantee that ¬q → ¬p is true
1/7
, 8/31/24, 5:46 PM
is read "p is necessary and sufficient for q" or "if p
then q, and conversely" or "p if and only if q"
biconditional operation
Two compound propositions are logically equivalent if they have the same truth value.
Logical equivalence p ≡ q 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 is always true. For example, p∨¬p.
contradiction if the compound proposition is always false. For example, p∧¬p.
logical equivalences that show how to correctly distribute a negation operation inside a
parenthesized expression containing the disjunction or conjunction operator.
De Morgan's Law
¬(p ∨ q) = (¬p ∧ ¬q)
¬(p ∧ q) = (¬p ∨ ¬q)
p ∨ (p ∧ q) ≡ p
Absorption laws
p ∧ (p ∨ q) ≡ p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p∨q≡q∨p
Commutative laws
p∧q≡q∧p
p ∧ ¬p ≡ F
¬T ≡ F
Complement laws
p ∨ ¬p ≡ T
¬F ≡ T
p → q ≡ ¬p ∨ q
Conditional identities
p↔q≡(p→q)∧(q→p)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨T≡T
Domination laws
p ∧F ≡F
Double negation law ¬(¬p) ≡ p
p∨p≡p
idempotent laws
p∧p≡p
p ∧T≡ p
identity laws
p ∨F ≡p
predicate a logical statement whose truth value is a function of one or more variables
domain of the predicate the set of all possible x values for P(x) is called the domain of the predicate
universal quantifier "for all x", is denoted ∀x, P(x). This means that for all values of x in the domain of P(x),
the predicate is true.
D420 Discrete Math: Logic
2/7
D420 Discrete Math: Logic
Jeremiah
Terms in this set (111)
proposition a statement that is either true or false
and
^
or
v
¬ negation
conditional operation, "if p, then q"
→
If p, q
q, if p
Equivalent English expressions that mean "if p implies q
p, then q" p only if q
p is sufficient for q
q is necessary for p
in a conditional proposition "→" p is the _______ p is the hypothesis and q is the conclusion
and q is the __________
The converse is the opposite of the For example, the converse of p → q (if p then q) is q → p (if q then p). If p → q is true, it
conditional statement does NOT guarantee that q → p is true
The inverse is the negation of the conditional For example, the inverse of p → q (if p then q) is ¬p → ¬q (if not p then not q). If p → q
statement is true, it does NOT guarantee that ¬p → ¬q is true
The contrapositive is the opposite and For example, the contrapositive of p → q (if p then q) is ¬q → ¬p (if not q then not p). If
negative of the conditional statement p → q is true, it DOES guarantee that ¬q → ¬p is true
1/7
, 8/31/24, 5:46 PM
is read "p is necessary and sufficient for q" or "if p
then q, and conversely" or "p if and only if q"
biconditional operation
Two compound propositions are logically equivalent if they have the same truth value.
Logical equivalence p ≡ q 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 is always true. For example, p∨¬p.
contradiction if the compound proposition is always false. For example, p∧¬p.
logical equivalences that show how to correctly distribute a negation operation inside a
parenthesized expression containing the disjunction or conjunction operator.
De Morgan's Law
¬(p ∨ q) = (¬p ∧ ¬q)
¬(p ∧ q) = (¬p ∨ ¬q)
p ∨ (p ∧ q) ≡ p
Absorption laws
p ∧ (p ∨ q) ≡ p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associative laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p∨q≡q∨p
Commutative laws
p∧q≡q∧p
p ∧ ¬p ≡ F
¬T ≡ F
Complement laws
p ∨ ¬p ≡ T
¬F ≡ T
p → q ≡ ¬p ∨ q
Conditional identities
p↔q≡(p→q)∧(q→p)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨T≡T
Domination laws
p ∧F ≡F
Double negation law ¬(¬p) ≡ p
p∨p≡p
idempotent laws
p∧p≡p
p ∧T≡ p
identity laws
p ∨F ≡p
predicate a logical statement whose truth value is a function of one or more variables
domain of the predicate the set of all possible x values for P(x) is called the domain of the predicate
universal quantifier "for all x", is denoted ∀x, P(x). This means that for all values of x in the domain of P(x),
the predicate is true.
D420 Discrete Math: Logic
2/7
