Deductive reasoning

From Wikipedia, the free encyclopedia

Deductive reasoning is the kind of reasoning in which the conclusion is necessitated by, or reached from, previously known facts (the premises). If the premises are true, the conclusion must be true. This is distinguished from abductive and inductive reasoning, where the premises may predict a high probability of the conclusion, but do not ensure that the conclusion is true.

Deductive reasoning may also be defined as inference in which the conclusion is of no greater generality than the premises or inference in which the conclusion is just as certain as the premises.

Contents 1 How it works 1.1 Valid 1.2 Invalid: 2 Popular misuses of the term 3 Symbolic logic 4 Axiomatization 5 Natural deductive logic 6 References 7 See also

[edit] How it works

Somebody could say, "Since it is wet, it must have rained". However, there is a hidden argument in this statement: "If it's raining then the street gets wet." Using the premise "If it's raining then the street gets wet" one could argue that "Since it's raining the street is wet" but not "The street is wet so it must be raining".

This is because the wet street is an unavoidable product created by the rain but the wet street does not have to be caused by rain. The basic statement "if something then something else" could logically be followed by "something is; so something else must be" and "something else is not; so something else cannot be". These are the first two basic valid reasoning types. A few examples follow:

[edit] Valid

1. Since Socrates is a man,
2. and since all men are mortal,
3. Socrates is mortal.

1. Since the picture is above the desk,
2. and since the desk is above the floor,
3. the picture is above the floor.

1. Since a cardinal is a bird,
2. and since all birds have wings,
3. a cardinal has wings.

All these sentences are of the form :

a -> b
b -> c
a -> c

[edit] Invalid:

1. Left wing politicians do not tolerate animal cruelty.
2. Richard thinks hitting a dog is wrong.
3. Richard is a left wing politician.

1. Every criminal opposes the government.
2. Everyone in the opposition party opposes the government;
3. Therefore, everyone in the opposition party is a criminal.

These are invalid because the premises fail to establish commonality between hitting a dog and being a left wing politician, and membership in the opposition party and being a criminal, respectively. This is the famous fallacy of the undistributed middle.

In other words, they are of them form :

  a -> c
  b -> c
  b -> a

[edit] Popular misuses of the term

It is occasionally taught in grade school that deductive reasoning proceeds from the general to the particular, while inductive reasoning proceeds from the particular to the general. This is false - or at least, is not the way logicians use these terms. There are deductively valid arguments that proceed from the particular to the general (Oscar is grouchy, therefore something is grouchy) and inductive arguments that proceed from the general to the particular (most Rice University students are smart, therefore this particular Rice University student is smart).

Sherlock Holmes frequently describes his methods as involving deductive reasoning in the various stories about the character. However, most of his "deductions" in fact used inductive or abductive reasoning; very few were actually deductive in nature. There was nearly always some concievable, if vanishingly unlikely, way his conclusions could have turned out to be incorrect, a fact exploited by many parodies of the Sherlock Holmes stories.

[edit] Symbolic logic

