Rules of Inference

Rules of inference are formal logical templates or patterns that allow a valid conclusion to be deduced from one or more given statements known as premises. They form the foundation of formal deductive reasoning and guarantee that if the initial premises are true, the resulting conclusion must necessarily be true as well.

In propositional logic, each rule of inference represents a conditional tautology. This means that when all premises are joined using conjunctions (∧) and linked to the conclusion through a conditional statement (→), the resulting compound proposition is true for every possible combination of truth values.

Unlike logical equivalence laws, which allow propositions with the same truth value to be substituted in both directions using a biconditional (↔), inference rules operate strictly in a single deductive direction. Their primary purpose is to advance step-by-step through formal proofs without compromising the validity of the argument.

Rules of Inference in Propositional Logic

The following table presents the most widely used rules of inference in propositional logic, along with their formal notation and a natural language example for each.

Rule	Tautological Form	Vertical Form	Example
Modus ponens (MP)	[(p → q) ∧ p] → q	$$\begin{matrix} p \rightarrow q \\ p \\ \hline \therefore q \end{matrix}$$	If it rains, the ground gets wet. It is raining. Therefore, the ground gets wet.
Modus tollens (MT)	[(p → q) ∧ ¬q] → ¬p	$$\begin{matrix} p \rightarrow q \\ \neg q \\ \hline \therefore \neg p \end{matrix}$$	If it rains, the ground gets wet. The ground is not wet. Therefore, it is not raining.
Hypothetical syllogism (HS)	[(p → q) ∧ (q → r)] → (p → r)	$$\begin{matrix} p \rightarrow q \\ q \rightarrow r \\ \hline \therefore p \rightarrow r \end{matrix}$$	If I study, I pass the exam. If I pass the exam, I celebrate. Therefore, if I study, I celebrate.
Disjunctive syllogism (DS)	[(p ∨ q) ∧ ¬p] → q	$$\begin{matrix} p \lor q \\ \neg p \\ \hline \therefore q \end{matrix}$$	I travel by train or by bus. I am not traveling by train. Therefore, I travel by bus.
Simplification	(p ∧ q) → p	$$\begin{matrix} p \land q \\ \hline \therefore p \end{matrix}$$	I have a dog and I have a cat. Therefore, I have a dog.
Conjunction	(p ∧ q) → (p ∧ q)	$$\begin{matrix} p \\ q \\ \hline \therefore p \land q \end{matrix}$$	The sky is clear. It is warm outside. Therefore, the sky is clear and it is warm outside.
Addition	p → (p ∨ q)	$$\begin{matrix} p \\ \hline \therefore p \lor q \end{matrix}$$	I have an apple. Therefore, I have an apple or I have an orange.
Constructive dilemma (CD)	[(p → q) ∧ (r → s) ∧ (p ∨ r)] → (q ∨ s)	$$\begin{matrix} p \rightarrow q \\ r \rightarrow s \\ p \lor r \\ \hline \therefore q \lor s \end{matrix}$$	If I go to the movies I spend money, and if I go to the park I walk. I go to the movies or I go to the park. Therefore, I spend money or I walk.
Destructive dilemma (DD)	[(p → q) ∧ (r → s) ∧ (¬q ∨ ¬s)] → (¬p ∨ ¬r)	$$\begin{matrix} p \rightarrow q \\ r \rightarrow s \\ \neg q \lor \neg s \\ \hline \therefore \neg p \lor \neg r \end{matrix}$$	If I cook I buy groceries, and if I go out I take a cab. I did not buy groceries or I did not take a cab. Therefore, I did not cook or I did not go out.
Absorption	(p → q) → [p → (p ∧ q)]	$$\begin{matrix} p \rightarrow q \\ \hline \therefore p \rightarrow (p \land q) \end{matrix}$$	If I run, I get tired. Therefore, if I run, then I run and get tired.
Proof by cases	[(p → q) ∧ (¬p → q)] → q	$$\begin{matrix} p \rightarrow q \\ \neg p \rightarrow q \\ \hline \therefore q \end{matrix}$$	If I go to work I wear a shirt, and if I stay home I wear a shirt. Therefore, I wear a shirt.
Resolution	[(p ∨ q) ∧ (¬p ∨ r)] → (q ∨ r)	$$\begin{matrix} p \lor q \\ \neg p \lor r \\ \hline \therefore q \lor r \end{matrix}$$	I take the train or I take the bus. I do not take the train or I arrive on time. Therefore, I take the bus or I arrive on time.

