Indirect Proof
Science works to either prove or disprove assertions. This is contrary to those who insist that science seeks only to disprove assertions. This mentality causes the acceptance of assertions unless they are proven false. Therein lies a dangerous way of thinking since it leads to "guilty until proven innocent" once an accusation is made. Assertions are not acceptable as fact until they are proven true. In this section, we consider "proof by contradiction", one side of scientific effort.
3.5.3 Indirect Proof
Consider a theorem P ⇒ C, where P represents p1, p2, ..., and pn, the premises. The method of indirect proof is based on the equivalence P → C ⇔ ¬(P∧ ¬C). In words, this logical law states that if P⇒ C, then P∧ ¬C is always false; that is, P∧ ¬C is a contradiction. This means that a valid method of proof is to negate the conclusion of a theorem and add this negation to the premises. If a contradiction can be implied from this set of propositions, the proof is complete. For the proofs in this section, a contradiction will often take the form t∧ ¬t.
For proofs involving numbers, a contradiction might be 1 = 0 or 0 < 0. Indirect proofs involving sets might conclude with x ∈ ∅ or ( x ∈ A and x ∈ Ac). Indirect proofs are often more convenient than direct proofs in certain situations. Indirect proofs are often called proofs by contradiction.
Example 3.5.14: An Indirect Proof. Here is an example of an indirect proof of the theorem in Example 3.5.7.
Table 3.5.15: An Indirect proof of p → r, q → s, p ∨ q ⇒ s ∨ r
Note 3.5.16: Proof Style. The rules allow you to list the premises of a theorem immediately; however, a proof is much easier to follow if the premises are only listed when they are needed.
Example 3.5.17: Yet Another Indirect Proof. Here is an indirect proof of a → b, ¬(b ∨ c) ⇒ ¬a.
Table 3.5.18 Indirect proof of a → b, ¬(b ∨ c) ⇒ ¬a
As we mentioned at the outset of this section, we are only presenting an overview of what a mathematical system is. For greater detail on axiomatic theories, see Stoll (1961). An excellent description of how propositional calculus plays a part in artificial intelligence is contained in Hofstadter (1980). If you enjoy the challenge of constructing proofs in propositional calculus, you should enjoy the game WFF’N PROOF (1962), by L.E. Allen.
Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.