Saturday, June 2, 2012

Introductory Logic, Part 2

Home  >  Philosophy  >  Logic

This is part 2 of my series on logic and critical thinking.
  1. Introductory Logic, Part 1—Introducing both logic in general (such as the difference between a deductive and inductive argument) and propositional logic in particular
  2. Introductory Logic, Part 2—More propositional logic
  3. Introductory Logic, Part 3—A defense of the material conditional

Bait

To bait both atheists and theists into reading this article on logic (though I hope you already have an interest in learning logic), consider this argument from evil:
  1. If God exists, then gratuitous evil does not exist.
  2. Gratuitous evil does exist.
  3. Therefore, God does not exist.
A theist cannot deny both premises on pain of irrationality (it is logically impossible that both premises are false) and I’ll show how one can prove it via symbolic logic in this article. Similarly, consider this moral argument:
  1. If God does not exist, then objective morality does not exist.
  2. Objective morality does exist.
  3. Therefore, God exists.
An atheist cannot deny both premises on pain of irrationality (it is logically impossible that both premises are false) and I’ll show how one can prove it via symbolic logic in this article.

Review

In my previous entry I talked about the connectives and various rules of logic. To recap the connectives:

ConnectiveSymbolic
Logic
English
Meaning
Notes
∧ (conjunction)p ∧ qp and qThe p and q parts are called conjuncts.
∨ (disjunction)p ∨ qp or qThe p and q parts are called disjuncts.
→ (conditional)p → qIf p, then qThe p part is called the antecedent and the q part is called the consequent. Sometimes p → q is read as “p implies q.”
↔ (biconditional)p ↔ qp, if and only if qThis means the same thing as “p → q and q → p.”
¬ (negation)¬pNot-pThe negation of P is ¬P, and ¬P means “not-P” or “P is false.”


To recap the rules of inference:

modus ponens
 
In English In Symbolic Logic
If p then q
p

Therefore, q
p → q
p

∴ q
modus tollens
 
In English In Symbolic Logic
If p then q
Not-q

Therefore, not-p
p → q
¬q

∴ ¬p


Disjunctive Syllogism
 
In English In Symbolic Logic
p or q
Not-p

Therefore, q
p ∨ q
¬p

∴ q
p or q
Not-q

Therefore, p
p ∨ q
¬q

∴ p
simplification
 
In English In Symbolic Logic
p and q

Therefore, p
p ∧ q

∴ p
p and q

Therefore, q
p ∧ q

∴ q


conjunction
 
p
q

∴ p ∧ q
constructive dilemma
 
(p → q) ∧ (r → s)
p ∨ r

∴ q ∨ s


hypothetical syllogism
 
p → q
q → r

∴ p → r
addition
 
p

∴ p ∨ q
absorption
 
p → q

∴ p → (p ∧ q)


Some equivalences:

equivalencename of equivalence
 
p ⇔ ¬¬pdouble negation
 
p → q ⇔ ¬q → ¬ptransposition (also called contraposition)
 
p → q ⇔ ¬p ∨ qmaterial implication
 
p ↔ q ⇔ (p → q) ∧ (q → p) biconditional equivalence
 
¬(p ∧ q) ⇔ ¬p ∨ ¬qDe Morgan’s laws
¬(p ∨ q) ⇔ ¬p ∧ ¬q
 
p ⇔ p ∧ p idempotence
p ⇔ p ∨ p


And some more equivalences:

equivalencename of equivalence
 
p ∧ q ⇔ q ∧ pcommutation
p ∨ q ⇔ q ∨ p
 
p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ rassociation
p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r
 
p → (q → r) ⇔ (p ∧ q) → rexportation
 
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)distribution
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)


Next I’ll introduce some cool new rules of inference: conditional proof and indirect proof (also known as proof by contradiction, among other names). I’ll also show how to use symbolic logic to prove a statement without using any premises.

Conditional Proofs

Recall that the conditional is symbolized as p → q where p is called the antecedent and q is called the consequent. The conditional proof aims to prove that a conditional is true, with the antecedent of the conditional being the conditional proof assumption which is often used to help show that if the antecedent is true then the consequent is true also. The structure of a conditional proof takes the following form below:

conditional proof
 
a) p conditional proof assumption
b)
 ...
 q
c) p → q a-b, conditional proof


For example, suppose we want to prove A → (B ∧ C) from premises 1 and 2 below:
  1. A → B
  2. A → C

  1. A conditional proof assumption
    1. B 1, 3, modus ponens
    2. C 2, 3, modus ponens
    3. B ∧ C 4, 5, conjunction
  1. A → (B ∧ C) 3-6, conditional proof
