
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Discrete Mathematics - Rules of Inference
To deduce new statements from the statements whose truth that we already know, Rules of Inference are used.
What are Rules of Inference for?
Mathematical logic is often used for logical proofs. Proofs are valid arguments that determine the truth values of mathematical statements.
An argument is a sequence of statements. The last statement is the conclusion and all its preceding statements are called premises (or hypothesis). The symbol $\therefore$, (read therefore) is placed before the conclusion. A valid argument is one where the conclusion follows from the truth values of the premises.
Rules of Inference provide the templates or guidelines for constructing valid arguments from the statements that we already have.
Table of Rules of Inference
Rule of Inference | Name | Rule of Inference | Name |
---|---|---|---|
$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$ |
Addition |
$$\begin{matrix} P \lor Q \\ \lnot P \\ \hline \therefore Q \end{matrix}$$ |
Disjunctive Syllogism |
$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$ |
Conjunction |
$$\begin{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}$$ |
Hypothetical Syllogism |
$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$ |
Simplification |
$$\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}$$ |
Constructive Dilemma |
$$\begin{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}$$ |
Modus Ponens |
$$\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}$$ |
Destructive Dilemma |
$$\begin{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}$$ |
Modus Tollens |
Addition
If P is a premise, we can use Addition rule to derive $ P \lor Q $.
$$\begin{matrix} P \\ \hline \therefore P \lor Q \end{matrix}$$
Example
Let P be the proposition, He studies very hard is true
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 \land Q $.
$$\begin{matrix} P \\ Q \\ \hline \therefore P \land Q \end{matrix}$$
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 \land Q$ is a premise, we can use Simplification rule to derive P.
$$\begin{matrix} P \land Q\\ \hline \therefore P \end{matrix}$$
Example
"He studies very hard and he is the best boy in the class", $P \land Q$
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{matrix} P \rightarrow Q \\ P \\ \hline \therefore Q \end{matrix}$$
Example
"If you have a password, then you can log on to facebook", $P \rightarrow Q$
"You have a password", P
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{matrix} P \rightarrow Q \\ \lnot Q \\ \hline \therefore \lnot P \end{matrix}$$
Example
"If you have a password, then you can log on to facebook", $P \rightarrow Q$
"You cannot log on to facebook", $\lnot Q$
Therefore − "You do not have a password "
Disjunctive Syllogism
If $\lnot P$ and $P \lor Q$ are two premises, we can use Disjunctive Syllogism to derive Q.
$$\begin{matrix} \lnot P \\ P \lor Q \\ \hline \therefore Q \end{matrix}$$
Example
"The ice cream is not vanilla flavored", $\lnot P$
"The ice cream is either vanilla flavored or chocolate flavored", $P \lor Q$
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{matrix} P \rightarrow Q \\ Q \rightarrow R \\ \hline \therefore P \rightarrow R \end{matrix}$$
Example
"If it rains, I shall not go to school, $P \rightarrow Q$
"If I don't go to school, I won't need to do homework", $Q \rightarrow R$
Therefore − "If it rains, I won't need to do homework"
Constructive Dilemma
If $( P \rightarrow Q ) \land (R \rightarrow S)$ and $P \lor R$ are two premises, we can use constructive dilemma to derive $Q \lor S$.
$$\begin{matrix} ( P \rightarrow Q ) \land (R \rightarrow S) \\ P \lor R \\ \hline \therefore Q \lor S \end{matrix}$$
Example
If it rains, I will take a leave, $( P \rightarrow Q )$
If it is hot outside, I will go for a shower, $(R \rightarrow S)$
Either it will rain or it is hot outside, $P \lor R$
Therefore − "I will take a leave or I will go for a shower"
Destructive Dilemma
If $(P \rightarrow Q) \land (R \rightarrow S)$ and $ \lnot Q \lor \lnot S $ are two premises, we can use destructive dilemma to derive $\lnot P \lor \lnot R$.
$$\begin{matrix} (P \rightarrow Q) \land (R \rightarrow S) \\ \lnot Q \lor \lnot S \\ \hline \therefore \lnot P \lor \lnot R \end{matrix}$$
Example
If it rains, I will take a leave, $(P \rightarrow Q )$
If it is hot outside, I will go for a shower, $(R \rightarrow S)$
Either I will not take a leave or I will not go for a shower, $\lnot Q \lor \lnot S$
Therefore − "Either it does not rain or it is not hot outside"