Deductive reasoning

• Ten things you didn't know about Wikipedia •
Deductive reasoning
From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article may require cleanup to meet Wikipedia's quality standards.
Please discuss this issue on the talk page or replace this tag with a more specific message.
This article has been tagged since June 2006.
This section does not cite any references or sources.
Please help improve this section by adding citations to reliable sources. (help, get involved!)
Unverifiable material may be challenged and removed.

(tagged since February 2007)

Deductive reasoning is the kind of reasoning where the conclusion is necessitated by previously known premises. If the premises are true then the conclusion must be true. For instance, beginning with the premises "sharks are fish" and "all fish have fins", you may conclude that "sharks have fins". This is distinguished from inductive reasoning and abductive reasoning where inferences can be made with some likelihood but never with complete certainty.

Deductive reasoning is dependent on its premises. That is, a false premise can possibly lead to a false result, and inconclusive premises will also yield an inconclusive conclusion.
Contents
[hide]

* 1 Examples
* 2 Popular misuses of the term
* 3 Inference rules
* 4 Formal definition
* 5 Natural deductive logic
* 6 References
* 7 See also

[edit] Examples

An example of deductive reasoning is the following:

All men are mortal (major premise),
Socrates is a man (minor premise),
Therefore Socrates is mortal.

Note that replacing "mortal" with any nonsensical property will not affect the validity of the argument:

All men are purple-skinned,
Socrates is a man,
Therefore Socrates is purple-skinned.

Intuitively, one might deny the major premise or the conclusion; yet anyone accepting the premises must accept the conclusion.

[edit] Popular misuses of the term

It is occasionally taught 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, it 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 conceivable, if vanishingly unlikely, way his conclusions could have turned out to be incorrect, fact exploited by many parodies of the Sherlock Holmes stories.

[edit] Inference rules

The following table lists some inference rules of propositional calculus. The table makes use of mathematical notation. The following symbols occur in the table:

* p ∨ q: p must be true, or q must be true (or both)
* p ∧ q: both p and q must be simultaneously true
* p → q: p implies q: if p is true then so is q
* p ↔ q: p is logically equivalent to q: if either is true/false, then so is the other.
* p ⊢ q: from p infer q (by applying basic inference rules, q can be shown to hold assuming p (note that this is equivalent to ( ⊢ p → q).

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 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, for any q, (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) If it is not true that p and q hold, then at least either p or q is not true
De Morgan's Theorem (2) ¬ (p ∨ q) ⊢ (¬p ∧ ¬q) If it is not true that p or q holds, then p does not hold and q does not hold
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 (therefore, (p ∧ q ∧ r) is unambiguous)
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 IF p is true THEN the negation of the negation of p is true
Transposition (p → q) ⊢ (¬q → ¬p) If p then q IMPLIES 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) IF p is true THEN p is true or p is false (this can be seen as a special case of addition)

[edit] Formal definition

A deduction (or proof) can be defined precisely in the context of a formal system like the propositional calculus. A proposition α is deduced from a collection Σ of premises by applying inference rules repeatedly (see above section). The deduction is a record of this repeated application of inference rules.

More formally, a finite sequence β1 ,..., βn of propositions is said to be a deduction of α from a collection of premises Σ if

* βn = α, and
* For all 1 ≤ i ≤ n, either βi is a premise (i.e. βi ∈ Σ) or βi is the result of the application of some inference rule on ealier propositions in the sequence.

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 Łukasiewicz (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

Logic Portal
[show]
v • d • e
Philosophy
Topics Portal · Category listings | Eastern philosophy · Western philosophy | History of philosophy (ancient • medieval • modern • contemporary)
Lists Basic topics · Topic list · Philosophers · Philosophies · Glossary · Movements · More lists
Branches Aesthetics · Ethics · Epistemology · Logic · Metaphysics · Political philosophy
Philosophy of Education · Economics · Geography · Information · History · Human nature · Language · Law · Literature · Mathematics · Mind · Philosophy · Physics · Psychology · Religion · Science · Social science · Technology · War
Schools Analytic philosophy · Aristotelianism · Continental Philosophy · Critical theory · Deconstructionism · Deontology · Dialectical materialism · Dualism · Empiricism · Epicureanism · Existentialism · Hegelianism · Hermeneutics · Humanism · Idealism · Kantianism · Logical Positivism · Marxism · Materialism · Monism · Neoplatonism · New Philosophers · Nihilism · Ordinary language · Phenomenology · Platonism · Positivism · Postmodernism · Poststructuralism · Pragmatism · Presocratic · Rationalism · Realism · Relativism · Scholasticism · Skepticism · Stoicism · Structuralism · Utilitarianism · Virtue ethics
[show]
v • d • e
Logic
Navigation: Portal · Category · WikiProject · Logic Stubs · Mathlogic Stubs · Cleanup · Noticeboard
Main Articles: Reason · History of Logic · Philosophical Logic · Mathematical Logic · Metalogic · Logic in computer science
Key Concepts

* Reasoning: Deduction · Induction · Abduction
* Informal Logic: Proposition · Inference · Argument · Validity · Cogency · Term logic · Critical Thinking · Fallacies · Syllogism
* Mathematical logic: Set · Syntax · Semantics · Wff · Axiom · Theorem · Consistency · Soundness · Completeness · Decidability · Formal system · Set theory · Proof theory · Model theory · Recursion theory
* Zeroth-Order Logic: Boolean functions · Monadic predicate calculus · Propositional calculus · Logical connectives · Truth Tables
* Predicate Logic: First-Order Logic · Quantifiers · Second-order logic
* Modal Logic: Deontic logic · Epistemic logic · Temporal logic · Doxastic logic
* Other non-classical logics: Computability logic · Fuzzy logic · Linear logic · Relevance logic · Non-monotonic logic

Controversies Paraconsistent Logic · Dialetheism · Intuitionistic logic · Paradoxes · Antinomies · Is logic empirical?
Key Figures Aristotle · Boole · Cantor · Carnap · Church · Frege · Gentzen · Gödel · Hilbert · Kripke · Peano · Peirce · Putnam · Quine · Russell · Skolem · Tarski · Turing · Whitehead
Lists Basic Topics in Logic · Topics in Logic · Logicians · Rules of Inference · Mathematical Logic Topics · Basic Discrete Mathematics Topics · Set theory topics · Paradoxes · Fallacies · Logical Symbols
Retrieved from "http://en.wikipedia.org/wiki/Deductive_reasoning"

Categories: Cleanup from June 2006 | All pages needing cleanup | Articles needing additional references from February 2007 | Logic | Problem solving | Philosophical terminology
Views

* Article
* Discussion
* Edit this page
* History

Personal tools

* Sign in / create account

Navigation

* Main page
* Contents
* Featured content
* Current events
* Random article

interaction

* About Wikipedia
* Community portal
* Recent changes
* Contact Wikipedia
* Donate to Wikipedia
* Help

Search

Toolbox

* What links here
* Related changes
* Upload file
* Special pages
* Printable version
* Permanent link
* Cite this article

In other languages

* Bosanski
* Български
* Česky
* Dansk
* Deutsch
* Eesti
* Español
* Français
* Galego
* 한국어
* Hrvatski
* Íslenska
* עברית
* Latviešu
* Magyar
* Македонски
* Nederlands
* 日本語
* ‪Norsk (bokmål)‬
* ‪Norsk (nynorsk)‬
* O'zbek
* Polski
* Português
* Русский
* Slovenščina
* Српски / Srpski
* Srpskohrvatski / Српскохрватски
* Svenska
* Tiếng Việt
* Türkçe
* Українська
* 中文

Powered by MediaWiki
Wikimedia Foundation

* This page was last modified 02:06, 28 August 2007.
* All text is available under the terms of the GNU Free Documentation License. (See Copyrights for details.)
Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a US-registered 501(c)(3) tax-deductible nonprofit charity.
* Privacy policy
* About Wikipedia
* Disclaimers

Your continued donations keep Wikipedia running!