Notice that the validity of a conditional proof does not rely on the conditional proof assumption actually being true; rather it relies on the fact that if it is true then it properly leads to the consequent. Nothing in the proof above, for example, relies an A actually being true, which brings us to this caveat: once the conditional proof has been ended, no lines inside it can be used again. Lines 3-6 are inaccessible for lines 7 onward. For example, note the mistakes below:
  1. A → B
  2. A → C

  1. A conditional proof assumption
    1. B 1, 3, modus ponens
    2. C 2, 3, modus ponens
    3. B ∧ C 4, 5, conjunction
  1. A → (B ∧ C) 3-6, conditional proof
  2. (A → B) ∧ A 1, 3, conjunctionMistake!
  3. (A → B) ∧ C 1, 5, conjunctionMistake!
It’s possible for a symbolic logic proof to have many conditional proofs, even conditional proofs inside other conditional proofs, provided they obey the accessibility restriction mentioned earlier (e.g. once an “inner” conditional proof is ended, the lines of that inner conditional proof can’t be accessed by the “outer” conditional proof). Sometimes one handy rule when doing conditional proofs is reiteration.

reiteration
 
p

∴ p


At first blush reiteration might not seem like a very handy rule, but its use comes from being able to put one proposition from the “outside” to the “inside,” as illustrated below
  1. B

  1. A conditional proof assumption
    1. B 1 reiteration
  1. A → B 2-3, conditional proof
Of course, the rule about accessibility applies with reiteration. Note for example the mistakes below:
  1. A → B
  2. A → C

  1. A conditional proof assumption
    1. B 1, 3, modus ponens
    2. C 2, 3, modus ponens
    3. B ∧ C 4, 5, conjunction
  1. A → (B ∧ C) 3-6, conditional proof
  2. A 3, reiterationMistake!
  3. C 5, reiterationMistake!

Indirect Proof

Another proof method known by various names as indirect proof and proof by contradiction begins by assuming the opposite of what you want to prove and then obtaining a logical contradiction, i.e. a contradiction of the p ∧ ¬p or ¬p ∧ p sort. The structure of an indirect proof:

indirect proof
 
a) p indirect proof assumption
b)
 ...
 q ∧ ¬q (or ¬q ∧ q)
c) ¬p a-b, indirect proof
a) ¬p indirect proof assumption
b)
 ...
 q ∧ ¬q (or ¬q ∧ q)
c) p a-b, indirect proof


For example, suppose we wanted to prove ¬(H ∧ R) from premise 1 below:
  1. (H ∧ R) → ¬(H ∧ R)

  1. H ∧ R indirect proof assumption
    1. ¬(H ∧ R) 1, 2, modus ponens
    2. (H ∧ R) ∧ ¬(H ∧ R) 2, 3, conjunction
  1. ¬(H ∧ R) 2-4, indirect proof
Suppose we wanted to prove B from premises 1-3 below:
  1. ¬B → ¬D
  2. ¬B → E
  3. [¬B → (¬D ∧ E)] → D

  1. ¬B indirect proof assumption
    1. ¬B conditional proof assumption
      1. ¬D 1, 5, modus ponens
      2. E 2, 5, modus ponens
      3. ¬D ∧ E 6, 7, conjunction
    1. ¬B → (¬D ∧ E) 5-8, conditional proof
    2. D 3, 9 modus ponens
    3. ¬D 1, 4, modus ponens
    4. D ∧ ¬D 10, 11 conjunction
  1. B 4-12, indirect proof
As the above example illustrates, you can have conditional proofs inside indirect proofs; you can also have indirect proofs inside conditional proofs. The same sort of accessibility restrictions go for indirect proofs as for conditional proofs. To illustrate, note the following mistakes:
  1. ¬B → ¬D
  2. ¬B → E
  3. [¬B → (¬D ∧ E)] → D

  1. ¬B indirect proof assumption
    1. ¬B conditional proof assumption
      1. ¬D 1, 5, modus ponens
      2. E 2, 5, modus ponens
      3. ¬D ∧ E 6, 7, conjunction
    1. ¬B → (¬D ∧ E) 5-8, conditional proof
    2. D 3, 9 modus ponens
    3. ¬D 1, 5, modus ponensMistake! 5 is inaccessible!
    4. E 7, reiterationMistake!
    5. D ∧ ¬D 10, 11 conjunction
  1. B 4-13, indirect proof
  2. D ∨ Z 10, additionMistake!
The next section has some interesting things to say about modus ponens and modus tollens.

Demonstrating Inconsistent Premises

One proves that the premises are inconsistent with each other by deriving a logical contradiction. This has an interesting application for modus ponens and modus tollens. First, consider the representative modus ponens argument below:
  1. P → Q
  2. P

  1. Q 1, 2, modus ponens
