A proof is a logical argument that tries to show that
a statement is true. In math, and computer science, a proof has to be well
thought out and tested before being accepted. But even then, a proof can
be discovered to have been wrong. There are many different ways to go
about proving something, we’ll discuss 3 methods: direct proof, proof by
contradiction, proof by induction.
Types of Proofs.
Suppose we wish to prove an implication p → q.
Here are some strategies we have available to try.
• Trivial Proof: If we know q is true then p →
q is true regardless of the truth value of p.
• Vacuous Proof: If p is a conjunction of
other hypotheses and we know one or more of these hypotheses is false, then p
is false and so p → q is vacuously true regardless of the truth value of q.
• Direct Proof: Assume p, and then use the
rules of inference, axioms, definitions, and logical equivalences to prove q.
• Indirect Proof or Proof by Contradiction:
Assume p and ¬q and derive a contradiction r ∧
¬r.
• Proof by
Contrapositive: (Special case of Proof by Contradiction.) Give a direct proof
of ¬q → ¬p. Assume ¬q and then use the rules of inference, axioms, definitions,
and logical equivalences to prove ¬p.(Can be thought of as a proof by
contradiction in which you assume p and ¬q and arrive at the contradiction p ∧ ¬p.)
• Proof by Cases: If the hypothesis p can be
separated into cases p1 ∨
p2 ∨ · · · ∨
pk, prove each of the propositions, p1 → q, p2 → q, . . . , pk → q, separately
0 comments:
Post a Comment
Let us know your responses and feedback