Jump to navigation
Jump to search
## Contents

## Introduction[edit]

## Rules for classical sentential calculus[edit]

### Rules for negations[edit]

### Rules for conditionals[edit]

### Rules for conjunctions[edit]

### Rules for disjunctions[edit]

### Rules for biconditionals[edit]

## Rules of classical predicate calculus[edit]

## Rules of substructural logic[edit]

## Table: Rules of Inference[edit]

### Example 1[edit]

### Example 2[edit]

## References[edit]

## See also[edit]

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

**Rules of inference** are syntactical **transform** 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

indicates such a subderivation from the temporary assumption to .

Sentential calculus is also known as propositional calculus.

- Reductio ad absurdum (or
*Negation Introduction*)

- Reductio ad absurdum (related to the law of excluded middle)

- Noncontradiction (or
*Negation Elimination*)

- Modus ponens (or
*Conditional Elimination*)

- Adjunction (or
*Conjunction Introduction*)

- Simplification (or
*Conjunction Elimination*)

- Addition (or
*Disjunction Introduction*)

- Case analysis (or
*Proof by Cases*or*Argument by Cases*)

- Biconditional Elimination

In the following rules, is exactly like except for having the term everywhere has the free variable .

Restriction 1: is a variable which does not occur in .

Restriction 2: is not mentioned in any hypothesis or undischarged assumptions.

Restriction: No free occurrence of in falls within the scope of a quantifier quantifying a variable occurring in .

Restriction: No free occurrence of in falls within the scope of a quantifier quantifying a variable occurring in .

Restriction 1: is a variable which does not occur in .

Restriction 2: There is no occurrence, free or bound, of in .

Restriction 3: is not mentioned in any hypothesis or undischarged assumptions.

The following are special cases of universal generalization and existential elimination; these occur in substructrual logics, such as linear logic.

- Rule of weakening (or monotonicity of entailment) (aka no-cloning theorem)

- Rule of contraction (or idempotency of entailment) (aka no-deleting theorem)

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

Rules of inference | Tautology | Name |
---|---|---|

Modus ponens | ||

Modus tollens | ||

Associative | ||

Commutative | ||

Law of biconditional propositions | ||

Exportation | ||

Transposition or contraposition law | ||

Hypothetical syllogism | ||

Material implication | ||

Distributive | ||

Absorption | ||

Disjunctive syllogism | ||

Addition | ||

Simplification | ||

Conjunction | ||

Double negation | ||

Disjunctive simplification | ||

Resolution | ||

Disjunction Elimination |

All rules use the basic logic operators. A complete table of "logic operators" is shown by a truth table, giving definitions of all the possible (16) truth functions of 2 boolean variables (*p*, *q*):

p |
q |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

T | T | F | F | F | F | F | F | F | F | T | T | T | T | T | T | T | T | ||

T | F | F | F | F | F | T | T | T | T | F | F | F | F | T | T | T | T | ||

F | T | F | F | T | T | F | F | T | T | F | F | T | T | F | F | T | T | ||

F | F | F | T | F | T | F | T | F | T | F | T | F | T | F | T | F | T |

where T = true and F = false, and, the columns are the logical operators: **0**, false, Contradiction; **1**, NOR, Logical NOR; **2**, Converse nonimplication; **3**, **¬p**, Negation; **4**, Material nonimplication; **5**, **¬q**, Negation; **6**, XOR, Exclusive disjunction; **7**, NAND, Logical NAND; **8**, AND, Logical conjunction; **9**, XNOR, If and only if, Logical biconditional; **10**, **q**, Projection function; **11**, if/then, Logical implication; **12**, **p**, Projection function; **13**, then/if, Converse implication; **14**, OR, Logical disjunction; **15**, true, Tautology.

Each logic operator can be used in an assertion about variables and operations, showing a basic rule of inference. Examples:

- The column-14 operator (OR), shows
*Addition rule*: when*p*=T (the hypothesis selects the first two lines of the table), we see (at column-14) that*p*∨*q*=T.- We can see also that, with the same premise, another conclusions are valid: columns 12, 14 and 15 are T.

- The column-8 operator (AND), shows
*Simplification rule*: when*p*∧*q*=T (first line of the table), we see that*p*=T.- With this premise, we also conclude that
*q*=T,*p*∨*q*=T, etc. as showed by columns 9-15.

- With this premise, we also conclude that
- The column-11 operator (IF/THEN), shows
*Modus ponens rule*: when*p*→*q*=T and*p*=T only one line of the truth table (the first) satisfies these two conditions. On this line,*q*is also true. Therefore, whenever p → q is true and p is true, q must also be true.

Machines and well-trained people use this look at table approach to do basic inferences, and to check if other inferences (for the same premises) can be obtained.

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 ), 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 be the proposition "If it rains today", be "We will not go on a canoe today" and let be "We will go on a canoe trip tomorrow". Then this argument is of the form:

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 by sunset." Proof by rules of inference: Let be the proposition "It is sunny today", the proposition "It is colder than yesterday", the proposition "We will go swimming", the proposition "We will have a barbecue", and the proposition "We will be home by sunset". Then the hypotheses become and . Using our intuition we conjecture that the conclusion might be . Using the Rules of Inference table we can proof the conjecture easily:

Step | Reason |
---|---|

1. | Hypothesis |

2. | Simplification using Step 1 |

3. | Hypothesis |

4. | Modus tollens using Step 2 and 3 |

5. | Hypothesis |

6. | Modus ponens using Step 4 and 5 |

7. | Hypothesis |

8. | Modus ponens using Step 6 and 7 |

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

None of the audio/visual content is hosted on this site. All media is embedded from other sites such as GoogleVideo, Wikipedia, YouTube etc. Therefore, this site has no control over the copyright issues of the streaming media.

All issues concerning copyright violations should be aimed at the sites hosting the material. This site does not host any of the streaming media and the owner has not uploaded any of the material to the video hosting servers. Anyone can find the same content on Google Video or YouTube by themselves.

The owner of this site cannot know which documentaries are in public domain, which has been uploaded to e.g. YouTube by the owner and which has been uploaded without permission. The copyright owner must contact the source if he wants his material off the Internet completely.

Wikipedia content is licensed under the GFDL and (CC) license