Basic arguments of the propositional calculus
Name	Sequent	Description
Modus Ponens	[(p → q) ∧ p] ⊢ q	if p then q; p; therefore q
Modus Tollens	[(p → q) ∧ ¬q] ⊢ ¬p	if p then q; not q; therefore not p
Hypothetical syllogism	[(p → q) ∧ (q → r)] ⊢ (p → r)	if p then q; if q then r; therefore, if p then r
Disjunctive syllogism	[(p ∨ q) ∧ ¬p] ⊢ q	Either p or q; not p; therefore, q
Constructive dilemma	[(p → q) ∧ (r → s) ∧ (p ∨ r)] ⊢ (q ∨ s)	If p then q; and if r then s; but either p or r; therefore either q or s
Destructive dilemma	[(p → q) ∧ (r → s) ∧ (¬q ∨ ¬s)] ⊢ (¬p ∨ ¬r)	If p then q; and if r then s; but either not q or not s; therefore rather not p or not r
Simplification	(p ∧ q) ⊢ p,q	p and q are true; therefore p is true
Conjunction	p, q ⊢ (p ∧ q)	p and q are true separately; therefore they are true conjointly
Addition	p ⊢ (p ∨ q)	p is true; therefore the disjunction (p or q) is true
Composition	[(p → q) ∧ (p → r)] ⊢ [p → (q ∧ r)]	If p then q; and if p then r; therefore if p is true then q and r are true
De Morgan's theorem (1)	¬ (p ∧ q) ⊢ (¬p ∨ ¬q)	The negation of (p and q) is equiv. to (not p or not q)
De Morgan's Theorem (2)	¬ (p ∨ q) ⊢ (¬p ∧ ¬q)	The negation of (p or q) is equiv. to (not p and not q)
Commutation (1)	(p ∨ q) ⊢ (q ∨ p)	(p or q) is equiv. to (q or p)
Commutation (2)	(p ∧ q) ⊢ (q ∧ p)	(p and q) is equiv. to (q and p)
Association (1)	[p ∨ (q ∨ r)] ⊢ [(p ∨ q) ∨ r]	p or (q or r) is equiv. to (p or q) or r
Association (2)	[p ∧ (q ∧ r)] ⊢ [(p ∧ q) ∧ r]	p and (q and r) is equiv. to (p and q) and r
Distribution (1)	[p ∧ (q ∨ r)] ⊢ [(p ∧ q) ∨ (p ∧ r)]	p and (q or r) is equiv. to (p and q) or (p and r)
Distribution (2)	[p ∨ (q ∧ r)] ⊢ [(p ∨ q) ∧ (p ∨ r)]	p or (q and r) is equiv. to (p or q) and (p or r)
Double negation	p ⊢ ¬¬p	p is equivalent to the negation of not p
Transposition	(p → q) ⊢ (¬q → ¬p)	If p then q is equiv. to if not q then not p
Material implication	(p → q) ⊢ (¬p ∨ q)	If p then q is equiv. to either not p or q
Material equivalence (1)	(p ↔ q) ⊢ [(p → q) ∧ (q → p)]	(p is equiv. to q) means, (if p is true then q is true) and (if q is true then p is true)
Material equivalence (2)	(p ↔ q) ⊢ [(p ∧ q) ∨ (¬q ∧ ¬p)]	(p is equiv. to q) means, either (p and q are true) or ( both p and q are false)
Exportation	[(p ∧ q) → r] ⊢ [p → (q → r)]	from (if p and q are true then r is true) we can prove (if q is true then r is true, if p is true)
Importation	[p → (q → r)] ⊢ [(p ∧ q) → r]	if r is true when q is true, under the condition that p is true, then if p and q are true, r is as well
Tautology	p ⊢ (p ∨ ¬p)	p is true is equiv. to p is true or p is false

[edit] Axiomatization

In formal terms, a deduction is a sequence of statements such that each statement can be derived from the preceding one. This leaves open the question of how to prove the first sentence (since it has no predecessor). Axiomatic propositional logic solves this by requiring the following conditions for a proof:

A proof of α from an ensemble Σ of well-formed formulas (wffs) is a finite sequence of wffs:

β1,...,βi,...,βn

where

βn = α

and for each βi (1 ≤ i ≤ n), either

• βi ∈ Σ

or

• βi is an axiom,

or

• βi is the output of Modus Ponens for two previous wffs, βi-g and βi-h.

Different versions of axiomatic propositional logics contain a few axioms, usually three or more, in addition to one or more inference rules. For instance, Gottlob Frege's axiomatization of propositional logic, which is also the first instance of such an attempt, has six propositional axioms and two rules. Bertrand Russell and Alfred North Whitehead also suggested a system with five axioms.