It turns out that it’s logically impossible for both premises of a modus ponens argument to be false. How can we prove it? Simply negate both premises and derive a logical contradiction.
  1. ¬(P → Q)
  2. ¬P

  1. ¬Q conditional proof assumption
    1. ¬P 2, reiteration
  1. ¬Q → ¬P 3-4, conditional proof
  2. P → Q 5, transposition
  3. ¬(P → Q) ∧ (P → Q) 1, 6, conjunction
It is likewise impossible for both premises of a modus tollens argument to be false. A representative modus tollens argument:
  1. P → Q
  2. ¬Q

  1. ¬P 1, 2, modus tollens
As before, we negate both premises and derive a logical contradiction:
  1. ¬(P → Q)
  2. ¬¬Q

  1. P conditional proof assumption
    1. Q 2, double negation
  1. P → Q 3-4, conditional proof
  2. ¬(P → Q) ∧ (P → Q) 1, 5, conjunction
So the only way to deny both premises of a modus ponens or modus tollens argument is to reject a rule of logic, and that is (presumably) much too high a price to pay. Next I’ll talk about how to prove things in symbolic logic without using premises.

Symbolic Logic Proofs Without Premises

So how do you prove things in propositional logic without premises? Easy: you can use conditional proofs and indirect proofs. For example, suppose we want to prove (A ∧ ¬A) → (K ∧ I):
  1. A ∧ ¬A conditional proof assumption
    1. ¬A 1, simplification
    2. A 1, simplification
    3. A ∨ (K ∧ I) 3 addition
    4. K ∧ I 2, 4, disjunctive syllogism
  1. (A ∧ ¬A) → (K ∧ I) 1-5, conditional proof
As you might suspect, anything follows from a contradiction. Using the sort of strategy above, we could have had A ∧ ¬A imply anything we wanted to thanks to rules of logic like simplification, addition, and disjunctive syllogism.

In propositional logic, proofs without premises are called theorems. As you might guess, not every statement is a theorem, but the famous law of logic the law of noncontradiction is. A famous rule of logic called the law of noncontradiction says that for any proposition p, it is impossible for p and not-p to be true at the same time and in the same context. In symbolic logic, the law of noncontradiction is expressed as ¬(p ∧¬p). Here’s how one can prove it:
  1. P ∧¬P indirect proof assumption
    1. P ∧¬P 1, reiteration
  1. ¬(P ∧ ¬P) 1-2, indirect proof
OK, so maybe that was too easy. Another rule of logic called the law of excluded middle says that for any proposition p, either p or not-p is true. Expressed in symbolic logic, the law of excluded middle is p ∨ ¬p. One way to prove the law is the theorem below:
  1. ¬(P ∨¬P) indirect proof assumption
    1. ¬P ∧¬¬P 1, De Morgan’s laws
  1. P ∨ ¬P 1-2, indirect proof
Still not much of a challenge, but oh well. At least we have the proof.

No, I Won’t Bait and Switch

First, for the atheist:
  1. If God exists, then gratuitous evil does not exist.
  2. Gratuitous evil does exist.
  3. Therefore, God does not exist.
Let G be “God exists” and E be “Gratuitous evil exists.” Then using symbolic logic the premises are:
  1. G → ¬E
  2. E
If we want to show that both premises being false is impossible, we negate both premises and derive a logical contradiction.
  1. ¬(G → ¬E)
  2. ¬E

  1. G conditional proof assumption
    1. ¬E2, reiteration
  1. G → ¬E 3-4, conditional proof
  2. ¬(G → ¬E) ∧ (G → ¬E) 1, 5, conjunction
So at least one of the premises must be true. Of course, the sword of logic cuts both ways. The moral argument:
  1. If God does not exist, then objective morality does not exist.
  2. Objective morality does exist.
  3. Therefore, God exists.
Using G to symbolize “God exists” and O as “Objective morality exists” the premises are these:
  1. ¬G → ¬M
  2. M
As before, if we want to show that both premises being false is impossible, we negate both premises and derive a logical contradiction.
  1. ¬(¬G → ¬M)
  2. ¬M

  1. ¬G conditional proof assumption
    1. ¬M ∧ ¬G2, 3, conjunction
    2. ¬M 4, simplification
  1. ¬G → ¬M 3-5, conditional proof
  2. ¬(¬G → ¬M) ∧ (¬G → ¬M) 1, 5, conjunction
The rational atheist would have to agree that at least one of the premises is true.

Symbolic Logic Summary

To summarize the rules of logic learned in this entry:

conditional proof
 
a) p conditional proof assumption
b)
 ...
 q
c) p → q a-b, conditional proof

reiteration
 
p

∴ p
indirect proof
 
a) p indirect proof assumption
b)
 ...
 q ∧ ¬q (or ¬q ∧ q)
c) ¬p a-b, indirect proof
a) ¬p indirect proof assumption
b)
 ...
 q ∧ ¬q (or ¬q ∧ q)
c) p a-b, indirect proof

No comments:

Post a Comment