Below we examine in detail the most commonly used deductive rules, their conditional structure, and examples applied across different contexts.

Modus Ponens

Modus ponens, from the Latin expression meaning “the mode that affirms by affirming,” is the most intuitive rule in propositional logic. It states that if a conditional statement is true and its antecedent holds simultaneously, then the consequent must necessarily be true as well.

Its conditional expression as a tautology is written as [(p → q) ∧ p] → q. This rule forms the direct foundation of natural deduction systems and sequential instruction execution in computer programming.

Examples

• Premise 1: If the traffic light is red, then the driver stops the vehicle.
  Premise 2: The traffic light is red.
  Conclusion: Therefore, the driver stops the vehicle.
• Premise 1: If a student passes the final exam, then they pass the course.
  Premise 2: The student passed the final exam.
  Conclusion: Therefore, they pass the course.
• Premise 1: If an integer n is divisible by 4, then n is an even number.
  Premise 2: The number 16 is divisible by 4.
  Conclusion: Therefore, the number 16 is an even number.

More information about modus ponens

Modus Tollens

Modus tollens comes from the Latin phrase meaning “the mode that denies by denying.” This rule establishes that if a conditional statement is valid and its consequent is false, the antecedent could not have occurred.

In formal notation, its structure corresponds to the tautology [(p → q) ∧ ¬q] → ¬p. It is an essential tool in proofs by contradiction and within the scientific method to reject hypotheses when predicted results fail to materialize.

Examples

• Premise 1: If there is a fire in the forest, then smoke is visible in the sky.
  Premise 2: Smoke is not visible in the sky.
  Conclusion: Therefore, there is no fire in the forest.
• Premise 1: If a polygon is a square, then it has exactly four sides.
  Premise 2: This geometric shape does not have four sides.
  Conclusion: Therefore, the shape is not a square.
• Premise 1: If a function f(x) is differentiable at a point x = a, then f(x) is continuous at that point.
  Premise 2: The function is not continuous at x = a.
  Conclusion: Therefore, the function is not differentiable at x = a.

More information about modus tollens

Hypothetical Syllogism

The hypothetical syllogism expresses the transitive property of logical implication. It indicates that if an initial condition leads to an intermediate result, and that intermediate result triggers a third consequence, there is a direct relationship between the starting point and the final outcome.

Its formal representation as a tautological conditional is [(p → q) ∧ (q → r)] → (p → r). This rule allows for the construction of complex argumentative chains and the sequential linking of mathematical theorems.

For example, if saving money each month allows someone to buy airline tickets, and buying those tickets makes an overseas trip possible, we directly conclude that saving money each month leads to traveling abroad. In algebra, if we establish that x > 5 → x > 2 and also that x > 2 → x > 0, we immediately deduce that x > 5 → x > 0.

More information about hypothetical syllogism

Disjunctive Syllogism

The disjunctive syllogism models reasoning by elimination between mutually exclusive alternatives within a given context. If at least one of two propositions is known to be true and one of them is refuted, the remaining proposition must necessarily be accepted as true.

Formally, it is described by the schema [(p ∨ q) ∧ ¬p] → q, or equivalently [(p ∨ q) ∧ ¬q] → p. It is the most common logical rule used in problem-solving where possible options are narrowed down.

As an everyday example, consider the statement that a purchase is paid for with a debit card or with cash. If it is verified that the buyer does not have cash, we necessarily conclude that the payment is made with a debit card. Mathematically, if an equation has potential solutions x = 3 or x = -3, and it is proven that x ≠ -3, we infer that x = 3.

More information about disjunctive syllogism

Simplification and Addition

The rules of simplification and addition operate on conjunction and disjunction connectives, respectively. Simplification allows any individual component to be extracted from a true conjunction using the formula (p ∧ q) → p, since if both parts are true simultaneously, each is true on its own.

On the other hand, addition allows any arbitrary proposition to be joined to a true statement via a disjunction, under the schema p → (p ∨ q). Because a disjunction requires only one of its terms to be true in order to be valid as a whole, the truth of the original proposition guarantees the truth value of the entire compound statement.

An elementary case of simplification occurs when stating that a triangle is equilateral and equiangular, immediately deducing that the triangle is equilateral. In the case of addition, if it is known with certainty that the number 2 is prime, it is formally valid to conclude that 2 is prime or 2 is odd.

