Inference and replacement rules
A long list
AboutThis page is meant as a resource on a large number of inference rules. Inference rules are rules that describe when one can validly infer a conclusion from a set of premises. Replacement rules are rules of what one can replace and still have a wff with the same truth-value; in other words, they are a list of logical equivalencies. The main difference between the two set of rules is that the first kind allows valid inference from the first set of propositions (premises) to the second set (the conclusion), but with replacement rules we can validly infer both ways. The images were creating using ScreenHunter (for image capturing) and Proof Tools (for creating the trees). |
Inference rules for propositional logicSome of the rules are known under multiple names. I have tried to list a few of the popular ones.Modus Ponens (MP) / Implication EliminationForm1. P→Q2. P ⊢ 3. Q Example 1. If the earth exists, then a planet exists. 2. The earth exists. Therefore, 3. A planet exists. Proof tree Modus Tollens (MT)Form1. P→Q 2. ¬Q ⊢ 3. ¬P Example 1. If Socrates is a man, then Socrates is mortal. 2. Socrates is not mortal. Therefore, 3. Socrates is not a man. Proof tree Hypothetical Syllogism (HS)Form1. P→Q 2. Q→R ⊢ 3. P→R Example 1. If it rains, then the street is wet. 2. If the street is wet, then the street is slippery. Therefore, 3. If it rains, then the street is slippery. Proof tree Disjunctive Syllogism (DS)Form1. P∨Q 2. ¬P ⊢ 3. Q Example 1. Socrates is either male or female. 2. Socrates is not female. Therefore, 3. Socrates is male. Proof tree Constructive Dilemma (CD)Form1. (P→Q)∧(R→S) 2. P∨R ⊢ 3. Q∨S Example 1. If Socrates is a man, then Socrates is mortal, and is Plato is a man, then Plato is mortal. 2. Either Socrates or Plato is a man. Therefore, 3. Either Socrates or Plato is mortal. Proof tree Destructive Dilemma (DD)Form1. (P→Q)∧(R→S) 2. ¬Q∧¬S ⊢ 3. ¬P∧¬R 1. If Socrates is a woman, then Socrates is dumb, and is Plato is a man, then Plato is dumb. 2. Socrates is not dumb and Plato is not dumb. Therefore, 3. Socrates is not a woman and Plato is not a man. Proof tree Conjunction Introduction (Conj.) / AdjunctionForm1. P 2. Q ⊢ 3. P∧Q Example 1. It rains. 2. It is monday. Therefore, 3. It rains and it is monday. Proof tree Simplification (Simp.) / Conjunction Elimination (CE)Form1. P∧Q ⊢ 2. P Example 1. It is tuesday and the sun shines. Therefore, 2. It is tuesday. Proof tree Addition (Add.) / Disjunction Introduction (DI)Form1. P ⊢ 2. P∨Q Example 1. I won the lottery. Therefore, 2. I won the lottery or I am a woman. Proof tree Replacement rules for propositional logicI will ommit exmaples of these and just list the forms and proofs.De Morgan's lawsForms⊢ ¬(P∧Q)↔(¬P∨¬Q) ⊢ ¬(P∨Q)↔(¬P∧¬Q) Proof trees Commutation (Com.)Forms⊢ P∧Q↔Q∧P⊢ P∨Q↔Q∨P Proof trees Association (Assoc.)Forms⊢ ((P∨Q)∨R)↔(P∨(Q∨R)) ⊢ (P∧(Q∧R))↔((P∧Q)∧R) Proof trees Distrubution (Dist.)Forms⊢ (P∧(Q∨R))↔((P∧Q)∨(P∧R)) ⊢ (P∨(Q∧R))↔((P∨Q)∧(P∨R)) Proof trees Double Negation (DN)Form⊢ P↔¬¬P Proof tree Material Implication (M. Imp.) / Material ConditionalForms⊢ (P→Q)↔(¬P∨Q) ⊢ (P→Q)↔¬(P∧¬Q) Proof trees Transposition (Trans.) / Contraposition (CP.)Form⊢ (P→Q)↔(¬Q→¬P) Proof tree Material Bi-implication / Material Equivalence (M. Equiv.)Forms⊢ (P↔Q)↔((P→Q)∧(Q→P)) ⊢ (P↔Q)↔((P∧Q)∨(¬P∧¬Q)) Proof trees ExportationForm⊢ ((P∧Q)→R)↔((P→(Q→R)))Proof tree Inference rules for predicate logicUniversal Instantiation (UI)Form1. ∀xFx ⊢ 2. Fa Where "a" is some constant which ∀x quantifies over. Example: 1. All humans have lungs. Therefore 2. Socrates has lungs. Proof tree Existential Generalization (EG)Form1. Fa ⊢ 2. ∃xFx Example: 1. Socrates has lungs. ⊢ 2. There is someone who has lungs. Proof tree Replacement rules for predicate logicQuantifier rules⊢ ((∃x)(...))↔(¬(∀x)(¬(...)))⊢ ((∀x)(...) ↔(¬(∃x)(¬(...))) "..." can be replaced by whatever as long as it results in a wff. I used "Fx" in my proof.Proof trees |