
- 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
Deductions in Discrete Mathematics
In propositional logics, sometimes we deduct one logical expression from another; we call them deductions. Deductions form the backbone of logical reasoning. Deductions are used to derive conclusions from premises. They follow rules that guarantee the truth of the conclusion if the premises are True. This concept is important in mathematical proofs in computer algorithms, and reasoning systems.
In this chapter, we will see what deductions are, understand some common deduction rules, and explore various examples to see how deductions operate in logic. We will also discuss valid deduction rules like modus ponens and show how truth tables can be used to validate them.
What are Mathematical Deductions?
A deduction is a logical process where, starting from a set of premises (assumptions), we find a conclusion that logically follows. For example, if we know that,
- If Edith eats her vegetables, she gets a cookie.
- Edith ate her vegetables.
Here, we can deduce that "Edith gets a cookie". This simple example shows a rule called modus ponens, one of the most common deduction rules.
In symbolic terms, modus ponens can be written as −
$$\mathrm{P\: \rightarrow\: Q,\: \ P \ \:\implies\: \ Q}$$
This notation means: if P is true, and we also know that P → Q, then Q must be true.
Modus Ponens (If-Then Reasoning)
Let us start with the classic modus ponens. It is like a simple yet powerful rule for reasoning with "if-then" statements. The structure looks like this −
- Premise 1 − If P, then Q (P → Q).
- Premise 2 − P is true.
- Conclusion − Therefore, Q is true.
For example, consider −
- Premise 1 − If it rains, the grass will be wet.
- Premise 2 − It is raining.
- Conclusion − The grass will be wet.
To prove that modus ponens is a valid rule, we can use a truth table. Let us construct one for P → Q and see how it works −
P | Q | P → Q |
---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
From the table, we can see that whenever P is true and P → Q is true, Q must also be true. This confirms that modus ponens is a valid form of deduction.
Modus Tollens (Contrapositive Reasoning)
Another important rule is modus tollens, this is a bit different but equally useful. It is the reverse of modus ponens and deals with what happens when the consequence is false. It can be written as −
- Premise 1: If P, then Q (P→Q).
- Premise 2: Q is false.
- Conclusion: Therefore, P must also be false.
Here is an example −
- Premise 1: If a number is divisible by 4, it is even.
- Premise 2: The number is not even.
- Conclusion: The number is not divisible by 4.
Truth Table
Like modus ponens, modus tollens can be verified using a truth table −
P | Q | P → Q | ¬Q | ¬P |
---|---|---|---|---|
T | T | T | F | F |
T | F | F | T | F |
F | T | T | F | T |
F | F | T | T | T |
Whenever Q is false and P → Q is true, P must also be false. This proves that modus tollens is a valid deduction rule.
Deduction with Multiple Premises
Deductions can involve multiple premises, where the conclusion is derived by combining these premises logically. A common example of this is syllogism. Syllogism works with using two premises to arrive at a conclusion −
- Premise 1 − All humans are mortal.
- Premise 2 − Socrates is a human.
- Conclusion − Socrates is mortal.
Syllogism uses logical transitivity: if P → Q and Q → R, then P → R. This kind of reasoning is widely used in both philosophy and mathematics to construct proofs.
Truth Tables and Deduction Validation
Truth tables are useful but not only for checking logical equivalence but also for validating deduction rules. By listing all possible truth values for premises and conclusions, we can verify whether a deduction is valid.
Example: Validating P → R and Q → R Implies P ∨ Q → R
To check whether P → R and Q → R together imply P ∨ Q → R, we build a truth table −
P | Q | R | P → R | Q → R | P ∨ Q → R |
---|---|---|---|---|---|
T | T | T | T | T | T |
T | T | F | F | F | F |
T | F | T | T | T | T |
T | F | F | F | T | F |
F | T | T | T | T | T |
F | T | F | T | F | F |
F | F | T | T | T | T |
F | F | F | T | T | T |
By examining the table, we can confirm that whenever both P → R and Q → R are true, P ∨ Q → R must also be true.
Applications of Deduction Rules
We have understood the idea of deductions with examples. Let us see their applications in real life where deductions used the most.
- Mathematical Proofs − Deduction allows us to prove theorems by logically deriving conclusions from known premises.
- Computer Science − In programming, deduction is used to validate the correctness of algorithms, particularly in decision-making processes and conditional statements.
- Artificial Intelligence − Deduction plays a role in reasoning systems where the goal is to derive new knowledge from existing facts.
Example of a Deduction in Action
Let us go through a real-world example of deduction −
- Premise 1 − If it rains, the game will be cancelled.
- Premise 2 − It is raining.
- Conclusion − The game is cancelled.
This example follows the form of modus ponens, and we can immediately deduce that the game will indeed be cancelled. This type of reasoning is foundational to both formal logic and everyday problem-solving.
Conclusion
In this chapter, we explained how deductions operate in discrete mathematics. We understood the importance of modus ponens and modus tollens, two of the most commonly used deduction rules. We also understood how truth tables help validate these deductions and also how the conclusions logically follow from premises.
Finally, we looked at how deductions are applied in various fields, from mathematical proofs to computer science and artificial intelligence.