Resolution

The resolution rule is an inference pattern that operates on two propositions expressed as disjunctions. It states that if one clause contains an assertion and the other contains its corresponding negation, both cancel each other out, allowing the disjunction of the remaining terms to be concluded:

$$\begin{matrix} p \lor q \\ \neg p \lor r \\ \hline \therefore q \lor r \end{matrix}$$

As shown in our reference table above, this rule serves as a cornerstone of formal logic. It is especially prominent in computer science, serving as the core operating principle behind automated theorem proving algorithms, SAT solvers, and computational systems based on logic programming.

To examine its practical application, consider the following statements:

• Premise 1: I take the train or I take the bus: p ∨ q.
  Premise 2: I do not take the train or I arrive on time: ¬p ∨ r.
  Conclusion: Resolving on the complementary literals yields: q ∨ r (I take the bus or I arrive on time).
• Premise 1: The input data is valid or the system issues an alert: p ∨ q.
  Premise 2: The input data is not valid or the file is saved: ¬p ∨ r.
  Conclusion: Applying resolution across both premises, we deduce: q ∨ r (the system issues an alert or the file is saved).

Proof Using Truth Tables

Every valid rule of inference constitutes a conditional tautology. This means that when evaluating the complete structure of the argument using a truth table, the column corresponding to the main conditional outputs true (T) in every possible row, regardless of the individual truth value assignments of the component propositions.

To verify the formal validity of a rule, a truth table is constructed by joining the premises through conjunctions (∧) as the antecedent and placing the conclusion as the consequent of the main implication (→).

Proof of Modus Ponens

The logical structure to evaluate is [(p → q) ∧ p] → q. In this table, we verify how the conjunction between the initial conditional and the assertion of its antecedent always guarantees the truth of the conclusion.

p	q	p → q	(p → q) ∧ p	[(p → q) ∧ p] → q
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

Because the final column contains exclusively true values, modus ponens is formally demonstrated to be a valid and tautological argument form.

Proof of Modus Tollens

For modus tollens, we analyze the compound proposition [(p → q) ∧ ¬q] → ¬p. Here we evaluate the effect of negating the consequent on the initial conditional statement.

p	q	¬p	¬q	p → q	(p → q) ∧ ¬q	[(p → q) ∧ ¬q] → ¬p
T	T	F	F	T	F	T
T	F	F	T	F	F	T
F	T	T	F	T	F	T
F	F	T	T	T	T	T

The outcome is identical: obtaining an exclusively true final column confirms the universal validity of modus tollens in propositional logic.

Proof of Simplification

For the rule of simplification, we analyze the conditional formula (p ∧ q) → p. The objective is to verify that deriving any component individually from a true conjunction is always valid.

p	q	p ∧ q	(p ∧ q) → p
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

Obtaining true values across all cases confirms that extracting an isolated proposition from a valid conjunction represents a fully tautological deduction.

Rules of Inference in Predicate Logic

In predicate logic, propositional inference rules cannot be applied directly to quantified expressions. The presence of quantifiers such as ∀ or ∃ binds the variables, preventing internal logical connectives from being manipulated in isolation.

To carry out deductions at this level, the procedure consists of temporarily removing quantifiers using instantiation rules, which derive propositions about elements in the domain. Once propositional expressions are obtained, standard inference rules are applied, and if the overall conclusion requires it, quantifiers are reinstated using generalization rules.

The following table summarizes the four inference rules for quantified statements, their formal notation, and the conditions governing the element or constant used:

Rule	Premise	Conclusion	Condition on Term
Universal Instantiation (UI)	∀x P(x)	P(c)	c represents any element or constant in the domain.
Universal Generalization (UG)	P(c)	∀x P(x)	c must be an arbitrary, generic element.
Existential Instantiation (EI)	∃x P(x)	P(c)	c is a new constant not previously introduced.
Existential Generalization (EG)	P(c)	∃x P(x)	c is a specific constant in the domain of discourse.

Universal Instantiation

Universal Instantiation states that if a predicate holds true for every element in a domain, it is valid to deduce that it holds for a particular object c in that domain. Its vertical deductive schema is formally expressed as:

$$\begin{matrix} \forall x \, P(x) \\ \hline \therefore P(c) \end{matrix}$$

Because the initial statement applies to the entire domain without exception, the term c can denote either a concrete individual or an arbitrary variable representing an unspecified element.

