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 −

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 −

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 −

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.