Rules of Inference

To deduce new statements from the statements whose truth that we already know, rules of inference are used.

Rules of inference are standard logical templates used to build valid arguments and prove conclusions from given premises in propositional logic.

Addition

If \(P\) is a premise, we cna use Addition rule to derive \(P \vee Q\).

\[\begin{split}\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}\end{split}\]

Example

Let \(P\): “He studies very hard”

Therefore: “Either he studies very hard or he is a very bad student.”

Here, \(Q\) is the proposition “He is a very bad student”.

Conjunction

If \(P\) and \(Q\) are two premises, we can use conjunction rule to derive \(P \wedge Q\).

\[\begin{split}\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}\end{split}\]

Example

Let \(P\): “He studies very hard.”

Let \(Q\): “He is the best boy in the class.”

Therefore: “He studies very hard and he is the best boy in the class.”

Simplification

If \(P \wedge Q\) is a premise, we can use simplification rule to derive \(P\).

\[\begin{split}\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}\end{split}\]

Example

Let \(P \wedge Q\): “He studies very hard and he is the best boy in the class.”

Therefore: “He studies very hard.”

Modus Ponens

If \(P\) and \(P \rightarrow Q\) are two premises, we can use modus ponens to derive \(Q\).

\[\begin{split}\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}\end{split}\]

Example

Let \(P \rightarrow Q\): “If you have a password, then you can log on to Facebook.”

Let \(P\): “You have a password.”

Therefore: “You can log on to Facebook.”

Modus Tollens

If \(P \rightarrow Q\) and \(\lnot Q\) are two premises, we can use modus tollens to derive \(\lnot P\).

\[\begin{split}\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}\end{split}\]

Example

Let \(P \rightarrow Q\): “If you have a password, then you can log on to Facebook.”

Let \(\lnot Q\): “You cannot log on to Facebook.”

Therefore: “You do not have a password.”

Disjunctive Syllogism

If \(\lnot P\) and \(P \vee Q\) are two premises, we can use disjunctive syllogism to derive \(Q\).

\[\begin{split}\begin{matrix} \lnot P \\ P \lor Q \\ \hline \therefore Q \end{matrix}\end{split}\]

Example

Let \(\lnot P\): “The ice cream is not vanilla flavored.”

Let \(P \vee Q\): “The ice cream is either vanilla flavored or chocolate flavored.”

Therefore: “The ice cream is chocolate flavored.”

Hypothetical Syllogism

If \(P \rightarrow Q\) and \(Q \rightarrow R\) are two premises, we can use hypothetical syllogism to derive \(P \rightarrow R\).

\[\begin{split}\begin{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}\end{split}\]

Example

Let \(P \rightarrow Q\): “If it rains, I shall not go to school.”

Let \(Q \rightarrow R\): “If I don’t go to school, I won’t need to do homework.”

Therefore: “If it rains, I won’t need to do homework.”

Constructive Dilemma

If \((P \rightarrow Q) \wedge (R \rightarrow S)\) and \(P \vee R\) are two premises, we can use constructive dilemma to derive \(Q \vee S\).

\[\begin{split}\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}\end{split}\]

Example

Let \(P \rightarrow Q\): “If it rains, I will take a leave.”

Let \(R \rightarrow S\): “If it is hot outside, I will go for a shower.”

Let \(P \vee R\): “Either it will rain or it is hot outside.”

Therefore: “I will take a leave or I will go for a shower.”

Destructive Dilemma

If \((P \rightarrow Q) \wedge (R \rightarrow S)\) and \(\lnot Q \vee \lnot S\) are two premises, we can use destructive dilemma to derive \(\lnot P \vee \lnot R\).

\[\begin{split}\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}\end{split}\]

Example

Let \(P \rightarrow Q\): “If it rains, I will take a leave.”

Let \(R \rightarrow S\): “If it is hot outside, I will go for a shower.”

Let \(\lnot Q \vee \lnot S\): “Either I will not take a leave or I will not go for a shower.”

Therefore: “Either it does not rain or it is not hot outside.”

---

Source

Discrete Mathematics - Rules of Inference