For instance a version of axiomatic propositional logic due to Jan Lukasiewicz (1878-1956) has a set A of axioms adopted as follows:

• [PL1] p → (q → p)
• [PL2] (p → (q → r)) → ((p → q) → (p → r))
• [PL3] (¬p → ¬q) → (q → p)

and it has the set R of Rules of inference with one rule in it that is Modu Ponendo Ponens as follows:

• [MP] from α and α → β, infer β.

The inference rule(s) allows people to derive the statements following the axioms or given wffs of the ensemble Σ.

[edit] Natural deductive logic

One version of natural deductive logic has no axioms. System L, developed by E.J. Lemmon, has only nine primitive rules that govern the syntax of a proof.

The nine primitive rules of system L are

1. The Rule of Assumption (A)
2. Modus Ponendo Ponens (MPP)
3. The Rule of Double Negation (DN)
4. The Rule of Conditional Proof (CP)
5. The Rule of ∧-introduction (∧I)
6. The Rule of ∧-elimination (∧E)
7. The Rule of ∨-introduction (∨I)
8. The Rule of ∨-elimination (∨E)
9. Reductio Ad Absurdum (RAA)

In system L, a proof has a definition with the following conditions:

1. has a finite sequence of wffs (well-formed formula)
2. each line of it is justified by a rule of the system L
3. the last line of the proof is what is intended, and this last line of the proof uses the only premise(s) that is given; or no premise if nothing is given.

Then if no premise is given, the sequent is called theorem. Therefore, the definitions of a theorem in system L are

• a theorem is a sequent that can be proved in system L, using an empty set of assumption.
• a theorem is a sequent that can be proved from an empty set of assumptions in system L.

An example of the proof of a sequent (Modus Tollendo Tollens in this case):

p → q, ¬q ⊢ ¬p [Modus Tollendo Tollens (MTT)]
Assumption number	Line number	Formula (wff)	Lines in-use and Justification
1	(1)	(p → q)	A
2	(2)	¬q	A
3	(3)	p	A (for RAA)
1,3	(4)	q	1,3,MPP
1,2,3	(5)	q ∧ ¬q	2,4,∧I
1,2	(6)	¬p	3,5,RAA
Q.E.D

An example of the proof of a sequent (a theorem in this case):

⊢p ∨ ¬p
Assumption number	Line number	Formula (wff)	Lines in-use and Justification
1	(1)	¬(p ∨ ¬p)	A (for RAA)
2	(2)	¬p	A (for RAA)
2	(3)	(p ∨ ¬p)	2, ∨I
1, 2	(4)	(p ∨ ¬p) ∧ ¬(p ∨ ¬p)	1, 2, ∧I
1	(5)	¬¬p	2, 4, RAA
1	(6)	p	5, DN
1	(7)	(p ∨ ¬p)	6, ∨I
1	(8)	(p ∨ ¬p) ∧ ¬(p ∨ ¬p)	1, 7, ∧I
	(9)	¬¬(p ∨ ¬p)	1, 8, RAA
	(10)	(p ∨ ¬p)	9, DN
Q.E.D

Each rule of system L has its own requirements for the type of input(s) or entry(es) that it can accept and has its own way of treating and calculating the assumptions used by its inputs.

[edit] References

• Vincent F. Hendricks, Thought 2 Talk: A Crash Course in Reflection and Expression, New York: Automatic Press / VIP, 2005, ISBN 87-991013-7-8

• Jennings, R. E., Continuing Logic, the course book of 'Axiomatic Logic' in Simon Fraser University, Vancouver, Canada

• Zarefsky, David, Argumentation: The Study of Effective Reasoning Parts I and II, The Teaching Company 2002

[edit] See also

Abductive reasoning Analogical reasoning Correspondence theory of truth Defeasible reasoning Hypothetico-deductive method Inductive reasoning

Inquiry Logical consequence Propositional calculus Retroductive reasoning Soundness Validity