Proposition
A declarative statement which is true or false, but not both.
p^q
conjunction; "and
tautology
a proposition that is always true regardless of the truth values of its subpropositions, e.g. p or not-p
contradiction
a proposition that is always false regardless of the truth values of its subpropositions, e.g. p and not-p
commutative law
p v q = q v p; p ^ q = q ^ p
Associative law
(p v q) v r = p v (q v r);(p ^ q) ^ r = p ^ (q ^r)
Distributive law
p v (q ^ r) = ( p v q) ^ (p v r); p ^ (q v r) = ( p ^ q) v ( p ^ r);
Idempotent law
p v p = p; p ^ p = p
Identity law
p v F = p, p ^ T = p; p v T = T, p ^ F = F
Complement law
p v not-p = T; p ^ not-p = F;
Double negative
not(not-p) = p
De Morgan's Law
not(p or q) = not-p ^ not-q ; not(pr ^ q) = not-p v not-q
Absorption law
p v ( p ^ q) = p; p ^ (p v q) = p
When is the conditional statement p -> q false?
when p is true, and q is false
When is the conditional statement p -> q true?
when p is false, regardless of whether q is true of false
Contrapositive
if p then q == if not-p then not-q
Biconditional statement
p if and only if q
Modus ponens
p ^ (p ->q) -> q
modus tollens
(not-q ^ (p ->q)) -> not-p
transitivity (hypothetical syllogism)
((p->q)^(q->r)) -> (p -> r)
Elimination (disjunctive syllogism)
((p v q) ^ not-p) -> q
Generalization
p -> (p v q)
Simplification
(p ^ q) -> p
Conjunction
(( p ) ^ (q)) -> (p^q)
Resolution
((p v q) ^ ( not-p or r)) -> (q v r)
Example: If it snows today, then we will go skiing. It is snowing today. Therefore we will go skiing.
Modus Ponens
Example: Not all CS majors play videog games = some CS majors do not play video games
not(∀x ∈ A) p(x) = (∃x ∈ A)not p(x) De Morgan universal quantifier
Universal quantifier
∀; all elements
Existential quantifier
∃; some