The Full Wiki

List of rules of inference: Wikis

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

Updated live from Wikipedia, last check: June 03, 2012 00:35 UTC (53 seconds ago)

From Wikipedia, the free encyclopedia

Logic portal

This is a list of rules of inference, logical laws that relate to mathematical formulae.

Contents

Introduction

Rules of inference are syntactical transformation rules which one can use to infer a conclusion from a premise to create an argument. A set of rules can be used to infer any valid conclusion if it is complete, while never inferring an invalid conclusion, if it is sound. A sound and complete set of rules need not include every rule in the following list, as many of the rules are redundant, and can be proven with the other rules.

Discharge rules permit inference from a subderivation based on a temporary assumption. Below, the notation

\varphi \vdash \psi\,\!

indicates such a subderivation from the temporary assumption \varphi\,\! to \psi\,\!.

Rules for classical sentential calculus

Sentential calculus is also known as propositional calculus.

Rules for negations

Reductio ad absurdum (or Negation Introduction)
\varphi \vdash \psi\,\!
\underline{\varphi \vdash \lnot \psi}\,\!
\lnot \varphi\,\!
Reductio ad absurdum (related to the law of excluded middle)
\lnot \varphi \vdash \psi\,\!
\underline{\lnot \varphi \vdash \lnot \psi}\,\!
\varphi\,\!
Noncontradiction (or Negation Elimination)
\varphi\,\!
\underline{\lnot \varphi}\,\!
\psi\,\!
Double negation elimination
\underline{\lnot \lnot \varphi}\,\!
\varphi\,\!
Double negation introduction
\underline{\varphi \quad \quad}\,\!
\lnot \lnot \varphi\,\!

Rules for conditionals

Deduction theorem (or Conditional Introduction)
\underline{\varphi \vdash \psi}\,\!
\varphi \rightarrow \psi\,\!
Modus ponens (or Conditional Elimination)
\varphi \rightarrow \psi\,\!
\underline{\varphi \quad \quad \quad}\,\!
\psi\,\!
Modus tollens
\varphi \rightarrow \psi\,\!
\underline{\lnot \psi \quad \quad \quad}\,\!
\lnot \varphi\,\!

Rules for conjunctions

Adjunction (or Conjunction Introduction)
\varphi\,\!
\underline{\psi \quad \quad \ \ }\,\!
\varphi \land \psi\,\!
Simplification (or Conjunction Elimination)
\underline{\varphi \land \psi}\,\!
\varphi\,\!
\underline{\varphi \land \psi}\,\!
\psi\,\!

Rules for disjunctions

Addition (or Disjunction Introduction)
\underline{\varphi \quad \quad \ \ }\,\!
\varphi \lor \psi\,\!
\underline{\psi \quad \quad \ \ }\,\!
\varphi \lor \psi\,\!
Separation of Cases (or Disjunction Elimination)
\varphi \lor \psi\,\!
\varphi \rightarrow \chi\,\!
\underline{\psi \rightarrow \chi}\,\!
\chi\,\!
Disjunctive syllogism
\varphi \lor \psi\,\!
\underline{\lnot \varphi \quad \quad}\,\!
\psi\,\!
\varphi \lor \psi\,\!
\underline{\lnot \psi \quad \quad}\,\!
\varphi\,\!

Rules for biconditionals

Biconditional introduction
\varphi \rightarrow \psi\,\!
\underline{\psi \rightarrow \varphi}\,\!
\varphi \leftrightarrow \psi\,\!
Biconditional Elimination
\varphi \leftrightarrow \psi\,\!
\underline{\varphi \quad \quad}\,\!
\psi\,\!
\varphi \leftrightarrow \psi\,\!
\underline{\psi \quad \quad}\,\!
\varphi\,\!
\varphi \leftrightarrow \psi\,\!
\underline{\lnot \varphi \quad \quad}\,\!
\lnot \psi\,\!
\varphi \leftrightarrow \psi\,\!
\underline{\lnot \psi \quad \quad}\,\!
\lnot \varphi\,\!
\varphi \leftrightarrow \psi\,\!
\underline{\psi \lor \varphi}\,\!
\psi \land \varphi \,\!
\varphi \leftrightarrow \psi\,\!
\underline{\lnot \psi \lor \lnot \varphi}\,\!
\lnot \psi \land \lnot \varphi \,\!

Rules of classical predicate calculus

In the following rules, \varphi(\beta / \alpha)\,\! is exactly like \varphi\,\! except for having the term \beta\,\! everywhere \varphi\,\! has the free variable \alpha\,\!.