To understand the application of this rule, consider the following cases:

• Premise: All even numbers are divisible by 2: ∀x (P(x) → D(x)).
  Conclusion: Choosing the number 4 yields: P(4) → D(4).
• Premise: In geometry, all equilateral triangles are equiangular: ∀x (E(x) → A(x)).
  Conclusion: Letting t represent a given triangle, we conclude: E(t) → A(t).

Universal Generalization

Universal Generalization allows a property to be concluded for the entire domain based on a deduction established for an arbitrary element c. The formal structure of the rule is represented as follows:

$$\begin{matrix} P(c) \\ \hline \therefore \forall x \, P(x) \end{matrix}$$

To guarantee the validity of the reasoning, the term c must be chosen in a strictly arbitrary manner. This means that c cannot originate from a specific assumption, nor from a prior existential instantiation, nor possess any special properties that distinguish it from other elements in the domain.

Let us see how it applies in deductive contexts:

• Algebraic reasoning: Let c be an arbitrary integer. If through valid algebraic steps we prove that 2c produces a multiple of 2, since no additional assumptions were made about c, we conclude that ∀x (2x is a multiple of 2).
• Geometric statement: If we consider an arbitrary regular polygon c and verify that the sum of its exterior angles equals 360°, we generalize the result by stating that ∀x (the sum of the exterior angles of a regular polygon x is 360°).

Existential Instantiation

Existential Instantiation allows a temporary name or individual constant c to be assigned to an object whose existence is guaranteed by an existential premise. The deductive format of the rule is:

$$\begin{matrix} \exists x \, P(x) \\ \hline \therefore P(c) \end{matrix}$$

The essential restriction when applying this rule is that the constant c must be a completely new symbol in the proof. A letter or constant that has already appeared in the premises or intermediate steps cannot be reused, preventing the invalid assumption that two independent properties belong to the exact same individual.

We analyze two situations where this assignment operates:

• Initial premise: There exists a prime number that is even: ∃x (P(x) ∧ E(x)).
  Conclusion: We designate that element with a previously unused constant, k, deducing: P(k) ∧ E(k).
• Initial premise: There exists a point in the plane that intersects line L: ∃x I(x).
  Conclusion: We temporarily label that point p₀ to continue the proof: I(p₀).

Existential Generalization

Existential Generalization allows us to state that there exists at least one element satisfying a given property if that property has been verified to be true for a specific object c. Its structure is defined as:

$$\begin{matrix} P(c) \\ \hline \therefore \exists x \, P(x) \end{matrix}$$

Unlike universal generalization, this rule does not require the element to be arbitrary. Verifying the property for a single concrete instance is sufficient to formally validate the existential quantifier over the domain.

Consider the following deductive examples:

• Premise: The number 3 satisfies the linear equation: 2(3) + 4 = 10.
  Conclusion: We deduce the existence of at least one integer solution: ∃x (2x + 4 = 10).
• Premise: The number 2 is prime and simultaneously an even number: P(2) ∧ E(2).
  Conclusion: We infer the existential proposition: ∃x (P(x) ∧ E(x)).

Formal Proof Example

To demonstrate the integration between quantifier rules and propositional logic, we develop the formal deduction for the classic deductive argument regarding mortality.

The argument is formulated in natural language as follows:

• All humans are mortal.
• Socrates is a human.
• Therefore, Socrates is mortal.

To formalize this reasoning in first-order logic, we define the individual constant s to represent Socrates, the predicate H(x) as “x is a human,” and the predicate M(x) as “x is mortal.” With these definitions, the set of premises and the conclusion take the following symbolic form:

• Premise 1: ∀x (H(x) → M(x))
• Premise 2: H(s)
• Conclusion: M(s)

To deduce the conclusion, we combine the studied rules in the following sequence:

1. State the first universal premise: ∀x (H(x) → M(x)).
2. Apply Universal Instantiation (UI) to step 1 using the specific constant s, yielding the conditional proposition: H(s) → M(s).
3. Introduce the second premise of the argument: H(s).
4. Compare steps 2 and 3. Having the conditional statement H(s) → M(s) and affirming its antecedent H(s), apply modus ponens (MP) to derive: M(s).

Through this procedure, the argument is proven valid, confirming that predicate logic can analyze the internal structure of statements and deduce conclusions that lie beyond the reach of propositional logic alone.