rules of
if p then q
p
therefore q
Modus Ponens
a special rule in a formal proof which allows us to assume the antecedent of a conditional and, once we deduce that consequent, to conclude the entire conditional
Conditional proof
a path on a truth tree for which a contradiction has been found
closed branch
if p then q
not q
therefore not p
modus tollens
a special rule in a formal proof which allows us to assume the negation of a proposition, deduce a self-contradiction, then conclude the original proposition
Reductio ad Absurdum
simple propositions or negations of simple propositions
literals
if p then q
if q then r
therefore if p then r
hypothetical syllogism
1. understand what a proof is: use previous steps as premises in a rule to deduce the conclusion
2. keep the goal in mind: work toward conclusion
3. say steps out loud to help recognize a rule
4. when stuck, try Absorption or Addition
5. check for unused steps; usually each step is used once
5 hints for developing formal proofs
p if and only if (p v p)
p if and only if (p . p)
(a conjunction or disjunction of a proposition with itself can be simplified to just the proposition)
tautology
a path on a truth tree which includes no contradiction
Open branch
p or q
not p
therefore q
disjunctive syllogism
forms of equivalent statements, which may replace each other wherever they occur (even if part of a larger proposition) and work from left to right AND right to left
Rules of replacement
a diagram which shows a set of propositions being decomposed into their literals in order to look for contradictions
Truth Tree
(if p then q) AND (if r then s)
p v r
therefore q v s
Constructive dilemma
1. Try working backwards from the conclusion, or forward and backward at the same time to meet in the middle
2. try implication and/or DeMorgans to change from conditional to disjunction to conjunction or reverse
3. certain rules work more often with certain types of conclusions
3 hints for solving formal proofs
to break down compound propositions into simple propositions (or their negation) which are called literals
decompose