The method of proof by contradiction establishes a statement as true by showing that its negation leads to two mutually exclusive results. This method is made possible by the fact that in Boolean Algebraic logic a proposition is either true or false and no where in between.
For every contradiction N and every proposition ᵹ the formula ᵹ ⇔ ( ¬ᵹ ⇒ N) is a tautology. If ¬ᵹ ⇒ N is true, then ᵹ is true by contraposition. N can also be represented by (ᴔ ∧ ¬ᴔ) where ᴔ is a proposition. If it can be shown that ¬ᵹ ⇒ ᴔ and ¬ᵹ ⇒ ¬ᴔ, then [¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ)] ⇔ ( ¬ᵹ ⇒ N). Since, the proposition ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ) can be constructed (is true) the only possibility is that ¬ᵹ must be false.
Assume P and Q are propositions, P ⇒ Q, and (P ⇒ Q) ⇔ ᵹ. (P ⇒ Q) ⇔ ¬(P ∧ ¬Q). So, ¬ᵹ ⇔ (P ∧ ¬Q). In order to prove ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ), if P ⇒ ᴔ and ¬Q ⇒ ¬ᴔ, then ¬ᵹ ⇒ (ᴔ ∧ ¬ᴔ) since [(P ⇒ ᴔ) ∧ (¬Q ⇒ ¬ᴔ)] ⇒ [(P ∧ ¬Q) ⇒ (ᴔ ∧ ¬ᴔ)]. Therefore P ⇒ Q is true according to the method of proof by contradiction.
No comments:
Post a Comment