Universal Introduction (or Universal Generalization)
\underline{\varphi\quad\;\;}\,\!
\forall \alpha\, \varphi\,\!

Restriction: None.

Universal Elimination (or Universal Instantiation)
\forall \alpha\, \varphi\!
\overline{\varphi{(\beta / \alpha)}}\!

Restriction: No free occurrence of \alpha\,\! in \varphi\,\! falls within the scope of a quantifier quantifying a variable occurring in \beta\,\!.

Existential Introduction (or Existential Generalization)
\underline{\varphi(\beta / \alpha)}\,\!
\exists \alpha\, \varphi\,\!

Restriction: No free occurrence of \alpha\,\! in \varphi\,\! falls within the scope of a quantifier quantifying a variable occurring in \beta\,\!.

Existential Elimination (or Existential Instantiation)
\exists \alpha\, \varphi\,\!
\underline{\varphi \vdash \psi}\,\!
\psi\,\!

Restriction: There is no free occurrence of \alpha\,\! in \psi\,\!.

Table: Rules of Inference - a short summary

The rules above can be summed up in the following table. The "Tautology" column shows how to interpret the notation of a given rule.

Rule of inference Tautology Name
\begin{align} p \ \therefore \overline{p \vee q} \ \end{align} p \rightarrow (p \vee q) Addition
\begin{align} p \wedge q \ \therefore \overline{p \quad \quad \quad} \ \end{align} (p \wedge q) \rightarrow p Simplification
\begin{align} p\ q\ \therefore \overline{p \wedge q} \ \end{align} ((p) \wedge (q)) \rightarrow (p \wedge q) Conjunction
\begin{align} p\ p \rightarrow q\ \therefore \overline{q \quad \quad \quad} \ \end{align} ((p \wedge (p \rightarrow q)) \rightarrow q Modus ponens
\begin{align} \neg q\ p \rightarrow q\ \therefore \overline{\neg p \quad \quad \quad} \ \end{align} ((\neg q \wedge (p \rightarrow q)) \rightarrow \neg p Modus tollens
\begin{align} p \rightarrow q\ q \rightarrow r\ \therefore \overline{p \rightarrow r} \ \end{align} ((p \rightarrow q) \wedge (q \rightarrow r)) \rightarrow (p \rightarrow r) Hypothetical syllogism
\begin{align} p \vee q \ \neg p \ \therefore \overline{q \quad \quad \quad} \ \end{align} ((p \vee q) \wedge \neg p) \rightarrow q Disjunctive syllogism
\begin{align} p \vee q \ \neg p \vee r \ \therefore \overline{q \vee r} \ \end{align} ((p \vee q) \wedge (\neg p \vee r)) \rightarrow (q \vee r) Resolution

[1]

Example 1

Let us consider the following assumptions: "If it rains today, then we will not go on a canoe today. If we do not go on a canoe trip today, then we will go on a canoe trip tomorrow. Therefore (Mathematical symbol for "therefore" is \therefore), if it rains today, we will go on a canoe trip tomorrow. To make use of the rules of inference in the above table we let p be the proposition "If it rains today", q be " We will not go on a canoe today" and let r be "We will go on a canoe trip tomorrow". Then this argument is of the form:

\begin{align} p \rightarrow q\ q \rightarrow r\ \therefore \overline{p \rightarrow r} \ \end{align}

Example 2

Let us consider a more complex set of assumptions: "It is not sunny today and it is colder than yesterday". "We will go swimming only if it is sunny", "If we do not go swimming, then we will have a barbecue", and "If we will have a barbecue, then we will be home by sunset" lead to the conclusion "We will be home before sunset." Proof by rules of inference: Let p be the proposition "It is sunny this today", q the proposition "It is colder than yesterday", r the proposition "We will go swimming", s the proposition "We will have a barbecue", and t the proposition "We will be home by sunset". Then the hypotheses become \neg p \wedge q, r \rightarrow p, \neg r \rightarrow s and s \rightarrow t. Using our intuition we conjecture that the conclusion might be t. Using the Rules of Inference table we can proof the conjecture easily:

Step Reason
1.\neg p \wedge q Hypothesis
2. \neg p Simplification using Step 1
3. r \rightarrow p Hypothesis
4. \neg r Modus tollens using Step 2 and 3
5. \neg r \rightarrow s Hypothesis
6. s Modus ponens using Step 4 and 5
7. s \rightarrow t Hypothesis
8. t Modus ponens using Step 6 and 7

References

  1. ^ Kenneth H. Rosen: Discrete Mathematics and its Applications,Fifth Edition, p. 58.







Got something to say? Make a comment.
Your name
Your email address
Message
Please enter the solution to case below
12+12=